Codeforces Round #562 (Div. 2)

蔚落 2021-10-29 17:50 270阅读 0赞

A. Circle Metro

题意：有两条线路线路，一条是正着走的，一条是倒着走的，一个人在第一条，一个人在第二条，给你两个人的起点和终点，问你是否能相遇。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

B. Pairs

题意：给你n对数ai和bi，问你是否存在两个数x，y使得在每一对数中至少出现一个x，或者一个y。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstring>
    #include<cmath>
    #include<cstdlib>
    #include<cstdio>
    #include<algorithm>
    #include<string>
    #include<map>
    #include<queue>
    #include<vector>
    #include<stack>
    #define ll long long
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    #define rep(i,a,b) for(int i=a;i<=b;i++)
    using namespace std;
    const int maxn=201010;
    int n,m,k,len=0,x,y,a[301010];
    map<int,map<int,int> > mp;
    struct node{
        int id,c;
    }p[301010];
    ll rd()
    {
        ll x=0,f=1;char ch=getchar();
        while(ch<'0'||ch>'9'){
         if(ch=='-')f=-1;ch=getchar();}
        while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
        return x*f;
    }
    bool cmp(node a,node b)
    {
        return a.c<b.c;
    }
    int init()
    {
        n=rd();m=rd();
        rep(i,1,m)
        {
            scanf("%d%d",&x,&y);
            a[x]++;
            a[y]++;
            mp[x][y]+=1;
            mp[y][x]+=1;
        }
        rep(i,1,n)
        {
            if(a[i]>0)
            {
                p[++len].id=i;
                p[len].c=a[i];
            }
        }
        sort(p+1,p+1+len,cmp);
    //    rep(i,1,len)
    //    {
    //        printf("%d %d\n",p[i].id,p[i].c);
    //    }
        rep(i,1,len)
        {
            for(int j=len;j>i;j--)
            {
                if(p[i].c+p[j].c>=m)
                {
                    //printf("i=%d j=%d\n",p[i].id,p[3].id);
                    //printf("c=%d c=%d\n",p[i].c,p[3].c);
                    if(p[i].c+p[j].c-mp[p[i].id][p[j].id]>=m)
                    {
                        //printf("%d %d\n",p[i].id,p[j].id);
                        return 1;    
                    }    
                }
                else break; 
            }
        }
        return 0;
    }
    void work()
    {
        
    }
    int main()
    {
        if(init()) printf("YES\n");
        else printf("NO\n");
        work();
    }

C. Increasing by Modulo

题意：给你n个数，每次可以是一些数字加1并取余m，求最小的操作次数使数列非递减。

思路：二分操作次数即可

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstring>
    #include<cmath>
    #include<cstdlib>
    #include<cstdio>
    #include<algorithm>
    #include<string>
    #include<map>
    #include<queue>
    #include<vector>
    #include<stack>
    #define ll long long
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    #define rep(i,a,b) for(int i=a;i<=b;i++)
    using namespace std;
    const int maxn=201010;
    int n,m,k,len=0,x,y,a[301010],b[301010];
    ll rd()
    {
        ll x=0,f=1;char ch=getchar();
        while(ch<'0'||ch>'9'){
         if(ch=='-')f=-1;ch=getchar();}
        while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
        return x*f;
    }
    void init()
    {
        n=rd();m=rd();
        rep(i,1,n) a[i]=rd();
    }
    bool check(int x)
    {
        for(int i=1;i<=n;i++)
        {
            if(b[i]<b[i-1])
            {
                if(b[i]+x>=b[i-1]) b[i]=b[i-1];
            }
            else{
                if((b[i]+x)%m>=b[i-1]&&(b[i]+x)>=m) b[i]=b[i-1];
            }
            //if(x==0) printf("%d %d\n",i,b[i]);
            if(b[i]<b[i-1]) return 1;
        }
        return 0;
    }
    void work()
    {
        int ans=0,l=0,r=m;
        while(l<=r)
        {
            //printf("%d %d\n",l,r);
            rep(i,1,n) b[i]=a[i];
            int mid=(l+r)>>1;
            if(check(mid)) 
            {
                l=mid+1; 
            }
            else 
            {
                r=mid-1;
                ans=mid;
            }
        }
        printf("%d\n",ans);
    }
    int main()
    {
        init();
        work();
    }

