$A. Diverse Strings$

A. Diverse Strings

$Description$

Description

有n次询问，每次询问一个字符串
st是否合法。合法输出”Yes”，否则输出”No”。每次询问以及回答都要换行。
“合法”：所有单个字母都是连续排列，但这并不意味着必须要严格相邻连续，如fced和r是合法的。
“不合法”：字母不连续排列的以及重复出现同一个字母。如az和babc
“连续排列”：即按照字母表顺序。注意’A’和’Z’不是相邻的。

$Solution$

Solution

受不了了，太水了太水了
签到题，很明显直接排序，然后如果相邻的字母在字母表里不是相邻的就直接NO。因为题目要求连续排列和不能重复嘛。对不起我实在憋不出什么话了，直接看代码吧

$Code$

Code

#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<bitset> #include<vector> #define ls (p<<1) #define rs (p<<1|1) //#pragma GCC optimize (2) //#pragma G++ optimize (2) #define over(i,s,t) for(register int i = s;i <= t;++i) #define lver(i,t,s) for(register int i = t;i >= s;--i) //#define int __int128 #define lowbit(p) p&(-p) using namespace std; typedef long long ll; typedef pair<int,int> PII; const int N = 1e5+7; string s; int n,m; int main() { scanf("%d",&n); over(i,1,n){         cin>>s; bool flag = 0; sort(s.begin(),s.end()); for(int i = 0;i<s.length()-1;++i){ if(s[i+1] - s[i] != 1){                 flag = 1; break; } } if(flag)puts("No"); else puts("Yes"); } } 

$B. Parity Alternated Deletions$

B. Parity Alternated Deletions

$Description$

Description

Polycarp有一个有n个数的数组，他会轮流从中删去数，比如：奇数-偶数-奇数-偶数-奇数-偶数-奇数-偶数··· 或：偶数-奇数-偶数-奇数-偶数-奇数-偶数-奇数···直到无法删除。

$Solution$

Solution

太水了太水了

直接模拟就好。
先算一下奇数和偶数的个数，如果个数相同或者差值就输出0（可以取完）
然后排个序，根据题意模拟取最小的即可。

$Code$

Code

#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<bitset> #include<vector> #define over(i,s,t) for(register int i = s;i <= t;++i) #define lver(i,t,s) for(register int i = t;i >= s;--i) //#define int __int128 #define lowbit(p) p&(-p) using namespace std; typedef long long ll; typedef pair<int,int> PII; const int N = 2e3+7; int n; int odd[N],even[N]; int main() { scanf("%d",&n); int tot1 = 0; int tot2 = 0; over(i,1,n){ int a; scanf("%d",&a); if(a&1)             odd[++tot1] = a; else even[++tot2] = a; } if(abs(tot1 - tot2)<=1){ puts("0"); return 0; } sort(odd+1,odd+1+tot1); sort(even+1,even+1+tot2); int ans = 0; if(tot1>tot2){ for(int i = 1;i <(tot1-tot2);++i)             ans += odd[i]; printf("%dn",ans); } else { for(int i = 1;i <(tot2-tot1);++i)             ans += even[i]; printf("%dn",ans); } return 0; } 

$C. Two Shuffled Sequences$

C. Two Shuffled Sequences

$D. Equalize Them All$

D. Equalize Them All

$Description$

Description

给定一个数列a，求出至少需要多少次操作才能使得a中的元素都相等。
而操作共有两种：
1操作：将
$a[i]$

a[i]变为
$a[i] + | a[i]-a[j] |$

a[i]+∣a[i]−a[j]∣
2操作：将
$a[i]$

a[i]变为
$a[i] – | a[i]-a[j] |$

a[i]−∣a[i]−a[j]∣

$Solution$

Solution

很明显这两种操作可以使得相邻不相等的数直接变成相等的数。也就是说只需要一次操作就可以使其相等。
题目中要求最少次数，贪心地想，肯定是让所有的数都变成出现次数最多的数最优。
然后就是找到出现次数最多的那一个，再正反跑两遍修改即可。
为什么要跑两遍呢，因为出现次数最大的那一个数不一定出现再哪里，正着跑一遍可以使最后都被修改，但是最前面的可能没有顾及到，所以需要再反着跑一遍。例如这个样例：

6 246662 

应该很清晰吧

$Code$

Code

