Cansult's blog

即使愿望永远无法实现
我也不愿就这样放手

0%

比赛总结 1038 - [2020 TJUICPC] 个人赛

Posted on Edited on In

我是傻逼

题目#1

题目#2

我是傻逼

A

签到

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (2000)
using namespace std;
int a[MAXN][MAXN], n;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        for (int j = (1 << (i - 1)) + 1; j <= (1 << i); j++)
            for (int k = 1; k <= (1 << (i - 1)); k++)
                a[j][k] = a[j - (1 << (i - 1))][k] ^ 1, a[k][j] = a[k][j - (1 << (i - 1))] ^ 1;
        for (int j = (1 << (i - 1)) + 1; j <= (1 << i); j++)
            for (int k = (1 << (i - 1)) + 1; k <= (1 << i); k++)
                a[j][k] = a[j - (1 << (i - 1))][k - (1 << (i - 1))] ^ 1;
    }
    for (int i = 1; i <= (1 << n); i++, puts(""))
        for (int j = 1; j <= (1 << n); j++)
            printf("%d ", a[i][j]);
    return 0;
}

B

不会

C

以前写过

现在不会

太真实了

在本题模数\(q\)下, 函数\(f(x) = x ^ 2\,\,\mathrm{Mod}\,\,q\)存在不动点 所以平方到一定次数后值就不会变了

或者 一般的, 平方取模的操作是有循环节的(只要操作次数大于模数剩余系的大小就会出现重复) 可以用vector保存循环节中的数, 区间平方就可以转化为下标的区间加, 记录好一个区间内下标集体加一时区间和的变化应该就能搞一搞...吧?

1
// 咕咕咕

D

不知道啥叫k维空间的超级球

看样例输了个\(\sqrt k - 1\)

然后过了...

E

用f[i][j]表示前i个数, 有j这个状态表示的质因数的最小代价

质因数最大到59就行了, 毕竟就算和2乘起来也到100多了....?

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
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
int f[102][1 << 17];
int n, a[102];
int p[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59};
int bit(int x) {
    int z = 0;
    for (int i = 0; i < 17; i++) {
        if (x % p[i] == 0) {
            z |= 1 << i;
        }
    }
    return z;
}
int main() {
    scanf("%d", &n);
    memset(f, 0x3f, sizeof f);
    f[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        for (int j = 1; j <= 59; j++) {
            int b = bit(j);
            int ub = ((1 << 17) - 1) ^ b;
            for (int k = ub; ; --k &= ub) {
                f[i][k | b] = min(f[i][k | b], f[i - 1][k] + abs(j - a[i]));
                if(k == 0) {
                    break;
                }
            }
        }
    }
    int ans = 0x3f3f3f3f;
    for (int i = 0; i < 1 << 17; i++) {
        ans = min(ans, f[n][i]);
    }
    printf("%d\n", ans);
    return 0;
}

F

连题都没整明白

G

上下跑然后算贡献就完事了

调了不知道多长时间

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
// 点分? 
// 维护 子树的深度和, 子树的深度的平方和, 子树大小
// 然后呢 链剖? 好像很合理
// 不用树剖

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define LL long long
#define MAXN (100000)
#define lowbit(i) ((i) & (-(i)))
using namespace std;
struct node {
    int size, fa, depth;
    LL sumsd, sumsd2;
} a[MAXN + 5];
struct edg {
    int from, to, next;
} b[MAXN * 2 + 5];
int g[MAXN + 5], cntb, n;
LL ans[MAXN + 5];
void ade(int fr, int t) {
    b[++cntb] = {fr, t, g[fr]};
    g[fr] = cntb;
}
void init(int now) {
    a[now].size = 1;
    a[now].sumsd = a[now].depth;
    a[now].sumsd2 = (LL)a[now].depth * a[now].depth;
    for (int i = g[now]; i; i = b[i].next)
        if (b[i].to != a[now].fa) {
            a[b[i].to].fa = now;
            a[b[i].to].depth = a[now].depth + 1;
            init(b[i].to);
            a[now].size += a[b[i].to].size;
            a[now].sumsd += a[b[i].to].sumsd;
            a[now].sumsd2 += a[b[i].to].sumsd2;
        }
}
void dfs(int now, LL nows, LL nowf) {
    if (now != 1) {
        nows = a[now].sumsd - (a[now].depth - 2) * a[now].size;
        nowf += a[a[now].fa].sumsd - a[now].sumsd - (a[a[now].fa].depth - 1) * (a[a[now].fa].size - a[now].size) + n - a[a[now].fa].size;
        ans[now] = ans[a[now].fa] + a[now].size - 2 * nows + a[1].size - a[now].size + 2 * nowf;
    }
    for (int i = g[now]; i; i = b[i].next)
        if (b[i].to != a[now].fa)
            dfs(b[i].to, nows, nowf);
}
int main() {
    scanf("%d", &n);
    for (int i = 1, xi, yi; i < n; i++)
        scanf("%d%d", &xi, &yi), ade(xi + 1, yi + 1), ade(yi + 1, xi + 1);
    a[1].depth = 1;
    init(1);
    ans[1] = a[1].sumsd2;
    dfs(1, a[1].sumsd, 0);
    for (int i = 1; i <= n; i++)
        printf("%lld\n", ans[i]);
    return 0;
}

By 操他妈我是傻逼的 Cansult