2022年第三届辽宁省大学生程序设计竞赛（正式赛）vp

Myth丶恋晨 2024-03-25 09:49 73阅读 0赞

**vp了一下，居然冲到了rk15，不错，感觉题的质量都不高啊，甚至有很多题数据错了，比如I题，HJL似乎都是错的**

![f06b162bb431f29748d60cedc326b3b2.png][]

[牛客竞赛\_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛\_牛客竞赛OJ (nowcoder.com)][ACM_NOI_CSP_CCPC_ICPC_OJ _nowcoder.com]

**A伟大奋斗**

**模拟**

![ffc823fd4fac98ffd936c78047eb1aa4.png][]

#include <bits/stdc++.h>
    //#define int long long
    #define low(x) (x&(-x))
    using namespace std;
    const int mxn=3e2+10;
    const int mxe=1e5+10;
    const int mod=9901;
    
    int n;
    void solve(){
        cin>>n;
        cout<<n-1949<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

**B可莉的五子棋**

**模拟**

**写了依托**

![b4c1d28131c23bf766bac25c02db15aa.png][]

#include <bits/stdc++.h>
    #define int long long
    #define low(x) (x&(-x))
    using namespace std;
    const int mxn=1e3+10;
    const int mxe=1e5+10;
    const int mod=9901;
    
    int n,m;
    string s[mxn];
    void solve(){
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>s[i],s[i]=" "+s[i];
        int ans1=0,ans2=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(i+4<=n){
                    if(s[i][j]==s[i+1][j]&&s[i+1][j]==s[i+2][j]&&s[i+2][j]==s[i+3][j]&&s[i+3][j]==s[i+4][j]&&s[i][j]=='1') ans1++;
                }
    
                if(i+4<=n){
                    if(s[i][j]==s[i+1][j]&&s[i+1][j]==s[i+2][j]&&s[i+2][j]==s[i+3][j]&&s[i+3][j]==s[i+4][j]&&s[i][j]=='2') ans2++;
                }
    
    
                if(j+4<=m){
                    if(s[i][j]==s[i][j+1]&&s[i][j]==s[i][j+2]&&s[i][j]==s[i][j+3]&&s[i][j]==s[i][j+4]&&s[i][j]=='1') ans1++;
                }
    
                if(j+4<=m){
                    if(s[i][j]==s[i][j+1]&&s[i][j]==s[i][j+2]&&s[i][j]==s[i][j+3]&&s[i][j]==s[i][j+4]&&s[i][j]=='2') ans2++;
                }
    
    
                if(i+4<=n&&j+4<=m){
                    if(s[i][j]==s[i+1][j+1]&&s[i][j]==s[i+2][j+2]&&s[i][j]==s[i+3][j+3]&&s[i][j]==s[i+4][j+4]&&s[i][j]=='1') ans1++;
                }
    
                if(i+4<=n&&j+4<=m){
                    if(s[i][j]==s[i+1][j+1]&&s[i][j]==s[i+2][j+2]&&s[i][j]==s[i+3][j+3]&&s[i][j]==s[i+4][j+4]&&s[i][j]=='2') ans2++;
                }
    
                if(i-4>=1&&j+4>=1){
                    if(s[i][j]==s[i-1][j+1]&&s[i][j]==s[i-2][j+2]&&s[i][j]==s[i-3][j+3]&&s[i][j]==s[i-4][j+4]&&s[i][j]=='1') ans1++;
                }
    
                if(i-4>=1&&j+4>=1){
                    if(s[i][j]==s[i-1][j+1]&&s[i][j]==s[i-2][j+2]&&s[i][j]==s[i-3][j+3]&&s[i][j]==s[i-4][j+4]&&s[i][j]=='2') ans2++;
                }
            }
        }
        cout<<ans1<<" "<<ans2<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

**C消除死域点**

**树上倍增**

![0b65bcf49b660789ad635442e821aaf1.png][]

思路：

先去预处理出所有结点的sz和dep，标记出哪些结点是死结点，然后考虑去枚举删哪条边，对于考虑删掉的某条边，该边下面的sz都不变，上面的死结点有些就不死了，因此我们需要快速算出上面有几个不死结点。注意到离该边比较近的结点一定会不死，再远的结点一定死了，因此具有二段性，可以在树上二分，而树上倍增其实就相当于在树上二分了，我们倍增地跳上去，直到跳到dep\[p\]-dep\[x\]-1>k为止。然后边枚举边维护贡献最大值，最后减去这个最大的贡献就好了

