小田的最大价值（暴力）

思路

我们先把数组排序，输出有两种情况：

• 如果$a[n-1]-a[0]>k$，输出$max(a[n-1],a[0])$；
• 否则输出$min(a[n-1],a[n-2])$。

代码

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

const int tt=1e5+10;
int a[tt];

int main(){
	freopen("max.in","r",stdin);
	freopen("max.out","w",stdout);
	int n,k;
	cin >>n>>k;
	for(int i=0;i<n;i++){
		cin >>a[i];
	}
	sort(a,a+n);
	if(a[n-1]-a[0]>k){
		cout <<max(a[n-1],a[0]);
	}else{
		cout <<min(a[n-1],a[n-2]);
	}
	return 0;
}

小田的交换数字（数学）

思路没想到的原因

把题目想太复杂了，还以为要用高精度算法。

思路

我们举一个例子，$5*5=25$,但$4*6=24$,说明两个数字差值越大，乘积越小。

所以我们只需把每个数位最小与最大的分成两个数字即可。

代码

#include <bits/stdc++.h>
#define int unsigned long long
using namespace std;

const int mod=998244353;

signed main(){
	freopen("mul.in","r",stdin);
	freopen("mul.out","w",stdout);
	int n;
	cin >>n;
	string a,b;
	cin >>a>>b;
	int s1=0,s2=0;
	for(int i=0;i<a.size();i++){
		s1=(s1*10+max(a[i],b[i])-'0')%mod;
		s2=(s2*10+min(a[i],b[i])-'0')%mod;
	}
	cout <<(int)((s1%mod)*(s2%mod))%mod;
	return 0;
}

小田的气球真好看（DP/双指针）

思路没想到的原因

在写的时候，没有所有变量开$long$ $long$,以后要注意开$long$ $long$!!!

思路

方法一：$DP$

状态表示：$f[i]$表示以$a[i]$结尾的合法区间的数量

状态计算：

• 如果$flag[a[i]]=0$，那么$f[i]=min(i,f[i-1]+1)$;
• 如果$i-flag[a[i]]<=k$，那么$f[i]=min(f[j]+i-j,f[i-1]+1)$;
• 如果$i-flag[a[i]]>k$，那么$f[i]=min(i-j,f[i-1]+1)$。

还有，不要忘记更新$flag[a[i]]$与$cnt$!

方法二：双指针

枚举起点$l$，以这个为起点，找到最后一个满足条件的$r$，这个区间有多长，就有多少个子区间。

👀️代码

方法一：$DP$

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

long long a[100010],f[100010],flag[100010];

int main(){
	freopen("balloon.in","r",stdin);
	freopen("balloon.out","w",stdout);
	long long n,k;
	cin >>n>>k;
	for(int i=1;i<=n;i++){
		cin >>a[i];
	}
	long long cnt=0;
	f[1]=1;
	flag[a[1]]=1;
	for(long long i=2;i<=n;i++){
		int j=flag[a[i]];
		if(j==0) f[i]=min(i,f[i-1]+1);
		if(i-j<=k) f[i]=min(f[j]+i-j,f[i-1]+1);
		if(i-j>k) f[i]=min(i-j,f[i-1]+1);
		flag[a[i]]=i;
		cnt+=f[i];
	}
	cout <<cnt+1;
	return 0;
}

方法二：$双指针$

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

const int N=1e5+5;  
int n,k,a[N],flag[N];  
long long res;  

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];
	}
	int l=1,r=0;
	while(l<=n){
		while(r<n&&(r+1-flag[a[r+1]]<=k||!flag[a[r+1]])){
			r++;
			flag[a[r]]=r;
		}
		res+=r-l+1;
		if(flag[a[l]]==l){
			flag[a[l]]=0;
		}
		l++;
	}
	cout <<res;
	return 0;
}

表达式求值（数据结构）

思路没想到的原因

没有理清思路，思路很乱。以后先在草稿上模拟一遍，在写代码。

思路

几个步骤，具体如下：

• 如果当前$s[i]$是$|$,或$!$,或$\&\$,就入符号栈；
• 如果当前$s[i]$是$($,或$t$,或$f$,就入数字栈；
• 如果当前$s[i]$是$)$，就一直把数字弹出，并弹出符号，进行运算。直到遇上$($；
• 最后答案是数字栈的顶端。

代码

#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 s;
		cin >>s;
		stack<char> fh,sz;
		for(int i=0;i<s.size();i++){
			if(s[i]=='!'||s[i]=='|'||s[i]=='&'){
				fh.push(s[i]);
			}else if(s[i]=='('||s[i]=='f'||s[i]=='t'){
				sz.push(s[i]);
			}else if(s[i]==')'){
				bool ans;
				if(sz.top()=='t') ans=1;
				else if(sz.top()=='f') ans=0;
				char v=fh.top();
				fh.pop();
				if(v=='!'){
					sz.pop();
					if(ans==1) sz.push('f');
					else sz.push('t');
				}else{
					while(sz.top()!='('){
						bool p;
						if(sz.top()=='t') p=1;
						else if(sz.top()=='f') p=0;
						if(v=='|') ans=ans||p;
						else if(v=='&') ans=ans&&p; 
						sz.pop();
					}
					sz.pop();
					if(ans==1) sz.push('t');
					if(ans==0) sz.push('f');
				}
			}
		}
		if(sz.top()=='t'){
			cout <<"true"<<endl;
		}else if(sz.top()=='f'){
			cout <<"false"<<endl;
		}
	}
	return 0;
}

小W去冒险（dfs深搜）

思路

用$dfs$搜区间，如果返回$0$，则不是区间，否则$ans++$。

代码

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

int g[1010][1010];
int vis[1010][1010];
int n,m;

void i(){
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			g[i][j]=0;
			vis[i][j]=0;
		}
	}
}

int dfs(int x,int y){
	if(x>=n||x<0||y>=m||y<0) return 0;
	if(!g[x][y]) return 0;
	if(vis[x][y]) return 0;
	vis[x][y]=1;
	return g[x][y]+dfs(x+1,y)+dfs(x-1,y)+dfs(x,y+1)+dfs(x,y-1);
}

int main(){
	freopen("ymx.in","r",stdin);
	freopen("ymx.out","w",stdout);
	cin >>n>>m;
	i();
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			char w;
			cin >>w;
			if(w=='0'){
				g[i][j]=0;
			}else{
				g[i][j]=1;
			}
		}
	}
	int ans=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(vis[i][j]) continue;
			int d=dfs(i,j);
			if(d!=0){
				ans++;
			}
		}
	}
	cout <<ans;
	return 0;
}

检查总结（DP）

思路没想到的原因

没想到状态计算，具体见思路。

思路

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

状态表示:$f[i]$表示从$i$到$n$最少需要删除多少个数字使序列合法。

状态计算:

• 如果$i+a[i]<=n$，那么$f[i]=min(f[i],f[i+a[i]+1])$；
• 如果$i+1<=n$，那么$f[i]=min(f[i],f[i+1]+1)$（没在$i+1<=n$加上$=$）。

代码

#include <bits/stdc++.h>
using namespace std;
const int tt=2e5+10;
int a[tt],f[tt];

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;
	for(int i=n-1;i>=1;i--){
		f[i]=1000000;
		if(i+a[i]<=n) f[i]=min(f[i],f[i+a[i]+1]);
		if(i+1<=n) f[i]=min(f[i],f[i+1]+1);
		if(f[i]==1000000) f[i]=0;
	}
	cout <<f[1];
	return 0;
}

谢谢