Codeforces Round 1515 解题报告

解题报告

---

完工了。

Codeforces Global Round 14考试总结：

赛时降智，只做出ABCD，实际上EF完全有实力做出来的/kk。

CF1515A Phoenix and Gold

大水题，由于数字互不相同，因此判一下全局是不是$x$，如果是则无解，否则肯定有解。

具体就随便交换一下前缀和为$x$的位置与任意位置就好了。

#include<stdio.h>
const int maxn=105;
int T,n,x,sum;
int a[maxn];
int main(){
    scanf("%d",&T);
    while(T--){
        sum=0;
        scanf("%d%d",&n,&x);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]),sum+=a[i];
        if(sum==x){
            puts("NO");
            continue;
        }
        puts("YES");
        int now=0,flg=0;
        for(int i=1;i<=n;i++){
            now+=a[i];
            if(now==x){
                flg=i;
                break;
            }
        }
        if(flg==0)
            for(int i=1;i<=n;i++)
                printf("%d ",a[i]);
        else{
            for(int i=1;i<=n;i++){
                if(i==flg+1)
                    printf("%d ",a[i-1]);
                else if(i==flg)
                    printf("%d ",a[i+1]);
                else printf("%d ",a[i]);
            }
        }
        puts("");
    }
    return 0;
}

CF1515B Phoenix and Puzzle

降智交了四五发才过/ll。

实际上就看cf上两个图上的正方形，发现能拼凑的正方形都是以这两个正方形为基础构造成的，那么平方数的$2$倍或$4$倍的数都合法。

#include<stdio.h>
#include<math.h>
int T,n;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        if(n&1){
            puts("NO");
            continue;
        }
        int k=sqrt(n/2);
        if(k*k==n/2)
            puts("YES");
        else if(n%4==0){
            int fst=sqrt(n/4);
            if(fst*fst==n/4)
                puts("YES");
            else puts("NO");
        }
        else puts("NO");
    }
    return 0;
}

CF1515C Phoenix and Towers

水题，从大到小枚举每个数，每次放最小的集合里就好了。

#include<stdio.h>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=100005;
int T,n,m,x;
int ans[maxn];
pair<int,int>h[maxn];
priority_queue< pair<int,int> >q;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d",&n,&m,&x);
        for(int i=1;i<=n;i++)
            scanf("%d",&h[i].first),h[i].second=i;
        sort(h+1,h+1+n);
        for(int i=1;i<=m;i++)
            q.push(make_pair(0,i));
        for(int i=n;i>=1;i--){
            int x=h[i].first-q.top().first,y=q.top().second;
            q.pop(),q.push(make_pair(-x,y));
            ans[h[i].second]=y;
        }
        int maxx=q.top().first,minn=q.top().first;
        while(!q.empty())
            q.pop(),minn=q.top().first;
        if(minn-maxx>x){
            puts("NO");
            continue;
        }
        puts("YES");
        for(int i=1;i<=n;i++)
            printf("%d%c",ans[i],i==n? '\n':' ');
    }
    return 0;
}

CF1515D Phoenix and Socks

首先不妨设$l\leqslant r$，然后一定也只需要消耗$\frac{r-l}{2}$的代价将右袜子变成左袜子，然后再判断一下左袜子可以直接匹配的右袜子和变成右袜子的左袜子可以匹配的数量。

#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=200005;
int T,n,l,r;
int a[maxn],tot[maxn];
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d",&n,&l,&r);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        if(l>r){
            reverse(a+1,a+1+n);
            swap(l,r);
        }
        for(int i=l+1;i<=n;i++)
            tot[a[i]]++;
        int need,ok=0;
        for(int i=1;i<=l;i++){
            if(tot[a[i]]>0)
                tot[a[i]]--,ok++;
            else need++;
        }
        int used=0;
        for(int i=1;i<=n;i++)
            if(tot[i]>1)
                used+=tot[i]/2;
        used=min(used,(n-l*2)/2);
        for(int i=1;i<=n;i++)
            tot[i]=0;
        printf("%d\n",(r-l)/2+(n-2*used-2*ok)/2);
    }
    return 0;
}

CF1515E Phoenix and Computers

首先考虑不通过自动开机打开一个长度为$len$的序列有多少种方式：

