T1 - 小田的最大价值

#include <bits/stdc++.h>  
#define qwq ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) 
using namespace std;  
/*
最大值和最小值之差，如果大于k，那么就是最大值

否则是次大值
*/

const int N = 1e5+5;

int n, a[N], k;

int main() {  
	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;  
}

T2 - 小田的交换数字

核心思想，两数相乘，在和不变的情况下，两个数相差越大，乘积越小。 所以就是要通过交换，使得一个数最大，一个数最小。

剩下的就是裸的高精乘了。

#include <bits/stdc++.h>  
#define qwq ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)  
using namespace std;  
  
long long n, res = 0, aa = 0, mod=998244353;  
string a, b;  
  
int main() {  
    freopen("mul.in", "r", stdin);
    freopen("mul.out", "w", stdout);
    qwq;  
    cin >> n >> a >> b;  
    // 在和相同的情况下，两数相差越大，乘积越小。  
    // 所以让一个数字最大，一个数字最小。  
    for (int i=0; i<n; i++) {  
        if (a[i] > b[i]) {  
            swap(a[i], b[i]);  
        }  
        aa = (aa*10 + a[i]-'0') % mod;  // 提前把 a 算出来，这样后面就是低精乘高精  
    }  
    for (int i=n-1; i>=0; i--) {  
        res = (res + aa*(b[i]-'0')) % mod;  
        aa = aa*10 % mod;  
    }  
    cout << res;  
    return 0;  
}

T3 - 小田的气球真好看

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

如何能尽快的判断是否满足条件呢？容易想到，因为每次都是尝试扩展一个气球，所以是否满足条件就只需要判断$r$这个气球与上一个相同颜色的气球即可。

同理，在$r$往后走的时候，都是一个元素一个元素在增加，所以可以利用桶来实时维护每个颜色的最新位置，这样代码就基本实现了。

需要注意的是当$l$往后走时，它如果是记录在桶里面的该颜色气球最后一次的位置，则需要将其消除。

时间复杂度为$O(n)$。

#include <bits/stdc++.h>  
using namespace std;  
  
const int N = 1e5+5;  
  
int n, k, c[N], lc[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 >> c[i];  
    int l=1, r=0;  
    while (l <= n) {  
        while (r < n and (r+1-lc[c[r+1]]<=k or !lc[c[r+1]])) {  
            r++;  
            lc[c[r]] = r;  
        }  
        res += r-l+1;  
        if (lc[c[l]] == l) lc[c[l]] = 0;  
        l++;  
    }  
    cout << res;  
    return 0;  
}

T4 - 表达式求值

#include<iostream>
using namespace std;

const int N = 2e4 + 10;
char stk[N], tt;

void cal() // 弹出栈顶元素直到遇到左括号，统计f和t数量，取出opt，计算结果并重新入栈
{
	int tn = 0, fn = 0;
	while (stk[tt] != '(')
	{
		if (stk[tt] == 't') tn++;
		else fn++;
		tt--;
	}
	tt --; // 去掉左括号
	char ans;
	char opt = stk[tt--];
	if (opt == '|')
	{
		if (tn) ans = 't';
		else ans = 'f';
	}
	else if (opt == '&')
	{
		if (fn) ans = 'f';
		else ans = 't';
	}
	else
	{
		if (tn) ans = 'f';
		else ans = 't';
	}
	stk[++tt] = ans;
}

int main()
{
	freopen("expr.in", "r", stdin);
	freopen("expr.out", "w", stdout);
	int t;
	cin >> t;
	while (t--)
	{
		tt = 0;
		string s;
		cin >> s;
		for(auto &it:s)
		{
			if (it == ',') continue;
			else if (it == ')') cal();
			else stk[++tt] = it;
		}
		if (stk[1] == 't') cout << "true\n";
		else cout << "false\n";
	}
}

T5 小W去冒险

思路 dfs连通图问题 以某个点出发, 把能联通的全部标记成不能走 ,标记的次数就是连通个数.

