「考试总结」ZROI-21-NOIP冲刺-TEST9 总结

#T1 红黑树

Time Limit: 1s | Memory Limit: 512MiB

#题意简述

给定一棵 \(n(n\leq10^6)\) 个节点的树，每个节点有红、黑两种颜色，每次可以将颜色相同的连通块染为另一种颜色，问将整棵树变为同种颜色的最少步数。

#大体思路

不难发现初始状态下相同颜色的点的变化必然是同步的，所以我们可以将一个颜色是相同的连通块合并为一个点，得到一棵新的树，然后我们发现我们最优的策略必然是从中心开始，一点一点地将整棵树变为同种颜色，不难发现这样所需的操作次数是 \(\left\lfloor\frac {len} 2\right\rfloor\)，其中 \(len\) 为新的树的直径，证明可以考虑 \(len\) 为奇数、偶数两种情况分开讨论。时间复杂度为 \(O(n)\).

#Code

#define ll long long
#define mset(l, x) memset(l, x, sizeof(l))

const int N = 2000010;
const int INF = 0x3fffffff;

template <typename T> inline void read(T &x) {
    x = 0; int f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    x *= f;
}

template <typename T> inline T Max(T a, T b) {return a > b ? a : b;}
template <typename T> inline T Min(T a, T b) {return a < b ? a : b;}

struct Edge {int u, v, nxt;} e[N], ne[N];
struct DSU {
    int fa[N], siz[N], num;

    inline void init(int x) {
        num = x;
        for (int i = 1; i <= num; ++ i)
          fa[i] = i, siz[i] = 1;
    }
    
    inline int find(int x) {
        while (x != fa[x]) x = fa[x] = fa[fa[x]]; return x;
    }

    inline void merge(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return;
        if (siz[x] > siz[y]) swap(x, y);
        siz[y] += siz[x], fa[x] = y;
    }
} dsu;

int n, col[N], head[N], ecnt(1), ncnt(1), nhead[N], vis[N], d[N];

inline void add_edge(int u, int v) {
    e[ecnt].u = u, e[ecnt].v = v;
    e[ecnt].nxt = head[u], head[u] = ecnt ++;
}

inline void connect(int u, int v) {
    ne[ncnt].u = u, ne[ncnt].v = v;
    ne[ncnt].nxt = nhead[u], nhead[u] = ncnt ++;

    ne[ncnt].u = v, ne[ncnt].v = u;
    ne[ncnt].nxt = nhead[v], nhead[v] = ncnt ++;
}

void combine(int x, int fa) {
    vis[x] = 1;
    for (int i = head[x]; i; i = e[i].nxt) {
        if (e[i].v == fa) continue;
        if (col[e[i].v] == col[x])
          dsu.merge(e[i].v, x), combine(e[i].v, x);
    }
}

void build(int x, int fa) {
    for (int i = head[x]; i; i = e[i].nxt) {
        if (e[i].v == fa) continue;
        if (col[e[i].v] != col[x])
          connect(dsu.find(x), dsu.find(e[i].v));
        build(e[i].v, x);
    }
}

int res;

void dfs(int x, int fa) {
    d[x] = d[fa] + 1;
    for (int i = nhead[x]; i; i = ne[i].nxt) {
        if (ne[i].v == fa) continue;
        dfs(ne[i].v, x);
    }
    if (d[x] > d[res]) res = x;
}

int main() {
    read(n); dsu.init(n);
    for (int i = 1; i <= n; ++ i) {
        char c; cin >> c; 
        if (c == 'R') col[i] = 1;
        else col[i] = 0;
    }
    for (int i = 1; i < n; ++ i) {
        int u, v; read(u), read(v);
        add_edge(u, v); add_edge(v, u);
    }
    for (int i = 1; i <= n; ++ i)
      if (!vis[i]) combine(i, 0);
    int st = 0, ed = 0;
    build(1, 0); dfs(dsu.find(1), 0);
    mset(d, 0); st = res; res = 0;
    dfs(dsu.find(st), 0); ed = res;
    printf("%d", d[ed] / 2);
    return 0;
}

#T2 操作序列

Time Limit: 1s | Memory Limit: 512MiB

#题意简述

给出一个长度为 \(k(k\leq10^5)\) 的数列，然后给出 \(n(n\leq10^5)\) 个操作：

操作分为三种：

1. \(a_i=b\)；
2. 给 \(a_i\) 加上 \(b\)；
3. 给 \(a_i\) 乘上 \(b\)；

其中 \(i,b\) 是给定的，每个操作只能用一次，最多使用 \(m(m\leq10^5)\) 个操作，让整个数列的乘积最大，给出最大乘积模 \(10^9+7\) 后的结果。

#大体思路

显然对于同一个位置，赋值操作只会使用一次，然后我们便可以将胜出的赋值操作转化为加法操作，然后对于加法操作，我们一定是先加贡献大的那个，之后便可以把所有的加法操作转化为乘法操作，注意到每一个加法操作一定是在相同位置上一步加法操作的基础上转化，得到新的权值——采用此操作可以使答案怎加多少倍。

之后将所有的乘法操作按照新的权值排序即可。

#Code

#define ll long long
#define pbk(x) push_back(x)

const int N = 100010;
const ll MOD = 1e9 + 7;
const int INF = 0x3fffffff;

template <typename T> inline void read(T &x) {
    x = 0; int f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    x *= f;
}

