Cansult's blog

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

0%

水题笔记 TJU ACM 2020第一学期 作业4 [杂题]

Posted on Edited on In

日他妈实在写不动了

题目

A

水题 开始没判断n == 0的情况wa了一发

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 如果可以做成两个相同的 那么就是先手获胜
// 如果不能呢, 就是k为1, 然后n为偶数 ...那就是分成了一奇一偶
// 哦豁

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    if (!n) {
        puts("Joker");
        return 0;
    }
    if (k != 1) puts("Ervin");
    else if (n & 1) puts("Ervin");
    else puts("Joker");
    return 0;
}

B

不知道为啥wa了

C

筛完枚举就完事了 测评机速度挺快

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#define LL long long 
#define MAXN (30000000)
#define MAXP (5000000)
using namespace std;
bool isp[MAXN + 5];
int prim[MAXP + 5];
int main() {
    int l, r;
    scanf("%d%d", &l, &r);
    memset(isp, true, sizeof(isp));
    isp[1] = false;
    for (int i = 1; i <= r; i++) {
        if (isp[i])
            prim[++prim[0]] = i;
        for (int j = 1; j <= prim[0] && (LL)i * prim[j] <= r; j++) {
            isp[i * prim[j]] = false;
            if (i % prim[j] == 0) break;
        }
    }
    int ans = 0;
    for (int a = 1; a * a <= r; a++)
        for (int b = max(a, (int)sqrt(l - a * a)); b * b + a * a <= r; b++)
            if (l <= a * a + b * b && a * a + b * b <= r && isp[a * a + b * b])
                ++ans;
    printf("%d", ans);
    return 0;
}

D

树状数组扫就完事了 甚至不需要离散化

一开始没发现a可能为0, T了几发

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
// f[k][i]为以i为结尾的长度为k的递减子序列个数

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define MAXB (100000)
#define MAXN (20000)
#define MAXK (10)
#define AH (1000000000)
#define LL int 
#define lowbit(x) ((x) & (-(x)))
using namespace std;
int b[MAXB + 5], f[MAXK + 5][MAXN + 5], ans, n, k, a[MAXN + 5];
inline void modify(const int& tar, const LL& num) {
    for (int i = tar; i <= MAXB; i += lowbit(i)) {
        b[i] += num;
        while (b[i] > AH) b[i] -= AH;
    }
}
inline LL enquiry(const int& tar) {
    LL re = 0;
    for (int i = MAXB; i; i -= lowbit(i)) {
        re += b[i];
        while (re > AH) re -= AH;
    }
    for (int i = tar; i; i -= lowbit(i)) {
        re -= b[i];
        re += ((re > 0) ? 0 : AH);
        while (re > AH) re -= AH;
    }
    return re;
}
void solve() {
    for (int i = 1; i <= n; i++)
        f[1][i] = 1;
    for (int i = 2; i <= k; i++) {
        memset(b, 0, sizeof(b));
        for (int j = 1; j <= n; j++)
            f[i][j] = enquiry(a[j]), modify(a[j], f[i - 1][j]);
    }
    for (int i = 1; i <= n; i++) {
        ans += f[k][i];
        while (ans > AH) ans -= AH;
    }
    printf("%d", ans);
}
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d", a + i), ++a[i];
    solve();
    return 0;
}

E

