前言

难度总体不大。 第一题偏打卡，大部分人都可以拿下。 第二题的dp思路并不困难，但是需要转换思路才行。 第三题也是比较基础的dfs搜索。

T1

讨厌鬼有n串长度为m的糖葫芦，一串糖葫芦用一串字符串表示，糖葫芦的甜度为所有字符的甜度之和。 字符的甜度为这个字符与字符'a'的差值。即'a'的甜度为 0,'b'的甜度为 1.....,'z'的甜度为 25。

讨厌鬼现在想吃一根独一无二的糖葫芦，且这串糖葫芦甜度最大。 一个糖葫芦独一无二当且仅当另外n-1根糖葫芦都与这根糖葫芦不同，若有一根糖葫芦本身或翻转后与这根糖葫芦相同，则这根糖葫芦不是独一无二的。例如糖葫芦"abc"与"cba"被认为是相同的，"abc"和"abc"也被认为是相同的。

讨厌鬼想知道，他吃到这根糖葫芦串的甜度最大是多少？若吃不到任何独一无二糖葫芦，则输出 0。

输入描述

第一行输入两个整数n,m(1 \leq n \leq 50000,1 \leq m \leq 10) 接下来n行，每行输入一个长度为m的字符串。 输出描述 一行一个整数表示最大的甜度。

输入
3 3
ccz
cba
zcc
输出
3
说明
只有第二根糖葫芦是独一无二的，甜度为 2 + 1 + 0 = 3。
    
输入
2 3
abc
cba
输出
0
说明
见题目描述。

思路和代码

把正序和倒序的字符串放到map里，统计map里每个字符串的出现次数，如果只出现了一次则开始统计，维护答案最大值即可。

#include <iostream>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
int n,m;
string s[100005];
map<string, int> mp;
int main() {
    cin>>n>>m;
    for(int i = 1; i<=n; i++) {
        cin>>s[i];
        mp[s[i]] += 1;
        string t = s[i];
        reverse(s[i].begin(), s[i].end());
        if(s[i] != t) mp[s[i]] += 1;
    }
    int ans = 0;
    for(auto it = mp.begin(); it != mp.end(); ++it) {
        if(it->second == 1) {
            string str = it->first;
            int tmp = 0;
            for(auto ch : str) {
                tmp += ch-'a';
            }
            ans = max(ans, tmp);
        }
    }
    cout << ans;
}
// 64 位输出请用 printf("%lld")

T2

小红喜欢 3 的倍数的数字，现在小红有一个长度为 n 的数字串，小红想通过分隔字符串的方式，获得一些子串，每个子串代表一个数字，那么小红最多能获得多少个数字是 3 的倍数呢？

比如，小红有数字 1123，那么可以分隔为[1,12,3]，这样获得了两个数字是 3 的倍数。

请注意，分隔后的数字串，不能包含前导零，比如 012 不能视为 12。可以分割出 0，0 也是 3 的倍数。

输入描述

第一行输入一个没有前导零的正整数 n，表示小红的数字。 1\leq n \leq 10^{10^5}

输出描述

输出一个整数，表示小红能够获得的 3 的倍数的数字的最大数量。

输入
1123
输出
2
说明
分割为 [1, 12, 3]，获得了 2 个 3 的倍数的数字。
输入
300
输出
3
说明
分割为 [3, 0, 0]，获得了 3 个 3 的倍数的数字。

思路和代码

动态规划。last[i]数组代表 前缀和%3==i的最后位置。dp[i]代表截止到i位置，能凑出的最多数字个数是几个。转移方程dp[i]=max(dp[i-1],dp[last[num]]+1)，注意对last[num]还没出现过的情况（这里初始化为-1）要特殊处理。

#include <iostream>
#include<string>
#include<algorithm>
using namespace std;
string s;
long long last[3] = {-1, -1, -1};
long long dp[100005];
int sum;
int main() {
    cin >> s;

    last[(s[0] - '0') % 3] = 0;
    dp[0] = last[0] == 0 ? 1 : 0;
    sum = (s[0] - '0') % 3;
    for (int i = 1; i < s.size(); i++) {
        sum = (sum + s[i] - '0') % 3;
        long long la = 0;
        if (last[sum] >= 0) la = dp[last[sum]];
        else if (sum == 0)la = 0;
        else la = -1;
        dp[i] = max(dp[i - 1], la + 1);
        last[sum] = i;
    }
    cout << dp[s.size() - 1];
}
// 64 位输出请用 printf("%lld")

T3

给一张有 n 个节点的无向图，初始时只有1号节点是湖，其他节点都是普通节点。 惠惠每天会选择一个节点施放爆裂魔法，被施放爆裂魔法后的普通节点将变成一个巨坑（被施放爆裂魔法后的巨坑还是巨坑，被施放爆裂魔法后的湖还是湖）。 如果一个巨坑节点周围的任意一个节点是湖，那么这个节点也会变成湖。

给出每天惠惠施放爆裂魔法的节点，你需要回答每天施放完爆裂魔法之后湖的数量是多少。

输入描述

第一行输入三个整数 n,m,T(1 \leq n,m,T \leq 2 \times 10^5) ，分别表示图的节点数，图的边数，施放爆裂魔法的天数。

接下来 m 行，每行输入两个整数 u,v(1 \leq u,v \leq n) 表示节点 u 和节点 v 之间有一条边。

最后一行输入 T 个整数 a_i(1 \leq a_i \leq n) 表示惠惠每天施放爆裂魔法的节点编号。

输出描述

输出 T 行，每行一个整数表示每天施放完爆裂魔法之后湖的数量。

输入
3 2 3
1 2
2 3
3 2 1
输出
1
3
3
说明
第一天施放完爆裂魔法后，节点3从普通节点变成了巨坑，节点的状态分别是：1是湖，2是普通节点，3是巨坑，只有1个湖。
第二天施放完爆裂魔法后，节点2从普通节点变成了巨坑，节点的状态分别是：1是湖，2是湖，3是湖，有3个湖。
第三天施放完爆裂魔法后，节点1还是湖，节点的状态分别是：1是湖，2是湖，3是湖，有3个湖。

思路和代码

搜索。对于一个节点x如果变成了坑，那就先遍历相临的边，看他是否会变成湖，如果变成湖了就以x为起点搜索所有可达的坑并且都变成湖。复杂度为线性。

#include <iostream>
#include<vector>
using namespace std;
vector<int> vv[200005];
int n,m,T;
int ans = 1;
int sta[200005];// 0普通节点，1坑，2湖
void dfs(int x, int fa) {
    ans++;
    for(auto y : vv[x]) {
        if(y!=fa&&sta[y]==1) {
            sta[y]=2;
            dfs(y,x);
        }
    }
}
int main() {
    cin>>n>>m>>T;
    sta[1] = 2;
    for(int u,v,i = 1; i<=m; i++) {
        cin>>u>>v;
        vv[u].push_back(v);
        vv[v].push_back(u);
    }
    while(T--) {
        int x; cin>>x;
        if(sta[x] == 0) {
            sta[x] = 1;// 我变成坑了
            for(auto y : vv[x]) {
                if(sta[y] == 2) {      
                    sta[x] = 2;break;
                }
            }
            if(sta[x] == 2) dfs(x, -1);
        }
        cout << ans << endl;
    }
}
// 64 位输出请用 printf("%lld")