本次比赛为校内的训练赛，题目均选自codeforces.
A. Text Volume
题目链接
https://codeforces.com/problemset/problem/837/A
题意
一个含有大小写字母和空格的字符串，字符串的体积就是这个字符串中大写字母最多的单词的大写字母的数量。
让求字符串的体积
思路
用getline(cin, s); 读字符串，然后遍历字符串计数大写字母，遇到空格就归零，维护最大值即可。
代码
// #pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <ctime>
#include <vector>
#include <fstream>
#include <list>
#include <iomanip>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s) memset(s, 0, sizeof(s))
const int inf = 0x3f3f3f3f;
#define LOCAL
const int maxn = 1e5 + 7;
int main(int argc, char * argv[])
{
int n;
string s;
while (cin >> n){
getchar();
getline(cin, s); //用getline读一行字符串放到s里
int cnt = 0;
int ans = 0;
for (int i = 0; i < s.size(); i++){
if (s[i] >= 'A' && s[i] <= 'Z'){ // 如果有大写字母则计数
cnt++;
}
if (s[i] == ' '){ // 遇到空格就归零
cnt = 0;
}
ans = max(ans, cnt); // 维护最大值
}
cout << ans << endl;
}
return 0;
}
B. Crossword solving
题目链接
https://codeforces.com/problemset/problem/822/B
题意
给一个字符串s和t，|s| <= |t|。你可以把s中的字母换成问号"?"，问号就可以表示任意的字符。然后要求你尽可能把少的字符改成问号，然后让s变成t的子串。
输入：s和t的长度，以及s和t
输出：要把s中的字母变成问号的数量，以及变的位置。
思路
暴力匹配！！！
就是枚举t上面的起点，我们假设起点为start。让start从0枚举到t.size() - s.size()
设以在t上以start为起点匹配s时，相同的字符个数为cnt，初始化为0.
然后让i在0~s.size() - 1这个区间逐个匹配s[i]和t[start + i]，当s[i] == t[start + i]时cnt++。更新cnt的最大值Max时记录一下此时的start，设为Mark_i = start
最后，先输出s.size() - Max。
从Mark_i开始匹配，如果s[i] != t[Mark_i + i]，则输出i + 1(因为字符串从0开始)
代码
// #pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <ctime>
#include <vector>
#include <fstream>
#include <list>
#include <iomanip>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s) memset(s, 0, sizeof(s))
const int inf = 0x3f3f3f3f;
#define LOCAL
const int maxn = 1e6 + 7;
int main(int argc, char * argv[])
{
int n, m;
while (cin >> n >> m){
string s, t;
cin >> s >> t;
int Max = -1, Mark_i = 0;
// Max为最大值，匹配字符的最大值，初始化为-1。Mark_i为取最大值时t上的起点。
int cnt = 0;
for (int i = 0; i <= m - n; i++){ // i是t上的起点，逐个枚举起点
cnt = 0;
for (int j = 0; j < n; j++){ // j表示s上的指针
// cout << s[j] << " " << t[i + j] << endl;
if (s[j] == t[i + j]){
// 判断对应位置是否相等，这里的i是t上的起点，所以需要t[i + j]
cnt++;
}
if (cnt > Max){
// 如果最大值有变化的话，那就更新最大值，并且更新最大值所对应的那个起点
Max = cnt;
Mark_i = i;
}
}
// cout << endl;
}
cout << n - Max << endl;
// 输出s的长度减去匹配字符的最大值，也就是未匹配字符的最小值。
for (int i = 0; i < n; i++){
if (s[i] != t[i + Mark_i]){ // 如果有一个不匹配，则输出i + 1。
cout << i + 1 << " ";
}
}
cout << endl;
}
return 0;
}
C. Wrath
题目链接
https://codeforces.com/problemset/problem/892/B
题意
第i个人可以杀死他前面的L[i]个人，等到铃声一响，所有人都会同时动手，杀死前面的人。求最后活着的人的个数。
即：第i个人会杀掉第j个人，如果j >= i - L[i] && j < i
思路
区间合并(关键字：差分+前缀和)
先说一下区间合并，对于一段整数区间[1, n]。每次把[l, r]染色，染色若干次，求最后染色情况。
对于将[l, r]染色，我们首先想到的做法是暴力:
for (int i = l; i <= r; i++){
b[i] = 1; // b数组即为染色情况，1为被染色，0表示没被染色
}
但这样染色的复杂度是O(n)，太慢了，需要改进一下。
设a数组初始化为0，每次染色[l, r]，让a[l]++, a[r + 1]--，最后对a求前缀和
对于i从2到n，让a[i] = a[i - 1] + a[i];。求前缀和之后，非0的地方是被染色的。
有点懵逼的话我们看一下下面的例子。
初始状态：
a: 0, 0, 0, 0 ,0。
对区间[1, 3]进行染色a[1]++, a[3 + 1]--。
a:1, 0, 0, -1, 0。
然后求前缀和: a[i] = a[i - 1] + a[i];
a:1, 1, 1, 0, 0。
这样就达成了染色的效果。
简单说就是a[l]++让最后的前缀和从l开始都增加了1，但为了去除对r后面的区间的影响，就让a[r + 1]--，然后求前缀和的时候从r + 1开始就能降下来。
联系本题
对于第i个人，他能杀死他前面的L[i]个人，所以每次合并区间[i- L[i], i - 1]就好了。但i - L[i]可能会小于0，所以还得在i - L[i]和0之间取个最大值，意思就是当i - L[i]小于0时取0。
代码
// #pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <ctime>
#include <vector>
#include <fstream>
#include <list>
#include <iomanip>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s) memset(s, 0, sizeof(s))
const int inf = 0x3f3f3f3f;
#define LOCAL
const int maxn = 1e6 + 7;
int main(int argc, char * argv[])
{
int n;
while (cin >> n){
int cnt = 0;
int a[maxn], b[maxn];
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
for (int i = 1; i <= n; i++){
cin >> a[i];
if (a[i] > 0){
// 当a[i]大于0的时候才会有区间，加上判断避免a[i] = 0时对b[0]的误操作
b[max(0, i - a[i])]++;
b[i]--;
}
}
for (int i = 1; i <= n; i++){
b[i] = b[i] + b[i - 1];
}
for (int i = 1; i <= n; i++){
if (b[i] == 0){
cnt++;
}
}
cout << cnt << endl;
}
return 0;
}
D. Coloring a Tree
题目链接
https://codeforces.com/problemset/problem/902/B
题意
给一棵有根树，节点标号1到n。1号节点为根节点，颜色用数字表示，初始时每个节点的颜色都是0。输入还给出给每个节点要被染的目标颜色（就是最后的结果），每次对i节点进行染色的时候，i节点的子节点也会变成相同的颜色。求最少的染色次数。
思路
从顶向下bfs，如果当前节点的父亲节点的颜色跟它的目标颜色不一样，那就将它染成目标颜色，并且计一次数。如果当前节点的颜色和父亲节点颜色一样，那就把它染成父亲节点的颜色，不计数（因为按照题意，染父亲节点的时候已经给它染过了）。
我是这么写的，但后来跟队友交流发现不用建图也可以，因为这题目输入的是每个节点的父亲节点的编号，所以拿数组来判断某个节点的目标颜色跟它父亲的目标颜色是否相同也是可以的。
代码
// #pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <ctime>
#include <vector>
#include <fstream>
#include <list>
#include <iomanip>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s) memset(s, 0, sizeof(s))
const int inf = 0x3f3f3f3f;
#define LOCAL
const int maxn = 1e6 + 7;
int pre[maxn];
int hope_color[maxn];
int color[maxn];
std::vector<int> G[maxn];
int n;
void add(int a, int b){
G[a].push_back(b);
}
void init(){
for (int i = 0; i <= n; i++){
pre[i] = 0;
color[i] = 0;
G[i].clear();
}
pre[1] = 1;
}
void bfs(){
queue<int> q;
q.push(1);
int cnt = 0;
while (!q.empty()){
int t = q.front();
q.pop();
if (color[pre[t]] != hope_color[t]){
color[t] = hope_color[t];
cnt++;
}
else{
color[t] = color[pre[t]];
}
for (int i = 0; i < G[t].size(); i++){
q.push(G[t][i]);
}
}
cout << cnt << endl;
}
void out_graph(){
for (int i = 1; i <= n; i++){
for (int j = 0; j < G[i].size(); j++){
cout << G[i][j] << " ";
}
cout << endl;
}
}
int main(int argc, char * argv[])
{
while (cin >> n){
init();
int a;
for (int i = 2; i <= n; i++){
cin >> a;
pre[i] = a;
add(a, i); // 加一条从i到a的边
}
for (int i = 1; i <= n; i++){
cin >> hope_color[i];
}
// out_graph();
bfs();
}
return 0;
}
E. Bear and String Distance
题目链接
https://codeforces.com/problemset/problem/628/C
题意
定义：
- 两个字母的距离就是他们在字母表上的距离，比如a和z的距离等于z和a的距离等于25。a和b的距离等于b和a的距离等于1。
- 两个长度相等的字符串的距离是这两个字符串对应位置的字母的距离之和。
要求：
给出一个字符串s和整数k，要求你求出一个字符串t，使得它和s的距离为k。
思路
贪心。
对于任意字母来说，离它最远的字母要么是a要么是z。求出字符串中所有字母离它最远的字母（a或者z）与它的距离之和，如果这个数小于k，那就说明所有字母都取了最远之后还不满足，那就无解，输出-1。
如果有解的情况，前期要么取a要么取z（都取最大值）。等到a和z的距离比剩余的距离还大的时候，就刚好取满。后面就原封不动跟原来的字符串一样就好了。
代码
// #pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <ctime>
#include <vector>
#include <fstream>
#include <list>
#include <iomanip>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s) memset(s, 0, sizeof(s))
const int inf = 0x3f3f3f3f;
#define LOCAL
const int maxn = 1e6 + 7;
int main(int argc, char * argv[])
{
int n, k;
string s;
while (cin >> n >> k){
cin >> s;
string ans = s; // ans表示最后输出字符串，先直接让它等于s，然后再逐位修改它的值。
int cnt = 0;
for (int i = 0; i < n; i++){
// 先判断全都取最大值的时候的数
cnt += max(abs('a' - s[i]), abs('z' - s[i]));
}
if (cnt < k){
cout << -1 << endl;
}
else{
for (int i = 0; i < n; i++){
// 先判断选a还是选z
if (abs('a' - s[i]) > abs('z' - s[i])){
// 选a的情况
if (abs('a' - s[i]) <= k){
//如果还能选a的话就选
k -= abs('a' - s[i]);
// 更新k值，表示所需距离减去这么'a' - s[i]这么多
ans[i] = 'a';
}
else{
// 如果不能的话那就向前选尽可能大的，然后把k置0。
ans[i] = char(s[i] - k);
k = 0;
break;
}
}
else{
// 选z的情况，这两个分支跟上面选a的情况类似，不再累述。
if (abs('z' - s[i]) <= k){
k -= abs('z' - s[i]);
ans[i] = 'z';
}
else{
ans[i] = char(s[i] + k);
k = 0;
break;
}
}
}
cout << ans << endl;
}
}
return 0;
}