BFS

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN (100)
#define num(x, y) (((x) - 1) * MAXN + (y))
using namespace std;
struct edg {
    int fr, to, next;
} b[MAXN * MAXN * 100];
const int xy[4][2] = { { 0, 1 }, { 0, -1 }, { -1, 0 }, { -1, 0 } };
int n, m, a[MAXN * MAXN * 2], g[MAXN * MAXN * 2], cntb, S, T;
void adn(int f, int t) { b[++cntb] = { f, t, g[f] }; g[f] = cntb; }
void bfs() {
    int dis[MAXN * MAXN * 3];
    queue<int> q;
    memset(dis, -1, sizeof(dis));
    q.push(T);
    dis[T] = 0;
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        for (int i = g[now]; i; i = b[i].next)
            if (dis[b[i].to] == -1) {
                dis[b[i].to] = dis[now] + 1;
                q.push(b[i].to);
            }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (dis[num(i, j)] <= dis[S] && a[num(i, j)] > 0)
                ans += a[num(i, j)];
    printf("%d\n", ans);
}
int main() {
    while (scanf("%d%d", &n, &m) != EOF) {
        memset(g, 0, sizeof(g));
        memset(a, 0, sizeof(a));
        cntb = 0;
        char s[MAXN + 5];
        for (int i = 1; i <= n; i++) {
            scanf("%s", s);
            for (int j = 1; j <= m; j++)
                if (s[j - 1] == 'S')
                    a[num(i, j)] = -2, S = num(i, j);
                else if (s[j - 1] == 'E')
                    a[num(i, j)] = -3, T = num(i, j);
                else if (s[j - 1] == 'T')
                    a[num(i, j)] = -1;
                else a[num(i, j)] = s[j - 1] - '0';
        }
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                if (a[num(i, j)] == -1) continue;
                int now = num(i, j), ni, nj;
                for (int k = 0; k < 4; k++) {
                    ni = i + xy[k][0], nj = j + xy[k][1];
                    if (ni > n || nj > m || a[num(ni, nj)] == -1 || ni < 1 || nj < 1) continue;
                    adn(now, num(ni, nj)), adn(num(ni, nj), now);
                }
            }
        bfs();
    }
    return 0;
}

F

二分就完事了

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (100000)
using namespace std;
int n, m, v[MAXN + 5];
bool jud(int x) {
    int nowans = 1;
    for (int i = 1, nowv = 0; i <= n; i++) {
        if (nowv + v[i] > x)
            nowv = 0, ++nowans;
        nowv += v[i];
    }
    return nowans <= m; 
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &v[i]);
    int l = 1, r = 1000000000;
    while (l < r) {
        int mi = (l + r) >> 1;
        if (jud(mi)) r = mi;
        else l = mi + 1;
    }
    printf("%d", r);
    return 0;
}

G

写不动

H

随便DP就完事了

没把f初始化为-INF, 导致可能从不合法的状态转移来WA了一发

没判断ans < 0WA了一发

还没输入n就初始化WA了一发

>=写成了>WA了一发

真行啊...

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (100000)
#define MAXM (100)
#define INF (1000000000)
using namespace std;
int n, m, k, f[MAXN + 5][MAXM + 5][3], a[MAXN + 5], d[MAXN + 5];
int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n + 1; i++)
        for (int j = 0; j <= m; j++)
            for (int k = 0; k <= 2; k++)
                f[i][j][k] = -INF;
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++)
        scanf("%d", &d[i]);
    f[1][m][0] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++) {
            if (j >= d[i]) f[i + 1][j - d[i]][0] = max(f[i + 1][j - d[i]][0], max(f[i][j][0], max(f[i][j][2], f[i][j][1])) + a[i]);
            for (int l = 0; l < 2; l++)
                f[i + 1][min(m, j + k)][l + 1] = max(f[i + 1][min(m, j + k)][l + 1], f[i][j][l]);
        }
    int ans = 0;
    for (int i = 0; i <= m; i++)
        for (int j = 0; j <= 2; j++)
            ans = max(ans, f[n + 1][i][j]);
    if (ans > 0) printf("%d", ans);
    else puts("-1");
    return 0;
}

I

预处理完了二分就行了

