@[toc]
补题链接：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<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e6+10;
void solve(){
string s; cin>>s;
int p = 0, res = 0;
while(p<s.size() && s.find("edgnb",p) != string::npos){
p = s.find("edgnb",p)+5;
res++;
}
cout<<res;
}
int main(){
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(c) = \operatorname{chr}(G(c, S))F
S
(c)=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(c)F
S
(c) 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<bits/stdc++.h>
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;
set<string>se;
for(int i = 0; i < s.size(); i++){
string t = s.substr(0,i+1);
// cout<<t<<" ";
set<char>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<<t<<"\n";
se.insert(t);
}
auto tt = se.end();
tt--;
cout<<(*tt)<<"\n";
}
int main(){
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<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5+10;
struct node{int to, w; };
vector<node>G[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位染w
c[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<<j);
}
}
cout<<res<<"\n";
return 0;
}J.Luggage Lock
链接：https://ac.nowcoder.com/acm/contest/24346/J
来源：牛客网
题目描述
Eileen has a big luggage and she would pick a lot of things in the luggage every time when A-SOUL goes out for a show. However, if there are too many things in the luggage, the 4-digit password lock on the luggage will be hard to rotate.
The state of lock is the four digits on the lock. In one step, she can choose consecutive digits to rotate up by one simultaneously or down by one simultaneously. For example, she can rotate \texttt{0000}0000 to \texttt{0111}0111 or \texttt{0900}0900 in one step because the rotated digits are consecutive, but she can't rotate \texttt{0000}0000 to \texttt{0101}0101 in one step. Since she has little strength, she wants to rotate the lock as few times as possible.
Now the lock is at state a_0a_1a_2a_3a
0
a
1
a
2
a
3
and the password is b_0b_1b_2b_3b
0
b
1
b
2
b
3
. As a fan of A-SOUL, you are asked to help Eileen find out the optimal plan to unlock but you only need to tell Eileen how many times she has to rotate.
输入描述:
The first line contains one integer TT (1 \leq T \leq 10^5)(1≤T≤10
5
), denoting the numer of test cases.
Each of the test cases contains a line containing the initial state a_0a_1a_2a_3a
0
a
1
a
2
a
3
and the target state b_0b_1b_2b_3b
0
b
1
b
2
b
3
.
输出描述:
For each test case, output a line containing a single integer, denoting the minimum steps needed to unlock.
示例1
输入
复制
6
1234 2345
1234 0123
1234 2267
1234 3401
1234 1344
1234 2468
输出
复制
1
1
4
5
1
4
题意：
- 将一个4位的锁转到另一个四位的锁，一次可以转动多个连续的位+1或者-1
- 问多少次可以转成目标锁
- T < 1e5。
思路：
- aaaa转到bbbb，等价于从0000转到aaaa和bbbb每一位相减的cccc
- 一共只有9999种状态，每次不超过36种转移。
可以暴力处理出0000到每一位的步数，然后对于询问直接输出即可。
#include<bits/stdc++.h>
using namespace std;
unordered_map<string,int>mp;
void bfs(){
queue<string>q;
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<<mp[c]<<"\n";
}
return 0;
}H.Line Graph Matching
链接：https://ac.nowcoder.com/acm/contest/24346/H
来源：牛客网
题目描述
In the mathematical discipline of graph theory, the line graph of a simple undirected weighted graph GG is another simple undirected weighted graph L(G)L(G) that represents the adjacency between every two edges in GG.
Precisely speaking, for an undirected weighted graph GG without loops or multiple edges, its line graph L(G)L(G) is an undirected weighted graph such that:
Each vertex of L(G)L(G) represents an edge of GG;
Two vertices of L(G)L(G) are adjacent if and only if their corresponding edges share a common endpoint in GG, and the weight of such edge between this two vertices is the sum of the weights of their corresponding edges.
A maximum weighted matching in a simple undirected weighted graph is defined as a set of edges where no two edges share a common vertex and the sum of the weights of the edges in the set is maximized.
Given a simple undirected weighted connected graph GG, your task is to find the sum of the weights of the edges in the maximum weighted matching of L(G)L(G).
输入描述:
The first line contains two integers nn (3 \le n \le 10^5)(3≤n≤10
5
) and mm (n-1 \le m \le \min(\frac{n(n-1)}{2}, 2 \times 10^5))(n−1≤m≤min(
2
n(n−1)
,2×10
5
)), indicating the number of vertices and edges in the given graph GG.
Then follow mm lines, the ii-th of which contains three integers uu, vv (1 \le u, v \le n)(1≤u,v≤n) and ww (1 \le w \le 10^9)(1≤w≤10
9
), indicating that the ii-th edge in the graph GG has a weight of ww and connects the uu-th and the vv-th vertices. It is guaranteed that the graph GG is connected and contains no loops and no multiple edges.
输出描述:
Output a line containing a single integer, indicating the sum of the weights of the edges in the maximum weighted matching of L(G)L(G).
示例1
输入
复制
5 6
1 2 1
1 3 2
1 4 3
4 3 4
4 5 5
2 5 6
输出
复制
21
示例2
输入
复制
6 5
1 2 4
2 3 1
3 4 3
4 5 2
5 6 5
输出
复制
12
示例3
输入
复制
5 5
1 2 1
2 3 2
3 4 3
4 5 4
5 1 5
输出
复制
14
题意：
- 给定一个无向图，将原图中的点换成边，边换成点。
如果原图中边1和边2公用一个端点A，那么生成图中边A的权值等于原图中边1+边2。
- 让我们求生成图中最大加权匹配（选出一组边的集合，使得集合里没有两条边公用一个顶点，使得集合中边的边权和最大），求出最大边权和
- n, m < 2e5
思路：
- 题目等价于求生成图的最大独立边集，但是转换后的图是建不出来的，所以试着在原图上找性质。
- 可以发现，对于图上的一个连通块来说：
如果边数为偶数，我们可以把所有边放入答案集中。
如果边数为奇数，我们需要删掉一条边再放入答案。
同时，我们不能删除这个联通块的桥，否则会多出两条无法匹配的边。
- 所以写法就是枚举奇数时要删哪条边：
如果这条边不是桥，那么对答案的贡献就是总权值和减去这条边的权值。
如果这条边是桥，我们再对两边都分别再删一条边进行讨论。
即tarjan找出所有桥两边连通块中边的个数更新答案。
- 也可以用并查集维护联通块的连通性，贪心的将边权按从大到小排序后加入集合，再额外的维护一个当前联通块是否存在尚未匹配且无法与其他边匹配的奇数边。
- 如果边u和v本就在一个集合。
如果本来存在单边，就匹配。
如果本来不存在单边，那么这条就是单边。
- 如果边u和v不在一个集合，此时需要合并联通块。
合并时如果两个集合本来就存在单边，那么u-v就是桥，让u-v与原先两个集合中大的单边匹配，然后保留小的单边。
如果本来都不存在单边，那么u-v就是新的单边。
如果本来一个存在单边，那么直接与u-v匹配。
#include<bits/stdc++.h>
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<<res<<"\n";
return 0;
}