noone___'s blog
0%

41801202-AGC010

发表于 分类于
AGC010

B

$n$ 个数字 $a_i$ ，构成一个环，每次从一个起点出发顺时针给这个环依次 $-1,-2,…,-n$ ，求是否有一种方案使所有数恰好被减到 $0$

注意这里 $-1,-2,…,-n$ 就要考虑差分

每次对 $i$ 操作使 $d_i-=n-1 , \forall j\in n 有 \ d_j+=1 (j!=i)$

每次操作会使整个数列共减少 $c=\frac{n\times (n+1)}{2}$ 显然必须满足 $\sum a_i \mod c=0$

设 $m_i$ 代表以 $i$ 开头的操作的个数

满足 $m_i$ 非负整数即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const int N=1e5+100;
ll a[N],d[N],c,n,sum;

int main(){
    scanf("%d",&n); c=(ll) n*(n+1)/2;
    for(rei i=1;i<=n;++i) scanf("%d",&a[i]),sum+=a[i];
    if(sum%c) return puts("NO"),0;
    sum/=c;
    for(rei i=1;i<=n;++i) d[i]=a[i%n+1]-a[i];
    for(rei i=1;i<=n;++i) if(d[i]>sum || (sum-d[i])%n){ puts("NO"); goto done;}
    puts("YES");
    done:
    getchar(),getchar();
    return 0;
}

剩下三道博弈论蚌埠住了

D

$n$ 个正整数满足 $\gcd(a_1,a_2,…,a_N)=1$ ，两人轮流以下操作：选择 $i\in n且 a_i>2 使 a_i—$ ，设 $g=\gcd(a_1,a_2,…,a_n) : \forall i\in n \ \ \ a_i=\frac{a_i}{g}$
当轮到某玩家操作时 $a_1=a_2=…=a_n$ 该玩家负

从特殊到一般考虑：

已经有一个 $a_i=1$ 时 $\gcd一定1$ ，此时的操作就简化为每个人每次将一个数 $-1$ ，即，此时先手必胜当且仅当偶数的个数为奇数

将偶数个数记为 $d_1$ ，奇数个数记为 $d_0$

在考虑一般情况：如果除的 $\gcd$ 是奇数，则对局面的奇偶性不影响，即， $d_1,d_0$ 都不变

由此，如果在某一方发现 $d_1$ 是奇数，则他希望 $\gcd$ 是奇数

有结论： 若 $2\nmid d_1$ 则先手必胜 ； 若 $2\mid d_1 且 d_0\geq 2 ; 或 2\mid d_1 且 数列中有 1$ 则后手必胜

证明被吃掉了Σ(っ °Д °;)っ

剩余的情况是：偶数个偶数，且剩一个 $>1$ 的奇数

此时先手一定不操作偶数，否则 $\gcd$ 为奇不改变就行，而后手满足 $2\nmid d_1$ 则后手必胜

先手一定会把奇数 $-1$ 让 $\gcd$ 变成偶数

那么模拟先手的操作，更换先后手，判断新局面即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const int N=1e5+100;
int n;
vector<int> a;

inline bool judge(const vector<int> &v){
    rei c[2]={0},g=0;
    bool one=false;
    vector<int> u(v);
    for(int x:v) ++c[x&1],one|= x==1;
    if(*c&1) return true;
    if(one || c[1]>1) return false;
    for(int &x:u) g=__gcd(g,x&=-2);
    for(int &x:u) x/=g;
    return !judge(u);//换手
}

int main(){
    scanf("%d",&n); a.reserve(n);
    for(rei i=1,x;i<=n;++i) scanf("%d",&x),a.emplace_back(x);
    puts(judge(a) ? "First" : "Second");
    getchar(),getchar();
    return 0;
}

E

一个长度为 $n$ 的数列 $a$ ，$A$ 会将整个序列任意排列，$B$ 选择一个相邻的互质数交换位置。 $A$ 希望最终序列字典序尽可能小， $B$ 希望尽可能大，求最终序列