卡了卡常才过得去

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (6000)
using namespace std;
int n, q, mogic[MAXN + 5][MAXN + 5];
char S[MAXN + 5];
inline int mabs(const int& x) { return (x > 0) ? x : (-x); }
inline int getint() {
    char x;
    int re = 0;
    while (1) {
        x = getchar();
        if (x <= '9' && x >= '0') break;
    }
    while (1) {
        re = (re << 1) + (re << 3) + x - '0';
        x = getchar();
        if (x >'9' || x < '0') break;
    }
    return re;
}
int main() {
    scanf("%s", S);
    n = strlen(S);
    for (int i = 0; i < n; i++) {
        mogic[i][i] = 0;
        for (int j = 1; i + j < n && i - j >= 0; j++)
            mogic[i - j][i + j] = mogic[i - j + 1][i + j - 1] + mabs(S[i - j] - S[i + j]);
    }
    for (int i = 1; i < n; i++) {
        mogic[i - 1][i] = abs(S[i] - S[i - 1]);
        for (int j = 1; i - j > 0 && i + j < n; j++)
            mogic[i - j - 1][i + j] = mogic[i - j][i + j - 1] + mabs(S[i - j - 1] - S[i + j]);
    }
    scanf("%d", &q);
    for (int i = 1, li, ri, ki; i <= q; i++) {
        li = getint();
        ri = getint();
        ki = getint();
        //scanf("%d%d%d", &li, &ri, &ki);
        --li, --ri;
        int l = 0, r = (ri - li + 1) / 2, m, ans = r;
        while (l <= r) {
            m = (l + r) >> 1;
            if (mogic[li + m][ri - m] <= ki) r = m - 1, ans = m;
            else l = m + 1;
        }
        printf("%d\n", ri - li + 1 - 2 * ans);
    }
    return 0;
}

J

不会

K

二维AC自动机

方法就是给把模板矩阵的每一行都看作一个字符串建AC自动机, 然后用文本串匹配的时候, 如果匹配成功, 就给"这个模板矩阵右上角应该在的位置"加一, 然后如果有一个位置的值大于模板矩阵的行数说明所有的行都被匹配过了

这个题因为所有模板矩阵的大小都一样, 可以放在一起建图, 只用匹配一次文本串, 节省点时间

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <map>
#define MAXC (2)
#define MAXN (1000000)
#define MAXM (1000)
#define MAXX (100)
#define pii pair<int, int>
using namespace std;
struct node {
    int son[MAXC], fail;
    vector<pii> num;
} b[MAXN << 1];
int a[MAXM + 5][MAXM + 5], cntb;
bool ans[MAXN + 5];
map<int, int> cntx[MAXM + 5][MAXM + 5];
void init(){
    queue<int> q;
    for (int i = 0; i < MAXC; i++) if (b[0].son[i]) q.push(b[0].son[i]);
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        for (int i = 0; i < MAXC; i++)
            if (b[now].son[i]) b[b[now].son[i]].fail = b[b[now].fail].son[i], q.push(b[now].son[i]);
            else b[now].son[i] = b[b[now].fail].son[i];
    }
}
int main() {
    int na, ma, nb, mb;
    scanf("%d%d%d%d", &na, &ma, &nb, &mb);
    for (int i = 1; i <= na; i++)
        for (int j = 1; j <= ma; j++)
            scanf("%1d", &a[i][j]);
    int t, bt;
    scanf("%d", &t);
    bt = t;
    while (t--) {
        for (int i = 1, now = 0; i <= nb; i++, now = 0) {
            for (int j = 1, bij; j <= mb; j++) {
                scanf("%1d", &bij);
                if (!b[now].son[bij]) b[now].son[bij] = ++cntb;
                now = b[now].son[bij];
            }
            b[now].num.push_back(make_pair(t, i));
        }
    }     
    init();
    for (int i = 1; i <= na; i++)
        for (int j = 1, now = 0; j <= ma; j++) {
            now = b[now].son[a[i][j]];
            for (int k = now; k; k = b[k].fail)
                for (int l = 0; l < b[k].num.size(); l++)
                    if (!ans[b[k].num[l].first] && i >= b[k].num[l].second) {
                        if (cntx[i - b[k].num[l].second + 1][j].find(b[k].num[l].first) == cntx[i - b[k].num[l].second + 1][j].end())
                            cntx[i - b[k].num[l].second + 1][j][b[k].num[l].first] = 1;
                        else
                            ++cntx[i - b[k].num[l].second + 1][j][b[k].num[l].first];
                        if (cntx[i - b[k].num[l].second + 1][j][b[k].num[l].first] == nb)
                            ans[b[k].num[l].first] = true;
                    }
        }
    for (int i = bt - 1; i >= 0; i--)
        puts(ans[i] ? "known" : "new");
    return 0;
}