#include <bits/stdc++.h>
using namespace std;
int r,c,cnt=0;
char a[110][110];
int dx[4]={1,0,-1,0};
int dy[4]={0,-1,0,1};//下左上右 
void dfs(int x,int y){
	a[x][y]='0'; //标记成不能走的.
	for(int i=0;i<=3;i++)
	{
		int xx=x+dx[i],yy=y+dy[i];
		if(xx>=1&&xx<=r&&yy>=1&&yy<=c&&a[xx][yy]>'0')//搜索下一个点
			dfs(xx,yy); 
	}
} 
int main(){
	freopen("ymx.in","r",stdin);
	freopen("ymx.out","w",stdout);
	cin>>r>>c;
	for(int i=1;i<=r;i++)
		for(int j=1;j<=c;j++)
			cin>>a[i][j];

	for(int i=1;i<=r;i++) //以每个点都当做起点试试 
		for(int j=1;j<=c;j++)
			if(a[i][j]>'0') //能连通就以这个点出发
			{
				cnt++;
				dfs(i,j);
			}
	cout<<cnt<<endl;
	return 0;	 
}

T6 检查总结

本题需要使用文件输入输出，文件名为 summary.in 和 summary.out。

题目描述

总结，对于学习而言，非常重要，犹如“西方不能没有耶路撒冷”，学习，也不能没有总结，总结自己学习的内容，既能够温故而知新，还能提升自己对知识体系的搭建，从而达到事半功倍的效果，认真总结一道题，甚至比去新做十道题更有效果。 布置了总结任务的小z，决定对同学们的总结进行检查，当然，检查总结是一件非常繁琐的事，所以他先做了一个初步统计，统计过程如下：对于每一位同学，先写下一个数字$x$，表示总结题目的数量，接下来会有$x$个数$y$，表示这些总结的评分，由于小z的记性还不错，所以他将检查的数字列在了一起，准备课后再仔细进行检查。 可惜的是，小z有时候比较粗心，他不小心把一些数字记错了（可能有，也可能没有），但是他确定只会多记，不会记错，那么只需要删除掉错误的数字即可，所以任务就是找到最少需要删除数字的数量。 这个任务不是很难，他决定让可爱的同学们来解决。 小z给同学们的提示是： 一个没有任何错误的序列是这样的：$[\color{red}{3, 4, 5, 6}, \color{green}{2, 6, 1}]$，通过观察可以发现，红色部分第一个$3$代表第一位同学有$3$个题目需要总结，$4,5,6$代表$3$个题目的评分。绿色部分第一个$2$代表第二位同学有$2$个题目需要总结，$6,1$代表$2$个题目的评分。 而$[1]、[1, 4, 3] 、[3, 2, 1]$则不是合法的序列。

输入描述

每个测试用例的第一行包含一个整数 $n$ ( $1 \le n \le 2 \cdot 10^5$ )， 表示序列的长度。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le 10^6$ ) - 表示序列的每个元素的大小。

输出描述

对于每个测试用例，输出一个数字--使序列 $a$ 没有任何错误的最小删除次数。

输入输出样例

输入 #1

7
3 3 4 5 2 6 1

输出 #1

0

输入 #2

4
5 6 3 2

输出 #2

4

输入 #3

5
1 2 3 4 5

输出 #3

2

说明/提示

【数据范围】 对于 $20 \%$ 的数据，$1 \leq n \leq 100$。 对于所有测试数据，如上文所描述 。

解析： 状态表示：$f[i]$表示从$i$到$n$保证序列合法需要删除的最小数字个数。 状态计算：对于每一个数字$a[i]$，发现如果保留，则$f[i] = f[i + a[i] + 1]$，如果不保留，则$f[i] = f[i+1] + 1$。 初始化：$f[n] = 1$ 和$f[n + 1] = 0$ 前者显然，后者可以发现，如果第$i$个数字到第$n$个数字为一个整体（即合法）,那么刚好可以转移$f[n+1]$的位置，其值为$0$。也可以单独去特判，这个初始化很重要。 最终结果：$f[1]$

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 20;
int f[N], a[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] = 0;
    f[n] = 1; 
    for(int i = n - 1; i >= 1; i--) {
        if(a[i] + i > n) f[i] = f[i + 1] + 1;
        else f[i] = min(f[i + 1] + 1, f[i + a[i] + 1]);
    }
    cout << f[1] << endl;
    return 0;
}