【CCPC网络赛】2021中国大学生程序设计竞赛(CCPC)- 网络选拔赛(重赛) 签到题5题

举报
小哈里 发表于 2022/04/29 22:22:00 2022/04/29
【摘要】 Problems Solved Problem ID Title Ratio (Accepted / Submitted) 1001 Median Problem 9.09% (5/55) 1002 Ka...

Problems
Solved Problem ID Title Ratio (Accepted / Submitted)
1001 Median Problem 9.09% (5/55)
1002 Kanade Doesn’t Want to Learn CG 16.30% (1904/11682)
1003 GCD on Tree 10.45% (7/67)
1004 Primality Test 37.59% (2693/7165)
1005 Monopoly 9.09% (522/5744)
1006 Nun Heh Heh Aaaaaaaaaaa 31.63% (1654/5229)
1007 Occupying Grids 22.35% (95/425)
1008 Subpermutation 40.59% (194/478)
1009 Public Transport System 11.33% (113/997)
1010 Bigraph Extension 20.71% (317/1531)
1011 Jumping Monkey 23.10% (662/2866)
1012 Contest Remake 9.15% (14/153)

1、Kanade Doesn’t Want to Learn CG

题意:

  • 给出ABCD四个点的坐标,构成一个篮筐。给出a,b,c,抛物线满足y = ax^2+bx+c。
  • 篮球从x=−114514^1919810次方投出,判断能否进球。
    在这里插入图片描述

思路:

  • 进球有两种方式,一种是下落直接进(此时方程y = ax^2+bx+c == y0 必有两解且 x0<=x_right<=x1),另一种情况是打到篮板反弹进球(因为是完全对称反弹,所以此时只需要满足x1<=x_right<=2x2-x0和 y0 < y|x=x1 < y2即可)。
  • 特判进不了的情况,比如撞到篮筐。
  • 也可以直接列举所有不能进的情况,剩下的就Yes。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

LL a, b, c;
LL x0,x1, y0, y1, y2;
LL f(LL x){ return a*x*x+b*x+c; }

int main(){
	int T;  cin>>T;
	while(T--){
		cin>>a>>b>>c;
		cin>>x0>>x1>>y0>>y1>>y2;
		if(f(x0)<=y0 || f(x1)>y2)cout<<"No\n";
		else if(f(x1)==y0)cout<<"No\n";
		else if(f(x1)>y0 && f(2*x1-x0)>=y0)cout<<"No\n";
		else cout<<"Yes\n";
	}
	return 0;
}



  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

2、Primality Test

题意:

  • 定义f(x)表示刚好大于x的第一个素数,g(x) = [f(x) + f( f(x) )] / 2向下取整。
  • 给出x,判断g(x)是否是个素数。

思路:

  • 因为f(x)全都是素数,g(x)在相邻两个素数之间(可以证明),所以x>1时g(x)必定是合数。
  • 也可以打表,发现全都是NO。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T;  cin>>T;
    while(T--){
        LL x;  cin>>x;
        if(x==1)cout<<"YES\n";
        else cout<<"NO\n";
    }
    return 0;
}


  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
//打表
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int maxn = 1e9+10;

