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

蒟蒻下分场……

比赛链接

A. Ahahahahahahahaha

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

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
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)$ 贪心即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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)$,依此模拟即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
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)$。

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
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)$。

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<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');
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×