[数据结构与算法]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)$

代码

	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)$

代码

  	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(tlogn)$

简单讲解：
$$\begin{gathered} 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}]\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right] \\ 所以[F_n{F}_{n?1}]=[F_2{F}_1]{\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^{n?2} \end{gathered}$$
前置知识：快速幂

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$，那么就可以打败敌人$i$，并且力量永久增加$b_i$，打败所有敌人最低需要多少初始力量。

思路

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

也可以二分答案。复杂度$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)$暴力可过。如果过了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(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)$

代码

	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稳定。（稳定的定义同上）

思路

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

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

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

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