Duck's Blog

热爱 Coding 的普通人

NOIP2022 联考 补题记录

发布于 2022-11-24 | 标签: 学习笔记 | 21分钟 | 3792字数

封闭了两周还是什么都不会，真逗乐。

11.14 T1

最终的状态一定是所有 11 都上浮并形成一个连通块。

由于让 11 上浮到最高处很难一次性做到位，可以考虑让每一个 00 下沉到最深的位置，且深度越大对答案的贡献越大。

于是我们可以形成一个贪心策略：对于每一个点 uu ，如果 au=1a_u=1 则不用管，否则一定能把 uu 交换到其子树中深度最大的 11 处，且对答案的贡献最大。

对每一个点维护一棵权值线段树，记录其子树中所有 11 的深度，通过线段树合并或 dsu on tree\text{dsu on tree} 等方式维护即可。

时间复杂度 O(nlog⁡n)\mathcal{O}(n\log{n}) 。

Code

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5e5 + 5, MAXM = 16e6 + 5;

vector<int> g[MAXN];

long long ans;
int n, a[MAXN], dep[MAXN], fa[MAXN], rt[MAXN];
int ls[MAXM], rs[MAXM], sum[MAXM], tot;

char s[MAXN];

inline void pushup(int u) {
    sum[u] = sum[ls[u]] + sum[rs[u]];
}

void update(int &u, int l, int r, int x, int k) {
    if (!u) u = ++tot;
    if (l == r) {
        sum[u] += k;
        return;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) update(ls[u], l, mid, x, k);
    else update(rs[u], mid + 1, r, x, k);
    pushup(u);
}

int merge(int u, int v, int l, int r) {
    if (u == 0) return v;
    if (v == 0) return u;
    if (l == r) {
        sum[u] += sum[v];
        return u;
    }
    int mid = (l + r) >> 1;
    ls[u] = merge(ls[u], ls[v], l, mid);
    rs[u] = merge(rs[u], rs[v], mid + 1, r);
    return pushup(u), u;
}

int query(int u, int l, int r) {
    if (u == 0) return 0;
    if (l == r) return l;
    int mid = (l + r) >> 1;
    if (sum[rs[u]]) return query(rs[u], mid + 1, r);
    return query(ls[u], l, mid);
}

void dfs(int u) {
    dep[u] = dep[fa[u]] + 1;
    for (int v: g[u]) {
        dfs(v);
        rt[u] = merge(rt[u], rt[v], 1, n);
    }
    if (!a[u] && sum[rt[u]]) {
        int x = query(rt[u], 1, n);
        ans += x - dep[u];
        update(rt[u], 1, n, x, -1);
        update(rt[u], 1, n, dep[u], 1);
    }
    if (a[u]) update(rt[u], 1, n, dep[u], 1);
}

int main() {
    freopen("maxswap.in", "r", stdin);
    freopen("maxswap.out", "w", stdout);
    scanf("%d%s", &n, s + 1);
    for (int i = 1; i <= n; i++) {
        a[i] = s[i] - '0';
    }
    for (int i = 2, u; i <= n; i++) {
        scanf("%d%d", &u, &fa[i]);
        g[fa[i]].push_back(i);
    }
    dfs(1);
    printf("%lld\n", ans);
}

11.16 T1

