A. 小红的正整数计数

签到

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>

using namespace std;

int l, r;

int main()
{
    cin >> l >> r;
    
    int res = 0;
    for (int i = l; i <= r; i++)
        if (i % 2 == 0)
            res++;
    
    cout << res << endl;
    
    return 0;
}

B. 小红的双生串

分别统计前半段和后半段出现最多的字符，再把整个字符串修改成只有这两个字符。

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
#include <bits/stdc++.h>

using namespace std;

string s;

int main()
{
    cin >> s;
    
    map<char, int> p1, p2;
    for (int i = 0; i < s.size(); i++)
    {
        if (i < s.size() / 2) p1[s[i]]++;
        else p2[s[i]]++;
    }
    
    int c1 = 0, c2 = 0;
    for (auto it: p1) c1 = max(c1, it.second);
    for (auto it: p2) c2 = max(c2, it.second);
    
    cout << s.size() - c1 - c2 << endl;
    
    return 0;
}

C. 小红的双生排列

只需要讨论所有的奇数在偶数位，偶数在奇数位，以及所有的奇数在奇数位，偶数在偶数位这两种情况。

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
#include <bits/stdc++.h>

#define int long long

using namespace std;

const int mod = 1e9 + 7;

int n;

int jie(int x)
{
    int res = 1;
    for (int i = 1; i <= x; i++) res = res * i % mod;
    return res;
}

signed main()
{
    cin >> n;
    
    int res = jie(n / 2) * jie((n + 1) / 2) % mod;
    if (n % 2) cout << res << endl;
    else cout << res * 2 % mod << endl;
    
    return 0;
}

D. 小红的双生数

不难判断，双生数的位数一定是偶数，因此需要对 \(x\) 进行分类讨论。

若 \(x\) 为奇数，则第一个大于等于 \(x\) 的双生数的位数一定比 \(x\) 多一位，构造成 \(11001100...\) 即可。

若 \(x\) 为偶数，则第一个大于等于 \(x\) 的双生数的位数可能跟 \(x\) 相同，也可能多两位。

  • 第一步，使用从左到右一次两位的方式遍历 \(x\) 的每一位数，直到当前两位数不同。把这两位数当成一个整数，只需找到第一个大于这两位数的双生数，替换即可。右边剩余的位数全部构造成 \(00110011...\) 即可。
  • 第二步，从左往右检查是否存在四位数全部相同的情况。存在，则从这四位数的后两位开始，若这两位数分别加一之后超过 \(9\)，或者与左边两位相同，就向左顺延两位再尝试执行加一操作，不断循环，直到找到能够执行加一操作的两位数，加一之后，把右边的其余位全部构造成 \(00110011...\)。如果没有找到能够执行加一操作的两位数，就把 \(x\) 的左边再添加两个 \(0\)，执行加一操作，右边的其余位构造方法同上。

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
#include <bits/stdc++.h>

using namespace std;

string s;

int main()
{
    cin >> s;

    if (s.size() % 2)
    {
        s += '0';
        for (int i = 0; i < s.size(); i += 2)
        {
            if (i % 4 == 0) s[i] = s[i + 1] = '1';
            else s[i] = s[i + 1] = '0';
        }
    }
    else
    {
        int idx = -1;
        for (int i = 0; i < s.size(); i += 2)
        {
            if (idx == -1)
            {
                if (s[i] != s[i + 1])
                { 
                    idx = i + 2;
                    if (s[i] > s[i + 1]) s[i + 1] = s[i];
                    else s[i + 1] = ++s[i];
                }
                if (i && s[i] == s[i - 1])
                {

                    idx = 0;
                    for (int j = i; j >= 0; j -= 2)
                    {
                        if (s[j] == '9') continue;
                        s[j]++, s[j + 1]++;
                        if (j && s[j] == s[j - 1])
                        {
                            if (s[j] == '9') continue;
                            s[j]++, s[j + 1]++;
                        }
                        idx = j + 2; 
                        break;
                    }
                }
                if (~idx) i = idx - 2;
            }
            else
            {
                if (i % 4 == idx % 4) s[i] = s[i + 1] = '0';
                else s[i] = s[i + 1] = '1';
            } 
        }
        if (!idx) s = '1' + s, s = '1' + s;
    }

    cout << s << endl;

    return 0;
}

E. 小红的双生英雄

经典的分组背包问题，对于每一对英雄组合，他们两个的所有选择方案都被放在同一组中。

令 \(f(i,j,k)\) 为前 \(i\) 组，总花费不超过 \(j\)，选择了 \(k\) 个英雄的最大战斗力。做一遍分组背包即可。

时间复杂度 \(O(n*c*4)\)

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
#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 1010;

struct Node
{
    int a, b, c;
};

int n, c, m;
int a[N], b[N];
vector<Node> s[N];
int cnt;
bool st[N];
int f[N][N][5];

signed main()
{
    cin >> n >> c >> m;
    for (int i = 1; i <= n; i++) cin >> a[i] >> b[i];
    for (int i = 0; i < m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        st[u] = st[v] = true;
        cnt++;
        s[cnt].push_back({a[u], b[u], 1});
        s[cnt].push_back({a[v], b[v], 1});
        s[cnt].push_back({a[u] + a[v], b[u] + b[v] + w, 2});
    }

    for (int i = 1; i <= n; i++)
    {
        if (st[i]) continue;
        s[++cnt].push_back({a[i], b[i], 1});
    }

    for (int i = 1; i <= cnt; i++)
        for (int j = 1; j <= c; j++)
            for (int k = 1; k <= 4; k++)
            {
                f[i][j][k] = f[i - 1][j][k];
                for (auto it: s[i])
                    if (j >= it.a && k >= it.c)
                        f[i][j][k] = max(f[i][j][k], f[i - 1][j - it.a][k - it.c] + it.b);
            }

    cout << f[cnt][c][4] << endl;
        
    return 0;
}

