2021暨南大学轩辕杯ACM程序设计新生赛题解

2023-11-05 06:32
文章标签 程序设计 2021 题解 acm 新生 暨南大学 轩辕

本文主要是介绍2021暨南大学轩辕杯ACM程序设计新生赛题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

title : 2021暨南大学轩辕杯ACM程序设计新生赛
date : 2021-12-12
tags : ACM,练习记录
author : Linno

在这里插入图片描述

题目链接：https://ac.nowcoder.com/acm/contest/26008

进度：10/13

总结

难度比较适合新生，基本上都有出题，而难题上限也很高，共5道题没人过，最高过题数8道。

我不是出题人，如果大家没有需要的话这份题解不会更了。

排在前面有很多大佬啊，如果下面题解有问题希望可以对我提出指正。

A.残秋挽歌

题意

给一个长度为n的字符串，如果存在出现次数大于n/2个’a‘，那么输出原字符串，否则反转输出。

思路

签到题。记录a的个数就可了。复杂度 O ( n ) O(n) O(n)

代码

	cin>>n;cin>>str;for(int i=0;i<n;i++){if(str[i]=='a'){num++;}}if(num>n/2)	for(int i=n-1;i>=0;i--) cout<<str[i];else for(int i=0;i<n;i++) cout<<str[i];

B.突 发 恶 疾

题面

输出斐波那契第n项模998244353

思路

签到题+1。递推求斐波那契数列，边推边模。复杂度 O ( n ) O(n) O(n)

代码

  	cin>>n;f[0]=0;f[1]=1;for(int i=2;i<=n;i++) f[i]=(f[i-1]+f[i-2])%mod;cout<<f[n]<<"\n";

C.突 发 恶 疾 plus

题面

把上一题的n数据范围调到1e18,且最多有1e5组数据。

来源：https://www.luogu.com.cn/problem/P4000

思路

使用矩阵快速幂。复杂度 O ( t l o g n ) O(tlogn) O(tlogn)

简单讲解：
F n = F n − 1 + F n − 2 F n − 1 = F n − 2 + F n − 3 [ F n F n − 1 ] = [ ( F n − 1 + F n − 2 ) F n − 1 ] = [ F n − 1 F n − 2 ] [ 1 1 1 0 ] 所 以 [ F n F n − 1 ] = [ F 2 F 1 ] [ 1 1 1 0 ] n − 2 F_n=F_{n-1}+F_{n-2} \\ F_{n-1}=F_{n-2}+F_{n-3}\\ [F_n\quad F_{n-1}]=[(F_{n-1}+F_{n-2})\quad F_{n-1}]=[F_{n-1}\quad F_{n-2}]\begin{bmatrix}1&1\\1&0\end{bmatrix}\\ 所以[F_n\quad F_{n-1}]=[F_2\quad F_1]\begin{bmatrix}1&1\\1&0\end{bmatrix}^{n-2} Fn​=Fn−1​+Fn−2​Fn−1​=Fn−2​+Fn−3​[Fn​Fn−1​]=[(Fn−1​+Fn−2​)Fn−1​]=[Fn−1​Fn−2​][11​10​]所以[Fn​Fn−1​]=[F2​F1​][11​10​]n−2
前置知识：快速幂

int fpow(int a,int b,int mod){int res=1;while(b){if(b&1) res=res*a%mod;a=a*a%mod;b>>=1;}return res;
}

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;int read(){	int x=0;char ch=getchar();while(ch<'0'||ch>'9')ch=getchar();while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x;}struct Matrix{int a[3][3];Matrix(){memset(a,0,sizeof(a));}void init(){a[1][1]=a[1][2]=a[2][1]=1;a[2][2]=0;}Matrix operator*(const Matrix b) {Matrix res;for(int i=1;i<=2;i++)for(int j=1;j<=2;j++)for(int u=1;u<=2;u++)res.a[i][j]=(res.a[i][j]+a[i][u]*b.a[u][j])%mod;return res;}
};inline int qpow(int n){Matrix ans,base;ans.init();base.init();while(n > 0){if(n&1) ans =ans *base;base = base *base;n>>=1;}return ans.a[1][1];
}
signed main(){freopen("C.in","r",stdin);freopen("C.out","w",stdout);int t,n;t=read();while(t--){n=read();printf("%lld\n",qpow(n-2));}return 0;
}