改编自 [COCI2017-2018#4] Automobil

原题对应 l=rl=r 的部分分，不妨先从这里入手。

考虑到我们只关心最终状态下所有数的和，操作顺序对于结果没有影响，可以把行和列的操作分开处理。

我们在第 ii 行维护一个标记 mulimul_i ，表示这一行被乘上的系数。

维护每一列的数字和 fif_i ，由于 ai,j=(i−1)m+ja_{i,j}=(i-1)m+j 容易发现 fi=fi−1+∑i=1nmulif_i=f_{i-1}+\sum\limits_{i=1}^n mul_i 。

先把行的操作处理完之后，列的修改就变成了在 ff 上的一维问题，很容易解决了。

现在考虑区间修改。我们可以用类似差分的思想，维护数组 diffi=mulimuli−1diff_i=\dfrac{mul_i}{mul_{i-1}} ，把区间修改转换在 diffdiff 上单点修改，通过前缀积递推出 mulimul_i 即可。

询问需要离线。时间复杂度 O(n)\mathcal{O}(n) 。

Code

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6 + 5, mod = 1e9 + 7;

struct Node {
    int op, x, y;
} g[MAXN << 1];

inline int Pow(int a, int b) {
    int ret = 1;
    for (; b; b >>= 1, a = 1ll * a * a % mod) if (b & 1) ret = 1ll * ret * a % mod;
    return ret;
}
#define inv(x) Pow(x, mod - 2)

int n, m, q, k, mul[MAXN], f[MAXN], row[MAXN], col[MAXN];

int main() {
    freopen("you.in", "r", stdin);
    freopen("you.out", "w", stdout);
    ios::sync_with_stdi\mathcal{O}(false);
    cin >> n >> m >> q;
    fill(row + 1, row + n + 1, 1);
    fill(col + 1, col + m + 1, 1);
    fill(mul + 1, mul + n + 1, 1);
    while (q--) {
        int op, l, r, v;
        cin >> op >> l >> r >> v;
        if (op == 1) {
            row[l] = 1ll * row[l] * v % mod;
            row[r + 1] = 1ll * row[r + 1] * inv(v) % mod;
        }
        if (op == 2) {
            col[l] = 1ll * col[l] * v % mod;
            col[r + 1] = 1ll * col[r + 1] * inv(v) % mod;
        }
    }
    int pre = 1;
    for (int i = 1; i <= n; i++) {
        pre = 1ll * pre * row[i] % mod;
        g[++k] = {1, i, pre};
    }
    pre = 1;
    for (int i = 1; i <= m; i++) {
        pre = 1ll * pre * col[i] % mod;
        g[++k] = {0, i, pre};
    }
    for (int i = 1; i <= k; i++) {
        if (!g[i].op) continue;
        mul[g[i].x] = 1ll * mul[g[i].x] * g[i].y % mod;
    }
    int sum = 0;
    for (int i = 1; i <= n; i++) sum = (sum + mul[i]) % mod;
    for (int i = 1; i <= n; i++) f[1] = (f[1] + 1ll * (1ll * (i - 1) * m % mod + 1) * mul[i]) % mod;
    for (int i = 2; i <= m; i++) f[i] = 1ll * (f[i - 1] + sum) % mod;
    for (int i = 1; i <= k; i++) {
        if (g[i].op) continue;
        f[g[i].x] = 1ll * f[g[i].x] * g[i].y % mod;
    }
    int ans = 0;
    for (int i = 1; i <= m; i++) ans = (ans + f[i]) % mod;
    cout << ans << endl;
}

11.17 T1

结论题。证明比较复杂，但是找规律可以比较容易地摸清楚。然后考场上就没敢猜。

考虑在置换上由 ii 向 pip_i 连一条边，最终形成的一定是由若干个独立的环（或者单点）组成的图。

然后根据样例大胆猜结论，对于一个环，如果环长度为 u=2ku=2^k ，那么对答案的贡献为 2u2^u ，否则为 22 。

全部乘起来就对了。时间复杂 O(∑n)\mathcal{O}(\sum n) 。

Code

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6 + 5, mod = 1e9 + 7;

int T, p[MAXN], vis[MAXN], power[MAXN], flag[MAXN], n;

int dfs(int x) {
    if (vis[x]) return 0;
    vis[x] = 1;
    return dfs(p[x]) + 1;
}

int main() {
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
    ios::sync_with_stdi\mathcal{O}(false);
    cin >> T;
    power[0] = 1;
    for (int i = 1; i <= 1e6; i++) {
        power[i] = 1ll * power[i - 1] * 2 % mod;
        flag[i] = (i & (i - 1)) == 0;
    }
    while (T--) {
        memset(vis, 0, sizeof(vis));
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> p[i];
        int ans = 1;
        for (int i = 1; i <= n; i++) {
            if (vis[i]) continue;
            int v = dfs(i);
            if (flag[v]) ans = 1ll * ans * power[v] % mod;
            else ans = 2ll * ans % mod;
        }
        cout << ans << endl;
    }
}

11.19 T1

可能是联考最简单的一道题。但是我那天弃考了，然后就输麻了。

11 到 nn 路径期望条数就是每条路径存在的概率加起来。在图上 dfs\text{dfs} 一遍就做完了。

时间复杂度 O(n+m)\mathcal{O}(n+m) 。

Code

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 5;

struct edge {
    int v, next;
    double w;
    edge() = default;
} e[MAXN];

int h[MAXN], in[MAXN], n, m, eid;

inline void insert(int u, int v, double w) {
    e[eid].v = v;
    e[eid].next = h[u];
    e[eid].w = w;
    h[u] = eid++;
}

double f[MAXN];

double dfs(int u) {
    if (f[u]) return f[u];
    if (u == n) return 1;
    for (int i = h[u]; i != -1; i = e[i].next) {
        int v = e[i].v;
        f[u] += dfs(v) * e[i].w;
    }
    return f[u];
}

int main() {
    freopen("count.in", "r", stdin);
    freopen("count.out", "w", stdout);
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof(h));
    for (int i = 1, u, v; i <= m; i++) {
        double w;
        scanf("%d%d%lf", &u, &v, &w);
        insert(u, v, w);
    }
    printf("%.2lf\n", dfs(1));
}

