「解题报告」Codeforces Round 669 (Div. 2)

蒟蒻下分场……

比赛链接

A. Ahahahahahahahaha

注意到 01 串一定有 $\ge n/2$ 个 0 或者 1，依此构造即可。

int c = 0; memset(a, 0, sizeof(a));
n = read(); for(int i = 1; i <= n; i++) a[i] = read(), c += (a[i] == 0);
n /= 2;
if(n & 1){
    if(c >= n){
        printf("%d", n), puts("");
        for(int i = 1; i <= n; i++) printf("0 ");puts("");
    }
    else if(!c){
        printf("%d", n << 1), puts("");
        for(int i = 1; i <= n * 2; i++) printf("1 ");  puts("");      
    }
    else{
        printf("%d", n + 1), puts("");
        for(int i = 1; i <= n + 1; i++) printf("1 ");  puts("");
    }
    continue;
}
if(c >= n){
    printf("%d", n), puts("");
    for(int i = 1; i <= n; i++) printf("0 ");
}
else{
    printf("%d", n), puts("");
    for(int i = 1; i <= n; i++) printf("1 ");
}

B. Big Vova

$O(n^2)$ 贪心即可。

for(int i = 1; i <= n; i++) usd[i] = 0;
n = read(); for(int i = 1; i <= n; i++) a[i] = read();
int lst = 0;
for(int i = 1; i <= n; i++) {
    int mx = 0;
    for(int j = 1; j <= n; j++){
        if(usd[j]) continue;
        if(mx == 0) mx = j;
        if(gcd(lst, a[mx]) < gcd(lst, a[j])) mx = j;
    }
    usd[mx] = 1, b[i] = a[mx];
    lst = gcd(lst, a[mx]);
}
for(int i = 1; i <= n; i++) printf("%d ", b[i]); puts("");

C. Chocolate Bunny

连续询问 $x,y$ 和 $y, x$，得到 $a,b$，则有 $\max(a,b)=\min(p_x,p_y)$，依此模拟即可。

n = read(); int lst = 1;
for(int i = 2; i <= n; i++){
    int x, y, z;
    printf("? %d %d\n", lst, i); fflush(stdout); 
    x = read();
    printf("? %d %d\n", i, lst); fflush(stdout); 
    y = read(), z = max(x, y);
    if(x < y) a[i] = z ;
    else a[lst] = z, lst = i;
}
for(int i = 1; i <= n; i++) vis[ a[i] ]++;
for(int i = 1; i <= n; i++) if(!vis[i]) {a[lst] = i; break;}
printf("! "); for(int i = 1; i <= n; i++) printf("%d ", a[i]); fflush(stdout);

D. Discrete Centrifugal Jumps

理性分析一下，边数看上去不是 $O(n^2)$ 的而是 $O(n)$ 的，那么可以线性地把图建出来，单调栈维护一下即可。
但是这个题并不需要最短路算法，注意到这是一个 DAG，因此直接 DP 计算即可，时间复杂度 $O(n)$。

n = read(); for(int i = 1; i <= n; i++) a[i] = read();
    
memset(f, 0x3f, sizeof(f)), f[1] = 0;
stk1[++top1] = 1, stk2[++top2] = 1;
for(int i = 2; i <= n; i++){
    while(top1 && a[ stk1[top1] ] < a[i]){
        f[i] = min(f[i], f[ stk1[top1] ]);
        while(top1 && a[ stk1[top1] ] == a[ stk1[top1 - 1] ]) top1--;
        if(top1) top1--;
    }
    if(top1) f[i] = min(f[i], f[ stk1[top1] ]);
    stk1[++top1] = i;

    while(top2 && a[ stk2[top2] ] > a[i]){
        f[i] = min(f[i], f[ stk2[top2] ]);
        while(top2 && a[ stk2[top2] ] == a[ stk2[top2 - 1] ]) top2--;
        if(top2) top2--;
    }
    if(top2) f[i] = min(f[i], f[ stk2[top2] ]);
    stk2[++top2] = i;

    f[i]++;
}

printf("%lld", f[n]);

E. Egor in the Republic of Dagestan

算是比较裸的一道 E 题了……
设 $f[u,0/1]$ 表示在 $u$ 点，选 0 边还是选 1 边的答案，对于一条边 $u\gets v$，应当有 $f[u,c]\gets \max(f[v,0],f[v,1])+1$，其中 $c$ 代表边 $u\gets v$ 的颜色。
注意到一个点不会被松弛超过一次，直接跑 Dijkstra 转移即可，时间复杂度 $O((n+m)\log n)$。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;

const int CN = 1e6 + 6;
const int INF = 0x3f3f3f3f;

class fs {public: int to,nxt,tp; void init(int t,int n,int p) {to = t, nxt = n, tp = p;} } E[CN << 1];
int hd[CN], ecnt = 0; void add(int x,int y,int z) {E[++ecnt].init(y, hd[x], z); hd[x] = ecnt;}

int n, m;

class DJ {public: int v, id; bool operator < (const DJ &a) const {return v > a.v;}} ;
DJ mk(int a, int b) {DJ d; d.v = a, d.id = b; return d;}
int d[CN][2]; bool vis[CN]; priority_queue<DJ> Q;
void SP(int u){
    memset(d, 0x3f, sizeof(d)), Q.push( mk(d[u][0] = d[u][1] = 0, u) );
    while(!Q.empty()){
        u = Q.top().id, Q.pop();
        if(vis[u]) continue; vis[u] = true; 
        int dis = max(d[u][0], d[u][1]);
        for(int k = hd[u]; k; k = E[k].nxt){
            int v = E[k].to, c = E[k].tp, cur; if(vis[v]) continue;
            if(d[v][c] > dis + 1){
                d[v][c] = dis + 1, cur = max(d[v][0], d[v][1]);
                if(cur < INF) Q.push( mk(cur, v) );
            }
        }
    }
}

int main()
{
    n = read(), m = read();
    for(int i = 1; i <= m; i++) {int u = read(), v = read(), t = read(); add(v, u, t);}
    SP(n);
    
    if(max(d[1][0], d[1][1]) < INF) printf("%d", max(d[1][0], d[1][1])), puts("");
    else puts("-1");
    for(int i = 1; i <= n; i++) putchar(d[i][0] > d[i][1] ? '0' : '1');
}