继续逃课。。。上分失败系列

心态崩了 _(:з」∠)_

A. Fake NP

暴力签到。

求范围 [L, R] 中出现次数最多的约数。

（最后半小时我居然被人 X 了

最后改成了先筛一发然后挨个枚举。

正解证明了我是个智障：

  1. 对于 L != R 的情况，2 一定是最好的。
  2. 对于 L == R 的情况，选 L

B. 3-palindrome

构造一个长度为 L， 的串，使得该串不包含任何长度为 3 的回文字串，且 C 出现的次数最少。

仍然是智(zhi)商(zhang)题，考虑下列串

AABBAABBAABB….

C. Find Amir

还是构造题。

长度为 N 的环上有一些点，连接点 i 和点 j 的代价为 其中 ，求最小代价。

1

print((int(input())-1)//2)

Emm…

D. Minimum number of steps

给一个 的串，进行一种操作叫做 str.replace("ab", "bba")

求经过多少次使得串内没有任何一个 ab 字串。

手玩找规律。。。

像我的话就是游程编码了一发，然后写了个心情复杂的数列递推。

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

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const ULL mod = ULL(1E9 + 7);

string s;
struct blk {
    char c; int ora;
    blk *n;
} PL[int(1E6 + 1E3)]; int ppos;
blk* head;

ULL qpow(ULL a, ULL b) {
    ULL ret = 1;
    while(b) {
        if(b&1) ret = (ret * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ret;
}

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> s;

    int _ = s.size();
    blk* cur = head = &PL[ppos++]; cur->c = s[0];
    for(int i=0;i<_;i++) {
        if(cur->c != s[i]) {
            cur->n = &PL[ppos++];
            cur = cur->n;
            cur->ora = 1;
            cur->c = s[i];
        } else ++cur->ora;
    }

    ULL t = 0;
    for(cur=head;cur;cur=cur->n) {
        if(cur->c == 'a' && cur->n) {
            ULL k = (qpow(2, cur->ora) - 1 + mod) % mod;
            k = (k * cur->n->ora) % mod;
            t = (t + k) % mod;
            if(cur->n->n) {
                cur->n->n->ora += cur->ora;
            }
        }
    }

    cout << t << endl;
}

E. Ice cream coloring

考场上并没有想出来。。

给一颗无根树，树上每个节点有一些冰淇淋，每种类型的冰淇淋一定构成一联通子树。
试给冰淇淋染色，共点的冰淇淋不能染相同颜色。求最小染色数及方案。

直接 dfs，给对每个点来说，没染过的冰淇淋染成当前已染冰淇淋集合的 mex。

主要是利用联通这个性质。。考虑一下似乎听起来很正确

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <set>
#include <vector>
#include <algorithm>

namespace istream {
    const int L = 1<<16;
    char buf[L], *S, *T;
    char c; bool uneof = true;

    inline char readch() {
        if(S==T) {
            T=(S=buf) + fread(buf, 1, L, stdin);
            if(S==T) { uneof = false; return EOF; }
        }
        return *S++;
    }

    void readint(register int &x) {
        x = 0; bool flag = 0;
        while((c < '0' || c > '9') && uneof) {
            flag = flag && (c == '-');
            c = readch();
        }
        if(!uneof) return;
        while(c >= '0' && c <= '9') {
            x = (x<<1) + (x<<3) + (c - '0'); c = readch();
        }
        x = flag ? -x : x;
    }
};
#define rint(x) (istream::readint(x))

const int MAX_N = int(4E5 + 1E3);
using std::set;
using std::vector;

set<int> Color[MAX_N];
int N, M;

struct tgno {
    int v; tgno* n;
} POOL[MAX_N<<1], *Head[MAX_N]; int ppos;

inline
void _add(int u, int v) {
    POOL[ppos].v = v;
    POOL[ppos].n = Head[u];
    Head[u] = &POOL[ppos++];
}

inline
void addEdge(int u, int v) {
    _add(u, v), _add(v, u);
}

int C;
int ans[MAX_N];
void dfs(int cur, int pre = 0) {
    vector<int> used; used.reserve(Color[cur].size());
    typedef set<int>::iterator It;
    
    for(It i=Color[cur].begin();i!=Color[cur].end();++i) {
        if(ans[*i]) used.push_back(ans[*i]);
    }

    int S = used.size();
    std::sort(used.begin(), used.end());

    int sta = 0, now = 1;
    for(It i=Color[cur].begin();i!=Color[cur].end();++i) {
        if(!ans[*i]) {
            while(sta < S) {
                if(now == used[sta]) now++, sta++;
                else break;
            }
            ans[*i] = now++;
        }

        C = std::max(C, now - 1);
    }

    for(tgno* i=Head[cur];i;i=i->n) {
        if(i->v != pre) {
            dfs(i->v, cur);
        }
    }
}

int main() {
    rint(N); rint(M);

    int n, c;
    for(int i=1;i<=N;i++) {
        rint(n);
        for(int j=0;j<n;j++) {
            rint(c);
            Color[i].insert(c);
        }
    }

    int u, v;
    for(int i=1;i<N;i++) {
        rint(u); rint(v);
        addEdge(u, v);
    }


    typedef set<int>::iterator It;
    for(It i=Color[1].begin();i!=Color[1].end();++i) {
        ans[*i] = ++C;
    }

    dfs(1);
    C = std::max(1, C);

    printf("%d\n", C);
    for(int i=1;i<=M;i++) {
        if(ans[i]) {
            printf("%d ", ans[i]);
        } else {
            printf("1 ");
        }
    }

    puts("");
}