#include<bits/stdc++.h>
    using namespace std;
    const int mxn=5e5+10;
    const int mxe=5e5+10;
    struct ty{
        int to,next;
    }edge[mxe<<1];
    struct Edge{
        int u,v;
    }e[mxe<<1];
    
    map<int,int> mp[mxn];
    vector<int> V;
    int n,k,u,v,tot=0,mx=0;
    int head[mxn],sz[mxn],dep[mxn];
    int F[mxn][33];
    void add(int u,int v){
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    void init(){
        tot=0;
        for(int i=0;i<=n;i++) head[i]=-1;
    }
    void dfs(int u,int fa){
        sz[u]=1;dep[u]=dep[fa]+1;
        F[u][0]=fa;
        for(int i=1;i<=30;i++) F[u][i]=F[F[u][i-1]][i-1];
        for(int i=head[u];~i;i=edge[i].next){
            if(edge[i].to==fa) continue;
            dfs(edge[i].to,u);
            sz[u]+=sz[edge[i].to];
        }
    }
    void dfs2(int x,int fa){
        //cout<<x<<'\n';
        if(sz[fa]-1>=k){
            int p=x;
            for(int i=30;i>=0;--i){
                if(F[p][i]&&sz[F[p][i]]-sz[x]<k+1) p=F[p][i]; 
            }
            mx=max(mx,dep[x]-dep[p]); 
        }
        for(int i=head[x];~i;i=edge[i].next){
            if(edge[i].to==fa) continue;
            dfs2(edge[i].to,x);
        }
    }
    void solve(){
        cin>>n>>k;
        init();
        for(int i=1;i<=n-1;i++){
            cin>>u>>v;
            add(u,v);
            add(v,u);
            //e[i]={u,v};
        }
        dfs(1,0);
        //for(int i=1;i<=n;i++) cout<<dep[i]<<" \n"[i==n];
        /*for(int i=1;i<=n;i++){
            if(dep[i]-1>=k) V.push_back(i);
        }
        //for(int i=0;i<V.size();i++) cout<<V[i]<<" \n"[i==V.size()-1];
        int ans=1e9,m=V.size();
        //cout<<dep[2]<<'\n';
        for(int i=3;i<=3;i++){
            int res=0;//不是死结点的个数
            for(int j=0;j<V.size();j++){
                if(dep[V[j]]-dep[e[i].v]-1<k&&dep[V[j]]>dep[e[i].v]&&check(e[i].v,V[j])) res++,cout<<V[j]<<'\n';
            }
            cout<<m-res<<'\n';
            ans=min(ans,m-res);
        }*/
        int ans=0;
        for(int i=1;i<=n;i++){
            if(sz[i]-1>=k) ans++;
        }
        //cout<<ans<<'\n';
        //for(int i=1;i<=n;i++) cout<<dep[i]<<" \n"[i==n];
        dfs2(1,0);
        cout<<ans-mx<<'\n';
    }
    int main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;   
    }

**D是期望题，不会，单独补QwQ**

**E病毒危机**

**模拟**

![9e2ab68c3af8afba8551b0f818c3f178.png][]

思路：

直接模拟

直接把队友代码贴上来吧

#include<bits/stdc++.h>
    using namespace std;
    const int mxn=1e5+10;
    int n,m,k,a[mxn],ans=1,v[mxn];
    int main(){
        ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
        cin>>n>>m;
        cin>>k;
        for(int x,i=1;i<=k;i++) cin>>x,v[x]=1;
        for(int f,i=2;i<=n;i++){
            cin>>k,f=0;
            for(int x,i=1;i<=k;i++){
                cin>>x;
                if(v[x]) f=1;
            }
            if(f) ans++;
        }
        cout<<ans<<'\n';
        return 0;
    }

**F互质**

**构造**

![ce18117aa4183891972a9ccb22102ad0.png][]

思路：

因为要和n互质，因此直接构造n-1，又要在范围里，直接输出(n-1)/2即可，然后对6进行特判