L

排序题 然而还是WA了两发

一次格式错了, 少了个空格

一次没有break, 导致比赛时间结束了还能答题 = =

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define MAXN (100000)
using namespace std;
struct que {
    int d, t;
} a[MAXN + 5];
bool cmp(const que& x, const que& y) { return x.d < y.d; }
int main() {
    int t;
    scanf("%d", &t);
    for (int j = 1; j <= t; j++) {
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i].d);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i].t);
        sort(a + 1, a + n + 1, cmp);
        int ans = 0;
        for (int i = 1; i <= n; i++)
            if (a[i].t <= m)
                ++ans, m -= a[i].t;
            else break;
        printf("Case %d: %d\n", j, ans);
    }
    return 0;
}

M

不会交互

N

粘了个快速幂板子

实际duck不必

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define LL long long
using namespace std;
int p = 10, num = 1378;
int fastpow(int k) {
    if (k == 0) return 1 % p;
    if (k == 1) return num % p;
    int re = fastpow(k >> 1);
    re = (re * re) % p;
    if (k & 1) re = (re * num) % p;
    return re;
}
int main() {
    int k;
    scanf("%d", &k);
    printf("%d", fastpow(k));
    return 0;
}

O

搞个桶就完事了

一开始没考虑一个数出现多次WA了一发

然后没考虑x^a[i]比桶的大小大WA了好几发

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (100000)
using namespace std;
int n, a[MAXN + 5], x, abab[MAXN + 5];
long long ans;
int main() {
    scanf("%d%d", &n, &x);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), ans += abab[min(MAXN + 1, x ^ a[i])], ++abab[a[i]];
    printf("%lld", ans);
    return 0;
}

P

水题

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
// 很多环 找出所有环的x的最小公倍数
// 如果环的节点数n为偶数, x = n / 2; 否则x = n;
// 如果有节点不在环上, 输出-1

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (100)
using namespace std;
int c[MAXN + 5], n, vis[MAXN + 5], l[MAXN + 5];
void dfs(int now) {
    ++vis[now];
    if (vis[c[now]] < 2) dfs(c[now]);
}
void solve(int now, int nowl) {
    ++vis[now];
    if (vis[c[now]] < 3) solve(c[now], nowl + 1);
    else l[++l[0]] = nowl;
}
int gcd(int x, int y) { return (y == 0) ? x : gcd(y, x % y); }
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &c[i]);
    for (int i = 1; i <= n; i++)
        if (!vis[i])
            dfs(i);
    for (int i = 1; i <= n; i++)
        if (vis[i] < 2) {
            puts("-1");
            return 0;
        }
    for (int i = 1; i <= n; i++)
        if (vis[i] < 3)
            solve(i, 1);
    for (int i = 1; i <= l[0]; i++)
        l[i] = (l[i] & 1) ? l[i] : (l[i] >> 1);
    int ans = l[1];
    for (int i = 2; i <= l[0]; i++)
        ans = ans * l[i] / gcd(ans, l[i]);
    printf("%d", ans);
    return 0;
}

Q

分组DP

