For XeniaF

(☆▽☆)

CF1553总结

发布于 2021-09-07 | 分类于 考试总结 | 19分钟 | 3622字数

CF1553总结

前言

CF1553 是我打的第一场 CF ，当时也没有写总结，现在来补一下。

A. Digits Sum

签到题。

要求 s(x+1)<s(x)s(x+1)<s(x) ，什么情况 s(x+1)s(x+1) 会小于 s(x)s(x) 呢，显然是 99 和 1010 的情况。这里值得注意的是，要用 (n+1)/10(n+1)/10 ，是求 s(x+1)s(x+1) ！如果此时 x=9x=9 ，也是属于一种的！

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll t,n;
 
inline ll read(){
    ll x=0,f=0;char c=getchar();
    while(!isdigit(c))  f|=c=='-',c=getchar();
    while(isdigit(c))   x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return f?-x:x;
}
 
int main(){
    t=read();
    for(register int i=1;i<=t;++i){
        n=read();
        printf("%lld\n",(n+1)/10);
    }
    return 0;
}

B. Reverse String

这个题没写，还没来得及补。据说暴力就可以过（？

C. Penalty

题意有点小绕，理解了题意就是大水题。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll t,lenc,o[20],z[20],fiks[20],fikt[20],f[20][3];
ll pre[20],ans;
char c[20];

inline ll read(){
    ll x=0,f=0;char c=getchar();
    while(!isdigit(c))  f|=c=='-',c=getchar();
    while(isdigit(c))   x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return f?-x:x;
}

inline void dfs(ll x,ll f,ll s){
    if(x>lenc){
        ans=min(ans,lenc);
        return;
    }
    ll df=o[x]+f;ll ds=z[x]+s;
    ll dkf=fikt[lenc]-fikt[x];ll dks=fiks[lenc]-fiks[x];
    ll dis=z[lenc]-z[x]+o[lenc]-o[x]+dkf+dks;
        if(o[x]+fikt[x]>z[x]+(10-x+1)/2||z[x]+fiks[x]>o[x]+(10-x)/2){
            ans=min(ans,x);
            return;
        }
    if(c[x-1]=='?')
        if(x&1)
            dfs(x+1,f+1,s),
            dfs(x+1,f,s);
        else
            dfs(x+1,f,s+1),
            dfs(x+1,f,s);
    else
        dfs(x+1,f,s);
}

int main(){
    t=read();
    for(register int ac=1;ac<=t;++ac){
        cin>>c;
        lenc=strlen(c);        
        
        for(register int i=0;i<lenc;++i){
            o[i+1]=o[i],z[i+1]=z[i],fikt[i+1]=fikt[i],fiks[i+1]=fiks[i];
            if(c[i]=='1'){
                if((i+1)&1)
                    o[i+1]=o[i]+1,z[i+1]=z[i];
                else
                    z[i+1]=z[i]+1,o[i+1]=o[i];
            } 
                
            else if(c[i]=='?'){
                if((i+1)&1)
                    fikt[i+1]=fikt[i]+1;
                else
                    fiks[i+1]=fiks[i]+1;
            }
                
        }
         cout<<endl;
        ans=0x3f3f3f3f;
        dfs(1,0,0);
        printf("%lld\n",ans);
        
    }
    return 0;
}

D. Backspace

很显然第一个字母要删也只是单个删，后面的都是自己和前面那个都要删。本来想着动态规划乱搞一波，后来想想貌似没有必要啊。

  • 动态规划：设 f[i][1/0]f[i][1/0] 表示 TT 中的字符 T[i]T[i] 是否在偶/奇数位置上出现过，o(n)o(n) 跑一遍，判断一下就好了。（因为 ii 和 i+1i+1 只有同奇偶才能将中间删完）

  • 贪心：遇到一个不匹配的字母就将它和它的后一位删掉。直到最后。正确性是因为既然能够搜索到这一个字母它和前一个字母一定隔着偶数个字母。

#include <bits/stdc++.h>
#define ll long long
#define maxn 200001
using namespace std;
ll t,lena,lenb;
ll f[maxn][2],pos,tmp;
char a[maxn],b[maxn];

int main(){
    cin>>t;
    for(register int ac=1;ac<=t;++ac){
        cin>>a>>b;
        lena=strlen(a);
        lenb=strlen(b);
        if(lena<lenb)   { printf("NO\n");continue; }
        if(lena==lenb&&strcmp(a,b)==0) { printf("YES\n");continue; }
        if(lena==lenb&&strcmp(a,b)!=0) { printf("NO\n");continue; }
        if((lena&1)==(lenb&1))  tmp=0;
        else                tmp=1;
        pos=0;
        for(register int i=tmp;i<lena;++i){
            if(a[i]!=b[pos]){
                ++i;
                continue;
            }
            else
                ++pos;
            if(pos==lenb)
                break;
        }
        if(pos==lenb)   { printf("YES\n"); }
        else            { printf("NO\n"); }
    }
    return 0;
}