如果第一个打开第一台，那么之后必须按顺序打开，共${k-1\choose 0}$种方式；如果第一个打开第二台，那么第二台后面的电脑必须按顺序，而第一台可以任意时候打开，共${k-1\choose 1}$；如果第一个打开第$i$台，第$i$台前的必须从后到前，第$i$台后的必须从前到后，因此共${k-1\choose i}$种方式。

因此总方式共$\sum_{i=0}^{k-1}{k-1\choose i}=2^{k-1}$。

设$f_{i,j}$为长度为$i$的序列经过$j$次开机全部开机的方案数，然后递推式很容易推出来就是

$$f_{len+j+1,i+j}\leftarrow f_{len,i}\times {i+j\choose j}\times 2^{j-1}$$

答案就是$\sum_{i=1}^n f_{n+1,i}$

#include<stdio.h>
const int maxn=405;
int n,mod,ans;
int f[maxn][maxn],c[maxn][maxn],pow[maxn];
inline int plus(int x){
    return x>=mod? x-mod:x;
}
int main(){
    scanf("%d%d",&n,&mod);
    for(int i=0;i<=n;i++){
        c[i][0]=c[i][i]=1;
        for(int j=1;j<i;j++)
            c[i][j]=plus(c[i-1][j]+c[i-1][j-1]);
    }
    pow[0]=1;
    for(int i=1;i<=n;i++)
        pow[i]=2ll*pow[i-1]%mod;
    f[0][0]=1;
    for(int len=0;len<n;len++)
        for(int i=0;i<=len;i++)
            for(int j=1;len+j<=n;j++)
                f[len+j+1][i+j]=plus(f[len+j+1][i+j]+1ll*f[len][i]*c[i+j][j]%mod*pow[j-1]%mod);
    for(int i=1;i<=n;i++)
        ans=plus(ans+f[n+1][i]);
    printf("%d\n",ans);
    return 0;
}

CF1515F Phoenix and Earthquake

考虑猜一个结论：只要沥青总吨数$total$大于等于$(n-1)X$，那么一定可以使图联通。

证明：考虑不断找到一条连接两个沥青总吨数大于等于$X$的边进行修建。
若已经修建了$e$条边后无法找到下一条边，那么可知$total-eX<X+(n-e-2)X$（左边是当前沥青总吨数，右边是考虑任意一条边两端的沥青总吨数加上其他连通块的沥青总吨数）。
因此$taotal<(n-1)X$，推出矛盾。

不难发现取该图的任意一个$\text{dfs}$树仍然满足条件，因此我们将图上的问题转换到了树上，而且易知树上每条边都要用到。

我们在树上进行$\text{dfs}$，$x$遍历完儿子$y$后，讨论连接$(x,y)$的边什么时候加入答案序列：如果$x$所在的连通块与$y$所在的连通块沥青总吨数大于等于$X$，那么可以直接连，否则可以放在最后连，用一个类似双端队列的东西就可以维护了。

由于每次可以直接把连接后儿子的沥青总吨数加到父亲上（没有连接的儿子不会影响父亲向上的连边），因此并不需要用并查集维护连通块的沥青总数。

时间复杂度：$O(n+m)$。

#include<stdio.h>
const int maxn=300005,maxm=maxn<<1;
int n,m,X,e,cnt1,cnt2;
int start[maxn],to[maxm],then[maxm],id[maxm],ans[maxn],a[maxn],vis[maxn];
long long sum;
inline void add(int x,int y,int i){
    then[++e]=start[x],start[x]=e,to[e]=y,id[e]=i;
}
void dfs(int x){
    vis[x]=1;
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(vis[y])
            continue;
        dfs(y);
        if(a[x]+a[y]>=X)
            a[x]+=a[y]-X,ans[++cnt1]=id[i];
        else ans[--cnt2]=id[i];
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&X);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),sum+=a[i];
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y,i),add(y,x,i);
    }
    if(sum<1ll*(n-1)*X){
        puts("NO");
        return 0;
    }
    puts("YES");
    cnt1=0,cnt2=n;
    dfs(1);
    for(int i=1;i<=n-1;i++)
        printf("%d\n",ans[i]);
    return 0;
}

CF1515G Phoenix and Odometers

有点神仙的题目呀。

考虑回路一定在这个点的强联通分量内，因此只需要考虑每个强联通分量的答案。

考虑一条一个回路重复$t$次的路径是不会对答案造成影响的，因此发现如果存在答案，一定有一种答案经过整个强连通分量。