#include<bits/stdc++.h>
    using namespace std;
    const int mxn=1e6+10;
    int main(){
        ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
        long long t,n,ans;
        cin>>t;
        while(t--){
            cin>>n;
            if(n==6) cout<<-1<<'\n';
            else cout<<(n-1)/2<<'\n';
        }
        return 0;
    }

**G 栈与公约数**

**暴力**

![0372a708c9e8fe840088c7d2b5391981.png][]

思路：

呃呃，这题写个暴力加个break就能过，逆

#include<bits/stdc++.h>
    using namespace std;
    const int mxn=1e6+10;
    long long t,op,x,a[mxn],tot,d;
    int main(){
        ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
        cin>>t;
        while(t--){
            cin>>op;
            if(op==1) cin>>x,a[++tot]=x;
            if(op==2) tot--;
            if(op==3) cout<<a[tot]<<'\n';
            if(op==4){
                cin>>x;
                for(int i=tot;i>=tot-x+1;i--){
                    d=__gcd(a[i-1],a[i]);
                    if(d==1) break;
                }
                for(int i=tot;i>=tot-x+1;i--) a[i]=d;
            }
        }
        return 0;
    }

**I 图的分割**

**二分+并查集**

![cdc9808cce7fa1225e3941faddb66ed4.png][]

思路：

首先有个贪心策略，因为要保证最大边最小，因此考虑从小到大去连边，直到连到了两个连通块

那么注意到这具有二段性，即最大边太小就不止两个，太大就只有一个

因此可以去二分

在check里面，因为删除的最大边是mid，因此把大于mid的边全部连上，去看看是不是有两个连通块

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=1e6+10;
    const int mxe=1e6+10;
    struct ty{
        int u,v,w;
    }e[mxe<<1];
    
    
    int n,m,u,v,w,ans,cnt;
    int f[mxn];
    int find(int x){
        return f[x]=(x==f[x])?x:find(f[x]);
    }
    void join(int u,int v){
        int f1=find(u),f2=find(v);
        if(f1!=f2) f[f1]=f2;
        cnt--;
    }
    bool check(int mid){
        for(int i=1;i<=n;i++) f[i]=i;
        cnt=n;
        for(int i=1;i<=m;i++){
            if(e[i].w>mid) join(e[i].u,e[i].v);
        }
        return cnt!=1;
    }
    void solve(){
        cin>>n>>m;
        for(int i=1;i<=m;i++){
            cin>>u>>v>>w;
            e[i]={u,v,w};
        }
        int l=1,r=1e8;
        while(l<=r){
            int mid=l+r>>1;
            if(check(mid)){
                r=mid-1;
                ans=mid;
            }else l=mid+1;
        }
        cout<<ans<<'\n';
    }
    int main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

这样直接考虑n-2条边的居然也能过，6

#include<bits/stdc++.h>
    using namespace std;
    const int mxn=1e6+10;
    int n,m,u,v,a[mxn];
    int main(){
        ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
        cin>>n>>m;
        for(int i=1;i<=m;i++) cin>>u>>v>>a[i];
        sort(a+1,a+m+1);
        cout<<a[m-n+2]<<'\n';
        return 0;
    }

**K 俄罗斯方块**

不懂，队友过的，贴一下代码