F && G. 小红的双生树

先考虑无法染成双生树的情况。

  • 当 \(n\) 为奇数时，\(n - 1\) 个节点两两配对，始终剩下一个节点无法配对，因此无法变成双生树。
  • 当 \(n\) 为偶数时，考虑遍历整棵树。当以节点 \(u\) 为根的子树节点数是奇数时，那么这棵子树无法变成双生子树，只能让节点 \(u\) 与它的父节点 \(fa\) 配对。因此，当 \(u\) 的父节点 \(fa\) 连接了超过 \(1\) 棵节点数为奇数的子树时，节点 \(fa\) 只能被分配给其中一棵子树来进行配对，其余的子树都无法变成双生子树。可以由此来判断该树能不能变成双生树。

接下来考虑双生树的构造方案。对于节点 \(u\)，设它的子节点是 \(v\)，当以 \(v\) 为根的子树节点数为奇数时，\(v\) 的颜色只能和 \(u\) 相同，当节点数时偶数时，这棵子树内部就已经两两配对，\(v\) 的颜色一定和 \(u\) 不同。由此可以发现，当根节点的颜色被确定时，双生树只有一种构造方案，因此只有根节点为红色和根节点为蓝色两种染色树，可以分别预处理出染成两种双生树需要的花费。

最后考虑路径修改，只需要预处理出把根节点到当前节点的简单路径全部染成红色，对答案的变化即可，使用 \(lca\) 即可把两条根到点的简单路径合并成一条点到点的简单路径。

设 \(f1[u][i]\) 为根节点染成 \(i\)，把以节点 \(u\) 为根节点的子树变成双生子树所需要的花费，\(i=0\) 代表红色，\(i=1\) 代表蓝色。状态转移方程为 \(f1[u][i] += f1[v][i]\)

\(f2[u][i]\) 表示把根节点到 \(u\) 的简单路径染成红色，对答案的贡献。状态转移方程为 \(f2[u][i] = f2[father][i] + calc(u)\)，\(calc(u)\) 代表把 \(u\) 染成红色对答案的贡献。

时间复杂度 O(nlogn)

### 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
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
130
 #include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int n, q;
string s, s0, s1;
vector<int> h[N];
int fa[N][25], dep[N], c[N];
int f1[N][2], f2[N][2];

void dfs1(int u, int father)
{
    dep[u] = dep[father] + 1;

    fa[u][0] = father;
    for (int i = 1; i <= 20; i++)
        fa[u][i] = fa[fa[u][i - 1]][i - 1];

    c[u]++;
    for (auto v: h[u])
    {
        if (v == father) continue;
        dfs1(v, u);
        c[u] += c[v];
    }
}

bool dfs2(int u, int father)
{
    if (n % 2) return false;

    int cnt = 0;
    for (auto v: h[u])
    {
        if (v == father) continue;
        if (c[v] % 2) 
        {
            cnt++;
            s0[v] = s0[u];
            s1[v] = s1[u];
        }
        else
        {
            if (s0[u] == 'B') s0[v] = 'R';
            else s0[v] = 'B';
            if (s1[u] == 'B') s1[v] = 'R';
            else s1[v] = 'B';
        }
        if (!dfs2(v, u)) return false;
    }

    return cnt < 2;
}

void dfs3(int u, int father)
{	
    f2[u][0] = f2[father][0];
    f2[u][1] = f2[father][1];
    if (s[u] == 'B')
    {
        if (s0[u] == 'R') f2[u][0]--;
        else f2[u][0]++;
        if (s1[u] == 'R') f2[u][1]--;
        else f2[u][1]++;
    }

    f1[u][0] = (s[u] != s0[u]);
    f1[u][1] = (s[u] != s1[u]);

    for (auto v: h[u])
    {
        if (v == father) continue;
        dfs3(v, u);
        f1[u][0] += f1[v][0];
        f1[u][1] += f1[v][1];
    }
}

int lca(int u, int v)
{
    if (dep[u] < dep[v]) swap(u, v);

    for (int i = 20; i >= 0; i--)
        if (dep[fa[u][i]] >= dep[v])
            u = fa[u][i];

    if (u == v) return u;

    for(int i = 20; i >= 0; i--)
        if (fa[u][i] != fa[v][i])
            u = fa[u][i], v = fa[v][i];

    return fa[u][0];
}
int main()
{
    cin >> n >> q >> s;
    for (int i = 0; i < n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        h[u].push_back(v), h[v].push_back(u);
    }

    s = s0 = s1 = ' ' + s;
    s0[1] = 'R', s1[1] = 'B';

    dfs1(1, 0);
    bool flag = dfs2(1, 0);
    if (flag) dfs3(1, 0);

    while (q--)
    {
        int x, y;
        cin >> x >> y;
        
        if (!flag) cout << -1 << endl;
        else
        {
            int t = lca(x, y);
            int r1 = f1[1][0] + f2[x][0] + f2[y][0] - f2[t][0] - f2[fa[t][0]][0];
            int r2 = f1[1][1] + f2[x][1] + f2[y][1] - f2[t][1] - f2[fa[t][0]][1];
            cout << min(r1, r2) << endl;
        }
    }

    return 0;
}