11.19 T2

考虑从小到大填数。把已经确定的点按照点权排序，模拟填数过程即可。

时间复杂度 O(Tn)\mathcal{O}(Tn) 。

Code

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e4 + 5;

vector<int> g[MAXN];

int T, n, cnt, w[MAXN];

pair<int, int> p[MAXN];

bool dfs(int u, int val) {
    cnt++;
    for (int v: g[u]) {
        if (w[v] > val || !w[v] && dfs(v, val))
            return true;
    }
    return false;
}

int main() {
    freopen("heap.in", "r", stdin);
    freopen("heap.out", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) 
            g[i].clear();
        for (int i = 1, fa; i <= n; i++) {
            scanf("%d", &fa);
            g[fa].push_back(i);
        }
        int k = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &w[i]);
            if (w[i]) p[++k] = {w[i], i};
        }
        int flag = 1;
        sort(p + 1, p + k + 1);
        cnt = 0;
        for (int i = 1; i <= k; i++) 
            if (dfs(p[i].second, p[i].first) || cnt > p[i].first) {
                flag = 0; break;
            }
        printf("%d\n", flag);
    }
}

11.19 T4

神仙题。

对于原图的一棵生成树，定义原图中连接祖先和后代的非树边为返祖边，连接没有祖先关系两点的非树边为横叉边。

一个非常重要的性质：对于最优的生成树，所有的非树边一定都为返祖边，如果存在非树边是横叉边，那么我们可以删除一条树边，把这条横叉边变成树边来增大答案。

由上面的性质，设点集为 SS ，考虑 u∈Su\in S 且 uu 不为根，则所有与 uu 相连的 vv 且 v∈Sv\in S 都和 uu 在同一棵子树上，否则 (u,v)(u,v) 为横叉边，进而每个点的子树点集确定。

注意到 n≤16n\le 16 ，考虑状压dp 。

设 f(u,S)f(u,S) 为以 uu 为根的子树点集为 SS 的答案，每次确定一个儿子 vv 及其子树点集 TT ，则有

f(u,S)=1+max⁡{f(v,T)+f(u,∁ST)+∣T∣}f(u,S)=1+\max\{f(v,T)+f(u,\complement_ST)+|T|\}

转移时枚举 vv 即可，时间复杂度 O(n22n)\mathcal{O}(n^22^n) 。

Code

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 21;