E. Permutation Shift

  • 一个看起来正确其实是错的思路

    • 对于每一个数字 pip_i ，有且只有一个 kk ，使得位移之后 pip_i 与目标数组相同。不同的数字的 kk 未必相同，也未必不同。考虑记录一下不同的数字中有多少个数字拥有相同的 kk 。

    • 开一个桶，不断 ++sum[k] ，这个数组的意思是，在这个 kk 下，有多少个数不需要进行交换。然后 o(n)o(n) 扫一遍，满足条件的 kk 就保存到答案数组中。

    • 时间复杂度 o(n)o(n) 。

    这个算法其实是有问题的。

    为什么一定是判断 sum[k]+m−1≥ksum[k]+m-1 \ge k 呢？万一刚好可以两两互换呢？那岂不是还要判断吗？复杂度又上去了。。。

    #include <bits/stdc++.h>
#define ll long long
#define maxn 100001
using namespace std;
ll t,n,m;
ll a[maxn],c[maxn];
ll val[maxn];
ll ans[maxn];
ll k[maxn];

inline ll read(){
    ll x=0,f=0;char c=getchar();
    while(!isdigit(c))  f|=c=='-',c=getchar();
    while(isdigit(c))   x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return f?-x:x;
}

int main(){
    t=read();
    for(register int ac=1;ac<=t;++ac){
        n=read();m=read();
        for(register int i=1;i<=n;++i)
            a[i]=read(),val[a[i]]=i;
        for(register int i=1;i<=n;++i)
            if(i==val[i])
                ++k[0];
            else if(i>val[i])
                ++k[n-i+val[i]];
            else
                ++k[val[i]-i];
        for(register int i=0;i<n;++i)
            cout<<k[i]<<endl;
        for(register int i=0;i<n;++i)
            if(k[i]+m+1>=n)
                ans[++ans[0]]=i;
        printf("%lld ",ans[0]);
        for(register int i=1;i<=ans[0];++i)
            printf("%lld ",ans[i]);
        printf("\n");
        for(register int i=0;i<n;++i)
            k[i]=0,val[i+1]=0;
        ans[0]=0;
    }
    return 0;
}

  • 正解

    • 考虑范围。mm 的范围似乎很有特色。很显然每一个 kk 要使得至少 n3\frac{n}{3} 的数字依然在原来的位置没有变动。满足条件的 kk 一定不超过 33 。设 k1k_1 使得超过 n3\frac{n}{3} 的数满足了条件，k2k_2 也满足了 k3k_3 也满足了此时就涵盖了所有的数字了不可能出现 k4k_4 了。对于每一个数，有且只有一个 kk 使得它能够在移动之后不用交换就变成目标树组中的它。
    • 接着考虑如何快速判断 kk 的可行度。经典连边，原数列的 xx 和新数列中的 xx 连一条边，跑联通块即可。复杂度 o(3n)o(3n) 。

    有一些小小的细节问题。

    for(register int i=1;i<=n;++i)
	a[i]=read(),++k[(i+n-a[i])%n];

    (i+n−a[i])(i+n-a[i])%n 为对应的 kk 。

    for(register int j=1;j<=n;++j)
	add(j,a[(j+i-1)%n+1]),vit[a[j]]=0;

    这里的 (j+i−1)%n+1(j+i-1)\%n+1 原来应该是 (j+i)(j+i) ，即移动 kk 位前对应的位置。也就是将移动后的 kk ，与原来的 aa 数组对应的原来的位置相连。

    for(register int j=1;j<=n;++j)
	if(!vit[j])
		work(j);

    workwork 就是跑联通块。

    if(n-cnt<=m)
	as[++as[0]]=i;

    加入答案。完整代码。

    #include <bits/stdc++.h>
#define ll long long
#define maxn 300001
using namespace std;
ll t,n,m;
ll a[maxn];
ll k[maxn];
ll cnt;
ll as[maxn];
ll nxt[maxn];
ll vit[maxn];
ll hd[maxn];
ll tot;
struct Node{
    ll to,nx;
}e[maxn<<1];

inline ll read(){
    ll x=0,f=0;char c=getchar();
    while(!isdigit(c))  f|=c=='-',c=getchar();
    while(isdigit(c))   x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return f?-x:x;
}

