codeforces 1600-2200 题目刷

F. Graph Without Long Directed Paths

题意

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

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

题解

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

ac代码

#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代码

#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;
}