并查集merge之前忘了判断他们是否已经在一个集里了WA了一发

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#define MAXN (1000)
using namespace std;
int fa[MAXN + 5], n, w[MAXN + 5], b[MAXN + 5], m, tw, f[MAXN + 5][MAXN + 5], ans, bw[MAXN + 5], bb[MAXN + 5];
vector<int> cla[MAXN + 5];
int find(int x) { return (fa[x] == x) ? x : (fa[x] = find(fa[x])); }
void merge(int x, int y) { fa[find(x)] = find(y); }
int main() {
    scanf("%d%d%d", &n, &m, &tw);
    for (int i = 1; i <= n; i++) scanf("%d", &w[i]), bw[i] = w[i], fa[i] = i;
    for (int i = 1; i <= n; i++) scanf("%d", &b[i]), bb[i] = b[i];
    for (int i = 1, xi, yi; i <= m; i++) {
        scanf("%d%d", &xi, &yi);
        if (find(xi) != find(yi)) {
            w[find(yi)] += w[find(xi)];
            b[find(yi)] += b[find(xi)];
            merge(xi, yi);
        }
    }
    for (int i = 1; i <= n; i++)
        cla[find(i)].push_back(i);
    for (int i = 1; i <= n; i++) {
        if (fa[i] == i) 
            for (int j = tw; j >= w[i]; j--)
                f[i][j] = max(f[i][j], f[i - 1][j - w[i]] + b[i]);
        for (int j = 0; j < cla[i].size(); j++)
            for (int k = tw; k >= bw[cla[i][j]]; k--)
                f[i][k] = max(f[i][k], f[i - 1][k - bw[cla[i][j]]] + bb[cla[i][j]]);
        for (int j = tw; j >= 0; j--)
            f[i][j] = max(f[i][j], f[i - 1][j]);
    }
    for (int j = 0; j <= tw; j++)
        ans = max(ans, f[n][j]);
    printf("%d", ans);
    return 0;
}

R

不会

不会是2SAT吧?

2你妈的SAT

直接建图暴力染就行了

建图有个高明之处 只给2 * i和2 * i + 1以及各对狗男女之间连边

因为要求的是三个人不同色, 只要有相邻的两人不同那么包含这两个人的三人就一定不同

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (200000)
struct edg {
    int from, to, next;
} b[MAXN * 2 + 5];
int g[MAXN + 5], cntb, n, vis[MAXN + 5], xy[MAXN + 5][2];
void ade(int fr, int t) { b[++cntb] = { fr, t, g[fr] }; g[fr] = cntb; }
void dfs(int now) {
    for (int i = g[now]; i; i = b[i].next)
        if (vis[b[i].to] == -1)
            vis[b[i].to] = !vis[now], dfs(b[i].to);
}
int main() {
    memset(vis, -1, sizeof(vis));
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &xy[i][0], &xy[i][1]);
        ade(xy[i][0], xy[i][1]);
        ade(xy[i][1], xy[i][0]);
        ade(2 * i, 2 * i + 1);
        ade(2 * i + 1, 2 * i);
    }
    for (int i = 1; i <= n * 2; i++)
        if (vis[i] == -1)
            dfs(i);
    for (int i = 1; i <= n; i++)
        printf("%d %d\n", vis[xy[i][0]] + 1, vis[xy[i][1]] + 1);
    return 0;
}

S

一开始还以为真正的素数会很大, 还搞了个Miller Rabin

结果发现最大也就三位数

从后往前加结果忘了从前往后判断是不是素数WA了几发

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
// 一个真正的素数要么是个位数 要么是一个真正的素数前面加上一个个位数的素数

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN (2000)
#define INF (1000000)
#define LL long long
using namespace std;
// const int pri[5] = { 4, 2, 3, 5, 7 };
bool isp[INF + 5];
int prim[INF + 5];
LL ans[MAXN + 5] = {4, 2, 3, 5, 7};
int n;
/*
LL fastpow(int a, LL b, LL p) {
    if (b == 0) return 1 % p;
    if (b == 1) return a % p;
    LL re = fastpow(a, b >> 1, p);
 re = re * re % p;
    if (b & 1) re = re * a % p;
  return re;
}
bool jud(LL x) {
  for (int i = 1; i <= pri[0]; i++)
     if (fastpow(pri[i], x, x) != pri[i])
         return false;
    return true;
}*/
void init() {
    memset(isp, true, sizeof(isp));
    isp[1] = false;
    for (int i = 1; i <= INF; i++) {
        if (isp[i])
            prim[++prim[0]] = i;
        for (int j = 1; j <= prim[0] && (LL)i * prim[j] <= INF; j++) {
            isp[i * prim[j]] = false;
            if (i % prim[j] == 0) break;
        }
    }
}
bool jud(LL x) {
    while (x) {
        for (int i = 1000000; i; i /= 10)
            if (!isp[x % i]) return false;
        x /= 10;
    }
    return true;
}
bool cmp(LL x, LL y) { return x < y; }
void solve() {
    while (ans[0] <= n) {
        for (int i = 1; i <= ans[0]; i++) {
            LL x = ans[i], nx;
            for (int j = 2; j <= 4; j++) {
                nx = x * 10 + prim[j];
                if (jud(nx))
                    ans[++ans[0]] = nx;
            }
        }
    }
    sort(ans + 1, ans + ans[0] + 1, cmp);
    ans[0] = unique(ans + 1, ans + ans[0] + 1) - ans - 1;
    printf("%lld", ans[n]);
}
int main() {
    scanf("%d", &n);
    if (n > 9) {
        puts("-1");
        return 0;
    }
    init();
    solve();
    return 0;
}