int is_prime(LL x){
    for(LL i = 2; i*i <= x; i++){
        if(x%i==0){
            return 0;
        }
    }
    return 1;
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T;  cin>>T;
    while(T--){
        LL x=T; // cin>>x;
        LL i;
        for(i = x+1; ; i++){
            if(is_prime(i)){
                break;
            }
        }
        LL j;
        for(j = i+1; ; j++){
            if(is_prime(j)){
                break;
            }
        }
        LL k = (i+j)/2;
        if(is_prime(k))cout<<"YES\n";
        else cout<<"NO\n";
    }
    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

3、Monopoly

题意:

  • n个位置围成一个圈,每个位置有一个分数ai。初始分数0(第0步),求能否获得分数x,输出最小的步数,不能输出-1。
  • T<20, n<5e5, m < 5e5, -1e12 < ai,x <1e12。

思路:

  • n个数作为一个循环,求前缀和 s[i] ,令原序列n个数的和为sn,可以得到s[i+n] = s[i] = sn。
  • 由s[i]+ks[n]==x 可以推出 ks[n]-x==s[i] 和 (x-s[i])%s[n]==0 。
    用第一个式子做,可以把所有的s[i] 和 与s[n]不同正负的ks[n]+s[i] 丢到 set里面,输入 x 后判断是否存在在set中 或是能通过 +ks[n]存在。(写了一发TLE。)
    用第二个式子做,考虑x和s[i] mod sn的模数相同,所以把s[i] 全都mod 一遍 sn丢到map里面去,输入x就可以找到是否存在相同模数,取出来计算步数即可。(全部存下来写了一发暴力TLE, 只存最大的sn写了一发WA,因为s[i]比x大就不行了。)
  • 对于模数相同的情况, 因为要找最小步数,且 x ==sn+ks[i], 所以s[i]自然是越大越好。如果仍然有多个,那就取位置最靠前的。
  • 开一个map<int, pair<int,int> >维护所有的{x, s[i], i},每次二分找到小于等于x的最大的数,同时得到其最靠前的位置,计算即可。
  • 对于sn<0 的情况,把全序列所有数取相反数转换为sn>0的情况处理。 如果sn==0则需要特判,此时所有情况只有原先的前缀和序列里有的情况,后面都是重复。
//1005-重写
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 2e5+10;

LL a[maxn], s[maxn];
map<LL,LL>ma;
map<LL, vector<pair<LL, LL> > >mp;

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T;  cin>>T;
    while(T--){
        ma.clear(); mp.clear();
        int n, m;  cin>>n>>m;
        for(int i = 1; i <= n; i++){
            cin>>a[i];  s[i] = s[i-1]+a[i];
            if(!ma.count(s[i]))ma[s[i]] = i;//WA!!
        }
        LL sn = s[n];  bool ok = 0;
        if(sn < 0){//负数取反处理
            sn = -sn;  ok = 1;
            for(int i = 1; i <= n; i++)s[i] = -s[i];
        }
        if(sn == 0){//特判0
            for(int i = 1; i <= m; i++){
                LL x;  cin>>x;
                if(x==0){cout<<"0\n"; continue; }
                if(ma.count(x))cout<<ma[x]<<"\n";
                else cout<<"-1\n";
            }
            continue;  //return 0; //WA
        }
        //正数统计
        for(int i = 1; i <= n; i++){
            LL md = (s[i]%sn+sn)%sn;
            mp[md].push_back({-s[i], i});//按照s[i]从大到小排序,顺序从前往后
        }
        for(auto it=mp.begin(); it!=mp.end(); it++)
            sort(it->second.begin(), it->second.end());
        while(m--){
            LL x;  cin>>x;
            if(ok) x = -x;
            if(x==0){cout<<"0\n"; continue; }
            LL xx = (x%sn+sn)%sn;
            if(mp.count(xx)){  
                pair<LL,LL> t = {-x, 0};
                int p = lower_bound(mp[xx].begin(),mp[xx].end(), t)-mp[xx].begin();
                if(p!=mp[xx].size()){
                    LL ans = mp[xx][p].second;
                    ans += (x+mp[xx][p].first)/sn*n;
                    cout<<ans<<"\n";
                }else{
                    cout<<"-1\n";
                }
            }else{
                cout<<"-1\n";
            }
        }
    }
    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

补题:continue写成了return 0;WA了一个半小时,无语了。
在这里插入图片描述
在这里插入图片描述

4、Nun Heh Heh Aaaaaaaaaaa

题意:

  • 给出一个字符串,找其中有多少个子序列满足NuhHehHeh加若干个a(不含0),答案mod 998244353。

思路:

  • 考虑 dp。将 NuhHehHeh 与后面的 a 拆开,设 f[ i ][ j ] 表示前 i 位中匹配到第 j 位的方案数,之后对于每个 f[ i ] [ 9] 乘上后面 a 的个数贡献就行。
  • 可以用滚动数组将空间复杂度优化到一维
//NuhHehHehaaa
#include<bits/stdc++.h>
using namespace std;
typedef long long LL; 
const LL mod = 998244353;
LL f[50];
int main(){
	int T;  cin>>T;
	while(T--){
		for(int i =1; i <= 10; i++)f[i] = 0;
		string s;  cin>>s;
		for(int x : s){
			if(x=='n'){
				f[3] += f[2];
				f[1]++;
			}else if(x=='u'){
				f[2] += f[1];
			}else if(x=='h'){
				f[9] += f[8];
				f[7] += f[6];
				f[6] += f[5];
				f[4] += f[3];
			}else if(x=='e'){
				f[8] += f[7];
				f[5] += f[4];
			}else if(x=='a'){
				f[10] += f[9]+f[10];
			}
			for(int i = 1; i <= 10; i++)f[i]%=mod;
		}
		cout<<f[10]%mod<<"\n";
	}
	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

5、Jumping Monkey

题意:

  • n个点的树,每个点有一个不一样的点权,求从每个点出发能到达的点数(需满足该点为该路径上的最大点权才能到达)
  • T < 1e4, n < 1e5, sum{n} < 8e5。

思路:

  • 考虑点权最大的那个结点x,显然其他所有点都能到达它,且到达它之后不能越过它到其他的点去。
  • 所以节点x一定是最优方案中最后一个到达的点,所以我们可以把这个点x去掉,再对剩下的独立联通块重复操作。
  • 因为在递归中难以实现每次去掉节点,所以反向按点权从小到大枚举结点x,并将x作为所有与x相连的(已经枚举过的)联通块的根(用并查集维护,只连一个点可以将复杂度从On降到logn)建立一棵新的树,每个节点的深度就是答案。
//1011
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 2e5+10;

int fa[maxn+10];
void init(int n){for(int i = 1; i <= n; i++)fa[i]=i;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x, int y){x=find(x);y=find(y);if(x!=y)fa[x]=y;}

vector<int>G[maxn], G2[maxn];
int c[maxn];
map<int,int>dc;

int a[maxn], vis[maxn];
void dfs(int x){
	for(int to : G2[x]){
        a[to] = a[x]+1;
        dfs(to);
    }
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T;  cin>>T;
    while(T--){
        int n;  cin>>n;
        for(int i = 1; i <= n; i++)G[i].clear(), G2[i].clear();
        init(n);
        memset(vis,0,sizeof(vis));
        for(int i = 1; i < n; i++){
            int u, v;  cin>>u>>v;
            G[u].push_back(v);
            G[v].push_back(u);
        }
        dc.clear();
        for(int i = 1; i <= n; i++){
            cin>>c[i];  dc[c[i]] = i;
        }
        vis[dc.begin()->second] = 1;
        for(auto it=++dc.begin(); it != dc.end(); it++){
            int u = it->second;
            for(int v : G[u]){ //建新树
                if(!vis[v])continue;
                int cc = find(v);
                merge(v,u);
                G2[u].push_back(cc);
            }
            vis[u] = 1;
        }
        int x = (--dc.end())->second;
        a[x] = 1;
        dfs(x);
        for(int i = 1; i <= n; i++)
            cout<<a[i]<<"\n";
    }
    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

文章来源: gwj1314.blog.csdn.net,作者:小哈里,版权归原作者所有,如需转载,请联系作者。

原文链接:gwj1314.blog.csdn.net/article/details/120697154

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。