D.wyh与质数

没写。

E.你一定是很喜欢兔子对吧…?

题面

给你n个敌人，如果当前力量大于等于 a i a_i ai​，那么就可以打败敌人 i i i，并且力量永久增加 b i b_i bi​，打败所有敌人最低需要多少初始力量。

思路

签到题+2。对于所有敌人，按 a i a_i ai​从小到大排序。从最弱的开始打；我们先搞定最弱的，然后如果达不到下一个敌人要求的力量，则答案补上那个差值。复杂度 O ( n ) O(n) O(n)

也可以二分答案。复杂度 O ( n l o g n ) O(nlogn) O(nlogn)

代码

#pragma GCC optimize("Ofast", "inline", "-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+7;
const int mod=1e9+7;
int read(){	int x=0;char ch=getchar();while(ch<'0'||ch>'9')ch=getchar();while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x;}struct X{int a,b;
}s[N];bool cmp(X x,X y){return x.a<y.a;
}int n,ans,x; bool check(int x){for(int i=1;i<=n;i++){if(x>=s[i].a) x+=s[i].b;else return false;}return true;
}signed main(){freopen("E.in","r",stdin);freopen("E.out","w",stdout);n=read();for(int i=1;i<=n;i++){s[i].a=read();s[i].b=read();}sort(s+1,s+1+n,cmp);ans=s[1].a;x=s[1].b+s[1].a;for(int i=2;i<=n;i++){if(x<s[i].a) ans+=(s[i].a-x),x=s[i].a+s[i].b;else x+=s[i].b;}printf("%lld\n",ans);return 0;
}

F.サクラノ詩 －櫻の森の上を舞う－

题面

求两个多项式卷积之后的结果，输出系数。

思路

次数相加，系数相乘。

O ( n 2 ) O(n^2) O(n2)暴力可过。如果过了G也可以直接搬G题的代码。

代码

	n=read();m=read();memset(c,0,sizeof(c));for(int i=0;i<=n;i++) a[i]=read();for(int i=0;i<=m;i++) b[i]=read();for(int i=0;i<=n;i++){for(int j=0;j<=m;j++){c[i+j]+=(a[i]*b[j])%mod;c[i+j]%=mod;}}for(int i=0;i<=n+m;i++) cout<<c[i]<<" ";cout<<"\n";

G.サクラノ刻　-櫻の森の下を歩む-

题目

和上题一样。但是多项式的次数提高到2e5。

思路

求多项式卷积可以用FFT（快速傅里叶变换）/NTT（快速数论变换），复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)，

因为是对大质数取模，所以是一个裸的NTT卷积板子。