考虑到 $B$ 只能交换互质的数，那么，所有不互质的数在 $A$ 确定位置后相对位置不会改变，即，对于 $i,j \ 其中 i<j 且 \gcd(a_i,a_j)\not ={1}$ ，连 $i\rightarrow j$ 以确保 $a_i$ 在 $a_j$ 左边，这构成一个DAG

通过拓扑可以得到合法解，而加入优先队列可以得到后手想要的最大解

注意先手尽可能把较小的往前面放，按权值小到大枚举 $u$ 的儿子 $v$ ，并连 $u\rightarrow v$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
const int N=2010;
int n,c[N],deg[N],G[N][N]; bool vis[N];
int head[N],Next[N<<1],ver[N<<1],tot;

inline void add(int u,int v){ ver[++tot]=v,Next[tot]=head[u],head[u]=tot; ++deg[v];}
priority_queue<int> q;

void dfs(int x){
    vis[x]=1;
    for(rei i=1;i<=n;++i){
        if(vis[i] || !G[i][x]) continue;
        add(x,i); dfs(i);
    }
}

void topsort(){
    for(rei i=1;i<=n;++i) if(!deg[i]) q.push(i);
    while(q.size()){
        rei x=q.top(); q.pop();
        printf("%d ",c[x]);
        for(rei i=head[x];i;i=Next[i]) q.push(ver[i]);
    }
}

int main(){
    scanf("%d",&n);
    for(rei i=1;i<=n;++i) scanf("%d",&c[i]);
    sort(c+1,c+1+n);
    for(rei i=1;i<=n;++i)
        for(rei j=i+1;j<=n;++j){
            if(__gcd(c[i],c[j])==1) continue;
            G[i][j]=G[j][i]=1;
        }
    for(rei i=1;i<=n;++i) if(!vis[i]) dfs(i);
    topsort();
    getchar(),getchar();
    return 0;
}

F

给定 $n$ 个节点的数，顶点 $i$ 上有 $a_i$ 枚石子，开始前 $A$ 可以选择一个节点并在其上面放一枚棋子，然后 $AB$ 交替以下操作：设棋子当前在点 $v$ ，若当前点 $v$ 行已经没有石子则当前玩家输，否则移除点 $v$ 上的一个石子；将棋子移到相邻的点 $u$。 要求找到所有点 $v$ 使 $A$ 开局前把棋子放到 $v$ 上时必胜

证明一个神仙结论：任何时候，每个人只会向满足 $A$ 更小的地方走，即，任何人不会向 $A_u\geq A_v$ 的点 $u$ 移动

  • 不妨设 $A$ 如此移动，即，棋子 $v\rightarrow u$ ，将原树看成以 $v$ 为根的有根树，考虑以 $u$ 为根的子树

    • 若 $B$ 在当前有必胜策略，则 $B$ 赢了
    • 若 $B$ 无必胜策略，则 $B$ 的最优策略是逃离 $u$ ，那么 $B:u\rightarrow v$ 如此 $A$ 会失去先手优势
    • 由此， $A$ 不可能取胜，则其不会这么走

由上可知，若子树中 $B$ 赢，则原树中 $A$ 赢，反之亦成立

$\text{dfs}$ 判断 ，$O(n^2)$ 解决即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
const int N=3010;
int head[N],Next[N<<1],ver[N<<1],tot;
int a[N],n;
bool first=true;

inline void add(int u,int v){ ver[++tot]=v,Next[tot]=head[u],head[u]=tot;}

bool dfs(int x,int fa=0){
    bool flag=1;
    for(rei i=head[x];i;i=Next[i]){
        rei y=ver[i]; if(y==fa || a[y]>=a[x]) continue;
        flag&=dfs(y,x);
    }
    return !flag;//经典换手
}

int main(){
    scanf("%d",&n);
    for(rei i=1;i<=n;++i) scanf("%d",&a[i]);
    for(rei i=1,u,v;i<n;++i) scanf("%d%d",&u,&v),add(u,v),add(v,u);
    for(rei i=1;i<=n;++i) if(dfs(i)) first ? first=false : putchar(32),printf("%d",i);
    puts("");
    getchar(),getchar();
    return 0;
}