int f[MAXN][1 << MAXN], g[MAXN][MAXN], fa[MAXN], n, m;
int popc[1 << MAXN], st[1 << MAXN];

int getf(int x) {
    return x == fa[x] ? x : fa[x] = getf(fa[x]);
}

inline void merge(int x, int y) {
    x = getf(x);
    y = getf(y);
    if (x != y) fa[y] = x;
}

int main() {
    freopen("tree.in", "r", stdin);
    freopen("tree.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v; i <= m; i++) {
        scanf("%d%d", &u, &v);
        u--, v--;
        g[u][v] = g[v][u] = 1;
    }
    for (int s = 0; s < (1 << n); s++) {
        for (int i = 0; i < n; i++) fa[i] = i;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                if ((s >> i & 1) && (s >> j & 1) && g[i][j])
                    merge(i, j);
            }
        int rt = -1;
        for (int i = 0; i < n; i++)
            if (s >> i & 1) {
                if (rt == -1) rt = i;
                popc[s]++;
                if (getf(i) == getf(rt)) st[s] |= 1 << i;
            }
    }
    for (int s = 0; s <= (1 << n) - 1; s++)
        for (int i = 0; i < n; i++)
            if (s >> i & 1) {
                int p = s ^ (1 << i);
                int k = st[p];
                if (k == 0) f[i][s] = 1;
                for (int j = 0; j < n; j++) {
                    if (g[i][j] && (st[p] >> j & 1))
                        f[i][s] = max(f[i][s], f[i][s ^ k] + f[j][k] + popc[k]);
                }
            }
    printf("%d\n", f[0][(1 << n) - 1]);
}

11.24 T1

答案为

min⁡(x,y)max⁡i=1n{∣x−xi∣+∣y−yi∣}\min\limits_{(x,y)}\max\limits_{i=1}^n\{|x-x_i|+|y-y_i|\}

把绝对值拆开：

min⁡(x,y)max⁡i=1n{(x+y)−(xi+yi),(xi+yi)−(x+y),(x−y)−(xi−yi),(xi−yi)−(x−y)}\min\limits_{(x,y)} \max\limits_{i=1}^n\{(x+y)-(x_i+y_i),(x_i+y_i)-(x+y),(x-y)-(x_i-y_i),(x_i-y_i)-(x-y)\}

令

A=max⁡i=1n(xi+yi)A=\max\limits_{i=1}^n(x_i+y_i)

B=min⁡i=1n(xi+yi)B=\min\limits_{i=1}^n(x_i+y_i)

C=max⁡i=1n(xi−yi)C=\max\limits_{i=1}^n(x_i-y_i)

D=min⁡i=1n(xi−yi)D=\min\limits_{i=1}^n(x_i-y_i)

u=x+yu=x+y

v=x−yv=x-y

则答案为

min⁡(x,y)max⁡{A−u,u−B,C−v,v−D}\min\limits_{(x,y)}\max\{A-u,u-B,C-v,v-D\}

易知当 u=A+B2,v=C+D2u=\dfrac{A+B}{2},v=\dfrac{C+D}{2} 时取得最小值，此时答案为

max⁡{A−B2,C−D2}\max\{\dfrac{A-B}{2},\dfrac{C-D}{2}\}

时间复杂度 Θ(n)\Theta(n) 。

Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
    ios::sync_with_stdi\mathcal{O}(false);
    int n, a = -2e9, b = 2e9, c = -2e9, d = 2e9, x, y;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x >> y;
        a = max(a, x + y);
        b = min(b, x + y);
        c = max(c, x - y);
        d = min(d, x - y);
    }
    cout << max(a - b, c - d) / 2 << endl;
}

11.24 T2

两周以来唯一场切的题目。

考虑 pp 最多也就 66 种，可以分情况枚举。