代码

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int MAXN=3*1e6+10,P=998244353,G=3,Gi=332748118; //G为P的原根 
char buf[1<<21],*p1=buf,*p2=buf;
int read(){	int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
int N,M,limit=1,L,r[MAXN];
int a[MAXN],b[MAXN];inline int fpow(int a,int k) {int base=1;while(k){if(k&1) base=(base*a)%P;a=(a*a)%P;k>>=1;}return base%P;
}inline void NTT(int *A, int type) {for(int i=0;i<limit;i++) if(i<r[i]) swap(A[i],A[r[i]]);for(int mid=1;mid<limit;mid<<=1) {	int Wn=fpow(type==1?G:Gi,(P-1)/(mid<<1));for(int j=0;j<limit;j+=(mid<<1)) {int w=1;for(int k=0;k<mid;k++,w=(w*Wn)%P){int x=A[j+k],y=w*A[j+k+mid]%P;A[j+k]=(x+y)%P,A[j+k+mid]=(x-y+P)%P;}}}
}
signed main(){freopen("F.in","r",stdin);freopen("F.out","w",stdout);N=read();M=read();for(int i=0;i<=N;i++) a[i]=(read()+P)%P;for(int i=0;i<=M;i++) b[i]=(read()+P)%P;while(limit<=N+M) limit<<=1,L++;for(int i=0;i<limit;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(L-1));	NTT(a,1);NTT(b,1);	for(int i=0;i<limit;i++) a[i]=(a[i]*b[i])%P;NTT(a,-1);	int inv=fpow(limit,P-2);for(int i = 0; i <= N + M; i++){printf("%d ",(a[i]*inv)%P);}puts("");return 0;
}

H.小鸟的秘密工坊

题目

对于一个01串，如果每一个0都有前面一个1对应则表示是一个稳定的串。判断给定串是否稳定。

思路

签到题+3。可以联想到栈，如果是1则进栈，是0则退栈，空的时候遇到0就说明不合法。复杂度 O ( n ) O(n) O(n)

代码

	int lf=0,rg=0,flag=0;string str;cin>>str;for(int i=0;i<str.length();i++){if(str[i]=='1') lf++;else{if(lf) lf--;else{flag=1;break;}}}if(flag||lf) puts("Rewrite");else puts("Key");

I.█

题面

给定n个01串，问能否将他们全部拼成一个串S，使得S稳定。（稳定的定义同上）

思路

给很多个括号序列，他们按上一题的方式预处理之后最终只有三种形态：

①" ( ( ( ((( (((" ,即只剩下右边未匹配的左括号
②" ) ) ) ))) )))" ,即只剩下左边未匹配的右括号

③" ) ) ( ( ))(( ))(("，即既有左边未匹配的右括号，也有右边未匹配的左括号

我们想法是贪心地把字符串按未匹配右括号数量由小到大排个序，然后排序拼接。我们最终的串就会变成这种形式" ( ( ( ) ) ( ( ) ) ) ((( \quad ))(( \quad ))) ((())(()))"（三个串的右括号数量分别是0,2,3）最终判断这样拼起来的串是否合理（能否简化成没有括号）即可。复杂度 预 处 理 O ( Σ ∣ s i ∣ ) ， 排 序 O ( n l o g n ) 预处理O(\Sigma |s_i|)，排序 O(nlogn) 预处理O(Σ∣si​∣)，排序O(nlogn)

代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
//#define int long long
using namespace std;
const int N=2e5+7;
const int mod=1e9+7;struct X{int l,r,flag;
}s[N];bool cmp(X a,X b){if(a.l==b.l) return a.r<b.r;return a.l>b.l;
}int n,len,num,flag;
string str;signed main(){freopen("I.in","r",stdin);freopen("I.out","w",stdout);cin>>n;for(int i=1;i<=n;i++){cin>>len>>str;for(int j=0;j<len;j++){if(str[j]=='1') s[i].l++;else{if(s[i].l) s[i].l--;else s[i].r++;}}}sort(s+1,s+1+n,cmp);for(int i=1;i<=n;i++){num+=s[i].l;num-=s[i].r;if(num<0){flag=1;break;}}if(flag||num) puts("Moon");else puts("Terra");return 0;
}

J.闊靛緥婧愮偣

题面

给你n个世界，每个世界都是一个01矩阵，其中同一个连通区域0可以看成是一个物体，他可以通过拓扑变换变成另外一个物体。问有没有哪个世界可以拓扑变换成原本的世界。

思路

如果世界A可以变换为世界B，那么他们连通的区域数量肯定是一样的（物体数量一样）。那么我们通过深搜跑每个世界的连通块个数并且判断是否和给定世界的连通块个数相等，就可以判断能否拓扑变换得来。

代码

#pragma GCC optimize("Ofast", "inline", "-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;char mp[15][15];
int n,m,cnt[10],ans=0;void dfs(int x,int y){if(mp[x][y]!='0'||x<1||x>m||y<1||y>m) return;mp[x][y]='1';dfs(x+1,y);dfs(x-1,y);dfs(x,y+1);dfs(x,y-1);
}int solve(){int res=0; for(int i=1;i<=m;i++){for(int j=1;j<=m;j++){if(mp[i][j]=='0'){dfs(i,j);res++;}}}return res;
}signed main(){cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){for(int k=1;k<=m;k++){cin>>mp[j][k];}}cnt[i]=solve();}for(int i=1;i<=m;i++){for(int j=1;j<=m;j++){cin>>mp[i][j];}}ans=solve();for(int i=1;i<=n;i++)if(cnt[i]==ans){cout<<i<<"\n";return 0;}cout<<-1<<"\n";return 0;
}