如果只有两个环（长度分别为$a,b$）的话很好考虑，因为这两个环很显然可以组成任意$\gcd(a,b)$的倍数的路径长度，而对于多个环则表示的一定是所有这些环长度的$\gcd$的倍数的路径长度。

现在我们的目标就是求出一个强连通分量中所有环的$\gcd$。

有一个结论就是它的$\text{dfs}$树上仅包含一条非树边的环一定可以表示出所有环，那么我们直接在$\text{dfs}$树上遍历就可以求出整个强连通分量的$\gcd$了。

时间复杂度：$O((n+m+q)\log V)$

#include<stdio.h>
#define int long long
const int maxn=200005,maxm=200005;
int n,m,dfns,e,Q,top,scc;
int start[maxn],to[maxm],then[maxm],worth[maxm],g[maxn],bel[maxn],dfn[maxn],low[maxn],stk[maxn],vis[maxn],dis[maxn];
inline void add(int x,int y,int z){
    then[++e]=start[x],start[x]=e,to[e]=y,worth[e]=z;
}
inline int min(int a,int b){
    return a<b? a:b;
}
inline int abs(int x){
    return x<0? -x:x;
}
int gcd(int a,int b){
    return b==0? a:gcd(b,a%b);
}
void tarjan(int x){
    dfn[x]=low[x]=++dfns,stk[++top]=x,vis[x]=1;
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(dfn[y]==0){
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(vis[y])
            low[x]=min(low[x],dfn[y]);
    }
    if(dfn[x]==low[x]){
        scc++;
        for(int y=0;y!=x;)
            y=stk[top--],bel[y]=scc,vis[y]=0;
    }
}
void dfs(int x){
    vis[x]=1;
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(bel[y]!=bel[x])
            continue;
        if(vis[y])
            g[bel[x]]=gcd(g[bel[x]],abs(dis[y]-dis[x]-worth[i]));
        else dis[y]=dis[x]+worth[i],dfs(y);
    }
}
signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%lld%lld%lld",&x,&y,&z);
        add(x,y,z);
    }
    for(int i=1;i<=n;i++)
        if(dfn[i]==0)
            tarjan(i);
    for(int i=1;i<=n;i++)
        vis[i]=0;
    for(int i=1;i<=n;i++)
        if(vis[i]==0)
            dfs(i);
    scanf("%lld",&Q);
    while(Q--){
        int x,s,t;
        scanf("%lld%lld%lld",&x,&s,&t);
        if(g[bel[x]]==0)
            puts(s==0? "YES":"NO");
        else puts(s%gcd(t,g[bel[x]])==0? "YES":"NO");
    }
    return 0;
}

CF1515H Phoenix and Bits

CF*3500的ds题的第一篇题解，好诶！

跑的还挺快，目前cf rk3。

神仙ds，类似平衡树的trie高阶操作。

首先考虑只有$3,4$操作应该怎么维护：$3$操作就直接找到当前结点，交换当前结点的左右儿子然后打上$lazy$标记，$4$操作就是像在线段树上一样把询问分配到$\log$个区间查询。

然后考虑$1$与$2$操作。

由于每次递归找结点太慢，因此可以直接用一个split操作把这些节点“取下来”，然后修改完后再用一个$merge$操作“并上去”。

因为最高位为$20$，所以不难发现$[\text{and},x,y,z]$操作等价于全部取反，$\text{or}$一下$z\ \text{xor}\ 2^{20}$，然后再次全部取反，由于全部取反等价于异或$2^{20}$，所以$\text{and}$可以直接用$\text{or},\text{xor}$代替。

然后是$\text{or}$操作，发现在某一位$\text{or}\ 1$是等价于对它的左儿子$\text{xor}$当前这位，然后合并其左儿子至右儿子的，因此我们递归处理就好了，注意如果可以直接用$\text{xor}$代替$\text{or}$的地方需要直接修改。（即需要修改的二进制位与当前子树的$\text{or}$没有重复的二进制位）

容易知道每次耗费$\log$时间的操作一定会永久删除一个trie树上一个可能的结点，因此时间复杂度为$O((n+m)\log^2 C)$

