T1 红色警戒

难度：主要难点在于读题。

算法：模拟。

子任务 $1$（$30$ 分）：由于所有桥的耐久度都相同，所以炸掉谁都一样，本来直接输出任何一座桥的耐久度都可以，但要注意耐久度为 $0$ 也要一辆卡车，所以至少要输出 $1$。

子任务 $2$（$30$ 分）：此时保证了数据从小到大排序，所以第一座桥的耐久度是最低的，输出 max(a[1] ,1) 即可。

子任务 $3$（$40$ 分）：此时要找到九座桥的最小值，再来按照前面的做法即可。

C++ 代码：

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

int main()
{
    int a, ans = 1001;
    cin >> a; if (a < ans) ans = a;
    cin >> a; if (a < ans) ans = a;
    cin >> a; if (a < ans) ans = a;
    cin >> a; if (a < ans) ans = a;
    cin >> a; if (a < ans) ans = a;
    cin >> a; if (a < ans) ans = a;
    cin >> a; if (a < ans) ans = a;
    cin >> a; if (a < ans) ans = a;
    cin >> a; if (a < ans) ans = a;
    if(ans == 0) ans = 1;
    
    cout << ans << endl;
    
    return 0;
}

T2 有趣的&运算

难度：需要一些数学思维，要能推理出只要拆开了就只会让结果变大或者保持不变，因此答案就是只分为一个区间 $[1,n]$，所有数进行与运算的结果。

算法：数学。

子任务 $1$（$30$ 分）：只有两个数，答案只有两种情况：a[1] + a[2] 或者 a[1] & a[2]，输出其中较小的即可。

子任务 $2$（$30$ 分）：$n$ 非常小，可以暴力枚举所有的划分方案，但实际上暴力枚举所有划分方案的代码挺难写。

子任务 $3$（$40$ 分）：求所有数进行与运算的结果，需要注意和求和的初始化为 $0$ 不同，与运算的初始化比较复杂。你可以初始化为第一个数或者初始化为补码为全 $1$ 的 $−1$。

做法1：

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

int main()
{
    int n, ai, ans;
    cin >> n;
    for (int i = 1; i <= n; i ++ )
    {
    	cin >> ai;
    	if (i == 1) ans = ai;
    	else ans = ans & ai;
    }
    
    cout << ans << endl;
    
    return 0;
}

做法2：

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

int main()
{
    int n, ai, ans = -1;
    cin >> n;
    for (int i = 1; i <= n; i ++ )
    {
    	cin >> ai;
    	ans = ans & ai;
    }
    
    cout << ans << endl;
    
    return 0;
}

T3 比赛的获奖规则

难度：结构体排序的模拟题。

算法：排序，模拟。

子任务 $1$（$30$ 分）：此时省去了排序的步骤，可以先算出有效队伍数量，然后算出需要输出的排名，最后输出对应的排名即可。

子任务 $2$（$30$ 分）：最后输出的就是排在前面金牌区的选手，耐心写完排序后会简单很多。

子任务 $3$（$40$ 分）：题目怎么说的就怎么排序就好，我的代码中有一些特殊处理，我把打星队伍的排名挪到了最低，这样最后输出某个排名区间的队伍会方便一点。

C++ 代码：

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

int n;
struct Team
{
    string school, team;
    int solved, tim;
    bool flag; // 是否打星
}a[200000 + 5];

bool cmp(Team x, Team y)
{
	if (x.flag == false && y.flag == false) return x.school < y.school;
	if (x.flag == false || y.flag == false) return x.flag > y.flag;
	if (x.solved != y.solved) return x.solved > y.solved;
	return x.tim < y.tim;
}

int main()
{
    cin >> n;
    int A = 0, J, Y, T;
    for (int i = 1; i <= n; i ++ )
    {
    	cin >> a[i].school >> a[i].team >> a[i].solved >> a[i].tim;
    	a[i].flag = (a[i].solved > 0) && (a[i].team.back() != '*');
    	A += a[i].flag;
    }
    J = A * 10 / 100 + (A * 10 % 100 > 0);
    Y = A * 30 / 100 + (A * 30 % 100 > 0) - J;
    T = A * 60 / 100 + (A * 60 % 100 > 0) - Y - J;
    sort(a + 1, a + n + 1, cmp);
    string s;
    cin >> s;
    
    int l, r;
    if (s == "gold") l = 1, r = J;
    else if (s == "silver") l = J + 1, r = J + Y;
    else l = J + Y + 1, r = J + Y + T;
    
    cout << (r - l + 1) << endl;
    for (int i = l; i <= r; i ++ )
    	cout << a[i].school << " " << a[i].team << " " << a[i].solved << " " << a[i].tim << endl;
    
    return 0;
}