K.不思议之国

没写

L.五彩斑斓的世界

题面

给个n*m的01矩阵，1表示有障碍，0表示空缺。你拥有很多条1×len的长条(len可以是任何数)，问你最少用多少条可以把所有空缺补上。

原题： https://codeforces.com/contest/1404/problem/E

思路

Dinic求二分图的最大独立集数量。

  直接考虑网络流,S连到i表示割掉这条边 i选横着,i连到T表示割掉这条边 i选竖着,流量为o,o是一个足够大的数,对于两个横着相邻的点,我们先加上他们的贡献(也就是-1),然后在网络流里面新建一个点,将两个点连向它流量为inf,这个点连向汇点,表示如果有一个点选了竖着,那么这两点的贡献就不算数,要减去他们的贡献,也就是加上1,最后答案就是dinic()-点数*o+贡献.

————————————————
版权声明：本文为CSDN博主「Deep_Kevin」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/Deep_Kevin/article/details/108449293

代码

#pragma GCC optimize("Ofast", "inline", "-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const int N=2e5+7,M=205;struct Edge{int v,w,nxt;
}e[N<<2];const int dx[]={1,1,0,0},dy[]={0,-1,0,-1};
int n,m,U[M][M],L[M][M],tot,st,ed;
int d[N],q[N],cur[N];
char mp[M][M];int cnt=1,head[N];
void addedge(int u,int v,int w){e[++cnt]=(Edge){v,w,head[u]};head[u]=cnt;e[++cnt]=(Edge){u,0,head[v]};head[v]=cnt;
}bool bfs(){  //bfs分层找增广路 for(int i=1;i<=ed;i++) d[i]=0,cur[i]=head[i];//当前弧优化 int l,r;q[l=r=1]=st;d[st]=1;for(int x=st;l<=r;x=q[++l]){for(int k=head[x],y;k;k=e[k].nxt){if(!d[y=e[k].v]&&e[k].w) d[y]=d[x]+1,q[++r]=y;}}return d[ed];
}int dfs(int x,int f){ //dfs获取最大流 if(x==ed) return f;int s=0,t;for(int &k=cur[x],y,z;k;k=e[k].nxt){y=e[k].v;z=min(e[k].w,f-s);if(d[y]==d[x]+1&&z){s+=t=dfs(y,z);e[k].w-=t;e[k^1].w+=t;if(s==f) return f;}}if(!s) return d[x]=0;return s;
}int dinic(){ //最大匹配数 int ans=0;while(bfs()) ans+=dfs(st,inf);return ans;
}signed main(){freopen("L.in","r",stdin);freopen("L.out","w",stdout);cin>>n>>m;int ans=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>mp[i][j];if(mp[i][j]=='0'){ans++;   //ans表示快的数量 if(mp[i-1][j]=='0') U[i][j]=++tot,ans--; //向上连边 if(mp[i][j-1]=='0') L[i][j]=++tot,ans--; //向下连边 }}}st=++tot;ed=++tot; //超级源点和超级汇点 for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){int x=L[i][j];if(U[i][j]) addedge(U[i][j],ed,1); //上边的点和超级汇点连边 if(!x) continue;addedge(st,x,1); //左边的点和超级源点连边 for(int t=0;t<4;t++){int tx=i+dx[t],ty=j+dy[t];if(U[tx][ty]) addedge(x,U[tx][ty],1); //每次转移代价均为1 }}}printf("%d\n",ans+dinic());return 0;
}

M.Lamunation!

没写。

参考资料

https://blog.csdn.net/Deep_Kevin/article/details/108449293

这篇关于2021暨南大学轩辕杯ACM程序设计新生赛题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/348069。

相关文章

认识、理解、分类——acm之搜索

认识、理解、分类——acm之搜索

普通搜索方法有两种：1、广度优先搜索；2、深度优先搜索； 更多搜索方法： 3、双向广度优先搜索； 4、启发式搜索（包括A*算法等）； 搜索通常会用到的知识点：状态压缩（位压缩，利用hash思想压缩）。
阅读更多...
C++ | Leetcode C++题解之第393题UTF-8编码验证

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目： 题解： class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &
阅读更多...
C语言 | Leetcode C语言题解之第393题UTF-8编码验证

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目： 题解： static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return
阅读更多...
C - Word Ladder题解

C - Word Ladder题解

C - Word Ladder 题解 解题思路： 先输入两个字符串S 和t 然后在S和T中寻找有多少个字符不同的个数（也就是需要变换多少次） 开始替换时： tips: 字符串下标以0开始 我们定义两个变量a和b，用于记录当前遍历到的字符 首先是判断：如果这时a已经==b了，那么就跳过，不用管； 如果a大于b的话：那么我们就让s中的第i项替换成b，接着就直接输出S就行了。 这样
阅读更多...
C语言程序设计(数据类型、运算符与表达式)

C语言程序设计(数据类型、运算符与表达式)

一、C的数据类型 C语言提供的数据类型： 二、常量和变量 2.1常量和符号常量 在程序运行过程中，其值不能被改变的量称为常量。 常量区分为不同的类型： 程序中用＃define（预处理器指令）命令行定义变量将代表常量，用一个标识符代表一个常量，称为符合常量。 2.2变量 变量代表内存中具有特定属性的一个存储单元，用来存放数据，在程序运行期间，这些值是可以 改变的。 变
阅读更多...
【秋招笔试】9.07米哈游秋招改编题-三语言题解

【秋招笔试】9.07米哈游秋招改编题-三语言题解

🍭 大家好这里是 春秋招笔试突围，一起备战大厂笔试 💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历 ✨ 本系列打算持续跟新 春秋招笔试题 👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸 ✨ 笔试合集传送们 -> 🧷春秋招笔试合集 🍒 本专栏已收集 100+ 套笔试题，笔试真题 会在第一时间跟新 🍄 题面描述等均已改编，如果和你笔试题看到的题面描述
阅读更多...
C语言程序设计(选择结构程序设计)

C语言程序设计(选择结构程序设计)

一、关系运算符和关系表达式 1.1关系运算符及其优先次序 ①＜（小于） ②＜＝（小于或等于） ③＞（大于） ④＞＝（大于或等于 ） ⑤＝＝（等于） ⑥！＝（不等于） 说明： 前4个优先级相同，后2个优先级相同，关系运算符的优先级低于算术运算符，关系运算符的优先级高于赋值运算符 1.2关系表达式 用关系运算符将两个表达式（可以是算术表达式或关系表达式，逻辑表达式，赋值表达式，字符
阅读更多...
LeetCode 第414场周赛个人题解

LeetCode 第414场周赛个人题解

目录 Q1. 将日期转换为二进制表示 原题链接 思路分析 AC代码 Q2. 范围内整数的最大得分 原题链接 思路分析 AC代码 Q3. 到达数组末尾的最大得分 原题链接 思路分析 AC代码 Q4. 吃掉所有兵需要的最多移动次数 原题链接 思路分析 AC代码 Q1. 将日期转换为二进制表示 原题链接 Q1. 将日期转换为二进制表示 思路分析
阅读更多...
GPU 计算 CMPS224 2021 学习笔记 02

GPU 计算 CMPS224 2021 学习笔记 02

并行类型 （1）任务并行 （2）数据并行 CPU & GPU CPU和GPU拥有相互独立的内存空间，需要在两者之间相互传输数据。 （1）分配GPU内存 （2）将CPU上的数据复制到GPU上 （3）在GPU上对数据进行计算操作 （4）将计算结果从GPU复制到CPU上 （5）释放GPU内存 CUDA内存管理API （1）分配内存 cudaErro
阅读更多...
2021-8-14 react笔记-2 创建组件 基本用法

2021-8-14 react笔记-2 创建组件 基本用法

1、目录解析 public中的index.html为入口文件 src目录中文件很乱，先整理文件夹。 新建components 放组件 新建assets放资源   ->/images      ->/css 把乱的文件放进去  修改App.js 根组件和index.js入口文件中的引入路径 2、新建组件 在components文件夹中新建[Name].js文件 //组件名首字母大写
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2