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

发表于 更新于 分类于
ZROI-21-NOIP冲刺-TEST17 总结

#屑在前面

由于身体原因及某几场考试的 T3、T4 不可补，于是中间就咕咕咕了几篇，补不补随缘吧/wq

#T1 博弈

Time Limit: 1s | Memory Limit: 512MiB | 题目连接

#大体思路

首先显然开环的顺序由先手决定，考虑大于等于四个结的环，如果后手不选择交换，先手一定只能拿到 4 个，如果选择交换那么先手一定一个都拿不到，所以显然先手会选择从小到大开环，然后我们 DP 一遍即可，时间复杂度为 \(O(n\log n)\).

数据范围只有 \(100\) 就离大谱...

#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
#define ll long long

const int N = 105;
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 dp[N][2][2]; int n, a[N];

int main() {
    read(n);
    for (int i = 1; i <= n; ++ i) read(a[i]);
    sort(a + 1, a + 1 + n);
    for (int i = n; i; -- i) {
        if (a[i] >= 4) {
            if (dp[i + 1][1][0] + a[i] - 4 > dp[i][1][0]) {
                dp[i][0][0] = dp[i + 1][0][0] + 4;
                dp[i][1][0] = dp[i + 1][1][0] + a[i] - 4;
            }
            if (dp[i + 1][0][1] + a[i] - 4) {
                dp[i][1][1] = dp[i + 1][1][1] + 4;
                dp[i][0][1] = dp[i + 1][0][1] + a[i] - 4;
            }
        }
        if (dp[i + 1][1][1] + a[i] > dp[i][1][0]) {
            dp[i][0][0] = dp[i + 1][0][1];
            dp[i][1][0] = dp[i + 1][1][1] + a[i];
        }
        if (dp[i + 1][0][0] + a[i] > dp[i][0][1]) {
            dp[i][1][1] = dp[i + 1][1][0];
            dp[i][0][1] = dp[i + 1][0][0] + a[i];
        }
    }
    printf("%lld %lld", dp[1][0][0], dp[1][1][0]);
    return 0;
}

#T2 齿轮

Time Limit: 1s | Memory Limit: 512MiB | 题目连接

#大体思路

注意到在同一连通块中的任意两个齿轮之间的转速关系仅与两者的齿数有关，中间的所有齿轮的影响都可以被抵消掉，于是我们可以将一个连通块中的所有齿轮根据旋转方向的不同分为两个不交的集合（是二分图），考虑将两个齿轮咬合后连通块锁死当且仅当两者咬合前在同一连通块且所属集合相同，于是我们需要维护每个齿轮所属的连通块及所属的集合。

当两个连通块合并时，采用启发式合并，将齿轮数小的集合并到较大的集合中，若其中一方锁死，则整体锁死，否则当咬合的两个齿轮咬合前所属的集合相同时，应当将较小的集合中的所有点所属的集合取反，均摊后时间复杂度为 \(O(n\log n)\).

