NOIP 模拟赛 10.04

做题记录
, , , ,

翻牌 $\texttt{flip}$

这题是一道简单的二分查找题目。
对中位数 $x$ 进行二分（可以选择 $x \in A \cup B$ 或者 $x \in [1, 10^9] $。
每次 check 的时候计算 $\displaystyle \sum\limits_{i=1}^n[a_i \ge x] + \max\limits_{[l,r] \in [1,n]}\{\sum\limits_{i=l}^r ([b_i \ge x] - [a_i \ge x])\}$ 是否 $> \dfrac{n-1} 2$，成立则代表 $x$ 一定不在中位数的右边，即 r=mid+1，这题就做完了。
时间复杂度 $ \mathcal O (n \log_2 n) $。

Code 
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
#include <stdio.h>
#define max(a, b) ((a) > (b) ? (a) : (b))
constexpr int N = 300005;
int a[N], b[N];
int main() {
    freopen("flip.in", "r", stdin);
    freopen("flip.out", "w", stdout);
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &a[i], &b[i]);
    auto check = [n] (const int &s) {
        int cnt = 0, sum = 0, mx = 0;
        for (int i = 1; i <= n; i++) {
            cnt += a[i] >= s;
            sum += (b[i] >= s) - (a[i] >= s);
            if (sum < 0) sum = 0;
            mx = max(mx, sum);
        }
        return cnt + mx > n / 2;
    };
    int l = 1, r = 1e9, mid;
    while (l <= r) {
        mid = l + (r - l >> 1);
        if (check(mid)) l = mid + 1;
        else r = mid - 1;
    }
    printf("%d\n", r);
    return 0;
}

塔 $\texttt{tower}$

$ \texttt{caution: } \text{本题我不是很清楚，若有疑问，欢迎评论} $

这是一道思维 dp 的题目。
令 $d_i$ 表示 $i$ 与 $i+1$ 塔之间的最小高度差。
设状态 $ f(i,j) $ 表示 到了第 $i$ 个塔，该塔的高度为 $j$ 时的最小区间加次数。
容易得出
$$
\begin{gather}
g’(j) &=& min \{ g(j - d_i) ,\ g(j + d_i) + d_i \} &\qquad (g’=f_{i+1}, g=f_{i}) \\
f(0,0) &=& 0 \\
\begin{array}{c}
f(0,1) \\
f(0,2) \\
\vdots \\
f(0, \sum\limits_{i=1}^{n-1} d_i)
\end{array} &=& +\infty
\end{gather}
$$

略证：
显然从 $j-d_i-1$ 转移不比 $j-d_i$ 好，另一种情况同理。
如果从 $j-d_i$ 转移而来，那么可以看作把前面的一些区间加 $[l, i-1]$ 更新为 $[l, i]$，总次数不变。另外一种显然需要 $d_i$ 次 $[i,i]$ 区间加，可以证明没有方案使其增加次数 小于$d_i$。

Code 
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
#include <stdio.h>
#include <string.h>
constexpr int N = 105;
int f[2][100005];
int d[N];
inline int min(int x, int y) {
    return x < y ? x : y;
}
int main() {
    freopen("tower.in", "r", stdin);
    freopen("tower.out", "w", stdout);
    int n;
    scanf("%d", &n);
    for (int i = 1; i < n; i++)
        scanf("%d", &d[i]);
    for (int i = 1; i <= 100000; i++) f[1][i] = i;
    for (int i = 1; i < n; i++) {
        auto next = f[i&1^1], pre = f[i&1];
        memset(next, 0x3f, sizeof(f) >> 1);
        for (int j = 0; j <= 100000; j++) {
//            next[j] = pre[j] + 1;
            if (j >= d[i]) next[j] = min(next[j], pre[j - d[i]] + d[i]);
            if (j + d[i] <= 100000) next[j] = min(next[j], pre[j + d[i]]);
        }
    }
    int ans = 0x3f3f3f3f;
    for (int i = 0; i <= 100000; i++)
        ans = min(ans, f[n&1][i]);
    printf("%d\n", ans);
    return 0;
}

图 $\texttt{graph}$

这题类似于性质题。
在本题中，如果一个诱导子图有 $x$ 个节点，那么最多就有 $\dfrac {3x} 2 $ 条边。而两个连通的子图至少需要 $2(x-1)$ 条边。
于是乎，我们有：
$$
\begin{aligned}
\dfrac {3x} 2 &\ge 2(x-1) \\
x &\le 4
\end{aligned}
$$
则（令 $(i, j, c)$ 表示 点 $i,j$ 之间的一条 颜色为 $c$ 的边，$E$ 为全图边集，$V$ 为全图点集）
$$
ans=\sum
\begin{Bmatrix}
n &\qquad (x=1) \\
\sum\limits_{(i,j,0) \in E} [(i,j,1) \in E] &\qquad (x=2) \\
\dots &\qquad (x=3,4)
\end{Bmatrix}
$$
为了更加直观，看图：

Code 
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
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>

