T1 小田的消消乐游戏（暴力）
考试时： 问题：这题是我最后写的，一开始以为是暴力就写了下就过了（35分），最后也是列了很多数据找到的规律才A的，以后要多做此类题提升对题目思路的敏锐
思路
第一眼看是道搜索题，实际5×10^5时间肯定过不了，所以要找别的方法
但是数据只有0和1（0≤a[i]≤1），所以数组的头和尾一定是不同的（相同一次就消了），对于一个数组a，我们寻找一个i使得a[i]==a[1]&&a[i+1]==a[n]这样就可以两次消除
那么有没有一个数据，使得一个更优的方法因为不满足如上条件而导致答案错误呢？
答案是没有，因为如果两次可以消掉，那么就一定满足如上条件，但还会有3次及以上的数据，可数据只有0和1，所以如果出现3次及以上的相同就一定可合并使得答案步数更少。
附AC代码
#include<bits/stdc++.h>
using namespace std;
int a[500010],n,t,w;
int main()
{
freopen("num.in","r",stdin);
freopen("num.out","w",stdout);
cin>>n;
cin>>t;
for(int i=2;i<n;i++)
{
cin>>a[i];
}
cin>>w;
if(t==w)
{
cout<<1;
return 0;
}
for(int i=2;i<n-1;i++)
{
if(a[i]==t&&a[i+1]==w)
{
cout<<2;
return 0;
}
}
cout<<-1;
return 0;
}
T2 小田的气球爆炸啦( 暴力 )
考试时：
错因1：考试时没有考虑那么多细节(n==2和巨无霸)，丢了很多分，有些细节还是后面检查才发现的
补题时：
错因2：最后还是没有考虑到n=2时的特判，以后要多用草稿纸分类讨论
思路
这道题大体思路比较简单，但还有很多特判和细节，所以还是不简单的
对于一个数组a[]，如果有一个数a[i]比其他所有数的总和 都大，那么不管他们怎么碰撞，总会只留下a[i]这一种气球（因为哪怕所有其他种类的气球都和a[i]碰，a[i]也会有剩下的）
而如果没有"巨无霸"就要想正常情况了
因为气球是两两消除的，所以气球总数是奇数时就总会剩下一个气球（拿出1个要剩下种类的气球，两两匹配消除即可），偶数时数量只有1的气球就一定不会被剩下（因为只剩一种气球时最少要留下2个相同颜色的气球，不相同就会碰撞消失）
最后还有一种n==2&&a[1]==a[2]的情况要特判（气球一定两两相撞消失）
附AC代码：
#include<bits/stdc++.h>
using namespace std;
int d,n,a[100010];
int main()
{
freopen("balloon.in","r",stdin);
freopen("balloon.out","w",stdout);
cin>>n;
long long b=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
b+=a[i];
d=max(a[i],d);
}
if(n==2&&a[1]==a[2])
{
cout<<0;
return 0;
}
if(d>=b-d)
{
cout<<1;
return 0;
}
if(b%2==0)
{
int ans=0;
for(int i=1;i<=n;i++)
{
if(a[i]>1) ans++;
}
cout<<ans;
}
else
{
cout<<n;
}
return 0;
}
T3小k的加减游戏（贪心）
总结（自己）
秒的
思路
选最小加，选最大的减的即可
代码：
#include<bits/stdc++.h>
using namespace std;
int n,a[10];
char g1,g2;
char cz[100010];
int main()
{
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
cin>>n;
cin>>a[0]>>a[1]>>a[2];
for(int i=1;i<=n;i++)
{
cin>>g1>>g2;
int d=g1-'A',e=g2-'A';
if(a[d]>a[e])
{
a[d]--;
a[e]++;
cz[i]=g2;
}
else
{
a[e]--;
a[d]++;
cz[i]=g1;
}
if(a[e]<0||a[d]<0)
{
cout<<"No";
return 0;
}
}
cout<<"Yes"<<endl;
for(int i=1;i<=n;i++)
{
cout<<cz[i]<<endl;
}
return 0;
}
T4蓬莱山仙峰台
总结（自己）
真没有(~老师原谅我这天做的太好了[自恋]~)
思路
用边便利，每次将不符合题目要求的标记，最后未标记的就是仙峰台
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,ans,g[100010],p[100010];
int main()
{
freopen("penglai.in","r",stdin);
freopen("penglai.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>g[i];
}
for(int i=1;i<=m;i++)
{
int q,z;
cin>>q>>z;
if(g[q]>g[z]) p[z]=1;
else if(g[q]==g[z])
{
p[z]=1;
p[q]=1;
}
else p[q]=1;
}
for(int i=1;i<=n;i++)
{
// cout<<p[i]<<" ";
if(p[i]==0) ans++;
}
cout<<ans;
return 0;
}
// 1 0 0 1 0 0
T5数学题1（数学）
总结（自己）
这道题其实还可以在思考加深一些，虽然我的想法可以过，但是还有时间复杂度更低的方法
思路
a+b要是b的倍数 则a也是b的倍数
因为a和b都是b的倍数 所以ab有倍数关系
他们的公因数是小的那个数
b有两种情况
b==a
b<a
因为b是b的最小倍数 所以a要么相等 要么比b大
所以其实就是a+b=b*b
#include<bits/stdc++.h>
using namespace std;
long long n,m,ans;
int main()
{
freopen("math1.in","r",stdin);
freopen("math1.out","w",stdout);
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;
}
T6小z的徒步旅行
总结（自己）
这是我唯一没写的一道题，下次要多打草稿
思路
dp三要素
f[i][j]定义：在第i天的第j个房子的方案数
初始化 f[1][0]=1(第0天在第1个房子有1种方案)
递推式 便利天数i 便利终点j 起点k f[i][j]+=(j到湖的路径总数*k到湖的路径-j到湖的长路数*k到湖的长路)*f[i-1][k]
有递推式随便A,注意下long long和mod就行
#include<bits/stdc++.h>
using namespace std;
long long c[1010],d[1010],r[1010],f[1010][110],n,t;
const int MOD=1e9+7;
int main()
{
freopen("walk.in","r",stdin);
freopen("walk.out","w",stdout);
cin>>n>>t;
for(int i=1;i<=n;i++)
{
cin>>d[i];
}
for(int i=1;i<=n;i++)
{
cin>>c[i];
r[i]=d[i]+c[i];
}
f[0][1]=1;
for(int i=1;i<=t;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=1;k<=n;k++)
{
f[i][j]+=((r[k]*r[j]-c[k]*c[j])%MOD)*f[i-1][k]%MOD;
}
}
}
long long ans=0;
for(int i=1;i<=n;i++)
{
ans+=f[t][i];
ans%=MOD;
}
cout<<ans;
return 0;
}