#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<bitset> #include<vector> #define over(i,s,t) for(register int i = s;i <= t;++i) #define lver(i,t,s) for(register int i = t;i >= s;--i) //#define int __int128 #define lowbit(p) p&(-p) using namespace std; typedef long long ll; typedef pair<int,int> PII; const int N = 2e5+7; int n,m; int cnt[N]; int a[N],maxx,max_num; int main() { scanf("%d",&n); over(i,1,n){ scanf("%d",&a[i]);         cnt[a[i]]++; } over(i,1,n) if(maxx < cnt[a[i]])             maxx = cnt[a[i]],max_num = a[i];     cout<<n - maxx<<endl; if(n == maxx)return 0;//顺手特判一下 over(i,2,n) if(a[i-1] == max_num && a[i] != max_num) if(a[i]>a[i-1]) printf("2 %d %dn",i,i-1),a[i] = a[i-1]; else printf("1 %d %dn",i,i-1),a[i] = a[i-1]; lver(i,n-1,1) if(a[i+1] == max_num && a[i] != max_num) if(a[i]>a[i+1]) printf("2 %d %dn",i,i+1),a[i] = a[i+1]; else printf("1 %d %dn",i,i+1),a[i] = a[i+1]; return 0; } 

$E. Median String$

E. Median String

$Description$

Description

给定长度为k的字符串s和t，保证s的字典序小于t。现有一个字典序单调递增的序列，其中所有的字符串长度都是k，字典序满足大于等于s且小于等于t。求出这个序列位于中间的字符串。
数据保证序列长度是奇数。
例：k=2,s=“az”,t=“bf”
序列就会是：[az,ba,bb,bc,bd,be,bf]
中间的字符串是：bc

$Solution$

Solution

这道题实际上就是让求一下26进制加法以及求中间数
遇见这种不熟悉的我们最好模拟一下我们熟悉的类似运算，比如10进制运算。

那么让我们模拟一下10进制的加法及求中间数

如193，286
192 + 286 = 478
百位4/2=2 十位 7/2=3 个位10+8/2=9
所以说如果当前位为奇数，那么除以2以后，下一位需要加上10

那么类比到26进制里，也是一样

$Code$

Code

#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<bitset> #include<vector> #define over(i,s,t) for(register int i = s;i <= t;++i) #define lver(i,t,s) for(register int i = t;i >= s;--i) //#define int __int128 #define lowbit(p) p&(-p) using namespace std; typedef long long ll; typedef pair<int,int> PII; const int N = 2e5+7; int n,m,k; string s1,s2; int arr[N]; int up,a; int main() { scanf("%d",&k);     cin>>s1>>s2; lver(i,k-1,0){ int a = s1[i] - 'a'; int b = s2[i] - 'a';         arr[i] = a+b+up; if(arr[i]>=26 && i != 0)up = 1,arr[i] -= 26;//26进制，注意进位 else up = 0; } over(i,0,k-1){ if(arr[i]&1)             arr[i+1] += 26;         arr[i] /= 2; } over(i,0,k-1){ printf("%c",arr[i] + 'a');//还原为字母 } puts(""); return 0; } 

$F. Graph Without Long Directed Paths$

F. Graph Without Long Directed Paths

一道水题，二分图染色。

$Description$

Description

给你一个无向图，把所有边标记方向，并使整张图中没有距离 ≥2 的路径，问你是否存在并输出方案。

第一行输出“YES”或“NO”，若存在，第二行按照读入顺序输出连边方向（对于每一条边，如果该条边的连边方向是按照输入的方向有
$u_i$

ui​到
$v_i$

vi​就输出1，否则就输出0）。

$Solution$

Solution

很明显这是一道染色问题，如果路径≥2，那么就会有两个相邻的点同时为入，或者同时为出。如果没有，就说明没有两条边或以上是连着走的。
画一下样例，顺便加一点数据。

虽然入度和出度不是这个意思，但是这里把它魔改一下用还是挺清晰的
然后代码就非常简单了。

$Code$

Code

#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<bitset> #include<vector> #define over(i,s,t) for(register int i = s;i <= t;++i) #define lver(i,t,s) for(register int i = t;i >= s;--i) //#define int __int128 #define lowbit(p) p&(-p) using namespace std; typedef long long ll; typedef pair<int,int> PII; const int N = 2e5+7; struct node{int u,v,val;}a[N]; int n,m; vector<int>G[N]; int vis[N];//记录颜色 int v[N];//记录是否走过 void dfs(int now,int sta){     vis[now] = sta;     v[now] = 1; //cout<<sta<<endl; for(int i = 0;i < G[now].size();++i){ int to = G[now][i]; if(!v[to]) dfs(to,-sta);//往下染 } } int main() { bool flag = 1; scanf("%d%d",&n,&m); over(i,1,m){ int u,v; scanf("%d%d",&a[i].u,&a[i].v);         G[a[i].u].push_back(a[i].v);//先建无向图         G[a[i].v].push_back(a[i].u); } dfs(1,1);//染色 over(i,1,m){ if(vis[a[i].u] != vis[a[i].v]){ if(vis[a[i].u] == 1)//是出度则为1也就是选择的边是从ui到vi的                 a[i].val = 1; else a[i].val = 0;//不是则为0 } else flag = 0; } if(!flag){ puts("NO"); } else { puts("YES"); over(i,1,m) printf("%d",a[i].val); puts(""); } return 0; }