【CCPC网络赛】2021中国大学生程序设计竞赛（CCPC）- 网络选拔赛（重赛） 签到题5题
【摘要】
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）