D. Good Triple

题意：给你一个字符串，问你存在Sn=Sn+k=Sn+2\*k 的区间数量是多少

思路：猜测，当长度大于20时必定存在上述的式子，所以20以下直接暴力即可

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstring>
    #include<cmath>
    #include<cstdlib>
    #include<cstdio>
    #include<algorithm>
    #include<string>
    #include<map>
    #include<queue>
    #include<vector>
    #include<stack>
    #define ll long long
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    #define rep(i,a,b) for(int i=a;i<=b;i++)
    using namespace std;
    const int maxn=201010;
    ll ans;
    char s[301010];
    int f[301010],l;
    ll rd()
    {
        ll x=0,f=1;char ch=getchar();
        while(ch<'0'||ch>'9'){
         if(ch=='-')f=-1;ch=getchar();}
        while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
        return x*f;
    }
    void init()
    {
        scanf("%s",s);
        l=strlen(s);
        for(int i=0;i<=l;i++)
           f[i]=101010100;
        for(int i=0;i<l;i++)
        {
            for(int j=1;j<=4000;j++)
                if(i+2*j<l)
                {
                    if(s[i]==s[i+j]&&s[i+j]==s[i+2*j])
                    {
                        f[i]=i+2*j;
                        break;
                    }
                }
        }
        for(int i=l-1;i>=0;i--)
        {
            f[i]=min(f[i+1],f[i]);
            //printf("%d\n",f[i]);
        }
        for(int i=0;i<l;i++)
        {
            if(f[i]!=101010100)ans+=(l-f[i]);
        }
        printf("%lld\n",ans);
    }
    void work()
    {
        
    }
    int main()
    {
        init();
        work();
    }

E. And Reachability

题意：![1524735-20190627215033395-1726489544.png][]

思路：dp\[i\]\[j\]表示第i位，&1<<j！=0  最近的那个数是多少（倒着更新）

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    #define rep(i,a,b) for(int i=a;i<=b;i++)
    #define dep(i,a,b) for(int i=b;i>=a;i--)
    using namespace std;
    #define ll long long
    const int N=3e5+5;
    const int M=20;
    int n,m,q,sum,a[N],dp[N][25],last[N],x,y,flag;
    ll rd()
    {
        ll x=0,f=1;char ch=getchar();
        while(ch<'0'||ch>'9'){
         if(ch=='-')f=-1;ch=getchar();}
        while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
        return x*f;
    }
    int main()
    {
        n=rd();m=rd();
        rep(i,1,n) a[i]=rd();
        rep(i,0,M) dp[n+1][i]=n+1,last[i]=n+1;
        dep(i,1,n)
        {
            rep(j,0,M) dp[i][j]=n+1;
            rep(j,0,M) 
               if((a[i]&(1<<j))!=0&&last[j]!=0)
               {
                   rep(k,0,M) dp[i][k]=min(dp[last[j]][k],dp[i][k]);    
               }    
            rep(j,0,M) if((a[i]&(1<<j))!=0) last[j]=i,dp[i][j]=i;
        } 
        rep(i,1,m)
        {
            x=rd();y=rd();flag=0;
            rep(j,0,M) 
                if((a[y]&(1<<j))!=0&&dp[x][j]<=y)
                {
                    flag=1;
                    break;
                 } 
            if(flag) printf("Shi\n");
            else printf("Fou\n");
        }
    }

转载于:https://www.cnblogs.com/The-Pines-of-Star/p/11099908.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211029/4c7b68aea5b24ad5873516ebe931c749.png
[1524735-20190627215033395-1726489544.png]: /images/20211029/fe4758aeb2f144b3b6e6c251dde499ea.png