inline void add(ll x,ll y){
    e[++tot].to=y;
    e[tot].nx=hd[x];
    hd[x]=tot;
}

inline void dfs(ll x){
    vit[x]=1;
    for(register int i=hd[x];i;i=e[i].nx)
        if(!vit[e[i].to])
            dfs(e[i].to);
}

inline void work(ll x){
    ++cnt;
    dfs(x);
}

int main(){
    t=read();
    for(register int ac=1;ac<=t;++ac){
        n=read();m=read();
        for(register int i=1;i<=n;++i)
            a[i]=read(),++k[(i+n-a[i])%n];
        as[0]=0;
        for(register int i=0;i<n;++i){
            if(k[i]<n-2*m)  continue;
            for(register int j=1;j<=n;++j)
                hd[j]=0;
            tot=0;
            for(register int j=1;j<=n;++j)
                add(j,a[(j+i-1)%n+1]),vit[a[j]]=0;
            cnt=0;
            for(register int j=1;j<=n;++j)
                if(!vit[j])
                    work(j);
            if(n-cnt<=m)
                as[++as[0]]=i;
        }
        printf("%lld ",as[0]);
        for(register int i=1;i<=as[0];++i)
            printf("%lld ",as[i]);
        printf("\n");
        
        for(register int i=0;i<=n;++i)
            k[i]=0;
    }
    return 0;
}

    附上一组卡了我 nn 久的数据：

    6 2
2 5 1 3 4 6

    答案是 00 。

F. Pairwise Modulo

最开始以为又是一堆乱七八糟的反演。其实就是推式子，用 BIT 优化一下。代码有点离谱，两个 BIT 结构体其实是可以变成一个的，当时调试程序的时候我以为这里有问题就改了。不管了。

具体推式子如下：

首先引入一个式子，设 x>yx>y ，则有：

\begin{equation} \begin{aligned} x\%y &= x- \llcorner x/y \lrcorner*y\\ y\%x &= y\\ x\%y+y\%x &= y+x-\llcorner x/y \lrcorner*y \end{aligned} \end{equation}

所以对于一个 ii ，有以下几个比较重要的变量：

  • sumsum ，保存 ii 以前的数的前缀和。（观察到无论是大的那一方 xx 还是小的一方 yy ，都要算它们的和）

    因此在最开始有：

    ans+=a[i]∗(i−1)+sumans+=a[i]*(i-1)+sum

    接下来考虑一下算后面那一堆讨厌的东西。

    因为 ansans 是继承型的，也就是说对于前面的一堆乱七八糟的我们可以放置不管，只要管 xx 都是 a[i]a[i] 和 yy 都是 a[i]a[i] 的情况。反正不管 xx 还是 yy 是 a[i]a[i] ，也就刚好对应了上面的式子：对于上面的式子，以 a[i]a[i] 为 xx 视角算一遍后面的东西，以a[i]a[i] 为 yy 的视角算一遍后面的东西。

    因此对于 y<a[i]y<a[i] 的所有 yy ，他们的总和已经保存在 dd 树状数组里了，直接减掉就好了。对于 y>a[i]y>a[i] ，枚举 yy 的倍数，并将 yy 的倍数在 dd 数组里面的值加上 yy 。方便后面的计算。

    在枚举的同时，不断减去 jj 到 j+a[i]−1j+a[i]-1 这一段存在的数的个数的和∗j*j ，因为这一段的答案都是 jj 。

    如果 a[i]=6a[i]=6 ，之前有一个 a[i]=3a[i]=3 ，在计算的时候会多算嘛。显然不会。具体为什么可以自己手动模拟一下。我比较懒，不太想写了。

    最后将 a[i]a[i] 加进保存个数的树状数组里面，方便以后的计算。

    #include <bits/stdc++.h>
#define maxn 2000000
#define mx 1e6+10
#define ll long long
using namespace std;
ll n,ans,cnt;
ll a;
struct BIT{
    ll tree[maxn<<2];

    inline void set(){
        memset(tree,0,sizeof(tree));
    }

    inline ll lowbit(ll x){
        return x&(-x);
    }

    inline void add(ll x,ll val){
        while(x<=mx){
            tree[x]+=val;
            x+=lowbit(x);
        }
    }

    inline ll query(ll x){
        ll res=0;
        while(x){
            res+=tree[x];
            x-=lowbit(x);
        }
        return res;
    }
}bit,tib;

inline ll read(){
    ll x=0,f=0;char c=getchar();
    while(!isdigit(c))  f|=c=='-',c=getchar();
    while(isdigit(c))   x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return f?-x:x;
}

