23.8.18 牛客暑期多校10部分题解

L - Grayscale Confusion

题目大意

有 $n$ 个三元组 { r i ,   g i ,   b i } \{r_i,\space g_i,\space b_i\} {ri​, gi​, bi​}，需要构造一个数组 $w_i$ 使得 $w_1=w_2$ 并且对于 $\forall i,j$ 满足如果$r_i<r_j,g_i<g_j,b_i<b_j$ 那么 $w_i<w_j$，若不存在输出 $-1$

解题思路

根据数据范围可以想到满足条件的建有向边然后跑一遍宽度优先的拓扑

在搜索到 $1,2$ 两个点时暂停，记录，并作为第二遍拓扑的开始使得二者想等即可

听说题解还有更高级的做法，貌似可以用偏序的方法把时间复杂度优化到 $O(n)$，可以自行了解

code

#include 
using namespace std;
const int N = 1009;
struct lol {int x, y;} e[N * N];
int n, ans, top[N], din[N], fl, r[N], g[N], b[N], w[N];
queue <int> q;
int bj(int x, int y) {return r[x] < r[y] && g[x] < g[y] && b[x] < b[y];}
void ein(int x, int y) {
    e[++ ans].x = top[x];
    e[ans].y = y;
    top[x] = ans;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i)
        scanf("%d%d%d", &r[i], &g[i], &b[i]);
    for (int i = 1; i <= n; ++ i)
        for (int j = i + 1; j <= n; ++ j) {
            if (bj(i, j)) ein(i, j), ++ din[j];
            if (bj(j, i)) ein(j, i), ++ din[i];
        }
    for (int i = 1; i <= n; ++ i) if (!din[i]) q.push(i);
    while (!q.empty()) {
        int x = q.front(); q.pop();
        if (x == 1 || x == 2) {fl += x; continue;}
        for (int i = top[x]; i; i = e[i].x) {
            int y = e[i].y;
            w[y] = max(w[y], w[x] + 1);
            -- din[y];
            if (!din[y]) q.push(y);
        }
    }
    if (fl != 3) {printf("-1"); return 0;}
    w[1] = w[2] = max(w[1], w[2]);
    q.push(1); q.push(2);
    while (!q.empty()) {
        int x = q.front(); q.pop();
        for (int i = top[x]; i; i = e[i].x) {
            int y = e[i].y;
            w[y] = max(w[y], w[x] + 1);
            -- din[y];
            if (!din[y]) q.push(y);
        }
    }
    for (int i = 1; i <= n; ++ i)
        printf("%d\n", w[i]);
    return 0;
}
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

D - Agnej

code

#include 
using namespace std;
const int N = 1e5 + 9;
int n, m, a[N], fl, ag;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= m; ++ j) scanf("%1d", &a[j]), a[j] += a[j - 1];
        if (m % 2 == 0) fl ^= (a[m] & 1);
        else if (a[m / 2 + 1] - a[m / 2] == 0) fl ^= (a[m] & 1);
        else if (a[m / 2] - a[0] == 0 || a[m] - a[m / 2 + 1] == 0) fl ^= ((a[m] & 1) ^ 1);
        else if (a[m / 2] - a[0] == 1 || a[m] - a[m / 2 + 1] == 1) fl ^= (a[m] & 1), ag ^= 1;
        else fl ^= (a[m] & 1);
    }
    printf(ag || fl ? "Alice" : "Bob");
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17