正文
【codeforces】【比赛题解】#960 CF Round #474 (Div. 1 + Div. 2, combined)
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
终于打了一场CF，不知道为什么我会去打00:05的CF比赛……
不管怎么样，这次打的很好！拿到了Div. 2选手中的第一名，成功上紫！
以后还要再接再厉！
【A】Check the string
题意：
一个合法的字符串可以这样生成：
初始是一个空串，然后小 A 同学往这个串中加入若干（大于零）个字符\(\texttt{a}\)，然后小 B 同学往这个串的末尾加入若干（大于零）个字符\(\texttt{b}\)，最后小 C 同学往这个串的末尾加入一些字符\(\texttt{c}\)，但要满足\(\texttt{c}\)的个数等于\(\texttt{a}\)的个数或\(\texttt{b}\)的个数。
问一个字符串是否是合法的。
题解：
模拟，注意细节。
#include<bits/stdc++.h> char str[10000];
int i,n,A,B,C; int main(){
scanf("%s",str); n=strlen(str);
if(str[0]!='a') {puts("NO"); return 0;}
for(i=0;i<n;++i) if(str[i]=='a') ; else break;
A=i;
if(i==n||str[i]!='b') {puts("NO"); return 0;}
for(;i<n;++i) if(str[i]=='b') ; else break;
if(i==n||str[i]!='c') {puts("NO"); return 0;}
B=i-A;
for(;i<n;++i) if(str[i]=='c') ; else break;
if(i!=n) {puts("NO"); return 0;}
C=n-B-A;
if(C!=A&&C!=B) {puts("NO"); return 0;}
puts("YES");
return 0;
}
【B】Minimize the error
题意：
有两个长度都为\(n\)的数组\(A\)和\(B\)，定义误差\(E=\sum_{i=1}^{n}(A_i-B_i)^2\)。
你需要对数组\(A\)执行恰好\(k_1\)次操作，对数组\(B\)执行恰好\(k_2\)次操作。一次操作即让数组中的一个数加一，或者减一。
问执行完操作后的最小误差\(E\)。
题解：
数组的每一位都是独立的。对于某一位\(A_i,B_i\)，对这一位执行操作可以让\((A_i-B_i)^2=|A_i-B_i|^2\)变大，或者变小。
显然变大是不合算的，所以计算出\(C_i=|A_i-B_i|\)，不论是对\(A\)还是对\(B\)的操作都是一样的，可以让\(C_i\)加一或者减一，但是不能减到负数。
而\(C_i\)越大，对它减一的收益就越大，所以每次贪心选取最大的\(C_i\)减去一。我使用了优先队列来加快速度，尽管暴力可过。
#include<bits/stdc++.h>
#define F(i,a,b) for(int i=a;i<=(b);++i)
#define ll long long
using namespace std; int n,A,B;
int a[100001],b[100001];
priority_queue<int> pq;
ll Ans=0; int main(){
scanf("%d%d%d",&n,&A,&B); A+=B;
F(i,1,n) scanf("%d",a+i);
F(i,1,n) scanf("%d",b+i);
F(i,1,n) a[i]=abs(a[i]-b[i]), pq.push(a[i]);
F(i,1,A){
int x=pq.top(); pq.pop();
if(x>0) pq.push(x-1);
else pq.push(1);
}
int x;
F(i,1,n) x=pq.top(), Ans+=(ll)x*x, pq.pop();
printf("%lld",Ans);
return 0;
}
【C】Subsequence Counting
题意：
对于一个数组，将这个数组的所有非空子序列写下，然后删掉满足：最大值与最小值的差大于等于\(d\)的子序列。
最后剩下了\(X\)个子序列。
请你给出原序列的一种合法排列。
题解：
考虑这样构造：
\(\overset{k_1}{\overbrace{x,\cdots,x}},\overset{k_2}{\overbrace{x+d,\cdots,x+d}},\overset{k_3}{\overbrace{x+2d,\cdots,x+2d}},\cdots\)。
这样的目的是让任意包含两个不同的数的子序列会被删掉，留下的只有包含相同数的。
这样最终剩下的子序列有多少个呢？通过一些简单的计算，我们得到答案：
\(\sum 2^{k_i}-1\)。
得到了这个，发现两组个数分别为\(k_i\)和\(1\)的数，会对答案产生\(2^{k_i}\)的贡献。
那么把\(X\)二进制拆分一下即可。
#include<bits/stdc++.h>
#define F(i,a,b) for(int i=a;i<=(b);++i)
#define ll long long int X,d,cnt;
ll now=1;
ll b[100001]; int main(){
scanf("%d%d",&X,&d);
if(X&1) {b[++cnt]=now; now+=d;}
int x=1; X>>=1;
while(X){
if(X&1){
for(int i=1;i<=x;++i) b[++cnt]=now;
now+=d;
b[++cnt]=now;
now+=d;
}
X>>=1; ++x;
}
printf("%d\n",cnt);
F(i,1,cnt) printf("%lld ",b[i]);
return 0;
}
【D】Full Binary Tree Queries
题意：
给你一个无限层的满二叉树（无限层也不考虑是完全还是满了2333）。
这个满二叉树的节点上有值，而且一个节点的左儿子的值是这个节点的值乘以2，右儿子的值是这个节点的值乘2加1。
你有三个操作：
①把值为X的节点所在层的所有节点的值往右循环移动K位。
②把值为X的节点所在层的所有节点往右循环移动K位，子树也一起移动。
③问值为X的节点走到根的路径上的值的序列。
请执行这些操作，并回答结果。
题解：
发现初始一个节点的值可以很轻松算出来，其实就是线段树上的节点的编号，很有规律。
因为\(X\)在long long范围，所以深度大于62的都是假的节点。
考虑暴力维护每一层循环移动的位数。再做做数学加加减减就完事了。
#include<bits/stdc++.h>
#define F(i,a,b) for(int i=a;i<=(b);++i)
#define dF(i,a,b) for(int i=a;i>=(b);--i)
#define ll long long int n;
ll lev[64]; inline int hibit(ll x){
int ans=-1;
while(x) x>>=1, ++ans;
return ans;
}
inline void shift(int lv,ll k){lev[lv]+=k&((1ll<<lv)-1);lev[lv]&=((1ll<<lv)-1);} int main(){
scanf("%d",&n);
F(i,1,n){
int t; ll x,k;
scanf("%d%lld",&t,&x);
if(t==1){
scanf("%lld",&k);
shift(hibit(x),k);
}
if(t==2){
scanf("%lld",&k);
F(j,hibit(x),61)
shift(j,k<<(j-hibit(x)));
}
if(t==3){
int lv=hibit(x);
ll y=(x-(1ll<<lv)+lev[lv])&((1ll<<lv)-1);
dF(j,lv,0) printf("%lld ",((y-lev[j])&((1ll<<j)-1))+(1ll<<j)), y>>=1; puts("");
}
}
return 0;
}
【E】Alternating Tree
题意：
对于一棵树，假设有一条简单路径\(u_1 \rightarrow u_2 \rightarrow u_3 \rightarrow \dots u_{m-1} \rightarrow u_{m}\)。
定义它的交替函数：\(A(u_{1},u_{m}) = \sum\limits_{i=1}^{m} (-1)^{i+1} \cdot V_{u_{i}}\)。
一条路径也可以有\(0\)条边，即\(u_1=u_m\)。
请计算所有不同路径的交替函数值的总和。答案对\(10^9+7\)取模。
题解：
考虑对于每一个点计算自己的贡献。
为了好处理，把树变成以1为根的有根树。
再考虑一个点的贡献：显然只有经过这个点的路径才会有贡献，即起点在这个点的一个子树（父亲连接的也算作一个子树），终点在其他子树的路径。
而对于一个路径，显然该点在奇数位贡献为正数，否则是负数。假设当前点为\(u\)。
对于起点在某一个大小为\(siz\)的子树中的\(v\)点，这个点在\(u\)的贡献就是\((-1)^{dis_{v,u}}\times (n-siz)\)。
\(n-siz\)即为终点可以在的位置的个数，只要不在同一个子树就可以。
发现只要\(v\)在同一个子树，最后乘的\(n-siz\)都是相同的。考虑把前面的也合并起来。
那么以\(u\)为根建树，\(u\)直接相连的每一个子树\(T\)都定义一个函数\(f(T)=\sum_{v\in T}(-1)^{dep_v}\)。
当\(v\)为\(T\)的根时，\(dep_v=0\)，之后每一层\(dep\)就多一。
这个函数有什么意义呢？发现\(f(T)\)正好就是刚刚的\((-1)^{dis_{v,u}}\)的总和的相反数。
那就是说子树\(T\)对\(u\)的贡献次数是\(-f(T)\times (n-siz_T)=-f(T)\cdot n+f(T)\cdot siz_T\)。
但是还漏了一种起点就是\(u\)本身的情况，那样会多贡献正好\(n\)次。
那就是说，总贡献是\((1-\sum f(T))\cdot n+\sum f(T)\cdot siz_T\)。
那\(siz_T\)通过DFS比较好算，考虑一下\(f(T)\)如何求出。
假如已经以\(u\)为根了，那么\(f(T)\)可以递归计算：\(f(T)=1-\sum f(G)\)，其中\(G\)是与\(T\)直接相连的子树。
这和刚刚的公式是一样的结构，也就是说总贡献为\(f(T_u)\cdot n+\sum f(T)\cdot siz_T\)，\(T_u\)即以\(u\)为根的整棵树。
但是这样还不够，因为要通过DFS计算答案，就必须指定一个点为根，比如\(1\)号点。
那么这时还能统计出每个\(u\)的每个\(f(T)\)吗？
考虑以\(1\)为根时的每个\(f(T)\)，那么以\(u\)为根时，\(f(T_u)\)就等于\(f(1)\)或者\(-f(1)\)。当\(u\)的深度是偶数（1的深度为0）时，就是\(f(1)\)，否则取相反数。
而对于\(u\)的\(f(T)\)呢？对于\(u\)的儿子的\(f(T)\)，值不变，但是\(u\)还有一个指向父亲的\(T\)，其实这个\(f(T)\)就等于\(f(T_u)\)【这个指的是以1为根的】减去\(f(T_u)\)【这个指的是以u为根的，即上面算出来的\(f(1)\)或相反数】。
那么一次DFS求出siz、dep和f值，第二次DFS直接求答案即可。
#include<bits/stdc++.h>
#define F(i,a,b) for(int i=a;i<=(b);++i)
#define eF(i,u) for(int i=h[u];i;i=nxt[i])
#define ll long long int Mod=1000000007;
int n,q;
int val[200001]; int h[200001],nxt[400001],to[400001],tot;
inline void ins(int x,int y){nxt[++tot]=h[x];to[tot]=y;h[x]=tot;} int f[200001],siz[200001],dep[200001]; ll Ans; void DFS(int u,int fa){
f[u]=1; dep[u]=dep[fa]+1; siz[u]=1;
eF(i,u) if(to[i]!=fa) DFS(to[i],u), f[u]-=f[to[i]], siz[u]+=siz[to[i]];
} void D2(int u,int fa){
eF(i,u) if(to[i]!=fa){
D2(to[i],u);
Ans=((Ans+(ll)f[to[i]]*siz[to[i]]%Mod*val[u]%Mod)%Mod+Mod)%Mod;
}
if(fa!=0) Ans=((Ans+(ll)(((dep[u]&1)?-f[1]:f[1])+f[u])*(n-siz[u])%Mod*val[u]%Mod)%Mod+Mod)%Mod;
} int main(){
int x,y;
scanf("%d",&n);
F(i,1,n) scanf("%d",val+i);
F(i,2,n) scanf("%d%d",&x,&y), ins(x,y), ins(y,x);
DFS(1,0);
F(i,1,n) if(dep[i]&1) Ans+=(ll)f[1]*val[i]; else Ans-=(ll)f[1]*val[i];
Ans=(Ans%Mod+Mod)%Mod; Ans=Ans*n%Mod;
D2(1,0);
printf("%lld\n",Ans);
return 0;
}
【F】Pathwalks
题意：
给定一个有向图，边有边权。
问最长的路径，满足条件：边权逐个严格增加，并且边的顺序是读入时的顺序。
只要回答长度即可。
题解：
用\(dp[i][j]\)表示走到节点\(i\)，并且最后的边权为\(j\)时的最长路径长度。
有转移：\(dp[i][j]=max(dp[k][l])+1,(l\leq k\to i)\)。
但是还要边的顺序是读入时的顺序。
那可以边读入边转移：读入\(u\to v=w\)时，可以转移\(dp[v][w]=max(dp[u][l])+1,(l\leq w)\)。
但是dp[i][j]存储的状态太多了，而且处理最大值也很吃力。
但是发现能转移的状态很少，而最大值是一个区间。
于是用动态开点的线段树解决这个问题。不需要离散化。
【也可以树状数组，因为求得是前缀】
#include<bits/stdc++.h>
#define F(i,a,b) for(int i=a;i<=(b);++i)
using namespace std; int n,m,Ans;
int a[100001],b[100001];
int u[100001],v[100001],w[100001];
int f[100001]; int dat[8000001],ls[8000001],rs[8000001],cnt; int Maxi(int rt,int l,int r,int a,int b){
if(a>b) return 0;
if(r<a||b<l) return 0;
if(a<=l&&r<=b) return dat[rt];
if(!ls[rt]) ls[rt]=++cnt;
if(!rs[rt]) rs[rt]=++cnt;
int mid=l+r>>1;
return max(Maxi(ls[rt],l,mid,a,b),Maxi(rs[rt],mid+1,r,a,b));
} void Ins(int rt,int l,int r,int p,int x){
if(l==r) {dat[rt]=x; return;}
if(!ls[rt]) ls[rt]=++cnt;
if(!rs[rt]) rs[rt]=++cnt;
int mid=l+r>>1;
if(p<=mid) Ins(ls[rt],l,mid,p,x);
else Ins(rs[rt],mid+1,r,p,x);
dat[rt]=max(dat[ls[rt]],dat[rs[rt]]);
} int main(){
scanf("%d%d",&n,&m); cnt=n;
F(i,1,m) scanf("%d%d%d",u+i,v+i,w+i), ++w[i];
F(i,1,m){
f[i]=Maxi(u[i],1,100001,1,w[i]-1)+1;
Ins(v[i],1,100001,w[i],f[i]);
}
F(i,1,m) Ans=max(Ans,f[i]);
printf("%d",Ans);
return 0;
}