T4 真的是毒瘤题吗

难度：比较麻烦的二维数组上的模拟，满分需要一个小技巧，求出初始值后每次只修改变动带来的影响。

算法：枚举，模拟。

子任务 $1$（$30$ 分）：只有操作 $2$，整个数组没有修改过，按照题目模拟求出所有单词出现的次数即可。

子任务 $2$（$30$ 分）：数据范围很小，可以纯枚举做所有操作。

子任务 $3$（$40$ 分）：数据范围比较大，每次查询不能纯暴力枚举了。当算出了初始的所有单词以及对应的出现次数后，容易发现每次只修改了一个位置，因此最多影响了和这个位置有关的单词。可以先去掉之前所有相关的单词，然后新增新产生的单词即可。这里我没有偷懒使用 map 存所有单词出现次数，而是直接采用了一个四维数组。然后我写了挺多辅助函数，来让我的主函数更简洁。当时间复杂度没有问题的时候，我建议同学们也可以采用这样的方法，不用图快，把每一块做清楚能省掉更多调试的时间。

C++ 代码：

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

int n, m;
char g[305][305];
int cnt[30][30][30][30];
int dx[] = {0, 1, 0, 1}, dy[] = {0, 0, 1, 1};

// 行数、列数、方向（竖1、横2、右下斜着3）、长度
string getS(int x, int y, int fx, int len)
{
    if (x < 1 || y < 1) return "";
    if (fx == 1 && x + len - 1 > n) return "";
    if (fx == 2 && y + len - 1 > m) return "";
    if (fx == 3 && (x + len - 1 > n || y + len - 1 > m)) return "";
    string res = "";
    for (int i = 0; i < len; i ++ )
    {
    	res += g[x][y];
    	x += dx[fx];
    	y += dy[fx];
    }
    return res;
}

// s 的出现次数加上 num
void cal(string s, int num)
{
	int a[4] = {0, 0, 0, 0};
	for (int i = 0; i < s.size(); i ++ )
		a[i] = s[i] - 'a' + 1;
	cnt[a[0]][a[1]][a[2]][a[3]] += num;
}

// 返回 s 的出现次数
int getCnt(string s)
{
	int a[4] = {0, 0, 0, 0};
	for (int i = 0; i < s.size(); i ++ )
		a[i] = s[i] - 'a' + 1;
	return cnt[a[0]][a[1]][a[2]][a[3]];
}

// 把 (x,y) 相关的单词数量增加 t
void change(int x, int y, int t)
{
	for (int len = 1; len <= 4; len ++ )
	{
		cal(getS(x, y, 1, len), t);
		cal(getS(x, y, 2, len), t);
		cal(getS(x, y, 3, len), t);
	}
	for (int len = 2; len <= 4; len ++ )
	{
		cal(getS(x - 1, y, 1, len), t);
		cal(getS(x, y - 1, 2, len), t);
		cal(getS(x - 1, y - 1, 3, len), t);
	}
	for (int len = 3; len <= 4; len ++ )
	{
		cal(getS(x - 2, y, 1, len), t);
		cal(getS(x, y - 2, 2, len), t);
		cal(getS(x - 2, y - 2, 3, len), t);
	}
	for (int len = 4; len <= 4; len ++ )
	{
		cal(getS(x - 3, y, 1, len), t);
		cal(getS(x, y - 3, 2, len), t);
		cal(getS(x - 3, y - 3, 3, len), t);
	}
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
    	for (int j = 1; j <= m; j ++ )
    		cin >> g[i][j];
    
    for (int i = 1; i <= n; i ++ )
    	for (int j = 1; j <= m; j ++ )
    		for (int len = 1; len <= 4; len ++ )
    		{
    			cal(getS(i, j, 1, len), 1);
    			cal(getS(i, j, 2, len), 1);
    			cal(getS(i, j, 3, len), 1);
    		}
    int q;
    cin >> q;
    while (q -- )
	{
		int op;
		cin >> op;
		if (op == 1)
		{
			int x, y;
			char c;
			cin >> x >> y >> c;
			change(x, y, -1);
			g[x][y] = c;
			change(x, y, 1);
		}
		if (op == 2)
		{
			string s;
			cin >> s;
			cout << getCnt(s) << endl;
		}
	}
    
    return 0;
}