目录
- A. Diverse Strings
- B. Parity Alternated Deletions
- C. Two Shuffled Sequences
- D. Equalize Them All
- E. Median String
- F. Graph Without Long Directed Paths
A. Diverse Strings
Description
有n次询问，每次询问一个字符串
st是否合法。合法输出"Yes"，否则输出"No"。每次询问以及回答都要换行。
“合法”：所有单个字母都是连续排列，但这并不意味着必须要严格相邻连续，如fced和r是合法的。
“不合法”：字母不连续排列的以及重复出现同一个字母。如az和babc
“连续排列”：即按照字母表顺序。注意’A’和’Z’不是相邻的。
Solution
受不了了，太水了太水了
签到题，很明显直接排序，然后如果相邻的字母在字母表里不是相邻的就直接NO。因为题目要求连续排列和不能重复嘛。对不起我实在憋不出什么话了，直接看代码吧
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
Description
Polycarp有一个有n个数的数组，他会轮流从中删去数，比如：奇数-偶数-奇数-偶数-奇数-偶数-奇数-偶数··· 或：偶数-奇数-偶数-奇数-偶数-奇数-偶数-奇数···直到无法删除。
Solution
太水了太水了
直接模拟就好。
先算一下奇数和偶数的个数，如果个数相同或者差值就输出0（可以取完）
然后排个序，根据题意模拟取最小的即可。
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("%d\n",ans);
}
else {
for(int i = 1;i <(tot2-tot1);++i)
ans += even[i];
printf("%d\n",ans);
}
return 0;
}
C. Two Shuffled Sequences
D. Equalize Them All
Description
给定一个数列a，求出至少需要多少次操作才能使得a中的元素都相等。
而操作共有两种：
1操作：将a[i]变为a[i]+∣a[i]−a[j]∣
2操作：将a[i]变为a[i]−∣a[i]−a[j]∣
Solution
很明显这两种操作可以使得相邻不相等的数直接变成相等的数。也就是说只需要一次操作就可以使其相等。
题目中要求最少次数，贪心地想，肯定是让所有的数都变成出现次数最多的数最优。
然后就是找到出现次数最多的那一个，再正反跑两遍修改即可。
为什么要跑两遍呢，因为出现次数最大的那一个数不一定出现再哪里，正着跑一遍可以使最后都被修改，但是最前面的可能没有顾及到，所以需要再反着跑一遍。例如这个样例：
6
246662
应该很清晰吧
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 %d\n",i,i-1),a[i] = a[i-1];
else printf("1 %d %d\n",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 %d\n",i,i+1),a[i] = a[i+1];
else printf("1 %d %d\n",i,i+1),a[i] = a[i+1];
return 0;
}
E. Median String
Description
给定长度为k的字符串s和t，保证s的字典序小于t。现有一个字典序单调递增的序列，其中所有的字符串长度都是k，字典序满足大于等于s且小于等于t。求出这个序列位于中间的字符串。
数据保证序列长度是奇数。
例：k=2,s=“az”,t=“bf”
序列就会是：[az,ba,bb,bc,bd,be,bf]
中间的字符串是：bc
Solution
这道题实际上就是让求一下26进制加法以及求中间数
遇见这种不熟悉的我们最好模拟一下我们熟悉的类似运算，比如10进制运算。
那么让我们模拟一下10进制的加法及求中间数
如193，286
192 + 286 = 478
百位4/2=2 十位 7/2=3 个位10+8/2=9
所以说如果当前位为奇数，那么除以2以后，下一位需要加上10
那么类比到26进制里，也是一样
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
一道水题，二分图染色。
Description
给你一个无向图，把所有边标记方向，并使整张图中没有距离 ≥2 的路径，问你是否存在并输出方案。
第一行输出“YES”或“NO”，若存在，第二行按照读入顺序输出连边方向（对于每一条边，如果该条边的连边方向是按照输入的方向有ui到vi就输出1，否则就输出0）。
Solution
很明显这是一道染色问题，如果路径≥2，那么就会有两个相邻的点同时为入，或者同时为出。如果没有，就说明没有两条边或以上是连着走的。
画一下样例，顺便加一点数据。虽然入度和出度不是这个意思，但是这里把它魔改一下用还是挺清晰的
然后代码就非常简单了。
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;
}