小田的消消乐游戏（暴力）

思路没想到的原因

没有想到一种特判，具体见思路。

思路

因为数字只由 $0$和 $1$组成，所以只有以下几种情况：

• 头尾数字相同，只需要删除一次；
• 头尾数字不同，但是在 $2 \sim n-1$这个范围中，存在一组相邻的数字，满足 $a[1] == a[i]$且 $a[i+1] == a[n]$，那么 $2$次就可以删掉，否则不能删除，比如 $1 1 1 1 0$；（没想到）
• 特殊情况，只有一个数字，无法删除。

代码

#include <bits/stdc++.h>
using namespace std;

const int N=5e5+10;
int f[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 >>f[i];
	if(n==1){
		cout <<"-1";
		return 0;
	}
	else if(f[1]==f[n]){
		cout <<1;
		return 0;
	}
	else{
		for(int i=2;i<n-1;i++){
			if(f[1]==f[i]&&f[i+1]==f[n]){
				cout <<"2"<<endl;
				return 0;
			}
		}
	}
	cout <<"-1";
	return 0;
}

小田的气球爆炸啦（暴力）

思路没想到的原因

没有写特判，具体见思路。

思路

分类讨论的题目，条件如下：

• 两种气球一样多，只能是$0$; 否则，最大值比其他数的总和还大时，必然只能留下最大值的气球；
• 数量是奇数，每种气球都可以留下来；（没想到）
• 数量是偶数，只要气球的数量大于$1$，就可以留下来。（没想到）

代码

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+10;
int f[N];

int main(){
	freopen("balloon.in","r",stdin);
	freopen("balloon.out","w",stdout);
	int n,res=0,m=-1;
	cin >>n;
	long long sum=0;
	for(int i=1;i<=n;i++){
		cin >>f[i];
		m=max(m,f[i]);
		sum+=f[i];
		if(f[i]>1) res++;
	}
	if(n==2&&f[1]==f[2]) cout <<0;
	else if(m>=sum-m) cout <<1;
	else if(sum&1) cout <<n;
	else cout <<res;
	return 0;
}

小k的加减游戏（dfs深搜）

思路没想到的原因

本来想用模拟，但没写出来，就放弃了。所以以后不能轻易放弃。

思路

$dfs$深搜所有情况，如答案存在，就一定可以找到，然后输出；

如答案不存在，递归会于某一层终止。

代码

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+10;
int n;
string s[N],ans[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 <<ans[i]<<endl;
		}
		exit(0);
	}
	if(s[x]=="AB") {
		if(a) ans[x]="B",dfs(x+1,a-1,b+1,c);
		if(b) ans[x]="A",dfs(x+1,a+1,b-1,c);
	}

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

	if(s[x]=="BC") {
		if(b) ans[x]="C",dfs(x+1,a,b-1,c+1);
		if(c) ans[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;
}

蓬莱山仙峰台（数据结构）

思路没想到的原因

没打草稿，导致没有写出来。以后要多打草稿。

思路

假设所有观景台都是仙峰台，若存在观景台$u$，$v$，高度$h[u] > h[v]$，则$v$不再满足条件。

代码

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+10;
bool st[N];
int h[N];

int main(){
    freopen("penglai.in","r",stdin);
    freopen("penglai.out","w",stdout);
    int n,m;
	cin >>n>>m;
    for(int i=1;i<=n;i++) cin >>h[i];
    for(int i=1;i<=n;i++) st[i]=1;
    for(int i=1;i<=m;i++){
        int u,v; 
        cin >>u>>v;
        if(h[u]>=h[v]){
        	st[v]=0;
		}
        if(h[v]>=h[u]){
        	st[u]=0;
		}
    }
    int cnt=0;
    for(int i=1;i<=n;i++){
    	cnt+=st[i];
	}
    cout <<cnt<<endl;
    return 0;
}

数学题1（数学）

思路没想到的原因

推出了公式，但在循环方面超时了。以后要注意时间复杂度。

思路

我们发现$b*gcd(a,b)$ 必然为$b$的倍数，那么$b*gcd(a,b)$的倍数$a+b$也必然为$b$的倍数。

所以，$a$必然为$b$的倍数。因为$a$为$b$的倍数，所以$gcd(a,b) = b$，原式可以化为$a+b=xb^2$,其中$x$为正整数。

代码

#include <bits/stdc++.h>
using namespace std;

int main(){
	freopen("math1.in","r",stdin);
	freopen("math1.out","w",stdout);
	long long n,m;
	long long 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;
}

小z的徒步旅行（DP）

思路没想到的原因

$DP$的积累还不够，以后要多积累。

思路

做$DP$的题，就要找到“状态表示”与“状态计算”，具体见下：

状态表示：$dp[i][j]$:第$i$天时在第$j$个小屋的方案数

状态计算：$sum += (r[j] * r[k] - l[j] * l[k]) * dp[i - 1][k]$

且注意：答案要取模 $10^9 + 7$,所以一定要记得$$!!!

代码

#include <bits/stdc++.h>
using namespace std;

const int MOD=1e9+7;
long long n,m,s[110],l[110],r[110],dp[1010][110];
bool f[100010];

int main(){
	freopen("walk.in","r",stdin);
	freopen("walk.out","w",stdout);
	cin >>m>>n;
	for(long long i=1;i<=m;i++) cin >>s[i];
		for(long long i=1;i<=m;i++){
			cin >>l[i];
			r[i]=l[i]+s[i];
	}
	dp[0][1]=1;
	for(long long i=1;i<=n;i++){
		for(long long j=1;j<=m;j++){
			long long sum=0;
			for(int k=1;k<=m;k++){
				sum+=(r[j]*r[k]-l[j]*l[k])*dp[i-1][k];
				sum%=MOD;
			}
			dp[i][j]=sum;
		}
	}
	long long sum=0;
	for(long long i=1;i<=m;i++){
		sum+=dp[n][i];
		sum%=MOD;
	}
	cout <<sum;
	return 0;
}

谢谢