ExaWizards2019题解

Source

ExaWizards2019

C

请先思考后再展开

因为推过去后,后面是生死与共的,考虑dp执行操作的一段后缀i,然后位置j是否活着
$f(i,j)=f(i+1,j-1/j+1)$ 然后不难发现其实那一段连续的1每次最多更改1位

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
char type[MAX_N];pr qes[MAX_N];
void main()
{
int n,q;scanf("%d%d%s",&n,&q,type+1);
for(int i=1;i<=q;i++)
{
char str1[10],str2[10];scanf("%s%s",str1,str2);
qes[i]=MP(str1[0]-'A',str2[0]=='R');
}
int fl=1,fr=n;
for(int i=q;i>=1;i--)
{
if(qes[i].SE)
{
if(fl>1 and type[fl-1]=='A'+qes[i].FR) fl--;
if(type[fr]=='A'+qes[i].FR) fr--;
}
else
{
if(fr<n and type[fr+1]=='A'+qes[i].FR) fr++;
if(type[fl]=='A'+qes[i].FR) fl++;
}
if(fl>fr) break;
}
write(fr-fl+1);
}

题解做法是mlogm的,就二分这个区间的端点,模拟这个格子上面的人来check即可

D

请先思考后再展开

先从大到小排序
f(i,j)表示考虑后缀i,各种方案的和

1
2
3
4
5
6
7
8
9
10
ll f[MAX_N][MAX_M];int a[MAX_N];
void main()
{
int n=qread(),now=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 i=0;i<MAX_M;i++) f[n][i]=i%a[n];
for(int i=n-1;i>=1;i--)
for(int j=0;j<MAX_M;j++)
f[i][j]=(f[i+1][j%a[i]]+f[i+1][j]*(n-i)%MOD)%MOD;
write(f[1][now]);
}

E

请先思考后再展开

一、 $i \leq min(B,W)$
ans=1/2
二、
设没有白色为fw,没有黑色为fb
$fb(i)=\sum_{j=B}^{i-1} C_{j-1}^{W-1} \frac{1}{2^j}$
fw类似,然后都有就是 1-fb-fw
那么答案为 $\frac{1}{2} (1-fw-fb)+fw$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void main()
{
fac[0]=1;for(int i=1;i<MAX_N;i++) fac[i]=fac[i-1]*i%MOD;
inv[1]=1;for(int i=2;i<MAX_N;i++) inv[i]=ll(MOD-MOD/i)*inv[MOD%i]%MOD;
facinv[0]=1;for(int i=1;i<MAX_N;i++) facinv[i]=facinv[i-1]*inv[i]%MOD;
bin[0]=1;for(int i=1;i<MAX_N;i++) bin[i]=bin[i-1]*inv[2]%MOD;
int B=qread(),W=qread(),fw=0,fb=0;
for(int i=1;i<=B+W;i++)
{
if(W<=i-1) add(fw,C(i-2,W-1)*bin[i-1]%MOD);
if(B<=i-1) add(fb,C(i-2,B-1)*bin[i-1]%MOD);
if(i<=W and i<=B) write2(inv[2]);
else write2( (inv[2]*(MOD*2+1-fw-fb)%MOD+fw)%MOD );
}
}

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