T

线段树随便搞搞就过了

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (200000)
#define LS(x) ((x) << 1)
#define RS(x) (((x) << 1) | 1)
#define LL long long
using namespace std;
struct node {
    int le, ri;
    LL minz;
} b[MAXN << 2];
int n, a[MAXN + 5], ans;
LL fr[MAXN + 5], S;
void init(int now, int le, int ri) {
    b[now].le = le, b[now].ri = ri;
    if (le == ri) {
        b[now].minz = fr[le];
        return ;
    }
    int mi = (le + ri) >> 1;
    init(LS(now), le, mi), init(RS(now), mi + 1, ri);
    b[now].minz = min(b[LS(now)].minz, b[RS(now)].minz);
}
int enq(int now, int le, int ri, LL s) {
    if (le == ri) {
        if (b[now].minz > s) return 0;
        return le;
    }
    int mi = (b[now].le + b[now].ri) >> 1;
    if (le > mi) return enq(RS(now), le, ri, s);
    else if (ri <= mi) return enq(LS(now), le, ri, s);
    else {
        if (b[RS(now)].minz <= s) return enq(RS(now), mi + 1, ri, s);
        else if (b[LS(now)].minz <= s) return enq(LS(now), le, mi, s);
        else return 0;
    }
}
int main() {
    scanf("%d%lld", &n, &S);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]), fr[i] = fr[i - 1] + a[i];
    init(1, 1, n);
    for (int i = 1; i <= n; i++)
        ans = max(ans, enq(1, i, n, fr[i - 1] + S) - i + 1);
    if (!ans) puts("-1");
    else printf("%d", ans);
    return 0;
}

U

数位DP

