A. 小田的消消乐游戏

题目类型：分类讨论

思路

因为只有0和1，所以可以根据不同的情况分类讨论：

• 若n==1，则输出-1。
• 若头部数字与尾部数字相同，则输出1。
• 头部数字与尾部数字​不同，但是在 便历2∼n−1这个范围中，存在一组满足 a[1]==a[i]并且 a[i+1]==a[n]，那么2次就可以删掉，输出2，否则也不能删除。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int a[N];
int main(){
	freopen("num.in","r",stdin);
    freopen("num.out","w",stdout);
    int n; 
    cin>>n;
    for(int i=1;i<=n;i++){
    	cin>>a[i];
	}
    if(n==1){
       cout<<-1;
       return 0;
	}
    else if(a[1]==a[n]){
       cout<<1;
       return 0;
	}
    else{
    	for(int i=2;i<n-1;i++){
    		if(a[1]==a[i]&&a[i+1]==a[n]){
    			cout<<2;
    			return 0;
			}
		}
	}
	cout<<-1;
	return 0;
}

这题在写的时候忘了写特判了，下次要注意到。

B. 小田的气球爆炸啦

题目类型：分类讨论

思路

这题也可以根据不同的情况分类讨论：

• 若n==2，且气球​一样多，输出0。
• 若最大值比其他数的总和还大时，必然只能留下最大值的气球，所以只能输出1。
• 若数量是​奇数，每种气球都可以留下来，输出n。
• 若数量是​偶数​，只要气球的数量大于1，就可以留下来，cnt++。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N];
int main(){
    freopen("balloon.in","r",stdin);
    freopen("balloon.out","w",stdout);
    int n,ma=0,ans=0;
    long long sum=0;
    cin>>n;
    for(int i=1;i<=n;i++){
    	cin>>a[i];
    	sum+=a[i];
    	ma=max(a[i],ma);
    	if(a[i]>1) ans++;
	}
	if(n==2&&a[1]==a[2]) cout<<0;
	else if(ma>=sum-ma) cout<<1;
	else if(sum&1) cout<<n;
	else cout<<ans;
	return 0;
}

这题在写的时候也忘了写特判了，下次要注意到。

C. 小k的加减游戏

题目类型：模拟或搜索

思路

模拟

直接找最大值进行运算即可。

搜索

先​搜索所有情况​，若答案存在，就一定可以找到，然后输出，若答案不存在，​递归会于某一层终止，然后输出-1​。

代码

模拟

#include<bits/stdc++.h>
using namespace std;
int main(){
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    long long n,a,b,c;
    string st;
    cin>>n>>a>>b>>c;
    for(int i=1;i<=n;i++){
    	string s;
    	cin>>s;
    	if(s=="AC"){
    		if(a>=c){
    			a--;
    			c++;
    			st+="C"; 
			}
			else{
				c--;
    			a++;
    			st+="A";
			}
		}
		else if(s=="AB"){
    		if(a>=b){
    			a--;
    			b++;
    			st+="B";
			}
			else{
				b--;
    			a++;
    			st+="A";
			}
		}
		else{
    		if(b>=c){
    			b--;
    			c++;
    			st+="C";
			}
			else{
				c--;
    			b++;
    			st+="B";
			}
		}
		if(a<0||b<0||c<0){
		cout<<"No";
		return 0;
	}
	}
	cout<<"Yes"<<endl;
	for(int i=0;i<=st.size()-1;i++) cout<<st[i]<<endl;
	return 0;
}

搜索

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n;
string s[N],d[N];
void dfs(int x,int a,int b,int c){
	if(x>n){
		cout<<"Yes"<<endl;
		for(int i=1;i<=n;i++){
			cout<<d[i]<<endl;
		}
		exit(0);
	}
	if(s[x]=="AB"){
		if(a) d[x]="B",dfs(x+1,a-1,b+1,c);
		if(b) d[x]="A",dfs(x+1,a+1,b-1,c);
	}

	if(s[x]=="AC"){
		if(a) d[x]="C",dfs(x+1,a-1,b,c+1);
		if(c) d[x]="A",dfs(x+1,a+1,b,c-1);
	}

	if(s[x]=="BC"){
		if(b) d[x]="C",dfs(x+1,a,b-1,c+1);
		if(c) d[x]="B",dfs(x+1,a,b+1,c-1);
	}
}
int main(){
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
	int a,b,c;
	cin>>n>>a>>b>>c;
	for(int i=1;i<=n;i++) cin>>s[i];
	dfs(1,a,b,c);
	cout<<"No";
	return 0;
}