#include<stdio.h>
const int maxn=200005,maxk=maxn*40;
int n,q,k,rt,cnt;
int lc[maxk],rc[maxk],lazy[maxk],Vand[maxk],Vor[maxk],res[maxk];
inline void swp(int &a,int &b){
    a+=b,b=a-b,a-=b;
}
inline void pushup(int now){
    Vand[now]=Vand[lc[now]]|Vand[rc[now]];
    Vor[now]=Vor[lc[now]]|Vor[rc[now]];
    res[now]=res[lc[now]]+res[rc[now]];
}
void insert(int dep,int &now,int val){
    if(now==0)
        now=++cnt;
    if(dep==0){
        Vand[now]=(k^val),Vor[now]=val,res[now]=1;
        return ;
    }
    if(((val>>(dep-1))&1)==0)
        insert(dep-1,lc[now],val);
    else insert(dep-1,rc[now],val);
    pushup(now);
}
void getxor(int dep,int now,int val){
    if(now==0)
        return ;
    if((val>>(dep-1))&1)
        swp(lc[now],rc[now]);
    int Va=Vand[now],Vo=Vor[now];
    Vand[now]=(Va&(k^val))|(Vo&val);
    Vor[now]=(Vo&(k^val))|(Va&val);
    lazy[now]^=val;
}
void pushdown(int dep,int now){
    if(lazy[now]==0)
        return ;
    getxor(dep-1,lc[now],lazy[now]),getxor(dep-1,rc[now],lazy[now]);
    lazy[now]=0;
}
void split(int dep,int &x,int &y,int l,int r,int L,int R){
    if(x==0||R<l||r<L){
        y=0;
        return ;
    }
    if(L<=l&&r<=R){
        y=x,x=0;
        return ;
    }
    int mid=(l+r)>>1;
    pushdown(dep,x),y=++cnt;
    split(dep-1,lc[x],lc[y],l,mid,L,R),split(dep-1,rc[x],rc[y],mid+1,r,L,R);
    pushup(x),pushup(y);
}
void merge(int dep,int &x,int &y){
    if(x==0){
        x=y;
        return ;
    }
    if(y==0||dep==0)
        return ;
    pushdown(dep,x),pushdown(dep,y);
    merge(dep-1,lc[x],lc[y]),merge(dep-1,rc[x],rc[y]);
    pushup(x);
}
void getor(int dep,int now,int val){
    if(now==0)
        return ;
    int add=val&Vand[now]; 
    if((add&Vor[now])==0){
        getxor(dep,now,add);
        return ;
    }
    pushdown(dep,now);
    if((val>>(dep-1))&1){
        getxor(dep-1,lc[now],1<<(dep-1));
        merge(dep-1,rc[now],lc[now]);
        lc[now]=0;
    }
    getor(dep-1,lc[now],val),getor(dep-1,rc[now],val);
    pushup(now);
}
int query(int dep,int now,int l,int r,int L,int R){
    if(now==0||R<l||r<L)
        return 0;
    if(L<=l&&r<=R)
        return res[now];
    int mid=(l+r)>>1;
    pushdown(dep,now);
    return query(dep-1,lc[now],l,mid,L,R)+query(dep-1,rc[now],mid+1,r,L,R);
}
void read(int &x){
    x=0;
    char c=getchar();
    for(;c<'0'||c>'9';c=getchar());
    for(;c>='0'&&c<='9';c=getchar())
        x=x*10+c-48;
}
int main(){
    scanf("%d%d",&n,&q),k=(1<<20)-1;
    for(int i=1;i<=n;i++){
        int x;
        read(x);
        insert(20,rt,x);
    }
    for(int i=1;i<=q;i++){
        int t,x,y,z,now;
        read(t);
        if(t==4){
            read(x),read(y);
            printf("%d\n",query(20,rt,0,k,x,y));
            continue;
        }
        read(x),read(y),read(z);
        split(20,rt,now,0,k,x,y);
        if(t==1)
            getxor(20,now,k),getor(20,now,z^k),getxor(20,now,k);
        if(t==2)
            getor(20,now,z);
        if(t==3)
            getxor(20,now,z);
        merge(20,rt,now);
    }
    return 0;
}

CF1515I Phoenix and Diamonds

似乎是你谷首杀，针不戳。

神奇的题目，感觉没有CF*3400评分这么夸张，不过这数据确实强。

由于钻石种类已经给定，因此我们可以知道拿钻石的优先级。

发现处理询问的复杂度与$c$总得有点关系，看$c$的数据范围就大胆猜想复杂度要带$\log C$，那么考虑如何每次至少把$c$除二。