预处理出位置 ii 左边比 aia_i 大的个数 l>(i)l_{>}(i) ，左边比 aia_i 小的个数 l<(i)l_{<}(i) ，右边比 aia_i 大的个数 r>(i)r_{>}(i) ，右边比 aia_i 小的个数 r<(i)r_{<}(i) ，分类讨论：

  • p=(1,2,3)p=(1,2,3) 答案为 ∑i=1nl<(i)×r>(i)\sum\limits_{i=1}^nl_{<}(i)\times r_{>}(i) 。

  • p=(3,2,1)p=(3,2,1) 答案为 ∑i=1nl>(i)×r<(i)\sum\limits_{i=1}^nl_{>}(i)\times r_{<}(i) 。

  • p=(2,1,3)p=(2,1,3) 答案为 ∑i=1n(l<(i)2)−ans(1,2,3)\sum\limits_{i=1}^n\dbinom{l_{<}(i)}{2}-ans_{(1,2,3)} 。

  • p=(2,3,1)p=(2,3,1) 答案为 ∑i=1n(l>(i)2)−ans(3,2,1)\sum\limits_{i=1}^n\dbinom{l_{>}(i)}{2}-ans_{(3,2,1)} 。

  • p=(1,3,2)p=(1,3,2) 答案为 ∑i=1nl<(i)×r<(i)−ans(2,3,1)\sum\limits_{i=1}^nl_{<}(i)\times r_{<}(i)-ans_{(2,3,1)} 。

  • p=(3,1,2)p=(3,1,2) 答案为 ∑i=1nl>(i)×r>(i)−ans(2,1,3)\sum\limits_{i=1}^nl_{>}(i)\times r_{>}(i)-ans_{(2,1,3)} 。

预处理用权值线段树/树状数组，时间复杂度 O(nlog⁡n)\mathcal{O}(n\log{n}) 。

Code

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 5;

int p[4], c[MAXN], a[MAXN], l_gt[MAXN], l_lt[MAXN], r_gt[MAXN], r_lt[MAXN], n;

long long ans[4][4][4];

#define lowbit(x) x & -x

inline void add(int x, int k) {
    for (; x <= n; x += lowbit(x)) c[x] += k;
}

inline int query(int x) {
    int res = 0;
    for (; x; x -= lowbit(x)) res += c[x];
    return res;
}

signed main() {
    freopen("b.in", "r", stdin);
    freopen("b.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 1; i <= 3; i++) {
        scanf("%d", &p[i]);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= n; i++) {
        add(a[i], 1);
        l_lt[i] = query(a[i] - 1);
        l_gt[i] = i - query(a[i]);
    }
    memset(c, 0, sizeof(c));
    for (int i = n; i >= 1; i--) {
        add(a[i], 1);
        r_lt[i] = query(a[i] - 1);
        r_gt[i] = n - i - query(a[i]) + 1;
    }
    for (int i = 1; i <= n; i++) {
        ans[1][2][3] += 1ll * l_lt[i] * r_gt[i];
        ans[3][2][1] += 1ll * l_gt[i] * r_lt[i];
    }
    long long ans1 = 0;  // 231 + 321
    long long ans2 = 0;  // 123 + 213
    for (int i = 1; i <= n; i++) {
        ans1 += 1ll * l_gt[i] * (l_gt[i] - 1) / 2;
        ans2 += 1ll * l_lt[i] * (l_lt[i] - 1) / 2;
    }
    ans[2][1][3] = ans2 - ans[1][2][3];
    ans[2][3][1] = ans1 - ans[3][2][1];
    long long ans3 = 0;  // 213 + 312
    long long ans4 = 0;  // 132 + 231
    for (int i = 1; i <= n; i++) {
        ans3 += 1ll * l_gt[i] * r_gt[i];
        ans4 += 1ll * l_lt[i] * r_lt[i];
    }
    ans[3][1][2] = ans3 - ans[2][1][3];
    ans[1][3][2] = ans4 - ans[2][3][1];
    printf("%lld\n", ans[p[1]][p[2]][p[3]]);
}
赞赏
# 学习笔记
已运行:
浏览数: 次 | 访客数: 人
Powered by Gridea
0%
召唤看板娘