【题目记录】——2021中国大学生程序设计竞赛（CCPC）- 网络选拔赛

短命女 2022-09-09 13:50 190阅读 0赞

### 文章目录 ###

*  1001 Cut The Wire 思维
 *  1006 power sum 思维
 *  1009 Command Sequence 模拟+思维
 *  1011 Shooting Bricks DP

题目集地址 [2021中国大学生程序设计竞赛（CCPC）- 网络选拔赛][2021_CCPC_-]  
题目集原地址 [2021中国大学生程序设计竞赛（CCPC）- 网络选拔赛][2021_CCPC_- 1]  
这次题目集做了三道简单题1001,1006,1009

# 1001 Cut The Wire 思维 #

题目地址[1001 Cut The Wire][]  
题意：一条路上从标号为1的路灯开始，最大值无上限，路灯与路灯之间有电线，电线连接的规则是：  
如果路灯标号x为偶数，则x到 x 2 \\frac\{x\}\{2\} 2x之间有一条电线。  
如果路灯标号x为奇数，则x到3x+1之间有一条电线。  
给出你一个x，表示你站在编号为x与x+1的路灯之间。问你最多剪掉多少根电线。  
思路：根据数学规律找到左右边界再计算即可。  
AC代码：

#include <bits/stdc++.h>
    #define INF 0x3f3f3f3f
    #define ll long long
    using namespace std;
    
    void solve()
    { 
        int n;
        int result=0;
        int yu;
        scanf("%d",&n);
        int temp=n;
        result+=((temp+1)/2);
        yu=n%3;
        if(yu==1)
            temp=(n+2)/3;
        else if(yu==2)
        { 
            temp=(n+1)/3;
        }
        else
        { 
            temp=n/3;
        }
        if(n&1)
            n++;
        if(temp&1)
        { 
            result+=((n-temp+1)/2);
        }
        else
        { 
            result+=((n-temp)/2);
        }
        printf("%d\n",result);
    }
    
    int main()
    { 
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
        int T;
        scanf("%d\n",&T);
        while(T--)
        { 
            solve();
        }
        return 0;
    }

# 1006 power sum 思维 #

题目地址[1006 power sum][]  
题目大意：给一个数字n，整数k和一个数组a\[i\]， a i ∈ − 1 , 1 a\_i\\in\{-1,1\} ai∈−1,1，数组a\[i\]的长度不超过K+2，满足 ∑ i = 1 k a i ∗ i 2 = n \\sum^\{k\}\_\{i=1\}\{a\_i\*i^2\}=n ∑i=1kai∗i2=n  
输出一个01字符串，0表示第i个数 x 2 x^2 x2\*(-1)，1表示第i个数 x 2 x^2 x2\*1，  
思路：可以看到相邻两个数的平方的差值是按照连续奇数序列上升的，也就是说大于4的k值后面每一个1001都会是一个4，这样只需要先找出前面4项的表示，后面只需要看有几个4就有几个1001即可。  
AC代码：

#include <bits/stdc++.h>
    #define ll long long
    #define INF 0x3f3f3f3f
    using namespace std;
    
    int main()
    { 
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	string a[4]={ "","1","0001","01"};
        int b[4]={ 0,1,4,2};
        int t;
        scanf("%d",&t);
        while(t--)
        { 
            string ans;
            int x,num = 0;
            scanf("%d",&x);
            num += b[x%4];
            ans=a[x%4];
            while(x >= 4)
            { 
                x-=4;
                num+=4;
                ans+="1001";
            }
            cout << num << endl;
            cout << ans << endl;
        }
        return 0;
    }

# 1009 Command Sequence 模拟+思维 #

题目地址：[1009 Command Sequence][]  
题目大意：给定一个命令序列，有四种命令，上下左右移动，问给出的序列有多少个连续子序列能够让机器人回到原点  
思路：一开始觉得是一个动态规划之类的。结果发现只需要模拟就好了，设初始坐标为0,0，每走到一个坐标就让坐标值的访问次数加一，最后所有坐标值减一的值到1类和，最后求所有坐标值得累和就可以了。  
AC代码：