设$c$的最高位为$\omega$，对于第$\omega$位，设一个钻石是“轻的”当且仅当其重量小于$2^{\omega-1}$，否则如果它的重量小于$2^{omega}$，那么它是“重的”，一个很显然的结论就是在最高位不变的情况下不能取多于一个“重的”钻石。

自然而然地设$lightv_{l,r,k}/lightw_{l,r,k}$表示对于第$k$位，$l$到$r$“轻的”钻石价值和与重量和，$extra_{l,r,k}$表示对于第$k$位，$l$到$r$“轻的”钻石重量加上一个最小的“重的”钻石的重量之和。

状态是$O(n^2\log c)$的，不好存储，考虑上线段树，将上面的区间$[l,r]$改为其对应线段树上的结点$now$，那么很容易写出一个$\log c$的$\text{pushup}$来动态维护这三个数组。

查询部分，我们就先判掉叶子结点的情况，然后考虑重钻石与轻钻石都可以取走的情况，然后再判一判是不是只能取轻钻石，如果都不是的话就递归两个儿子处理。

记得动态维护当前$c$的最高位$\omega$。

时间复杂度：$O((n+q)\log n\log c)$。（复杂度不太会证/kel）

#include<stdio.h>
#include<algorithm>
#define inf 1000000000000000001
using namespace std;
const int maxn=200005,maxk=19,maxt=maxn<<2;
int n,m,omega;
int pos[maxn],id[maxn],w[maxn],v[maxn],lc[maxt],rc[maxt];
long long c;
long long a[maxn],lightv[maxt][maxk],extra[maxt][maxk],lightw[maxt][maxk];
inline int cmp(int x,int y){
    return v[x]>v[y]||(v[x]==v[y]&&w[x]<w[y]);
}
inline void getval(int now,int p){
    for(int i=1;i<=18;i++){
        lightv[now][i]=lightw[now][i]=0,extra[now][i]=inf;
        if(w[p]<(1<<(i-1)))
            lightv[now][i]=a[p]*v[p],lightw[now][i]=a[p]*w[p];
        else if(w[p]<(1<<i)&&a[p]>0)
            extra[now][i]=w[p];
    }
}
inline void pushup(int now){
    for(int i=1;i<=18;i++){
        lightv[now][i]=lightv[lc[now]][i]+lightv[rc[now]][i];
        lightw[now][i]=lightw[lc[now]][i]+lightw[rc[now]][i];
        extra[now][i]=min(extra[lc[now]][i],lightw[lc[now]][i]+extra[rc[now]][i]);
    }
}
void build(int l,int r,int now){
    if(l==r){
        getval(now,id[l]);
        return ;
    }
    int mid=(l+r)>>1;
    lc[now]=now<<1,rc[now]=now<<1|1;
    build(l,mid,lc[now]),build(mid+1,r,rc[now]);
    pushup(now);
}
void update(int l,int r,int now,int pos){
    if(l==r){
        getval(now,id[l]);
        return ;
    }
    int mid=(l+r)>>1;
    if(pos<=mid)
        update(l,mid,lc[now],pos);
    else update(mid+1,r,rc[now],pos);
    pushup(now);
}
void calc(){
    while(omega>1&&(1<<((omega-1)-1))>c)
        omega--;
}
long long query(int l,int r,int now){
    if(l==r){
        long long num=min(a[id[l]],c/w[id[l]]);
        c-=num*w[id[l]],calc();
        return num*v[id[l]];
    }
    if(lightw[now][omega]<=c){
        long long res=lightv[now][omega];
        c-=lightw[now][omega],calc();
        return res;
    }
    if(lightw[now][omega-1]<=c&&c<extra[now][omega-1]){
        long long res=lightv[now][omega-1];
        c-=lightw[now][omega-1],calc();
        return res;
    }
    int mid=(l+r)>>1;
    return query(l,mid,lc[now])+query(mid+1,r,rc[now]);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%lld%d%d",&a[i],&w[i],&v[i]),id[i]=i;
    sort(id+1,id+1+n,cmp);
    for(int i=1;i<=n;i++)
        pos[id[i]]=i;
    build(1,n,1);
    for(int i=1;i<=m;i++){
        int t,k,d;
        scanf("%d",&t);
        if(t==1||t==2){
            scanf("%d%d",&k,&d);
            a[d]+=(t==1? k:-k),update(1,n,1,pos[d]);
        }
        if(t==3){
            scanf("%lld",&c),omega=18,calc();
            printf("%lld\n",query(1,n,1));
        }
    }
    return 0;
}//