T1小田的最大价值（贪心）
总结（自己）
sort写错了 下次自己没有了解东西的不要乱写
思路
看最小和最大满不满足要求即可
附AC代码
#include<bits/stdc++.h>
using namespace std;
int n,a[200010],k;
int main()
{
freopen("max.in","r",stdin);
freopen("max.out","w",stdout);
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+n+1);
if(a[n]-a[1]>k) cout<<a[n];
else cout<<a[n-1];
return 0;
}
T2小田的交换数字（暴力）
总结（自己）
没什么问题（有些人拿高精度写的hhh）
思路
定个 long long 按位乘再取模就行
附AC代码
#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353;
string a,b;
long long c,d,n;
int main()
{
freopen("mul.in","r",stdin);
freopen("mul.out","w",stdout);
cin>>n>>a>>b;
for(int i=0;i<n;i++)
{
if(a[i]<b[i]) swap(a[i],b[i]);
c=(c*10+a[i]-'0')%MOD;
d=(d*10+b[i]-'0')%MOD;
}
cout<<c*d%MOD;
return 0;
}
T3小田的气球真好看(dp)
总结（自己）
双指针也可写，但作者写的bug还没de出来www
思路
先定义一个flag[i]表示i种类的气球最近的是哪个位置
DP三要素
f[i]定义：以i结尾的方案总数
初始化：
flag[a[1]]=1 f[1]=1
递推式：
如果后面可以接 那么f[i]=min(f[j]+i-flag[a[i]]（全都是好看的区间）) 否则 f[i]=min(i-j（超过flag[a[i]]的都不是好看的区间）)
但有个细节（long long不用说）因为最多只会有f[i-1]+1个区间以i结尾，所以还要取个min（同时受限于两个条件）
随便A
附AC代码
#include<bits/stdc++.h>
using namespace std;
long long f[110000],k,a[100010],n,flag[110000];
int main()
{
freopen("balloon.in","r",stdin);
freopen("balloon.out","w",stdout);
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
flag[a[1]]=1;
f[1]=1;
for(long long i=2;i<=n;i++)
{
long long j=flag[a[i]];
flag[a[i]]=i;
if(i-j<=k) f[i]=min(f[j]+i-j,f[i-1]+1);
else f[i]=min(i-j,f[i-1]+1);
}
long long ans=0;
for(int i=1;i<=n;i++)
{
ans+=f[i];
}
cout<<ans;
return 0;
}
T4表达式求值（栈）
总结（自己）
思路错了 而且最后还没de出bug
思路
遇状遇符遇左（括号）入（栈） 遇到右括再计算
附AC代码
#include<bits/stdc++.h>
using namespace std;
int t,tt1=-1,idx=0,tt2=-1;
string a;
char f[1005],z[1005];
int main()
{
freopen("expr.in","r",stdin);
freopen("expr.out","w",stdout);
cin>>t;
while(t--)
{
stack<int> f,z;
cin>>a;
int n=a.size();
for(int i=0;i<n;i++)
{
if(a[i]=='t'||a[i]=='f'||a[i]=='(') z.push(a[i]);
else if(a[i]=='!'||a[i]=='&'||a[i]=='|') f.push(a[i]);
else if(a[i]==')')
{
int idx=-1;
string b="";
char l;
if(f.top()=='!'){
if(z.top()=='t') z.pop(),z.pop(),z.push('f');
else z.pop(),z.pop(),z.push('t');
f.pop();
continue;
}
while(z.top()!='(') b+=z.top(),z.pop();
z.pop();
if(f.top()=='&') l='t';
else if(f.top()=='|') l='f';
for(int i=0;i<b.size();i++){
if(f.top()=='&'&&b[i]=='f'){
l='f';
break;
}
else if(f.top()=='|'&&b[i]=='t'){
l='t';
break;
}
}
f.pop();
z.push(l);
}
}
if(z.top()=='t') cout<<"true"<<endl;
else cout<<"false"<<endl;
}
return 0;
}
T5小W去冒险(搜索)
总结（自己）
没什么问题（本人的dfs还行）
思路
用dfs标记即可
附AC代码
#include<bits/stdc++.h>
using namespace std;
bool b[110][110];
int f[10][2]={{1,0},{0,1},{-1,0},{0,-1}};
int a[110][110],n,m,ans;
void dfs(int x,int y)
{
b[x][y]=1;
for(int i=0;i<4;i++)
{
int nx=x+f[i][0],ny=y+f[i][1];
if(b[nx][ny]==0&&nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]!=0) dfs(nx,ny);
}
}
int main()
{
freopen("ymx.in","r",stdin);
freopen("ymx.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char k;
cin>>k;
a[i][j]=k-'0';
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i][j]!=0&&b[i][j]==0){
ans++;
dfs(i,j);
}
cout<<ans;
return 0;
}
T6检查总结（dp）
总结（自己）
没时间骗分了www
思路
dp三要素：
f[i]定义：从n到i这个区间的最少删除数
初始化 f[n]=1
递推式
要么删 f[i+1]+1
要么不删 f[i+a[i]+1]
取个min就行
随便A
附AC代码
#include<bits/stdc++.h>
using namespace std;
int n,f[2000010],a[2000010];
int main()
{
freopen("summary.in","r",stdin);
freopen("summary.out","w",stdout);
memset(f,0x3f,sizeof(f));
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
f[n]=1;
for(int i=n;i>=1;i--)
{
f[i]=min(f[i+1]+1,f[i+a[i]+1]);
}
cout<<f[1];
return 0;
}