int main(){
    n=read();
    bit.set();
    tib.set();
    for(register int i=1;i<=n;++i){
        a=read();
        ans+=a*(i-1)+cnt;
        cnt+=a;
        ans-=bit.query(a);
        for(register ll j=a;j+a<mx;j+=a){
            ans-=(tib.query(j+a-1)-tib.query(j-1))*j;
            bit.add(j,a);
        }
        tib.add(a,1);
        printf("%lld ",ans);
    }
    return 0;
}

CF1553G

在 10610^6 里面的数，最多由 99 个质数相乘。（这个很容易计算吧，这个貌似只有在开数组的时候可以用到）对于每个询问 axa_x 和 aya_y ，答案不可能超过 33 ，有以下三种可能：

  • 不用新建节点：说明 axa_x 和 aya_y 拥有共同质数，换句话来说，如果把每一个质数建立一个联通块，axa_x 和 aya_y 一定同时存在与某一个联通块之中。
  • 新建 11 个：说明对于任意一个节点新建一个节点可以使得他们在一个联通块中。在预处理中同时处理 ai+1a_i+1 的所有质因子，彼此连边，说明这些质因子可以通过新建一个节点彼此到达。
  • 新建 22 个：前面两种情况都不行，那就只能这种了呗

其实是因为如果 ax∗(ax+1)a_x*(a_x+1) 依然与 aya_y 不联通的话，一定与 ay∗(ay+1)a_y*(a_y+1) 联通（都是偶数嘛）所以答案不超过 22 。

程序也挺好写的，后面用了一个 setset 套 mapmap ，还挺巧妙的 ，可以判断一个数对是否已经存在。反正 mapmap 就是什么不行就找map

#include <bits/stdc++.h>
#define ll long long
#define maxn 200001
#define maxm 1000010
using namespace std;
ll n,m;
ll a[maxn];
ll x,y;
ll pos[maxm];
ll tmp[maxm];
ll num[maxn<<1];
ll fa[maxm];
ll mx;
ll isprime[maxn<<1][15];
ll prime[maxm];
set<pair<ll,ll> >q;

inline ll read(){
    ll x=0,f=0;char c=getchar();
    while(!isdigit(c))  f|=c=='-',c=getchar();
    while(isdigit(c))   x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return f?-x:x;
}

inline ll find(ll x) { return (x==fa[x])?x:fa[x]=find(fa[x]); }

inline void init(){
    prime[0]=prime[1]=1;
    for(register int i=2;i<=mx;++i){
        if(!prime[i]){
            for(register int j=i;j<=mx;j+=i){
                prime[j]=i;
                if(pos[j])
                    isprime[pos[j]][++num[pos[j]]]=i;
                if(tmp[j])
                    isprime[tmp[j]+n][++num[tmp[j]+n]]=i;
            }
        }
    }
}

int main(){
    n=read();m=read();
    for(register int i=1;i<=n;++i){
        a[i]=read();
        pos[a[i]]=i;
        tmp[a[i]+1]=i;
        mx=max(mx,a[i]+1);
    }
    for(register int i=1;i<=mx;++i)
        fa[i]=i;
    init();
    for(register int i=1;i<=n;++i)
        for(register int j=1;j<=num[i];++j)
            fa[find(a[i])]=find(isprime[i][j]);
    for(register int i=1;i<=n;++i){
        isprime[i+n][++num[i+n]]=a[i];
        for(register int j=1;j<=num[i+n];++j)
            for(register int k=j+1;k<=num[i+n];++k){
                ll dx=find(isprime[i+n][j]);
                ll dy=find(isprime[i+n][k]);
                if(dx>dy)   swap(dx,dy);
                if(dx!=dy)
                    q.insert(make_pair(dx,dy));
            }
    }
    for(register int i=1;i<=m;++i){
        x=read();y=read();
        x=find(a[x]);
        y=find(a[y]);
        if(x>y)     swap(x,y);
        if(x==y)    printf("0\n");
        else if(q.count(make_pair(x,y)))    printf("1\n");
        else        printf("2\n");
    }
    return 0;
}

总结

写的真长啊（对我来说已经很长了。第一次打 CF 经验不足导致了很多很多的问题，英语看不懂也是一大痛苦之处。总的来说，过度依赖他人的翻译，没看清题目耽误了大量时间。后面打 vp 的时候，写代码也不够细致，调式耽误了一点点时间，影响了 GG 的思考。改题的时候 EE 也历经艰难，有些不尽人意。

# 考试总结
【LGR-089】洛谷 8 月月赛 II总结 上一篇
P2485 [SDOI2011]计算器 下一篇
浏览数 次 | 访客数 人
Powered by Gridea ©2019 | Theme By HsxyHao
Powered by ？
0%