constexpr int N = 100005, MOD = 998244353;
struct Edge {
    int v, c;
    inline Edge (int _v, int _c) : v(_v), c(_c) {}
    inline bool operator< (const Edge &rhs) const { return v < rhs.v; }
    inline bool operator== (const Edge &rhs) const { return v == rhs.v && c == rhs.c; }
    inline bool operator!= (const Edge &rhs) const { return v != rhs.v || c != rhs.c; }
};

std::vector<Edge> e[N];
inline bool has(int fr, int to, int c) {
    for (const Edge &y : e[fr])
        if (y == Edge(to, c)) return true;
    return false;
}
int main() {
    freopen("graph.in", "r", stdin);
    freopen("graph.out", "w", stdout);
#ifndef ONLINE_JUDGE
    #define pf(...) fprintf(stderr, __VA_ARGS__)
    freopen("graph.err", "w", stderr);
#else
    #define pf(...) 0
#endif
    int n, m;
    scanf("%d%d", &n, &m);
    for (int u, v, c; m--; ) {
        scanf("%d%d%d", &u, &v, &c);
        e[u].emplace_back(v, c);
        e[v].emplace_back(u, c);
    }
    int ans = n;
    for (int i = 1; i <= n; i++) {
        for (const Edge &ei : e[i]) {
            if (ei.v > i && ei.c && has(ei.v, i, 0)) // 找到 (i, v, 1)   v > i 
                ++ans, pf("%d %d\n", i, ei.v);
        }
    }

    int cnt3 = 0;
    for (int u = 1; u <= n; u++)
        for (Edge e1 : e[u])
        for (Edge e2 : e[u])
            if (e1 != e2 && e1.v < e2.v && e1.c && e2.c) { // 找到 (u, v1, 1) (u, v2, 1)   v1 < v2
                if (has(u, e1.v, 0) && has(e1.v, e2.v, 0) || // (u, v1, 0) (v1, v2, 0) 或 
                    has(u, e2.v, 0) && has(e2.v, e1.v, 0))   // (u, v2, 0) (v2, v1, 0)
                    ++ans, pf("%d %d %d\n", u, e1.v, e2.v);
                if (has(u, e2.v, 0)) std::swap(e1, e2);
                if (has(u, e1.v, 0) && (int)e[e1.v].size() == 3 && (int)e[e2.v].size() == 3) { // 有 (u, v1, 0)
                    int v3 = -1; // 找 (v1, v3, 0)
                    for (const Edge &e3 : e[e1.v])
                        if (e3.v != u && !e3.c) v3 = e3.v;
                    if (~v3 && has(v3, e2.v, 0) && has(v3, e2.v, 1)) // 有 (v3, v2, 0) (v3, v2, 1)
                        ++cnt3, pf("%d %d %d %d\n", u, e1.v, e2.v, v3);
                }
                // 这里还有最后一种情况，我没有写，但是仍然通过了测试数据，这数据太水了
            }
    printf("%d\n", (ans + cnt3 / 2) % MOD);
    return 0;
}
std 
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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <bits/stdc++.h>
using namespace std;
set<pair<int, int>> c[3];
int n, m;
vector<pair<int, int>> E[100005];
bool vis[100005];
int ne;
void dfs(int u) {
    vis[u] = true;
    ne++;
    for (const pair<int, int>& edge : E[u]) {
        int v = edge.first;
        if (!vis[v]) dfs(v);
    }
}

bool vis0[100005];
void dfs0(int u) {
    vis0[u] = true;
    ne++;
    for (const pair<int, int>& edge : E[u]) {
        int v = edge.first;
        int w = edge.second;
        if (w == 0 && !vis0[v]) dfs0(v);
    }
}

bool vis1[100005];
void dfs1(int u) {
    vis1[u] = true;
    ne++;
    for (const pair<int, int>& edge : E[u]) {
        int v = edge.first;
        int w = edge.second;
        if (w == 1 && !vis1[v]) dfs1(v);
    }
}

int main() {
    freopen("graph.in","r",stdin);
    freopen("graph.out","w",stdout); 
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        if (u > v) swap(u, v);
        if (c[w].find({u, v}) != c[w].end()) continue;
        E[u].emplace_back(v, w);
        E[v].emplace_back(u, w);
        c[w].insert({u, v});
    }
    int ans = n;

    for (const pair<int, int>& edge : c[0]) {
        int u = edge.first;
        int v = edge.second;
        if (c[1].count({u, v})) {
            ans++;
            c[2].insert({u, v});
        }
    }

    for (int i = 1; i <= n; i++) {
        for (const pair<int, int>& edge1 : E[i]) {
            for (const pair<int, int>& edge2 : E[i]) {
                int v1 = edge1.first;
                int w1 = edge1.second;
                int v2 = edge2.first;
                int w2 = edge2.second;
                if (w1 == 0 && w2 == 1) {
                    if (c[2].count({min(v1, v2), max(v1, v2)})) ans++;
                }
            }
        }
    }
    
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            ne = 0;
            dfs(i);
            if (ne == 4) {
                ne = 0;
                dfs0(i);
                if (ne != 4) continue;
                ne = 0;
                dfs1(i);
                if (ne != 4) continue;
                ans++;
            }
        }
    }
    cout << ans;
    return 0;
}

勇士斗恶龙 $\texttt{dragon}$