#include <iostream>
    #include <vector>
    #include <algorithm>
    #include <queue>
    #include <time.h>
    #include <unordered_map>
    using namespace std;
    typedef long long ll;
    const int maxn=2e6+10;
    ll t,n,x,y;
    char str[maxn];
    ll sum(ll t) { 
        return t*(t-1)/2;
    }
    ll Hash() { 
        return x*1000000+y;
    }
    int main() { 
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
        scanf("%lld",&t);
        while(t--) { 
            unordered_map<ll,ll>U;
            U[0]=1;
            ll ans=0;
            x=0,y=0;
            scanf("%lld",&n);
            getchar();
            scanf("%s",str+1);
            for(int i=1; i<=n; i++) { 
                switch(str[i]) { 
                case 'U':
                    y++;
                    break;
                case 'D':
                    y--;
                    break;
                case 'L':
                    x--;
                    break;
                case 'R':
                    x++;
                    break;
                }
                U[Hash()]++;
            }
            unordered_map<ll,ll>::iterator p;
            for(p=U.begin(); p!=U.end(); p++)
                ans+=sum(p->second);
            printf("%lld\n",ans);
        }
        return 0;
    }

# 1011 Shooting Bricks DP #

题目地址[1011 Shooting Bricks][]  
此题目与[洛谷1174][1174]撞题，题意参考洛谷即可。  
思路：dp

#include <bits/stdc++.h>
    //#include <iostream>
    //#include <cstdio>
    //#include <cstring>
    //#include <algorithm>
    //#include <vector>
    //#include <map>
    //#include <stack>
    //#include <queue>
    #define ll long long
    #define INF 0x3f3f3f3f
    using namespace std;
    const int N = 205;
    int n, m, k;
    int sy[N][N],sn[N][N];//sy[i][j],sn[i][j]第i列消耗j颗子弹得到的分数,y表示最后一颗子弹打在第i列上，n表示没有打在第i列上
    int s[N][N],c[N][N];//s表示每个位置的砖块的分数，c表示每个位置是否会得到一个子弹
    int fn[N][N],fy[N][N];//fn[i][j],fy[i][j]表示前i列一共消耗j颗子弹得到的分数，最后一颗是否打在第i列上,n表示没有打在第i列，y表示打在第i列
    void init()
    { 
        memset(sy,0,sizeof(sy));
        memset(sn,0,sizeof(sn));
        memset(fy,0,sizeof(fy));
        memset(fn,0,sizeof(fn));
        memset(c,0,sizeof(c));
    }
    void solve()
    { 
        scanf("%d%d%d",&n,&m,&k);
        for(int i = 1;i <= n;i ++)
        { 
            for(int j = 1;j <= m;j++)
            { 
                char ch;
                scanf("%d %c",&s[i][j],&ch);
                if(ch=='Y')
                { 
                    c[i][j] = 1;
                }
            }
        }
        for(int i = 1;i <= m;i++)
        { 
            int cnt = 0;
            for(int j = n;j >= 1;j--)
            { 
                if(c[j][i])
                { 
                    sn[i][cnt] += s[j][i];
                }
                else
                { 
                    cnt++;
                    sn[i][cnt] = sn[i][cnt-1] + s[j][i];
                    sy[i][cnt] = sn[i][cnt-1] + s[j][i];
                }
            }
        }
    
        for(int x = 1; x <= m; x++)//当前列
        { 
            for(int y = 0; y <= k;y++)//总共y个子弹
            { 
                for(int z = 0;z <= n&&z <= y;z++)//当前列用了z个子弹
                { 
                    fn[x][y]=max(fn[x][y],fn[x-1][y-z]+sn[x][z]);
                    if(z!=0) fy[x][y]=max(fy[x][y],fn[x-1][y-z]+sy[x][z]);
                    if(y-z>0) fy[x][y]=max(fy[x][y],fy[x-1][y-z]+sn[x][z]);
                }
            }
        }
        cout<<fy[m][k]<< endl;
        init();
    }
    
    int main()
    { 
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    // int t = 1;
    	int t;
    	scanf("%d",&t);
    	while(t--)
    	{ 
    		solve();
    	}
        return 0;
    }

[2021_CCPC_-]: https://acm.hdu.edu.cn/search.php?field=problem&key=2021%D6%D0%B9%FA%B4%F3%D1%A7%C9%FA%B3%CC%D0%F2%C9%E8%BC%C6%BE%BA%C8%FC%A3%A8CCPC%A3%A9-+%CD%F8%C2%E7%D1%A1%B0%CE%C8%FC&source=1&searchmode=source
[2021_CCPC_- 1]: https://acm.hdu.edu.cn/contests/contest_show.php?cid=1031
[1001 Cut The Wire]: https://acm.hdu.edu.cn/showproblem.php?pid=7100
[1006 power sum]: https://acm.hdu.edu.cn/showproblem.php?pid=7105
[1009 Command Sequence]: https://acm.hdu.edu.cn/showproblem.php?pid=7108
[1011 Shooting Bricks]: https://acm.hdu.edu.cn/showproblem.php?pid=7110
[1174]: https://www.luogu.com.cn/problem/P1174