codeforces 1600-2200 题目刷

F. Graph Without Long Directed Paths

题意

给定一个无向图,里面没有重边也没有circle也就是自反。问把这个无向图变成有向图,怎么变才能使得图中的路径没有超过2的,就是可以穿过两条边的路径。

输出是 每条边是正向还是反向。

题解

一开始想着只能有树的格式,但是其实是找一个偶数环。如果有奇数环就一定无法实现路径小于2,偶数环都可以实现。之后将每个点指定为1或者0。之后如果1到0就把边置为1,0到1就把边置为0。详情请看代码。

ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head

const int maxn = 2e5+10;
struct node{
int next,to;
}G[maxn<<2];
int head[maxn];
int cnt;
void init(){
cnt = 0;
memset(head,-1,sizeof(head));
}
void addedge(int u,int v){
G[cnt].to = v;
G[cnt].next = head[u];
head[u] = cnt++;
}
int n,m;
map<pair<int,int>,int> mx;
int vis[maxn];
bool flag = false;
void dfs(int u,int fa,int f){
vis[u] = f;
for(int i=head[u];~i;i=G[i].next){
int v = G[i].to;
if(v == fa) continue;
mx[make_pair(u,v)] = f;
mx[make_pair(v,u)] = f^1;
if(vis[v] == -1){
}else{
if(vis[v]^vis[u]) continue;
else {
flag = true;
continue;
}
}
dfs(v,u,f^1);
}
}
int main(){
#ifdef LOCAL
freopen("1.in","r",stdin);
#endif
init();
scanf("%d%d",&n,&m);
vector<pair<int,int> > ve;
rep(i,0,m){
int u,v; scanf("%d%d",&u,&v);
addedge(u,v);
addedge(v,u);
ve.push_back(make_pair(u,v));
}
memset(vis,-1,sizeof(vis));
dfs(1,-1,1);
if(flag) {
puts("NO");
}else{
puts("YES");
for(auto &x : ve){
printf("%d",mx[x]);
}
puts("");
}

return 0;
}

E. Median String

题意

问两个字符串$s,t$。他们字典序中间的那个字符串是什么。

举个栗子: a 和 e的中间字符串就是c。

题解

就是模拟大数加和大数除法。将字符串看成26进制的数字。

ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head

const int maxn = 2e5+10;
char s[maxn];
char t[maxn];
char ans[maxn];
char temp[maxn];
int n;
int main(){
#ifdef LOCAL
freopen("2.in","r",stdin);
#endif
scanf("%d",&n);
scanf("%s",s+1);
scanf("%s",t+1);
int flag = 0;
per(i,1,n+1){
int tt = (s[i] + t[i] - 'a'*2 + flag);
flag = 0;
if(tt >= 26) flag = 1;
temp[i] = (tt%26+'a');
}
int ttt = 1;
if(flag) temp[0] = 'b';
if(flag) ttt=0;
flag = 0;
rep(i,ttt,n+1){
int tt = (temp[i] - 'a' + flag*26);
flag = 0;
if(tt%2==1) flag = 1;
tt /=2;
ans[i] = (tt+'a');
}
printf("%s",ans+1);
return 0;
}