CFR604

CFR604 div1

CF1264B Beautiful Sequence

请先思考后再展开

非常简洁的方法:先根据奇偶性把1、2填上去,然后选a0个2改成0,选a3个1改成3,一个从前找,一个从后找,有解的话一定能构造出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
fo(i,0,3) a[i]=qread();
int c0=a[0]+a[2],c1=a[1]+a[3],n=c0+c1;if(abs(c0-c1)>1) gg();
if(c0>c1)
{
fo(i,0,n-1) b[i]=(i&1?1:2);
fo(i,0,n-1) if(a[0] and b[i]==2) b[i]=0,a[0]--;
fd(i,n-1,0) if(a[3] and b[i]==1) b[i]=3,a[3]--;
}
else
{
fo(i,0,n-1) b[i]=(i&1?2:1);
fo(i,0,n-1) if(a[3] and b[i]==1) b[i]=3,a[3]--;
fd(i,n-1,0) if(a[0] and b[i]==2) b[i]=0,a[0]--;
}
fo(i,0,n-2) if(abs(b[i]-b[i+1])!=1) gg();
puts("YES");fo(i,0,n-1) write1(b[i]);

CF1264C Beautiful Mirrors with queries

请先思考后再展开

很明显设期望状态的时候考虑差分,即从位置i到i+1期望步数,答案就是维护和
$$
q_i=p_i/100,对于标记点g_{i}=\frac{1}{q_i},记S_i=\sum_{j=lst}^i g_j
\\
g_i=1+(1-\frac{1}{q_i}) S_i,S_i=S_{i-1}+1+(1-\frac{1}{q_i}) S_i,S_i=\frac{S_{i-1}+1}{q_i}
$$

可以无脑上常数8的矩乘,我是手动实现二元组表示乘a加b,总之ST表预处理这个区间的东西

区间和$(l,r)=\frac{1}{q_l}*[l+1到r的矩阵乘积]$,$O(qlogn*乘法复杂度)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
pr Mul(pr a,pr b){return {a.FR*b.FR%MOD,(a.SE*b.FR+b.SE)%MOD};}
int p[N];pr f[N][30];pr ask(int l,int r){pr ret={1,0};fd(i,20,0)if(l+bin(i)-1<=r)ret=Mul(ret,f[l][i]),l+=bin(i);return ret;}
set<int> all;
ll fuk(int l,int r){pr t=ask(l+1,r);return (invm(p[l])*t.FR+t.SE)%MOD;}
void main()
{
int n=qread(),q=qread();fo(i,1,n) p[i]=qread()*invm(100)%MOD,f[i][0]={invm(p[i]),invm(p[i])};
fo(j,1,20) fo(i,1,n-bin(j)+1) f[i][j]=Mul(f[i][j-1],f[i+bin(j-1)][j-1]);
ll now=fuk(1,n);all.insert(1);all.insert(n+1);
while(q--)
{
int x=qread();int left=*(--all.lower_bound(x)),right=*all.upper_bound(x);
if(all.count(x)) now+=fuk(left,right-1)-fuk(left,x-1)-fuk(x,right-1),all.erase(x);
else now-=fuk(left,right-1)-fuk(left,x-1)-fuk(x,right-1),all.insert(x);
now=(now%MOD+MOD)%MOD;write2(now);
}
}

CF1264D Beautiful Bracket Sequence

请先思考后再展开

很容易想到一个已知串的深度,为$max_i\ min(i左边的左括号,i右边的右括号)$

然后其实这个有些不错的性质,反证一下可知:只需要找到一个位置满足$i左边的左括号=i右边的右括号$,且这个位置唯一
$$
\\
记a为前缀左括号,b为前缀右括号,pre为前缀问号,
ans=\sum_i \sum_j j*C_{pre_i}^{j-a_i}*C_{pre_n-pre_i}^{j-(b_n-b_i)}
\\
很自然的想法是保留i去掉j,j=(j-a_i+a_i)
\\
ans=
\sum_i pre_i \sum_j C_{pre_i-1}^{j-a_i-1}C_{pre_n-pre_i}^{j-(b_n-b_i)}+
\sum_i a_i \sum_j C_{pre_i}^{j-a_i}C_{pre_n-pre_i}^{j-(b_n-b_i)}
\\
ans=
\sum_i pre_i \sum_j C_{pre_i-1}^{i-b_i-j}C_{pre_n-pre_i}^{j-(b_n-b_i)}+
\sum_i a_i \sum_j C_{pre_i}^{i-b_i-j}C_{pre_n-pre_i}^{j-(b_n-b_i)}
\\
ans=\sum_i pre_i C_{(pre_n-1)}^{(i-b_n)}+a_i C_{pre_n}^{(i-b_n)}
$$
code

CF1264E Beautiful League

「WC2007」剪刀石头布

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