struct Node {
    int id; double val;
    
    inline Node() {}
    inline Node(int _id, double _val) {id = _id, val = _val;}
};
struct action {int op, pos; ll val;} p[N];

int k, n, m; ll a[N], ans = 1, cov[N];

vector <Node> add, mul, v[N];
vector <int> fnl;

inline double calc(int pos, double val) {
    return (1.0 * a[pos] + val) / (1.0 * a[pos]);
}

inline bool cmp(Node x, Node y) {return x.val > y.val;}

inline bool cmp2(int x, int y) {
    if (p[x].pos != p[y].pos) return p[x].pos < p[y].pos;
    else if (p[x].op != p[y].op) return p[x].op < p[y].op;
    else return p[x].val < p[y].val;
}

int main() {
    read(k), read(n), read(m);
    for (int i = 1; i <= k; ++ i) read(a[i]);
    for (int i = 1; i <= n; ++ i) {
        int op, pos; ll val;
        read(op), read(pos), read(val);
        p[i].op = op, p[i].pos = pos, p[i].val = val;
        if (op == 1) {
            if (!cov[pos]) cov[pos] = i;
            else if (p[cov[pos]].val < val)
              cov[pos] = i;
        }
        else if (op == 2) v[pos].pbk(Node(i, 1.0 * val));
        else mul.pbk(Node(i, 1.0 * val));
    }
    for (int i = 1; i <= k; ++ i) if (cov[i])
      v[i].pbk(Node(cov[i], 1.0 * (p[cov[i]].val - a[i])));
    for (int i = 1; i <= k; ++ i) sort(v[i].begin(), v[i].end(), cmp);
    for (int i = 1; i <= k; ++ i) {
        double sum = 1.0 * a[i];
        for (auto x : v[i]) {
            mul.pbk(Node(x.id, (sum + x.val) / sum));
            sum += x.val;
        }
    }
    sort(mul.begin(), mul.end(), cmp);
    for (int i = 0; i < m && i < mul.size(); ++ i) fnl.pbk(mul[i].id);
    sort(fnl.begin(), fnl.end(), cmp2);
    for (auto x : fnl) {
        if (p[x].op == 1) a[p[x].pos] = max(a[p[x].pos], p[x].val);
        else if (p[x].op == 2) (a[p[x].pos] += p[x].val) %= MOD;
        else (a[p[x].pos] *= p[x].val) %= MOD;
    }
    for (int i = 1; i <= k; ++ i) (ans *= a[i]) %= MOD;
    printf("%lld", ans); return 0;
}

#T3 吃零食

Time Limit: 1s | Memory Limit: 256MiB

#题意简述

对于 \(n(n\leq10^6)\) 的一个排列 \(p_i\)，它的贡献是 \(s=\sum(i\bmod p_i)\)，现在已知 \(s(s\leq10^{18})\)，请给出一组合法的 \(p_i\)，若无解则输出 SPFA is dead!。

#大体思路

首先，显然 \(s\) 的上界是 \[ \sum_{i=0}^{n-1}i=\dfrac{n\cdot(n-1)}2 \] 然后，考虑进行如下构造：

最初，\(a_n=1,a_i=i+1(i\in\{2,3,\dots,n-1\})\)，显然这样的贡献和是 \(S=\frac{n\cdot(n-1)}2\)，我们考虑 \(\Delta s=S-s\)，从大到小枚举 \(i\)，对于 \(i\leq\Delta s\)，我们每次交换 \(a_i\) 和 \(a_{i-1}\)，显然这样会使 \(\Delta s\) 减小 \(i\)，可以用归纳法证明，这样可以得到 \[ [3,\dfrac {n\cdot(n-1)}2 - 2]\cup\{\dfrac{n\cdot(n - 1)}2\} \] 中的所有数，剩下的部分单独特殊构造即可。

#Code

#define ll long long

const int N = 2000010;
const int INF = 0x3fffffff;

template <typename T> inline void read(T &x) {
    x = 0; int f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    x *= f;
}

ll n, s, a[N];

int main() {
    read(n), read(s);
    if (s == 0) {
        for (int i = 1; i <= n; ++ i)
          printf("%d\n", i);
        return 0;
    } else if (s == 1) {
        if (n < 2) printf("SPFA is dead!\n");
        else {
            printf("2\n1\n");
            for (int i = 3; i <= n; ++ i)
              printf("%d\n", i);
        }
        
    } else if (s == 2) {
        if (n < 3) printf("SPFA is dead!\n");
        else {
            printf("3\n1\n2\n");
            for (int i = 4; i <= n; ++ i)
              printf("%d\n", i);
        }
    } else {
        if (s > n * (n - 1) / 2) {puts("SPFA is dead!\n"); return 0;}
        ll rest = n * (n - 1) / 2 - s;
        for (int i = 1; i < n; ++ i) a[i] = i + 1; a[n] = 1;
        if (rest == 1) {
            if (n & 1) a[1] = 3, a[2] = 1, a[n] = 2;
            else swap(a[1], a[n]);
        } else {
            for (int i = n - 1; i; -- i) if (rest >= i)
              rest -= i, swap(a[i], a[i - 1]);
        }
        for (int i = 1; i <= n; ++ i) printf("%lld ", a[i]);
    }
    return 0;
}

#T4 数树

Time Limit: 3s | Memory Limit: 512MiB

咕咕咕～