• The 2021 ICPC Asia Shenyang Regional Contest补题


    vp打铁了,感觉差距很大,若是icpc出不了线,还是线下举行的话,就没比赛打了,情况已经很糟糕了,好好加油吧,不要放弃。

    E. Edward Gaming, the Champion

    统计edgnb的数量,使用substr函数截取字符串

    #include
    #define int long long
    #define endl '\n'
    #define For(i,a,b) for(i=(a);i<=(b);++i)
    #define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
    using namespace std;
    const int N=7e5+5;
    const int inf=1e18;
    const int mod=1e9+7;
    int fac[40];
    int qpow(int a,int b){
        int res=1;
        while(b)
        {
            if(b&1) res=res*a%mod;
            a=a*a%mod;
            b>>=1;
        }
        return res;
    }
    int getinv(int x){return qpow(x,mod-2);}
    int C(int a,int b)
    {
        return (fac[a]*getinv(fac[a-b])%mod)*getinv(fac[b])%mod;
    }
    int n;
    string s;
    void solve()
    {
        cin>>s;
        n=s.length();
        s=" "+s;
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            if(s[i]=='e')
            {
                if(s.substr(i,5)=="edgnb")
                    ans++;
            }
        }
        cout<<ans<<endl;
    }
    signed main()
    {
        //ios;
        //int T;cin>>T;
        //while(T--)
            solve();
        return 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51

    B. Bitwise Exclusive-OR Sequence

    对于每个二进制位,都作为一个图进行染色,为使得和最小的,因此染色的一条链中0和1数目较小的为1,累加进入ans

    #include
    //#define int long long
    #define endl '\n'
    #define For(i,a,b) for(i=(a);i<=(b);++i)
    #define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
    using namespace std;
    const int N=7e5+5;
    const int inf=1e18;
    const int mod=1e9+7;
    /*
    int fac[40];
    int qpow(int a,int b){
        int res=1;
        while(b)
        {
            if(b&1) res=res*a%mod;
            a=a*a%mod;
            b>>=1;
        }
        return res;
    }
    int getinv(int x){return qpow(x,mod-2);}
    int C(int a,int b)
    {
        return (fac[a]*getinv(fac[a-b])%mod)*getinv(fac[b])%mod;
    }*/
    int n,m,cnt,head[N],tmp[2];
    bool vis[N],col[N],flag;
    struct node
    {
        int to,nxt,w;
    }e[N*2];
    void add(int from,int to,int w)
    {
        e[++cnt].to=to;
        e[cnt].w=w;
        e[cnt].nxt=head[from];
        head[from]=cnt;
    }
    void dfs(int u,int pre,int x,int se)
    {
        tmp[se]++,vis[u]=1,col[u]=se;
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].to,w=e[i].w;
            if(v==pre) continue;
            int g=((w>>x)&1)?(!se):se;
            if(vis[v])
            {
                if(col[v]!=g)
                {
                    cout<<-1<<endl;exit(0);
                }
                else continue;
            }
            dfs(v,u,x,g);
        }
    }
    void solve()
    {
        cin>>n>>m;
        for(int i=1;i<=m;i++)
        {
            int u,v,w;cin>>u>>v>>w;
            add(u,v,w);add(v,u,w);
        }
        long long ans=0;
        for(int i=0;i<=30;i++)
        {
            tmp[0]=tmp[1]=0;
            for(int j=0;j<=n;j++) vis[j]=col[j]=0;
            for(int j=1;j<=n;j++)
            {
                if(!vis[j])
                    dfs(j,0,i,0);
                ans+=min(tmp[0],tmp[1])*pow(2,i);
                tmp[0]=tmp[1]=0;
            }
        }
        cout<<ans<<endl;
    }
    signed main()
    {
        ios;
        //int T;cin>>T;
        //while(T--)
            solve();
        return 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89

    F. Encoded Strings I

    利用unordered_mapmp; unordered_setse;两个容器一下省了好多时间,注意不能排序,不然会超时

    #include
    //#define int long long
    #define endl '\n'
    #define For(i,a,b) for(i=(a);i<=(b);++i)
    #define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
    using namespace std;
    const int N=7e5+5;
    const int inf=1e18;
    const int mod=1e9+7;
    /*
    int fac[40];
    int qpow(int a,int b){
        int res=1;
        while(b)
        {
            if(b&1) res=res*a%mod;
            a=a*a%mod;
            b>>=1;
        }
        return res;
    }
    int getinv(int x){return qpow(x,mod-2);}
    int C(int a,int b)
    {
        return (fac[a]*getinv(fac[a-b])%mod)*getinv(fac[b])%mod;
    }*/
    int n;
    string s;
    unordered_map<char,int>mp;
    unordered_set<char>se;
    void solve()
    {
        cin>>n>>s;
        s=" "+s;
        string tmp="",ans="";
        for(int i=1;i<=n;i++)
        {
            mp.clear();
            for(int j=1;j<=i;j++)
                mp[s[j]]=j;
            tmp="";
            for(int j=1;j<=i;j++)
            {
                int g=mp[s[j]];
                se.clear();
                for(int k=g+1;k<=i;k++)
                    se.insert(s[k]);
                char c=(char)('a'+se.size());
                tmp.append(1,c);
            }
            ans=max(tmp,ans);
        }
        cout<<ans<<endl;
    }
    signed main()
    {
        ios;
        //int T;cin>>T;
        //while(T--)
            solve();
        return 0;
    }
    
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64

    J. Luggage Lock

    思维还是太差了,看完一道题尽想着取模拟,虽然说也能找到一些细节,但没办法整体思考。
    思路:
    1.表面上能想到的东西。锁可向上转可向下转,9能到1,说明可对10进行取模操作。
    2.对连续四个按键操作的情况共有十种。1000,0100,0010,0001,1100,0110,0011,1110,0111,1111。
    3.想到这点便是关键,通过这是十种转动关系可向上转,向下转。共有20中新状态,便可想到队列、广搜。

    #include
    //#define int long long
    #define endl '\n'
    #define For(i,a,b) for(i=(a);i<=(b);++i)
    #define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
    using namespace std;
    const int N=7e5+5;
    const int inf=1e18;
    const int mod=1e9+7;
    /*
    int fac[40];
    int qpow(int a,int b){
        int res=1;
        while(b)
        {
            if(b&1) res=res*a%mod;
            a=a*a%mod;
            b>>=1;
        }
        return res;
    }
    int getinv(int x){return qpow(x,mod-2);}
    int C(int a,int b)
    {
        return (fac[a]*getinv(fac[a-b])%mod)*getinv(fac[b])%mod;
    }*/
    int n,ans[N];
    bool vis[N];
    string s[10]={"1000","0100","0010","0001","1100","0110","0011","1110","0111","1111"};
    queue<pair<string,int>>q;
    string spin(string ss,int x,int d)
    {
        string str=ss;
        for(int i=0;i<4;i++)
        {
            if(s[x][i]=='1')
            {
                str[i]=(str[i]-'0'+d+10)%10+'0';
            }
        }
        return str;
    }
    void init()
    {
        while(!q.empty()) q.pop();
        vis[0]=1;ans[0]=0;
        q.push({"0000",0});
        while(!q.empty())
        {
            string ss=q.front().first;int g=q.front().second;
            q.pop();
            for(int i=0;i<10;i++)
            {
                string s1=spin(ss,i,1);
                string s2=spin(ss,i,-1);
                int num1=stoi(s1),num2=stoi(s2);
                if(!vis[num1]) vis[num1]=1,ans[num1]=g+1,q.push({s1,g+1});
                if(!vis[num2]) vis[num2]=1,ans[num2]=g+1,q.push({s2,g+1});
            }
        }
    }
    void solve()
    {
        init();
        cin>>n;
        while(n--)
        {
            string s1,s2;cin>>s1>>s2;
            int g=0;
            for(int i=0;i<=3;i++)
            {
                g+=((s2[i]-'0')-(s1[i]-'0')+10)%10*pow(10,3-i);
            }
            //cout<
            cout<<ans[g]<<endl;
        }
    }
    signed main()
    {
        ios;
        //int T;cin>>T;
        //while(T--)
            solve();
        return 0;
    }
    
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87

    H. Line Graph Matching

    真的想不到啊!大佬的思路很清晰

    #include
    #define int long long
    #define endl '\n'
    #define For(i,a,b) for(i=(a);i<=(b);++i)
    #define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
    using namespace std;
    const int N=7e5+5;
    const int inf=1e18;
    const int mod=1e9+7;
    /*
    int fac[40];
    int qpow(int a,int b){
        int res=1;
        while(b)
        {
            if(b&1) res=res*a%mod;
            a=a*a%mod;
            b>>=1;
        }
        return res;
    }
    int getinv(int x){return qpow(x,mod-2);}
    int C(int a,int b)
    {
        return (fac[a]*getinv(fac[a-b])%mod)*getinv(fac[b])%mod;
    }*/
    int n,m,cnt=1,tot,head[N],deg[N],ans,sz[N],mi,p;
    int dfn[N],low[N],ti;
    struct node
    {
        int to,nxt,w;
    }e[N];
    void add(int from,int to,int w)
    {
        e[++cnt].to=to;
        e[cnt].w=w;
        e[cnt].nxt=head[from];
        head[from]=cnt;
    }
    void tarjan(int u,int ine)
    {
        sz[u]=deg[u];
        dfn[u]=low[u]=++ti;
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].to,w=e[i].w;
            if(!dfn[v])
            {
                tarjan(v,i);
                sz[u]+=sz[v];
                low[u]=min(low[u],low[v]);
                if(low[v]>dfn[u])
                {
                    if ((((sz[v]-1)/2)&1)==0)
                        mi=min(mi,w);
                }
                else
                    mi=min(mi,w);
            }
            else if(i!=(ine^1))
            {
                mi=min(mi,w);
                low[u]=min(low[u],dfn[v]);
            }
            if(dfn[u]<dfn[v]) p++;
        }
    }
    void solve()
    {
        cin>>n>>m;
        for(int i=1;i<=m;i++)
        {
            int u,v,w;cin>>u>>v>>w;
            add(u,v,w),add(v,u,w);
            ans+=w;
            deg[u]++,deg[v]++;
        }
        for(int i=1;i<=n;i++)
        {
            if(!dfn[i])
            {
                mi=inf;
                p=0;
                tarjan(i,0);
                if(p&1) ans-=mi;
            }
        }
        cout<<ans<<endl;
    }
    signed main()
    {
        ios;
        //int T;cin>>T;
        //while(T--)
            solve();
        return 0;
    }
    
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
  • 相关阅读:
    vue3.2 table遍历form表单数据校验
    Python练习题:实现所有奇数长度子列表的和
    【Java进阶篇】第六章 IO流
    python Django QQ第三方登陆认证
    语音前处理技术在会议场景中的应用及挑战
    MySQL高级:(十六)主从复制
    Python爬虫——Requests 库基本使用
    SpringSecurity-基于微服务的认证与权限访问
    ONLYOFFICE Docs v7.5.0
    部署LVS-NAT群集实验
  • 原文地址:https://blog.csdn.net/weixin_51934288/article/details/126858032