细节恶心 呕

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define LL long long
using namespace std;
LL solve(LL x) {
    LL ans = 0, f[21][10][2][2];
    int a[21];
    a[0] = 0;
    for (LL i = 1000000000000000000, j = 19; i; i /= 10, j--) {
        a[j] = x / i % 10;
        if (a[j] && !a[0]) a[0] = j;
    } 
    if (!a[0]) a[0] = 1;

    // greater
    // f[i][j][0 / 1][0 / 1] 表示前i位已经确定, 第i位是j时, 否 / 是紧贴这上限, 到目前为止否 / 是全是0时 的单调递增数的个数

    memset(f, 0, sizeof(f));
    for (int j = 1; j < a[a[0]]; j++) f[a[0]][j][0][0] = 1;
    if (!x) return 1;
    f[a[0]][a[a[0]]][1][0] = 1;
    f[a[0]][0][0][1] = 1;

    for (int i = a[0]; i > 1; i--)
        for (int j = 0; j < 10; j++)
            for (int l = 0; l < 2; l++) {
                if (f[i][j][0][l])
                    for (int k = (l ? 0 : j); k < 10; k++)
                        f[i - 1][k][0][l && (k == 0)] += f[i][j][0][l];
                if (f[i][j][1][l]) {
                    if (a[i - 1] >= j)
                        f[i - 1][a[i - 1]][1][l && (a[i - 1] == 0)] = 1;
                    for (int k = j; k < a[i - 1]; k++)
                        f[i - 1][k][0][l && (k == 0)] += f[i][j][1][l];
                }
            }
    
    for (int i = 0; i < 10; i++)
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++)
                ans += f[1][i][j][k];

    memset(f, 0, sizeof(f));
    for (int j = 1; j < a[a[0]]; j++) f[a[0]][j][0][0] = 1;
    f[a[0]][a[a[0]]][1][0] = 1;
    f[a[0]][0][0][1] = 1;

    for (int i = a[0]; i > 1; i--)
        for (int j = 0; j < 10; j++) 
            for (int l = 0; l < 2; l++) {
                if (f[i][j][0][l])
                    for (int k = (l ? 9 : j); k >= 0; k--)
                        f[i - 1][k][0][l && (k == 0)] += f[i][j][0][l];
                if (f[i][j][1][l]) {
                    if (a[i - 1] <= j)
                        f[i - 1][a[i - 1]][1][l && (a[i - 1] == 0)] = 1;
                    for (int k = min(j, a[i - 1] - 1); k >= 0; k--)
                        f[i - 1][k][0][l && (k == 0)] += f[i][j][1][l];
                }
            }
    if (a[0] > 1) {
        for (int i = 0; i < 10; i++)
            for (int j = 0; j < 2; j++)
                for (int k = 0; k < 2; k++)
                    ans += f[1][i][j][k];
        ans -= 9ll * (a[0] - 1) + 1; // 减去重复的 0 和 111 222 333 这种东西 
        int dx = a[a[0]];
        LL gg = 0;
        for (int i = 1; i <= a[0]; i++)
            gg = gg * 10 + dx;
        dx -= (gg > x);
        ans -= dx;
    }
    return ans;
}
int main() { 
    int t;
    scanf("%d", &t);
    while (t--) {
        LL le, ri;
        scanf("%lld%lld", &le, &ri);
        printf("%lld\n", solve(ri) - solve(le - 1));
    }/* 
	while (1) {
    	int x;
       	scanf("%d", &x);
       	printf("%lld\n", solve((LL)x));
    }*/
    return 0;
}

V

插板法看一下\(f(n)\)最多的取值也就\(10^6\)级别的

果断枚举\(f(n)\)

T了一发, 不知道为啥再交了一遍就好了

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (4000000)
#define LL long long
using namespace std;
int num[MAXN + 5][10], f[MAXN + 5]; // down
void init() {
    for (int i1 = 0; i1 <= 17; i1++)
        for (int i2 = 0; i1 + i2 <= 17; i2++)
            for (int i3 = 0; i1 + i2 + i3 <= 17; i3++)
                for (int i4 = 0; i1 + i2 + i3 + i4 <= 17; i4++)
                    for (int i5 = 0; i1 + i2 + i3 + i4 + i5 <= 17; i5++)
                        for (int i6 = 0; i1 + i2 + i3 + i4 + i5 + i6 <= 17; i6++)
                            for (int i7 = 0; i1 + i2 + i3 + i4 + i5 + i6 + i7 <= 17; i7++)
                                for (int i8 = 0; i1 + i2 + i3 + i4 + i5 + i6 + i7 + i8 <= 17; i8++)
                                    for (int i9 = 0; i1 + i2 + i3 + i4 + i5 + i6 + i7 + i8 + i9 <= 17; i9++) {
                                        f[++f[0]] = i1 + 4 * i2  + 9 * i3 + 16 * i4 + 25 * i5 + 36 * i6 + 49 * i7 + 64 * i8 + 81 * i9;
                                        num[f[0]][1] = i1; 
                                        num[f[0]][2] = i2; 
                                        num[f[0]][3] = i3; 
                                        num[f[0]][4] = i4; 
                                        num[f[0]][5] = i5; 
                                        num[f[0]][6] = i6; 
                                        num[f[0]][7] = i7; 
                                        num[f[0]][8] = i8; 
                                        num[f[0]][9] = i9; 
                                    }
}
int main() {
    init();
    LL k, a, b;
    int ans = 0;
    scanf("%lld%lld%lld", &k, &a, &b);
    for (int i = 1; i <= f[0]; i++) 
        if (f[i] * k <= b && f[i] * k >= a) {
            LL now = f[i] * k;
            int nownum[10];
            memset(nownum, 0, sizeof(nownum));
            while (now) {
                ++nownum[now % 10];
                now /= 10;
            }
            bool gg = true;
            for (int j = 1; j < 10; j++)
                if (nownum[j] != num[i][j]) {
                    gg = false;
                    break;
                }
            if (gg) ++ans;
        }
    printf("%d", ans);
    return 0;
}

