文章目录

• • • E.Edward Gaming, the Champion
    • F.Encoded Strings I
    • B.Bitwise Exclusive-OR Sequence
    • J.Luggage Lock
    • H.Line Graph Matching

补题链接：https://ac.nowcoder.com/acm/contest/24346
https://codeforces.com/gym/103427

E.Edward Gaming, the Champion

链接：https://ac.nowcoder.com/acm/contest/24346/E
来源：牛客网

题目描述
On November 6, 2021, the Chinese team Edward Gaming (EDG) defeated the South Korea team DWG KIA (DK) to win the 2021 League of Legends World championship in Reykjavík, Iceland, lifting the Summoner’s Cup for the first time in their history.

While both teams had looked dominant throughout the competition, DK arguably had the advantage. The team hadn’t lost a single game until they reached the semi-finals and was the only team to make it out of the Group Stage without a single defeat. They were clearly the team to beat.

EDG had given them a hit at the very first game of the final. The game started with a well-executed gank in the bot lane by EDG for the first blood. Later, EDG took every single Drake and the Baron, and ultimately destroyed the DK’s Nexus after 35 minutes.

But DK wouldn’t leave it unanswered. They maintained an advantage throughout the second game. Not even the incredible Baron steal by EDG’s legendary jungler, Jiejie, could help the team.

The third game turned out to be a difficult one. EDG seems to have control over more resources during the first 30 minutes. However, DK constantly killed every single dragon, and they finally took down the Nexus with the Hand of Baron.

In the fourth game, EDG had rethought their approach and took higher precedence in the control over dragons. The strategy had immediately taken effect, and they won the game after 33 minutes.

All things came down to the last game of the finals. Initially, DK took up the first dragon without much resistance from EDG. Shortly after, EDG picked first blood as DK took the Herald. Everything was fairly even at that moment. The balance finally started to tip in EDG’s favor during a team fight in the mid-lane, with EDG killing DK’s midlaner Showmaker before they had a chance to respond. The fight finally ended up with four kills and one death for EDG. They snowballed their advantage and finally secured the trophy.

The triumph of the Worlds 2021 made EDG the first team from LPL to win both the Mid-Season Invitational and the World Championship. You have just written a long string to celebrate this great victory. How many occurrences of “edgnb” as a continuous substring are there in the long string? Please write a program to count the number.
输入描述:
The only line contains a nonempty string, which consists of no more than 200,000200000 lowercase Latin letters, ‘a’ to ‘z’.
输出描述:
Output a line containing a single integer, indicating the number of occurrences of “edgnb” in the given string.
示例1
输入
复制
edgnb
输出
复制
1

题意：

• 给你一个字符串，问有几个"edgnb"的子串 。(2e5)

思路：

• 扫一遍累加答案即可

#include
using namespace std;
typedef long long LL;
const int N = 2e6+10;void solve(){string s;  cin>>s;int p = 0, res = 0;while(pp = s.find("edgnb",p)+5;res++;}cout<ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int T=1;  //cin>>T;while(T--){solve();}return 0;
}

F.Encoded Strings I

链接：https://ac.nowcoder.com/acm/contest/24346/F
来源：牛客网

题目描述
Tommy has just invented an interesting string encoding algorithm, which is described below.
For every string SS, we may define a character-mapping function F_SF
S
​
, which maps every character occurring in SS to a lowercase letter, as below
F_S© = \operatorname{chr}(G(c, S))F
S
​
©=chr(G(c,S))
where \operatorname{chr}(i)chr(i) is the (i+1)(i+1)-th lowercase Latin letter, and G(c, S)G(c,S) is the number of different characters after the last occurrence of cc in SS.
To encode a string SS by Tommy’s algorithm, replace every character cc in SS by F_S©F
S
​
© simultaneously.
For example, the encoded string of “abc” is “cba”, and the encoded string of “cac” is “aba”.

You are given a string of length nn and then encode all the nn nonempty prefixes. Your task is to find the encoded string that has the greatest lexicographical order among all the encoded strings.
输入描述:
The first line contains an integer nn (1 \le n \le 1,000)(1≤n≤1000).

