Atcoder 杂题

AGC014D [博弈，贪心]

大意：两人轮流给树黑白染色（白先手），若最终存在一个白点周围都是白点，白胜，问胜负

题解：

当一个点与两个或以上叶子相邻时白必胜
若它只与一个叶子相邻，将它和这个叶子删掉（一个叶子白点相当于边界的作用）

 1 #include<bits/stdc++.h>
 2 #define FOR(i,a,b) for (register int i=(a);i<=(b);i++)
 3 #define For(i,a,b) for (register int i=(a);i>=(b);i--)
 4 #define mem(i,j) memset(i,j,sizeof(i))
 5 #define GO(u) for (register int j=f[u];j!=-1;j=nxt[j])
 6 #define fi first
 7 #define se second
 8 #define pii pair<int,int>
 9 #define MP make_pair
10 using namespace std;
11 typedef long long ll;
12 const int N=1e5+5;
13 int n,a,b,lf[N],d[N],rt;
14 int tot=0,f[N],nxt[N<<1];
15 struct E
16 {
17     int u,v;
18 }e[N<<1];
19 inline void add(int u,int v)
20 {
21     tot++;
22     nxt[tot]=f[u];
23     f[u]=tot;
24     e[tot]=(E){u,v};
25     return;
26 }
27 inline int read()
28 {
29     int x=0,f=1;
30     char c=getchar();
31     while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
32     while (c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
33     return f*x;
34 }
35 inline void write(int x)
36 {
37     if (x<0) putchar('-'),x=-x;
38     if (x>9) write(x/10);
39     putchar(x%10+'0');
40     return;
41 }
42 inline void yes() {printf("First
");exit(0);}
43 inline void no() {printf("Second
");exit(0);}
44 inline int dfs(int u,int fa)
45 {
46     int cnt=0;
47     GO(u)
48     {
49         int v=e[j].v;
50         if (v==fa) continue;
51         cnt+=dfs(v,u);
52     }
53     if (cnt>1) yes();
54     return cnt^1;
55 }
56 int main()
57 {
58     mem(f,-1);
59     n=read();
60     if (n==2) no();
61     if (n==1) yes();
62     FOR(i,1,n-1) a=read(),b=read(),add(a,b),add(b,a),d[a]++,d[b]++;
63     FOR(i,1,n) lf[i]=(d[i]==1);
64     FOR(i,1,n) if (!lf[i]) {rt=i;break;}
65     if (dfs(rt,0)) yes();
66     no();
67     return 0;
68 }

View Code

AGC010D [博弈，思维]

大意：有$n$个数，两个人轮流操作，每次操作选择一个数减一后所有数除以他们的$GCD$，全部数变为$1$时无法操作（输），问胜负

题解：

小性质：当存在至少两个数是奇数时，无论你操作哪一个数，那个数的奇偶变一下，其它都不变
由小性质得，全是奇数时先手必败，因为轮到对手时总有偶数，由于初始$GCD$为$1$，所以一开始至少有一个奇数，下面讨论偶数个数的奇偶性
1，若有奇数个偶数，先手必胜，先手操作一个偶数后符合小性质，后手必败
2，若有偶数个偶数，且没有奇数（某个局面，不特指初始），先手必败，先手不得不操作一个偶数，变成了情况1
3，若有偶数个偶数，且有奇数时，先手肯定不想操作偶数，先手想操作奇数并除以$2$，所以如果有多个奇数或存在$1$，先手必败，否则操作那个奇数，变成一个子问题，层数$O(logn)$级别

 1 #include<bits/stdc++.h>
 2 #define FOR(i,a,b) for (register int i=(a);i<=(b);i++)
 3 #define For(i,a,b) for (register int i=(a);i>=(b);i--)
 4 #define mem(i,j) memset(i,j,sizeof(i))
 5 #define GO(u) for (register int j=f[u];j!=-1;j=nxt[j])
 6 #define fi first
 7 #define se second
 8 #define pii pair<int,int>
 9 #define MP make_pair
10 using namespace std;
11 typedef long long ll;
12 const int N=1e5+5;
13 int n,a[N],ji,ou,pos,now,gcd;
14 inline int read()
15 {
16     int x=0,f=1;
17     char c=getchar();
18     while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
19     while (c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
20     return f*x;
21 }
22 inline void write(int x)
23 {
24     if (x<0) putchar('-'),x=-x;
25     if (x>9) write(x/10);
26     putchar(x%10+'0');
27     return;
28 }
29 inline void yes() {if (now) printf("First
");else printf("Second
");exit(0);}
30 inline void no() {if (now) printf("Second
");else printf("First
");exit(0);}
31 inline int GCD(int x,int y)
32 {
33     if (!y) return x;
34     if (x<y) return GCD(y,x);
35     return GCD(y,x%y);
36 }
37 inline void solve()
38 {
39     ou=0,ji=0;
40     FOR(i,1,n) ji+=(a[i]&1),ou+=(!(a[i]&1));
41     if (!ou) no();
42     if (ou&1) yes();
43     if (!ji) no();
44     if (ji>1) no();
45     FOR(i,1,n) if (a[i]&1) {pos=i;break;}
46     if (a[pos]==1) no();
47     a[pos]--;
48     gcd=a[1];
49     FOR(i,2,n) gcd=GCD(gcd,a[i]);
50     FOR(i,1,n) a[i]/=gcd;
51     now^=1;
52     solve();
53     return;
54 }
55 int main()
56 {
57     now=1;
58     n=read();
59     FOR(i,1,n) a[i]=read();
60     solve();
61     return 0;
62 }

View Code

AGC010E [思维，拓扑排序]

大意：长度为$2000$值域为$10^8$的序列，两个人分别对其操作一次，第一个人任意安排顺序，第二个人任意次交换相邻的互质的数，前者希望最终字典序最小，后者希望最终字典序最大，问最终序列

题解：

本题的两个关键点：1，互质的数位置可以乱换，这意味互质的数之间大的在前面，2，不互质的数相对顺序不会变，这意味第一个人一开始会把小的放前面
将所有不互质的点连边，每次取当前最小的点拓扑排序，遍历时仍然优先小点遍历，把所有目前入读为零的点丢到堆里去（因为它们互质，大的在前面）

 1 #include<bits/stdc++.h>
 2 #define FOR(i,a,b) for (register int i=(a);i<=(b);i++)
 3 #define For(i,a,b) for (register int i=(a);i>=(b);i--)
 4 #define mem(i,j) memset(i,j,sizeof(i))
 5 #define GO(u) for (register int j=f[u];j!=-1;j=nxt[j])
 6 #define fi first
 7 #define se second
 8 #define pii pair<int,int>
 9 #define MP make_pair
10 #define pb push_back
11 using namespace std;
12 typedef long long ll;
13 const int N=2020;
14 int n,a[N],vis[N],cnt=0,ans[N],du[N];
15 vector<int> vec[N],G[N];
16 priority_queue <pii> q;
17 inline int read()
18 {
19     int x=0,f=1;
20     char c=getchar();
21     while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
22     while (c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
23     return f*x;
24 }
25 inline void write(int x)
26 {
27     if (x<0) putchar('-'),x=-x;
28     if (x>9) write(x/10);
29     putchar(x%10+'0');
30     return;
31 }
32 inline int GCD(int x,int y)
33 {
34     if (!y) return x;
35     if (x<y) return GCD(y,x);
36     return GCD(y,x%y);
37 }
38 inline void dfs(int u)
39 {
40     vis[u]=1;
41     FOR(i,0,(int)vec[u].size()-1)
42     {
43         int v=vec[u][i];
44         if (vis[v]) continue;
45         G[u].pb(v);
46         du[v]++;
47         dfs(v);
48     }
49     return;
50 }
51 bool cmp(const int x,const int y) {return a[x]<a[y];}
52 int main()
53 {
54     n=read();
55     FOR(i,1,n) a[i]=read();
56     sort(a+1,a+n+1);//1
57     FOR(i,1,n) FOR(j,1,n) if (i!=j) if (GCD(a[i],a[j])>1) vec[i].pb(j);
58 //    FOR(i,1,n) sort(vec[i].begin(),vec[i].end()); //2
59     FOR(i,1,n) if (!vis[i])
60     {
61         dfs(i);
62         q.push(MP(a[i],i));
63     }
64     while (q.size())
65     {
66         pii tmp=q.top();
67         q.pop();
68         ans[++ans[0]]=tmp.fi;
69         FOR(i,0,(int)G[tmp.se].size()-1)
70         {
71             int v=G[tmp.se][i];
72             du[v]--;
73             if (!du[v]) q.push(MP(a[v],v));
74         }
75     }
76     FOR(i,1,n) write(ans[i]),putchar(' ');
77     return 0;
78 }

View Code

ARC082E [思维]

大意：给出$200$个点，请你求出所有合法点集的权值和，一个点集合法即这些点恰好是某个凸包的顶点集，一个合法点集的权值定义如下，设在凸包之中的点数为$n$（包括边间和顶点），其值为$2^{n-|S|}$

题解：

这题让我们计算合法的，而不是全部的，这就很好
这题根据定义，每一个凸包都有$2^{...}$的贡献，反过来考虑，$2^{...}$的组合意义即为这些点的所有子集，这些子集都对这个凸包有$1$的贡献
再进一步转换，不考虑凸包，直接考虑点集，每个存在一个子集能构成凸包的点集，对答案有$1$的贡献
于是用总点集数，减去共线的点集数，就是答案

 1 #include<bits/stdc++.h>
 2 #define FOR(i,a,b) for (register int i=(a);i<=(b);i++)
 3 #define For(i,a,b) for (register int i=(a);i>=(b);i--)
 4 #define mem(i,j) memset(i,j,sizeof(i))
 5 #define GO(u) for (register int j=f[u];j!=-1;j=nxt[j])
 6 #define fi first
 7 #define se second
 8 #define pii pair<int,int>
 9 #define MP make_pair
10 #define pb push_back
11 using namespace std;
12 typedef long long ll;
13 const int N=205;
14 const int mod=998244353;
15 int n,x[N],y[N],ans=0,er[N];
16 inline int read()
17 {
18     int x=0,f=1;
19     char c=getchar();
20     while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
21     while (c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
22     return f*x;
23 }
24 inline void write(int x)
25 {
26     if (x<0) putchar('-'),x=-x;
27     if (x>9) write(x/10);
28     putchar(x%10+'0');
29     return;
30 }
31 int main()
32 {
33     n=read();
34     FOR(i,1,n) x[i]=read(),y[i]=read();
35     er[0]=1;
36     FOR(i,1,n) er[i]=2LL*er[i-1]%mod;
37     ans=(1LL*er[n]-1-n+mod)%mod;
38     FOR(i,1,n) FOR(j,1,i-1) 
39     {
40         int cnt=0;
41         FOR(k,1,j-1) if (1LL*((y[i]-y[j])*(x[j]-x[k]))==1LL*((x[i]-x[j])*(y[j]-y[k]))) cnt++;
42         ans=(1LL*ans-er[cnt]+mod)%mod;
43     }
44     write(ans);
45     return 0;
46 }

View Code

AGC008E [基环树，计数，排列置换]

大意：给出长度$nleq 10^5$值域$[1,n]$的序列$a$，构造排列$p$，使得对于任意$i$都有$p_i=a_i或p_{p_i}=a_i$，问有多少种能构造出来的排列$p$

题解：

这种排列置换的问题我们必然放到图论里面去分析
问题的本质在于给定$a$，求$p$的可能状况，反过来考虑，加入我们知道$p$，怎样的$a$是可能的
连边$i->p_i$后形成一个个环，我们得到了点之间的相对关系后把这些边擦去，考虑换成$i->a_i$的边，那么由题意可知，这种边，1，连到下一个，2，连到下一个的下一个
对于全是1的情况，形状不变，对于全是2，若是奇环，大小不变但顺序有变，若是偶环，拆成两个偶环，若两种情况都有，变成一个基环内向树
对于一个基环内向树，我们需要把挂在环上的一条条链按方向塞回环上，这时按照两条链之间的距离讨论，有方案数$0,1,2$三种情况
通过分析我们顺理成章地得到了无解的情况，1，存在了除了换和基环内向树以外的其它结构，2，基环树上某相邻两条链之间的距离小于前面那条的长度
处理方案数稍稍麻烦，需要记录长度为$i$的环的个数，以及对每个基环树处理

  1 #include<bits/stdc++.h>
  2 #define FOR(i,a,b) for (register int i=(a);i<=(b);i++)
  3 #define For(i,a,b) for (register int i=(a);i>=(b);i--)
  4 #define mem(i,j) memset(i,j,sizeof(i))
  5 #define GO(u) for (register int j=f[u];j!=-1;j=nxt[j])
  6 #define fi first
  7 #define se second
  8 #define pii pair<int,int>
  9 #define MP make_pair
 10 #define pb push_back
 11 using namespace std;
 12 typedef long long ll;
 13 const int N=1e6+5;
 14 const int mod=1e9+7;
 15 int n,a[N],du[N],cnt=0,vis[N],cir[N],tag[N],len[N],lth[N],s[N];
 16 int fac[N],inv[N],er[N],stck[N],top=0,ans=1;
 17 int tot=0,f[N],nxt[N];
 18 struct E
 19 {
 20     int u,v;
 21 }e[N];
 22 inline int read()
 23 {
 24     int x=0,f=1;
 25     char c=getchar();
 26     while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
 27     while (c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
 28     return f*x;
 29 }
 30 inline void write(int x)
 31 {
 32     if (x<0) putchar('-'),x=-x;
 33     if (x>9) write(x/10);
 34     putchar(x%10+'0');
 35     return;
 36 }
 37 inline void no() {printf("0
");exit(0);}
 38 inline int qpow(int x,int y) {int ret=1;for (;y;y>>=1,x=1LL*x*x%mod) if (y&1) ret=1LL*ret*x%mod;return ret;}
 39 inline int Inv(int x) {return qpow(x,mod-2);}
 40 inline void Init()
 41 {
 42     er[0]=fac[0]=1;
 43     FOR(i,1,n) er[i]=1LL*er[i-1]*2%mod,fac[i]=1LL*fac[i-1]*i%mod;
 44     inv[n]=Inv(fac[n]);
 45     For(i,n-1,0) inv[i]=1LL*inv[i+1]*(i+1)%mod;
 46     return;
 47 }
 48 inline int C(int x,int y)
 49 {
 50     int ret=1LL*fac[x]*inv[y]%mod*inv[x-y]%mod;
 51     return ret;
 52 }
 53 inline void Work1()//找环+判无解
 54 {
 55     queue <int> Q;
 56     while (Q.size()) Q.pop();
 57     int d[N];
 58     FOR(i,1,n) d[i]=du[i];
 59     FOR(i,1,n) if (!d[i]) Q.push(i);
 60     while (Q.size())
 61     {
 62         int tmp=Q.front();Q.pop();
 63         d[a[tmp]]--;
 64         if (!d[a[tmp]]) Q.push(a[tmp]);
 65         vis[tmp]=-1;
 66     }
 67     FOR(i,1,n) if (vis[i]==0)
 68     {
 69         int now=i;
 70         cnt++;
 71         while (!vis[now]) vis[now]=1,cir[now]=cnt,now=a[now];
 72     }
 73     FOR(i,1,n) if (vis[i]==-1) if (du[i]>1) no();
 74     FOR(i,1,n) if (vis[i]==1) if (du[i]>2) no();
 75 //    printf("vis : ");FOR(i,1,n) printf("%d ",vis[i]);putchar('
');
 76 //    printf("cir : ");FOR(i,1,n) printf("%d ",cir[i]);putchar('
');
 77     return;
 78 }
 79 inline void add(int u,int v)
 80 {
 81     tot++;
 82     nxt[tot]=f[u];
 83     f[u]=tot;
 84     e[tot]=(E){u,v};
 85     return;
 86 }
 87 inline int dfs(int u,int fa) {GO(u) if (e[j].v!=fa&&!cir[e[j].v]) return dfs(e[j].v,u)+1;return 0;}
 88 inline void Work2()//找基环树+找链长度+按长度统计环 
 89 {
 90     FOR(i,1,n) add(a[i],i);
 91     FOR(i,1,n) vis[i]=0;
 92     FOR(i,1,n) if (cir[i]) if (!vis[i])
 93     {
 94         int now=i,jihuan=0,l=0;
 95         while (!vis[now])
 96         {
 97             vis[now]=1;
 98             GO(now) if (!cir[e[j].v]) jihuan=1;
 99             len[now]=dfs(now,0);
100             now=a[now];
101             l++;
102         }
103         tag[cir[i]]=jihuan;
104         if (!jihuan) lth[cir[i]]=l;
105     }
106     FOR(i,1,cnt) s[lth[i]]++;
107 //    printf("tag : ");FOR(i,1,cnt) printf("%d ",tag[i]);putchar('
');
108 //    printf("len : ");FOR(i,1,n) printf("%d ",len[i]);putchar('
');
109 //    printf("lth : ");FOR(i,1,cnt) printf("%d ",lth[i]);putchar('
');
110     return;
111 }
112 int aa[N],bb[N];
113 inline void DP(int u)
114 {
115     aa[0]=bb[0]=0;
116     int val=1;
117     while (!len[u]) u=a[u];
118     int st=u;
119     u=a[u];
120     int step=1;
121     while (u!=st)
122     {
123         while (!len[u]) step++,u=a[u];
124         bb[++bb[0]]=step;
125         aa[++aa[0]]=len[u];
126         step=0;
127         if (u!=st) u=a[u],step++;
128     }
129     FOR(i,1,aa[0])
130     {
131         if (aa[i]>bb[i]) val=0;
132         else if (aa[i]<bb[i]) val=2LL*val%mod;
133     }
134     stck[++top]=val;
135     return;
136 }
137 inline void Solve(int x)
138 {
139     int val=0;
140     if ((x&1)&&(x!=1)) FOR(i,1,s[x]/2) val=(1LL*val+1LL*C(s[x],2*i)*C(2*i,i)%mod*fac[i]%mod*qpow(x,i)%mod*er[s[x]-2*i]%mod*Inv(er[i])%mod)%mod;
141     else FOR(i,1,s[x]/2) val=(1LL*val+1LL*C(s[x],2*i)*C(2*i,i)%mod*fac[i]%mod*qpow(x,i)%mod*Inv(er[i])%mod)%mod;
142     if ((x&1)&&(x!=1)) val=(1LL*val+er[s[x]])%mod;
143     else val=(1LL*val+1)%mod;
144     stck[++top]=val;
145     return;
146 }
147 int used[N];
148 inline void Work3()//统计每个连通块的方案数 
149 {
150     mem(used,0);
151     FOR(i,1,n) vis[i]=0;
152     FOR(i,1,n) if (cir[i]&&(!lth[cir[i]])&&(!vis[cir[i]])) DP(i),vis[cir[i]]=1;//基环树
153     FOR(i,1,cnt) if (lth[i]&&!used[lth[i]]) Solve(lth[i]),used[lth[i]]=1;//环
154     return;
155 }
156 int main()
157 {
158 //    freopen("16.in","r",stdin);
159 //    freopen("dayinf.out","w",stdout);
160     mem(f,-1);
161     n=read();
162     FOR(i,1,n) a[i]=read(),du[a[i]]++;
163     Init();
164     Work1();
165     Work2();
166     Work3();
167     FOR(i,1,top) ans=1LL*ans*stck[i]%mod;
168     write(ans);
169     return 0;
170 }

View Code

ARC092F [强连通分量，DFS]

大意：给出一个$n leq 1000$个点$m leq 200000$条边的有向图，对于每条边询问，若将这条边反向，整个图的强联通分量个数是否会变

题解：

对于一条从$u$到$v$的边考虑以下两个条件

从$u$到$v$是否存在一条不经过这条边的路径
从$v$是否能到$u$

经过思考，若这两个条件只满足其中一个时会变，否则不会
第二个条件，通过每个点$DFS$求
第一个条件，每个点$DFS$两遍，一次从大到小枚举边，一次从小到大枚举边，记录到$v$的边是哪一条，若都是这一条，说明不存在，否则存在

 1 #include<bits/stdc++.h>
 2 namespace csx_std {
 3     using namespace std;
 4     typedef long long ll;
 5     #define FOR(i,a,b) for (register int i=(a);i<=(b);i++)
 6     #define For(i,a,b) for (register int i=(a);i>=(b);i--)
 7     #define mem(i,j) memset(i,j,sizeof(i))
 8     #define pii pair<int,int>
 9     #define pb push_back
10     #define MP make_pair
11     #define fi first
12     #define se second
13     #define GO(u) for (register int j=f[u];j!=-1;j=nxt[j])
14     const int N=1e3+5;
15     const int M=2e5+5;
16     const int mod=1e9+7;
17     inline int qpow(int x,int y) {int ret=1;for (;y;y>>=1,x=1LL*x*x%mod) if (y&1) ret=1LL*ret*x%mod;return ret;}
18     inline int Inv(int x) {return qpow(x,mod-2);}
19     inline void upd(int &x,int y) {x=(1LL*x+y)%mod;return;}
20     inline int chkmax(int &x,int y) {return (x<y)?(x=y,1):0;}
21     inline int chkmin(int &x,int y) {return (x>y)?(x=y,1):0;}
22     inline int read()
23     {
24         int x=0,f=1;
25         char c=getchar();
26         while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
27         while (c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
28         return f*x;
29     }
30     inline void write(int x)
31     {
32         if (x<0) x=-x,putchar('-');
33         if (x>9) write(x/10);
34         putchar(x%10+'0');
35         return;
36     }
37 }
38 using namespace csx_std;
39 int n,m,tmp1,tmp2,num[N][N],con[N][N],con_con[N][N],vis[N],p[N],q[N],uu[M],vv[M],cnt=0,ans[M];
40 int tot=0,f[N],nxt[M];
41 vector <int> G[N];
42 #define v G[u][i]
43 inline void dfs(int u,int fa)
44 {
45     con[fa][u]=1;
46     vis[u]=1;
47     FOR(i,0,(int)G[u].size()-1) if (!vis[v]) dfs(v,fa);
48     return;
49 }
50 inline void dfs1(int u)
51 {
52     vis[u]=1;
53     FOR(i,0,(int)G[u].size()-1) if (!vis[v]) p[v]=num[u][v],dfs1(v);
54     return;
55 }
56 inline void dfs2(int u)
57 {
58     vis[u]=1;
59     For(i,(int)G[u].size()-1,0) if (!vis[v]) q[v]=num[u][v],dfs2(v);
60     return;
61 }
62 #undef v
63 int main()
64 {
65     mem(f,-1);
66     n=read(),m=read();
67     FOR(i,1,m) tmp1=read(),tmp2=read(),G[tmp1].pb(tmp2),uu[i]=tmp1,vv[i]=tmp2,num[tmp1][tmp2]=++cnt;
68     FOR(i,1,n) {FOR(j,1,n) vis[j]=0;dfs(i,i);}
69     FOR(i,1,n)
70     {
71         FOR(j,1,n) p[j]=q[j]=0;
72         FOR(j,1,n) vis[j]=0;
73         dfs1(i);
74         FOR(j,1,n) vis[j]=0;
75         dfs2(i);
76         FOR(j,0,(int)G[i].size()-1)
77         {
78             int v=G[i][j];
79             if (p[v]!=num[i][v]||q[v]!=num[i][v]) con_con[i][v]=1;
80         }
81     }
82     FOR(i,1,m) if (con[vv[i]][uu[i]] xor con_con[uu[i]][vv[i]]) ans[i]=1;
83     FOR(i,1,m)
84         if (ans[i]) puts("diff");
85         else puts("same");
86     return 0;
87 }

View Code