对于修改齿数及询问直接处理即可，整体时间复杂度为 \(O((q+n)\log 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
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
#define ll long long
#define int long long 

const int N = 100010;
const int M = 200010;

template <typename T> inline void read(T &x) {
    int f = 1; x = 0; 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 nxt, u, v;} e[M];

int head[N], cnt(1), n, m, T, a[N];
int ans, val, siz[N], f[N], bel[N];
bool locked[N];

int find(int x) {while (x != f[x]) x = f[x] = f[f[x]]; return x;}
int gcd(int x, int y) {return y ? gcd(y, x % y) : x;}

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

void dfs(int u,int fa) {
    bel[u] ^= 1;
    for(int i = head[u]; i; i = e[i].nxt)
      if(e[i].v != fa) dfs(e[i].v, u);
}
signed main() {
    read(n), read(m);
    for (int i = 1; i <= n; ++ i) read(a[i]);
    for (int i = 1; i <= n; ++ i) f[i] = i;
    for (int i = 1; i <= n; ++ i) siz[i] = 1;
    while (m --) {
        int opt, x, y, c; read(opt);
        if (opt == 1) read(x), read(c), a[x] = c;
        else if (opt == 2) {
            read(x), read(y);
            if (x == y) continue;
            int fu = find(x), fv = find(y);
            if (siz[fu] > siz[fv])
              swap(x, y), swap(fu, fv);
            if (fu == fv) {
                if (bel[x] == bel[y])
                  locked[fv] = true;	
            } else {
                siz[fv] += siz[fu], f[fu] = fv;
                if (bel[x] == bel[y]) dfs(x, 0);
                add_edge(x, y), add_edge(y, x);
                if (locked[fu]) locked[fv] = true;
            }
        } else if (opt == 3) {
            read(x), read(y), read(c);
            int fu = find(x), fv = find(y);
            if (fu != fv) {puts("0"); continue;} 
            if (locked[fu]) {puts("0"); continue;}
            else {
                int fst = c * a[x], scd = a[y];
                int g = gcd(fst, scd); fst /= g, scd /= g;
                if (bel[x] != bel[y]) fst = -fst;
                printf("%lld/%lld\n", fst, scd); 
            }
        }
    }
    return 0;
}

#T3 排班方案

Time Limit: 2s | Memory Limit: 512MiB | 题目连接

#大体思路

简单颓一颓柿子不难得到： \[ \prod_{i=1}^n(d_{i-1}-(i-1)+d_i-d_{i-1})=\prod_{i=1}^n(d_i-i+1)=C, \] 由于限制 \(d_{i-1}\leq d_i\)，于是应当有 \(d_{i-1}-(i-1)+1\leq d_i-i+1+1\)，于是考虑从小到大枚举 \(C\) 的因数作为 \(d_{n}-n+1\)，然后根据直接暴力 DFS，显然剩下的越大越好，于是直接贪心构造剩下的序列即可，这样的递归不会超过 \(n\) 层，于是跑满的时间复杂度为 \(O(n\sqrt 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
31
32
33
34
35
36
37
38
39
40
41
42
const int N = 10000010;
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;}

int t, n, c, d[N], dv[N], dcnt;

bool solve(int x, int lmt, int rst) {
    if (rst == 1) {for (int i = 1; i <= x; ++ i) d[i] = 1; return true;}
    if (!x) return false; int mx = 0;
    if (rst <= lmt) {d[x] = rst; for (int i = 1; i < x; ++ i) d[i] = 1; return true;}
    for (int i = 2; i * i <= rst && i <= lmt; ++ i) if (!(rst % i)) {
        mx = Max(mx, i); 
        if (rst / i <= lmt) {d[x] = rst / i; return solve(x - 1, d[x] + 1, i);}
    }
    if (!mx) return false; else d[x] = mx;
    return solve(x - 1, d[x] + 1, rst / mx);
}

void MAIN() {
    read(n), read(c); dcnt = 0; bool flg = 0;
    for (int i = 1; i <= n; ++ i) d[i] = 1;
    for (int i = 1; i * i <= c && !flg; ++ i) if (!(c % i)) {
        dv[++ dcnt] = c / i; d[n] = i;
        if (solve(n - 1, d[n] + 1, c / i)) flg = 1;
    }
    if (!flg) for (int i = dcnt; i >= 1; -- i) {
        d[n] = dv[i];
        if (solve(n - 1, d[n] + 1, c / dv[i])) break;
    }
    for (int i = 1; i <= n; ++ i) printf("%d ", d[i] + i - 1); puts("");
}

int main() {read(t); while (t --) MAIN(); return 0;}

#T4 简单的数据结构题

Time Limit: 3s | Memory Limit: 512MiB | 题目连接

#大体思路

考虑将询问离线，然后维护以 \(i\) 为右端点的所有不同的区间与，同时记录以该值为区间与的左端点的范围（考虑区间与一定是单调不降的），显然这个左端点范围内的所有都可以与 \(i\) 组合，这样的区间与最多只会有 \(\log a_i=30\) 种，然后考虑将这个序列从以 \(i-1\) 为右端点转移到以 \(i\) 为右端点，显然只需要加入一个 \(a_i\)，然后将所有的原本的区间与全部与上一个 \(a_i\)，同时去重，这一步的复杂度为 \(O(\log n)\)，然后检查所有的区间与，如果是完全平方数，那么就将该区间与对应的左端点区间全部加一，最后对于每个询问检查对应区间和即可，注意每一次修改都是在之前的基础上进行修改。时间复杂度为 \(O(q\log n+n\log n\log a)\).

#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
66
67
68
69
70
71
72
73
74
75
76
77
78
#define ll long long
#define pii pair <int, int>
#define fir first
#define sec second
#define mp(a, b) make_pair(a, b)
#define pbk(x) push_back(x)

const int N = 500010;
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 l, r, val;} e[N], ne[N];
struct Bit {
    ll val[2][N]; int lmt;
    
    inline void init(int x) {lmt = x;}
    inline void reset() {while (lmt) val[0][lmt] = val[1][lmt] = 0, lmt --;}
    
    inline void change(int x, ll y) {
        for (int i = x; i <= lmt; i += (i & -i))
          val[0][i] += y, val[1][i] += y * x;
    }

    inline ll ask(int x) {
        ll res = 0;
        for (int i = x; i; i -= (i & -i))
          res += 1ll * (x + 1) * val[0][i] - val[1][i];
        return res;
    }

    inline void modify(int x, int y, ll c) {change(x, c), change(y + 1, -c);}
    inline ll query(int x, int y) {return ask(y) - ask(x - 1);}
} t;

int T, n, q, a[N], cnt, tot; ll ans[N];

vector <pii > sq[N];

inline void reset() {
    for (int i = 1; i <= n; ++ i) sq[i].clear();
    t.reset(); cnt = 0;
}

inline bool check(int x) {int dv = sqrt(x); return (dv * dv) == x;}

void MAIN() {
    read(n), read(q); reset(); t.init(n);
    for (int i = 1; i <= n; ++ i) read(a[i]);
    for (int i = 1; i <= q; ++ i) {
        int l, r; read(l), read(r);
        sq[r].pbk(mp(l, i));
    }
    for (int i = 1; i <= n; ++ i) {
        tot = 0;
        e[++ cnt] = (Node){i, i, a[i]};
        for (int j = 1; j <= cnt; ++ j) {
            Node now = e[j]; now.val &= a[i];
            if (tot && ne[tot].val == now.val)
              ne[tot].r = now.r;
            else ne[++ tot] = now;
        }
        cnt = tot;
        for (int j = 1; j <= cnt; ++ j) e[j] = ne[j];
        for (int j = 1; j <= cnt; ++ j)
          if (check(e[j].val)) t.modify(e[j].l, e[j].r, 1);
        for (auto now : sq[i]) ans[now.sec] = t.query(now.fir, i);
    }
    for (int i = 1; i <= q; ++ i) printf("%lld\n", ans[i]);
}

int main() {read(T); while (T --) MAIN(); return 0;}