The second line contains a string of length nn, which consists of only the first 2020 lowercase letters, ‘a’ to ‘t’.
输出描述:
Output the encoded string that has the greatest lexicographical order among all the encoded strings.
示例1
输入
复制
4
aacc
输出
复制
bbaa
说明
In the first sample case, the four nonempty prefixes “a”, “aa”, “aac” and “aacc” will be encoded to “a”, “aa”, “bba” and “bbaa” respectively, where “bbaa” has the greatest lexicographical order.

In the second sample case, the three nonempty prefixes “a”, “ac” and “aca” will be encoded to “a”, “ba” and “aba” respectively, where “ba” has the greatest lexicographical order.
示例2
输入
复制
3
aca
输出
复制
ba

题意：

• 给你一个长度为n的字符串，对该字符串的每个前缀按规则解码输出。
• 解码的规则是：si = ( s中最后一次出现si后的后缀中不同字符的数量+ " a " )

思路：

• 枚举字符串的每个前缀，对于对应的前缀，暴力处理出每种字符最后出现的位置，和对应后缀中不同的字符个数，加入集合里，最后n个结果字符串排个序输出字典序最大的即可。

#include
using namespace std;
typedef long long LL;
const int N = 2e6+10;
int c[200];
void solve(){int n;  cin>>n;string s;  cin>>s;setse;for(int i = 0; i < s.size(); i++){string t = s.substr(0,i+1);// cout<ss;for(int j = 0; j < 200; j++)c[j] = -1;for(int j = t.size()-1; j >= 0; j--){if(c[t[j]]==-1)c[t[j]] = ss.size();ss.insert(t[j]);}for(int j = 0; j < t.size(); j++){t[j] = c[t[j]]+'a';}// cout<ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int T=1;  //cin>>T;while(T--){solve();}return 0;
}

B.Bitwise Exclusive-OR Sequence

链接：https://ac.nowcoder.com/acm/contest/24346/B
来源：牛客网

题目描述
AAA has a nonnegative integer sequence a_1,a_2,\ldots,a_na
1
​
,a
2
​
,…,a
n
​
with mm constraints, each of which is described as a_u \oplus a_v = wa
u
​
⊕a
v
​
=w, where \oplus⊕ denotes the bitwise exclusive-OR operation.

More precisely, the bitwise exclusive-OR operation is a binary operation which is equivalent to applying logical exclusive-OR to every pair of bits located on the same positions in binary notation of operands. In other words, a binary digit of the result is equal to 11 if and only if bits on the respective positions in the operands are different. For example, if X = 109_{10} = 1101101_{2}X=109
10
​
=1101101
2
​
and Y = 41_{10} = 101001_{2}Y=41
10
​
=101001
2
​
, then X \oplus Y = 1000100_{2} = 68_{10}X⊕Y=1000100
2
​
=68
10
​
.

Now AAA wants to find out the minimum sum of all the elements in the sequence, or determine that the sequence meets all the constraints does not exist.
输入描述:
The first line contains two integers nn (1 \le n \le 10^5)(1≤n≤10
5
) and mm (0 \le m \le 2 \times 10^5)(0≤m≤2×10
5
), denoting the length of sequence and the number of conditions.

The follow mm lines, each of which contains three integers uu, vv (1 \le u, v \le n)(1≤u,v≤n) and ww (0 \le w < 2^{30})(0≤w<2
30
), indicating a constraint that a_u \oplus a_v = wa
u
​
⊕a
v
​
=w.
输出描述:
Output a line containing a single integer, indicating the minimum sum of all the elements in the sequence or -1−1 if the sequence meets all the constraints does not exist.
示例1
输入
复制
3 2
1 2 1
2 3 1
输出
复制
1
说明
In the first sample case, the sequence [a_1,a_2,a_3]=[0,1,0][a
1
​
,a
2
​
,a
3
​
]=[0,1,0] meets all the constraints and has the minimum sum of all the elements.

题意：

• 有n个点和m个约束，每个约束包含三个数u，v，w，表示a[u]^a[v]=w
• 求满足m个约束 并且 和最小的序列的和。

思路：

• 知道两数的异或值，等价于知道两数二进制下的每位是否相等。即知道了其中一个值，另一个也唯一确定。
• 那么如果把所有关系建图（在u和v之间连一条权值为w的边），那么只要知道某个结点的权值，同一个连通块内的其他点权也唯一确定。
• 先跑一遍dfs判断解的情况，如果存在某个环上的异或和不为0，则无合法解，输出−1 （因为每个点都用了两遍）
• 再跑一遍dfs，每个点都按位黑白染色，将较少的颜色所在位赋为1，这样的每个点每一位加起来后的和就会最小。

#include
using namespace std;
typedef long long LL;
const int N = 2e5+10;struct node{int to, w; };
vectorG[N];int vis[N];
void check(int u, int w){vis[u] = w;for(node x : G[u]){int v = x.to;if(vis[v]==-1)check(v, w^x.w); //下个点的期望点权为当前^边权else if(vis[v] != (w^x.w)){ //对于一个联通块，如果某点点权与rt冲突，就寄cout<<"-1\n";exit(0);}}
}int c[N][31], cc[3];  //每个联通块每一位黑白颜色的数量
void dfs(int u, int p, int w){  //第u个点第p位染wc[u][p] = w;cc[w]++;for(node x : G[u]){int v = x.to;if(!c[v][p]){if(x.w>>p&1)dfs(v, p, 3-w);else dfs(v, p, w);}}
}int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n, m;  cin>>n>>m;for(int i = 1; i <= m; i++){int u, v, w;  cin>>u>>v>>w;G[u].push_back({v,w});G[v].push_back({u,w});}memset(vis,-1,sizeof vis);LL res = 0;for(int i = 1; i <= n; i++){if(vis[i]==-1)check(i, 0);}for(int i = 1; i <= n; i++){if(c[i][0]!=0)continue;for(int j = 0; j <= 30; j++){cc[1] = cc[2] = 0; dfs(i,j,1); res += 1ll*min(cc[1],cc[2])*(1<

#include
using namespace std;unordered_mapmp;
void bfs(){queueq;q.push("0000");mp["0000"] = 0;while(q.size()){string t = q.front();  q.pop();for(int len = 1; len <= 4; len++){for(int l = 0; l+len<=4; l++){int r = l+len-1;string add = t, sub = t;for(int i=l; i <= r; i++){add[i] = (add[i]-'0'+1)%10+'0';sub[i] = (sub[i]-'0'+9)%10+'0';}if(!mp.count(add)){ mp[add] = mp[t]+1; q.push(add); }if(!mp.count(sub)){ mp[sub] = mp[t]+1; q.push(sub); }}}}
}int main(){bfs();int T;  cin>>T;while(T--){string a, b, c="0000";  cin>>a>>b;for(int i = 0; i < 4; i++){c[i] = (b[i]-a[i]+10)%10+'0';}cout<

#include
using namespace std;
typedef long long LL;
const int N = 2e5+10;struct edge{ int u, v, w; }e[N];
bool cmp(edge x, edge y){ return x.w>y.w; }
int f[N];  //连通块中剩下的那条边的边权int fa[N+10];
void init(int n){for(int i = 0; i <= n; i++)fa[i]=i;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x, int y){x=find(x);y=find(y);if(x!=y)fa[x]=y;}int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n, m;  cin>>n>>m;for(int i = 1; i <= m; i++)cin>>e[i].u>>e[i].v>>e[i].w;sort(e+1, e+m+1, cmp);init(n+1);LL res = 0;for(int i = 1; i <= m; i++){int x = find(e[i].u), y = find(e[i].v), z = e[i].w;if(x == y){if(!f[x])f[x] = z;else res += f[x]+z, f[x]=0;}else{merge(y, x);if(!f[x] && !f[y])f[x] = z;else if(!f[x] || !f[y])res += f[x]+f[y]+z, f[x] = 0;else res += max(f[x], f[y])+z, f[x] = min(f[x], f[y]);}}cout<