总结
第一类：思考题
小田的最大价值（基础）
思路
这里明显的知道MAX比MIN更值！ 所以，只有在迫不得以才会用MIN！
题解
#include<bits/stdc++.h>
using namespace std;
int a[200010];
int main(){
freopen("max.in","r",stdin);
freopen("max.out","w",stdout);
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+1+n);
if(a[n]-a[1]<=k){
cout<<a[n-1];
}else{
cout<<a[n];
}
return 0;
}
注意的点
无。
题目传送门，启动!
小田的交换数字（中等）
思路
用数理的思想，两个数的差值最大化。 这样乘积才会最少，使得取余后最小!
在计算过程中，要不断取余！ 数据才不会溢出。
题解
#include<bits/stdc++.h>
using namespace std;
bool cmp(string a,string b){
if(a.size()!=b.size()){
return a.size()>b.size();
}
for(int i=0;i<a.size();i--){
if(a[i]!=b[i]){
return a[i]>b[i];
}
}
return true;
}
long long add(vector<int> a){
long long t=0,r=0,op=998244353;
vector<int> c;
for(int i=a.size()-1;i>=0;i--){
t=r*10+a[i];
c.push_back(t/op);
r=t%op;
}
return r;
}
int main(){
freopen("mul.in","r",stdin);
freopen("mul.out","w",stdout);
int n;
cin>>n;
string A,B;
cin>>A>>B;
if(cmp(B,A)){
string h=A;
A=B;
B=h;
}
int i=B.size()-1;
while(i>=0){
if(A[i]<B[i]){
char u=B[i];
B[i]=A[i];
A[i]=u;
}
i--;
}
vector<int> a,b;
for(int i=A.size()-1;i>=0;i--){
a.push_back(A[i]-'0');
}
for(int i=B.size()-1;i>=0;i--){
b.push_back(B[i]-'0');
}
long long sa=add(a),sb=add(b),op=998244353;
cout<<(long long)((sa*sb)%op);
return 0;
}
注意的点
注意：取余过程要用高精度，最后输出用long long
反思：
当时想歪了，没有想到可以先取余再乘上， 所以以后注意优化的点，尽量往小去想，除法用逆元，乘法直接搞！
题目传送门，启动!
第二类：简单算法题
小田的气球（中等~困难）
思路
第一种：双指针（困难）
1，枚举起点l，以这个为起点,找到最后一个满足条件的r，这个区间有多长，就有多少个子区间：1，12，123……
2.如何判断满足条件，用标记数组
3.要更新标记数组
需要注意的是当l往右走时，如果值是记录在标记数组的最后一个位置，则需要消除
第二种：DP（较为基础）
f[i]表示以a[i]为结尾的合法区间的数量。
辅助数组 j=flag[a[i]]颜色为a[i]的气球上次出现的位置是j 初始化： f[1]=1,flag[a[1]]=1
1.条件：j==0:f[i]=min(i,f[i-1]);
因为这样只必定 不会超i，所以两个条件选 小的
2.条件：i-j<=k:f[i]=min(f[i]+i-j,f[i-1]+1) 因为 3.条件：i-j>k:f[i]=min(i-j,f[i-1]+1)
因为f[i]是以i颜色为结尾的区间数量
所以要排除j个数。
答案：f[1]+……+f[n]
题解(DP)
#include<bits/stdc++.h>
using namespace std;
int a[100010],flag[100010],f[100010];
int main(){
freopen("balloon.in", "r", stdin);
freopen("balloon.out", "w", stdout);
long long s=1;
int n,k;
cin>>n>>k;
f[1]=1;
for(int i=1;i<=n;i++){
cin>>a[i];
}
flag[a[1]]=1;
for(int i=2;i<=n;i++){
int j=flag[a[i]];
if(j==0){
f[i]=min(i,f[i-1]);
}
if(i-j<=k){
f[i]=min(f[j]+i-j,min(f[i-1]+1,i));
}
if(i-j>k){
f[i]=min(i-j,f[i-1]+1);
}
flag[a[i]]=i;
s+=f[i];
}
cout<<s;
return 0;
}
较难的算法应用
D. 表达式求值（中等）
思路
这题是一个很简单的手动模拟c++运行的题型。也是表达式类的典型例题。 所以是十分简单！搞不懂为什么只有我一个学生做出来了。
废话不多说，这题只是单纯模拟，不过只是加一个栈而已，是模板题
题目传送门，启动!
题解
#include<bits/stdc++.h>
using namespace std;
int main(){
freopen("expr.in","r",stdin);
freopen("expr.out","w",stdout);
int t;
cin>>t;
while(t--){
string a;
stack<char> op;
stack<char> ture;
cin>>a;
for(int i=0;i<a.size();i++){
if(a[i]=='t') ture.push('t');
if(a[i]=='f') ture.push('f');
if(a[i]==',') op.push(',');
if(a[i]=='&'){
op.push('&');
op.push('(');
}
if(a[i]=='|'){
op.push('|');
op.push('(');
}
if(a[i]=='!'){
op.push('!');
op.push('(');
}
if(a[i]==')'){
int res=1;
while(op.top()!='('){
op.pop();
res++;
}
//cout<<res<<endl;
op.pop();
if(op.top()=='!'){
for(int i=1;i<=res;i++){
char now=ture.top();
if(now=='f'){
ture.pop();
ture.push('t');
}else{
ture.pop();
ture.push('f');
}
}
}
else if(op.top()=='&'&&res>1){
bool st=1;
for(int i=1;i<=res;i++){
char now=ture.top();
if(now=='f'){
st=0;
}
ture.pop();
}
if(st){
ture.push('t');
}else{
ture.push('f');
}
}else{
bool st=0;
for(int i=1;i<=res;i++){
char now=ture.top();
if(now=='t'){
st=1;
}
ture.pop();
}
if(st){
ture.push('t');
}else{
ture.push('f');
}
}
op.pop();
}
}
if(ture.top()=='t'){
cout<<"true"<<endl;
}else{
cout<<"false"<<endl;
}
}
return 0;
}
反思：
本次题目做得不错但代码太长了，如果错了的话会 很难找到错误!!!
下次要简单直接，向判断中多位循环可以合并， 用bool来引向，就更简洁！
E. 小W去冒险（基础）
思路
纯爆搜！，用深搜就可以！
注意的是ans最好在主函数中编写，因为递归函数循环完时，必定会返回主函数！！
题目传送门，启动！
题解
#include<bits/stdc++.h>
using namespace std;
int dx[6]={1,0,-1,0},dy[6]={0,1,0,-1},a[110][110],n,m;
bool st[110][110];
long long ans=0;
void dvs(int x,int y){
st[x][y]=1;
a[x][y]=0;
for(int i=0;i<4;i++){
int nx=dx[i]+x,ny=dy[i]+y;
if(!(st[nx][ny])&&a[nx][ny]!=0&&nx>=0&&ny>=0&&nx<=n&&ny<=m){
dvs(nx,ny);
}
}
return;
}
int main(){
freopen("ymx.in","r",stdin);
freopen("ymx.out","w",stdout);
cin>>n>>m;
char cs;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>cs;
a[i][j]=cs-'0';
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]!=0){
dvs(i,j);
ans++;
}
}
}
cout<<ans;
return 0;
}
反思
这一题模板没背熟，才会拉下100分
最短路模板也要背！
F. 检查总结（困难偏上）
思路
本题是一道DP题，思路上来说有点复杂
在这一题中，f[i]不再表示成1~i合并的最少步数，而是i~n的最少步数，所以要从n开始遍历！
我们来看公式：
f[i]=min(f[i+1]+1,f[i+a[i]+1);
删除a[i] (f[i+1]+1) ：上一个的步数加上这一次删除用的步数。
不删a[i] (f[i+a[i]+1],前提：i+a[i]<=n) ：不删所以要之前的a[i]个都不是题数所以i+a[i]就是求最后的评分的位置。而+1就可以知道上一次的步数！
初始化： f[n]=1,f[n+1]=0;
题目传送门，启动！
题解
#include<bits/stdc++.h>
using namespace std;
int f[200010],a[200010];
int main(){
freopen("summary.in","r",stdin);
freopen("summary.out","w",stdout);
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
f[n]=1;
f[n+1]=0;
for(int i=n;i>=1;i--){
if(i+a[i]<=n){
f[i]=min(f[i+1]+1,f[i+a[i]+1]);
}
else{
f[i]=f[i+1]+1;
}
}
cout<<f[1];
return 0;
}