#include<bits/stdc++.h>
    using namespace std;
    int a[1100][1100],e[8][8]={
        {1},{1,1},{1,7,7},{2,7,7,4},{2,2,3,4,4},{2,3,3,4,9,9},{8,8,3,5,9,9,6},{8,8,5,5,5,6,6,6}};
    int ee[7][7]={
        {1},{1,1},{1,2,2},{3,2,2,4},{3,3,4,4,4},{3,5,6,6,6,7},{5,5,5,6,7,7,7}};
    int r[8][8]={
        {1,1,2,2,3,3,4,4},{1,1,2,2,3,3,4,4},{5,5,6,6,7,7,8,8},{5,5,6,6,7,7,8,8},{9,9,10,10,11,11,12,12},{9,9,10,10,11,11,12,12},{13,13,14,14,15,15,16,16},{13,13,14,14,15,15,16,16}};
    int rr[8][7]={
        {1,2,2,2,3,11,11},{1,1,2,3,3,11,11},{1,4,4,4,3,12,12},{9,9,4,10,10,12,12},{9,9,5,10,10,13,13},{6,5,5,5,8,13,13},{6,6,7,8,8,14,14},{6,7,7,7,8,14,14}};
    int main()
    {
        int n,i,j,k,l,m,h;
        cin>>n;
        if((n*(n+1)/2)%4){
            cout<<"NO";
            return 0;
        }
        cout<<"YES\n";
        if(n==7){
            for(i=0;i<n;i++){
                for(j=0;j<=i;j++){
                    cout<<ee[i][j]<<' ';
                }
                cout<<endl;
            }
        }
        else if(n==8){
            for(i=0;i<n;i++){
                for(j=0;j<=i;j++){
                    cout<<e[i][j]<<' ';
                }
                cout<<endl;
            }
        }
        else if(n%8==0){
            for(i=0;i<8;i++){
                for(j=0;j<=i;j++){
                    cout<<e[i][j]<<' ';
                }
                cout<<endl;
            }
            k=1;l=0;h=9;
            for(i=8;i<n;i++){
                for(j=0;j<=i-k;j++){
                    cout<<h+j/8*16+r[i%8][j%8]<<' ';
                }
                for(;j<=i;j++){
                    cout<<h+i/8*16+e[i%8][j%8]<<' ';
                }
                if(i>8&&i%8==7){
                    h+=9+i/8*16;
                }
                k=(k%8)+1;
                cout<<endl;
            }
        }
        else{
            for(i=0;i<7;i++){
                for(j=0;j<=i;j++){
                    cout<<ee[i][j]<<' ';
                }
                cout<<endl;
            }
            k=1;h=7;
            for(i=7;i<n;i++){
                for(j=0;j<7;j++){
                    cout<<h+rr[(i+1)%8][j]<<' ';
                }
                for(;j<=i-k;j++){
                    cout<<h+14+(j-7)/8*16+r[(i+1)%8][(j+1)%8]<<' ';
                }
                for(;j<=i;j++){
                    cout<<h+14+(j-7)/8*16+e[(i+1)%8][(j+1)%8]<<' ';
                }
    
    
    
                k=(k%8)+1;
                if(i%8==6){
                    h+=16+7+(i-8)/8*16;
                }
                cout<<endl;
            }
    
        }
    }

**M 画画**

**构造**

纯构造，讨论n的奇偶性，尽量全部填满

#include<bits/stdc++.h>
    using namespace std;
    int a[1100][1100];
    int main()
    {
        int t,n,i,j,k,l,m;
        cin>>t;
        while(t--){
            scanf("%d",&n);
            memset(a,0,sizeof a);
            if(n%2){
                for(i=0;i<n;i+=2){
                    a[i][i]=1;
                }
            }
            else{
                for(i=1;i<n;i+=2){
                    a[i][i]=1;
                }
            }
            for(i=0;i<n;i++){
                for(j=0;j<n;j++){
                    printf("%d",1-a[i][j]);
                }
                printf("\n");
            }
        }
    }

[f06b162bb431f29748d60cedc326b3b2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/2f64ef855e69474b983d754d4fb6ce56.png
[ACM_NOI_CSP_CCPC_ICPC_OJ _nowcoder.com]: https://ac.nowcoder.com/acm/contest/53005
[ffc823fd4fac98ffd936c78047eb1aa4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/1704e506f6ad46a5b1d411e2bf79d4c9.png
[b4c1d28131c23bf766bac25c02db15aa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/f6c588e633ff49c9b8603e077f09986c.png
[0b65bcf49b660789ad635442e821aaf1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/4722e09ce0474c39ab50f39cf857c1a5.png
[9e2ab68c3af8afba8551b0f818c3f178.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/177627c6fec14993857902c429034bf4.png
[ce18117aa4183891972a9ccb22102ad0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/a39a4202cf2e407d9ac22bd2ae58faab.png
[0372a708c9e8fe840088c7d2b5391981.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/7f39a1ca518943958d0ddc1bf08f75f0.png
[cdc9808cce7fa1225e3941faddb66ed4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/f3ffc9e689fe47a4a8b58cab717cd653.png