A. 小田的最大价值

题目类型：排序加分类讨论

思路

  • 先将数组排序。
  • 若最大值减最小值>k，则输出最大值。
  • 若最大值减最小值<=k，则输出次大值。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N];
int main(){
	freopen("max.in","r",stdin);
	freopen("max.out","w",stdout);
	int k,n;
	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];
	else cout<<a[n-1];
	return 0;
}

本题代码已AC，下一次继续保持。

B. 小田的交换数字

题目类型：字符串

思路

  • 如果想得到a*b的​结果最小，那就要使a​与b的差最大。
  • 所以遍历0至n，若a[i]>b[i]交换a[i]与b[i]的值。
  • 最后只要将答案对998244353取模就好了。

代码

#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
const int mod=998244353;
int s1,s2;
signed main(){
    freopen("mul.in","r",stdin);
	freopen("mul.out","w",stdout);
    int n;
    string a,b;
    cin>>n;
    cin>>a>>b;
    for(int i=0;i<n;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;
}

这道题我在写的时候不知道怎么将a与b相乘，下一次要把事情想的简单点。

C. 小田的气球真好看

题目类型：双指针或DP

思路

DP

  • 初始状态为f[1]=1，flag[a[1]]=1。
  • 状态转移为：
  • if(j==0) f[i]=min(i,f[i-1]+1)。
  • else if(i-j<=k) f[i]=min(f[j]+i-j,f[i-1]+1)。
  • else if(i-j>k) f[i]=min(i-j,f[i-1]+1)。

双指针

  • 枚举起点l，以这个为起点,找到最后一个满足条件的r，这个​区间有多长，就有多少个子区间​。
  • 用标记数组，标记0到l之间的子序列数量。
  • 要更新标记数组 。
  • 当l往右走时​，如果值是记录在标记数组的最后一个位置，则需要消除。

注意

不管是双指针还是DP，都要用long long。

代码

DP

#include<bits/stdc++.h>
using namespace std;
long long f[100010],flag[100010],a[100010];
int main(){
    freopen("balloon.in","r",stdin);
    freopen("balloon.out","w",stdout);
    long long n,k,ans=0,j;
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    f[1]=1;
    flag[a[1]]=1;
    for(long long i=2;i<=n;i++){
        j=flag[a[i]];
        if(j==0) f[i]=min(i,f[i-1]+1);
        else if(i-j<=k) f[i]=min(f[j]+i-j,f[i-1]+1);
        else if(i-j>k) f[i]=min(i-j,f[i-1]+1);
		flag[a[i]]=i;
    }
    for(long long i=1;i<=n;i++)  ans+=f[i];
    cout<<ans;
    return 0;
}

双指针

#include<bits/stdc++.h>  
using namespace std;  
const int N=1e5+5;  
int n,k,a[N],flag[N];  
long long cnt=0;  
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;  
		cnt+=r-l+1;  
		if(flag[a[l]]==l) flag[a[l]]=0;  
		l++;  
	}  
	cout<<cnt;  
	return 0;  
}

这道题目在写的时候想到了双指针，但没写出来，就放弃了。所以以后不能轻易放弃。

D. 表达式求值

题目类型：栈

思路

  • 这道题目需要用一个逻辑栈与一个符号栈来做。
  • 若s[i]='t'或'f'，压入逻辑栈。
  • 其他的压入符号栈。
  • 若遇到右括号，遍历得出括号里的答案。
  • 最后看逻辑栈栈头元素，若逻辑栈栈头元素为't',输出true,若逻辑栈栈头元素为'f',输出false。

代码

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

这道题只想着一个栈做，下次要想着用两个栈做。

D. 表达式求值

题目类型：栈

思路

  • 这道题目需要用一个数字栈与一个符号栈来做。
  • 若s[i]='t'

代码

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

这道题只想着一个栈做，下次要想着用两个栈做。

E. 小W去冒险

题目类型：搜索

思路

这道题目其实就是DFS模版改一下即可。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,dy[6]={0,1,0,-1},dx[6]={1,0,-1,0},a[110][110];
int cnt=0;
char c;
bool st[110][110];
void dfs(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>=1&&ny>=1&&nx<=n&&ny<=m){
			dfs(nx,ny);
		}
	}
	return;
}
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++){
			cin>>c;
			a[i][j]=c-'0';
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]!=0) {
				dfs(i,j);
			    cnt++;
			}
		}
	}
	cout<<cnt;
	return 0;
}

这道题在写的时候模版写出来了，但有一个地方没有改，下一次还是要根据题目做出改变。

F. 检查总结

题目类型：DP

思路

  • 初始状态为f[n]=1，f[n+1]=0。
  • 状态转移为：
  • if(i+a[i]<=n) f[i]=min(f[i+1]+1,f[i+a[i]+1]);
  • else f[i]=f[i+1]+1。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N],f[N];
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;
}

DP还没有学过，老师说以后会单独开一节课来讲DP。

  1. Language
  2. 兼容模式
  3. 主题
  3. Worker 0, 10ms
  4. Powered by Hydro v5.0.0-beta.13 Community