W

W题 water题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#define MAXN (200000)
using namespace std;
int main() {
    string A, B, C;
    cin >> A >> B >> C;
    int n = A.length(), ans = 0;
    for (int i = 0; i < n; i++)
        if (A[i] == B[i] && B[i] != C[i]) ++ans;
        else if (A[i] != B[i] && A[i] == C[i]) ++ans;
        else if (B[i] == C[i] && A[i] != B[i]) ++ans;
        else if (A[i] != B[i] && B[i] != C[i] && C[i] != A[i]) ans += 2;
    cout << ans;
    return 0;
}

X

你要硬说他是二维偏序到也差不多...

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (200000)
#define MAXZ (600000)
#define lowbit(i) ((i) & (-(i)))
using namespace std;
struct kard {
    int a[3];
} c[MAXN + 5], x;
struct que {
    bool type;
    int a[2];
} q[(MAXN << 1) + 5];
int n, ans, b[MAXZ + 5], z[MAXZ + 5], cntq;
bool cmp1(int x, int y) { return x < y; }
bool cmp2(const kard& x, const kard& y) {
    if (x.a[0] == y.a[0])
        return ((x.a[1] == y.a[1]) ? (x.a[2] < y.a[2]) : (x.a[1] < y.a[1]));
    else return x.a[0] < y.a[0];
}
bool cmp3(const que& x, const que& y) {
    return ((x.a[0] == y.a[0]) ? (x.a[1] < y.a[1]) : (x.a[0] < y.a[0]));
}
void modify(int x) {
    for (int i = x; i <= z[0]; i += lowbit(i))
        ++b[i];
}
int enquiry(int x) {
    int re = 0;
    for (int i = x; i; i -= lowbit(i))
        re += b[i];
    return re;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d%d", &c[i].a[0], &c[i].a[1], &c[i].a[2]), sort(c[i].a, c[i].a + 3, cmp1),
            z[++z[0]] = c[i].a[0], z[++z[0]] = c[i].a[1], z[++z[0]] = c[i].a[2];
    sort(z + 1, z + z[0] + 1);
    z[0] = unique(z + 1, z + z[0] + 1) - z - 1;
    for (int i = 1; i <= n; i++) {
        ++cntq;
        q[cntq].a[0] = lower_bound(z + 1, z + z[0] + 1, c[i].a[0]) - z;
        q[cntq].a[1] = lower_bound(z + 1, z + z[0] + 1, c[i].a[1]) - z;
        q[cntq].type = false;
        ++cntq;
        q[cntq].a[0] = lower_bound(z + 1, z + z[0] + 1, c[i].a[1]) - z;
        q[cntq].a[1] = lower_bound(z + 1, z + z[0] + 1, c[i].a[2]) - z;
        q[cntq].type = true;
    }
    sort(q + 1, q + cntq + 1, cmp3);
    for (int i = 1; i <= cntq; i++) {
        if (q[i].type) ans += (enquiry(q[i].a[1]) == n);
        else modify(q[i].a[1]);
    }
    printf("%d", ans);
    return 0;
}

Y

不会

Z

随便写写就好了

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

By 我是傻逼的 Cansult