这题在写的时候把-1写上了，下次要注意字符串的大小。

D. 蓬莱山仙峰台

题目类型：模拟或邻接表

思路

模拟

先假设所有观景台​都是仙峰台,cnt=n，若u,v存在高度h[u]>h[v]，则v不再满足条件，cnt--,最后输出答案。

邻接表

建造一个图，再来遍历，输出。

代码

模拟

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],b[N];
int main(){
	freopen("penglai.in", "r", stdin);
    freopen("penglai.out", "w", stdout);
	int n,m;
	cin>>n>>m;
	int ans=n;
	for(int i=1;i<=n;i++) cin>>a[i];
	while(m--){
		int x,y;
		cin>>x>>y;
		if(a[x]>a[y]) if(b[y]==0) b[y]=1,ans--;
		if(a[x]<a[y]) if(b[x]==0) b[x]=1,ans--;
		if(a[x]==a[y]){
			if(b[x]==0) b[x]=1,ans--;
			if(b[y]==0) b[y]=1,ans--;
		}
	}
	cout<<ans;
	return 0;
}

邻接表

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+20;
int h[N],e[N],ne[N],idx,a[N];
void add(int a,int b){
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int main(){
	freopen("penglai.in", "r", stdin);
	freopen("penglai.out", "w", stdout);
	int n,m;
	cin>>n>>m;
	memset(h,-1,sizeof h);
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		bool flag=true;
		for(int j=h[i];j!=-1;j=ne[j]){
			int id=e[j];
			if(a[id]>=a[i]){
				flag=false;
				break;
			} 
		}
		if(flag) ans++;
	}
 	cout<<ans;
	return 0;
}

这题不知道怎么连接，所以就放弃了，下次应该再多想一下。

E. 数学题1

题目类型：数学

思路

我们发现bgcd(a,b) 必然为b的倍数，那么bgcd(a,b)的倍数a+b也必然为b的倍数。所以，a必然为b的倍数。因为a为b的倍数，所以gcd(a,b)=b，原式可以化为a+b=x(bb),其中x为正整数。后面再简化后可得(a+b)%(bb)==0这个判断条件。

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
	freopen("math1.in","r",stdin);
	freopen("math1.out","w",stdout);
	int n,m,ans=0;
	cin>>n>>m;
	for(long long b=1;b<=m;b++) for(long long a=b;a<=n;a+=b) if((a+b)%(b*b)==0) ans++;
	cout<<ans;
	return 0;
}

这道题本来在想，想到后面实在不知道怎么想了，放弃了，下次应该再在想一下。

F. 小z的徒步旅行

题目类型：DP

思路

状态计算：sum+=(r[j]∗r[k]−l[j]∗l[k])∗f[i−1][k]。

注意：写完之后答案还要取模1e9+10;

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD=1e9+7;
int s[110],l[110],r[110],f[1010][110],n,m;
signed main(){
	freopen("walk.in","r",stdin);
	freopen("walk.out","w",stdout); 
	cin>>m>>n;
	for(int i=1;i<=m;i++) cin>>s[i];
	for(int i=1;i<=m;i++){
		cin>>l[i];
		r[i]=l[i]+s[i];
	}
	f[0][1]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int sum=0;
			for(int k=1;k<=m;k++){
				sum+=(r[j]*r[k]-l[j]*l[k])*f[i-1][k];
				sum%=MOD;
			}
			f[i][j]=sum;
		}
	}
	int ans=0;
	for(int i=1;i<=m;i++){
		ans+=f[n][i];
		ans%=MOD;
	}
	cout<<ans;
	return 0;
}

DP还没有学过，老师说以后会单独开一节课来讲DP。