AGC002题解

Source

AGC002
好题:E、F

B

请先思考后再展开

按题意模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int siz[MAX_N];bool v[MAX_N];
void main()
{
int n=qread(),m=qread();
v[1]=1;for(int i=1;i<=n;i++) siz[i]=1;
while(m--)
{
int x=qread(),y=qread();siz[x]--;siz[y]++;
if(v[x]) v[y]=1;
if(siz[x]==0) v[x]=0;
}
int ans=0;for(int i=1;i<=n;i++) ans+=v[i];
write(ans);
}

C

请先思考后再展开

按题意模拟
不过想了一会儿

1
2
3
4
5
6
7
8
9
10
11
12
13
int a[MAX_N];
void main()
{
int n=qread(),L=qread();for(int i=1;i<=n;i++) a[i]=qread();
for(int i=1;i<=n-1;i++) if(a[i]+a[i+1]>=L)
{
puts("Possible");
for(int j=1;j<i;j++) printf("%d\n",j);
for(int j=n-1;j>=i+1;j--) printf("%d\n",j);
printf("%d",i);return;
}
puts("Impossible");
}

D

请先思考后再展开

我写了个很显然的整体二分+dsu,时间是nlogn的,唯一缺点是离线
网上好像有些人用的是log方的带撤销的并查集,其实没必要,直接从左往右做就行了
rose用的是kruskal重构树,时间下界为nlogn,而且是在线的

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
// #include<unordered_map>
using namespace std;
int bin[40],lg[1<<21];
namespace mine
{
typedef long long ll;
#define double long double
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3fll;
ll qread()
{
ll ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void writeln(int num){write(num);puts("");}
#define FR first
#define SE second
#define MP make_pair
#define pr pair<int,int>
#define PB push_back
#define vc vector
void chmax(int &x,const int y) {x=x>y?x:y;}
void chmin(int &x,const int y) {x=x<y?x:y;}
const int MAX_N=1e5+10;
const int MOD=1e9+7;
void add(int &x,int y) {x+=y;if(x>=MOD) x-=MOD;if(x<0) x+=MOD;}
struct DSU
{
int fa[MAX_N],siz[MAX_N];
void clear(){for(int i=1;i<MAX_N;i++) fa[i]=i,siz[i]=1;}
int findfa(int x) {return x==fa[x]?x:fa[x]=findfa(fa[x]);}
void merg(int x,int y)
{
int fx=findfa(x),fy=findfa(y);
if(fx==fy) return;
if(siz[fx]<siz[fy]) swap(fx,fy);
siz[fx]+=siz[fy];fa[fy]=fx;
}
bool check(int x,int y,int z)
{
x=findfa(x),y=findfa(y);
if(x==y) return siz[x]>=z;
return siz[x]+siz[y]>=z;
}
}dsu;
int ans[MAX_N];
pr e[MAX_N];struct Qes{int x,y,z,id,nowl,nowr;}q[MAX_N];
int ct[MAX_N],now[MAX_N];
void main()
{
int n=qread(),m=qread();
for(int i=1;i<=m;i++) e[i].FR=qread(),e[i].SE=qread();
int qq=qread();
for(int i=1;i<=qq;i++)
{
int x=qread(),y=qread(),z=qread();
q[i]=(Qes){x,y,z,i,1,m};
}
for(int T=20;T>=0;T--)
{
memset(ct,0,sizeof ct);
for(int i=1;i<=qq;i++) ct[q[i].nowl]++;
for(int i=1;i<=m;i++) ct[i]+=ct[i-1];
for(int i=qq;i>=1;i--) now[ct[q[i].nowl]--]=i;
dsu.clear();
int fl=1,fr=0;
for(int mid=1;mid<=m;mid++)
{
while(fr+1<=qq and (q[now[fr+1]].nowl+q[now[fr+1]].nowr)/2<=mid) fr++;
dsu.merg(e[mid].FR,e[mid].SE);
if(fl<=fr)
{
for(int i=fl;i<=fr;i++)
{
int t=now[i];if(q[t].nowl>q[t].nowr) continue;
if(dsu.check(q[t].x,q[t].y,q[t].z)) ans[q[t].id]=mid,q[t].nowr=mid-1;
else q[t].nowl=mid+1;
}
fl=fr+1;
}
}
}
for(int i=1;i<=qq;i++) writeln(ans[i]);
}
};
int main()
{
srand(time(0));
bin[0]=1;for(int i=1;i<=30;i++) bin[i]=bin[i-1]<<1;
lg[1]=0;for(int i=2;i<(1<<21);i++) lg[i]=lg[i>>1]+1;
mine::main();
}

E

请先思考后再展开

因为是个平等博弈,sg是可以用的
然后不知道怎么表达一个状态,想过排序,但没想下去……
就是从大到小排序后,这就是不规则的棋盘,类似这样:

然后用sg函数推一推,很容易证明一条线上的【是否必胜】是相同的
那么暴力找即可,复杂度下界为n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int a[MAX_N];
void main()
{
int n=qread();for(int i=1;i<=n;i++) a[i]=qread();
sort(a+1,a+n+1);reverse(a+1,a+n+1);
for(int x=1;x<=n;x++)
if(x+1>a[x+1])
{
int up=(a[x]-x),right=0;
while(x+right+1<=n and x<=a[x+right+1]) right++;
int now;
if(up==0 and right==0) now=0;
else if(up==0) now=right&1;
else if(right==0) now=up&1;
else now=(up!=0 and right!=0);
puts(now?"First":"Second");
break;
}
}

F

请先思考后再展开

因为第一个球都是相同颜色,考虑把每个颜色贡献到第二个球上面统计
然后每次把一个颜色给统计进来
设f(i,j)表示有i个白球,j个其他颜色(显然i>=j)

$$
f(i,j)=f(i-1,j)+\
f(i,j-1) \times (n-j+1) \times C_{n-i+(k-1)*(n-j+1)-1}^{k-2}
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void main()
{
inv[1]=1;for(int i=2;i<MAX_M;i++) inv[i]=ll(MOD-MOD/i)*inv[MOD%i]%MOD;
fac[0]=1;for(int i=1;i<MAX_M;i++) fac[i]=(ll)fac[i-1]*i%MOD;
facinv[0]=1;for(int i=1;i<MAX_M;i++) facinv[i]=(ll)facinv[i-1]*inv[i]%MOD;
int n=qread(),k=qread();
if(k==1) {puts("1");return;}
f[0][0]=1;
for(int i=1;i<=n;i++) for(int j=0;j<=i;j++)
{
if(i>0) add(f[i][j],f[i-1][j]);
if(j>0) add(f[i][j],(ll)f[i][j-1]*(n-j+1)%MOD*C(n-i+(k-1)*(n-j+1)-1,k-2)%MOD );
}
printf("%d",f[n][n]);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/797f.html
转载请注明出处,谢谢!