2022牛客暑期多校训练营（加赛）（EGHJM）

个人题解，非广告
题集链接；

E Everyone is bot

博弈论

思路

考虑n=10,p=3：
假设前7人均选择复读，则第8,9,10人均不选择复读，因为此三人任意一人选择复读，另外两人可以在下一轮接下，该人即被禁言；
同理，若前4人均选择复读，则第5,6,7,8,9,10人均不选择复读，因为此六人任意一人选择复读，就会有两人跟随，该人即被禁言，到达上面一种情况；
进一步地，若第一人选择复读，那么另外9人均不会选择复读；

每种情况删去了p人，即最后可能拿到奖励的为前 $n\%p$ 人，其余人均不敢复读；

代码

队友代码如下

#include 
using namespace std;
int n,k;
int a[1020];
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        int x;
        for(int j=1;j<=n;j++){
            cin>>x;
            if(i==j){
                a[i]=x;
            }
        }
    }
    for(int i=1;i<=(n%k);i++){
        cout<<a[i]<<" ";
    }
    for(int i=(n%k)+1;i<=n;i++){
        cout<<0<<" ";
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

G Good red-string

贪心

思路

与合法括号序列类似，标记cr,ce,cd为子串中字符r,e,d的个数；
对于任意i,j，应该满足 $cr[1,i]⩾ce[1,i]⩾cd[1,i],cr[j,n]⩽ce[j,n]⩽cd[j,n],cr[1,n]=ce[1,n]=cd[1,n]=n/3$ ；

具体操作时，依照 $cr[1,i]⩾ce[1,i],ce[j,n]⩽cd[j,n]$ 来优先分配?位，再将剩余?位向 $n/3$ 靠拢；

代码

#include 
using namespace std;
void solve()
{
string g;
        cin >> g;
        int n = g.length(), m = n / 3, c = 0;
        stack<int> stk;
        for (int i = 0; i < n; i++)
        {
            if (g[i] == 'd')
                ++c;
            else if (g[i] == 'e')
                --c;
            else if (g[i] == '?')
                stk.push(i);
            if (c > 0)
            {
                if (!stk.empty())
                {
                    g[stk.top()] = 'e', stk.pop(), --c;
                }
                else
                {
                    printf("No\n");
                    return;
                }
            }
        }
        c = 0;
        while (!stk.empty())
            stk.pop();
        for (int i = n - 1; i >= 0; i--)
        {
            if (g[i] == 'r')
                ++c;
            else if (g[i] == 'e')
                --c;
            else if (g[i] == '?')
                stk.push(i);
            if (c > 0)
            {
                if (!stk.empty())
                {
                    g[stk.top()] = 'e', stk.pop(), --c;
                }
                else
                {
                    printf("No\n");
                    return;
                }
            }
        }
        int cr = 0, ce = 0, cd = 0;
        for (int i = 0; i < n; i++)
        {
            if (g[i] == 'r')
                ++cr;
            else if (g[i] == 'e')
                ++ce;
            else if (g[i] == 'd')
                ++cd;
        }
        for (int i = 0; i < n; i++)
        {
            if (g[i] == '?')
            {
                if (cr < m)
                {
                    g[i] = 'r', ++cr;
                }
                else if (ce < m)
                {
                    g[i] = 'e', ++ce;
                }
                else if (cd < m)
                {
                    g[i] = 'd', ++cd;
                }
            }
        }
        cr = 0, ce = 0, cd = 0;
        for (int i = 0; i < n; i++)
        {
            if (g[i] == 'r')
                ++cr;
            else if (g[i] == 'e')
                ++ce;
            else if (g[i] == 'd')
                ++cd;
            if (!(cr >= ce && ce >= cd))
            {
                printf("No\n");
                return;
            }
        }
        cr = 0, ce = 0, cd = 0;
        for (int i = n; i >= 1; i--)
        {
            if (g[i] == 'r')
                ++cr;
            else if (g[i] == 'e')
                ++ce;
            else if (g[i] == 'd')
                ++cd;
            if (!(cr <= ce && ce <= cd))
            {
                printf("No\n");
                return;
            }
        }
        printf("Yes\n");
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
}
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

H Here is an Easy Problem of Zero-chan

LCA

题意

定义$f(x)={\prod }_{i=1}^{n}lca(x,i)$ ，给定 q 个 x ，输出每个 x 的 $f(x)$ 中结尾0的个数；

思路

定义 $cnt[x]$ 为以 x 为根的子树中节点个数；
考虑子树中的节点，对 $f(x)$ 的总贡献为 $cnt[x]x$；
考虑 x 的某个祖先节点 y,z ，满足z是y的父节点，在z子树中且不在y子树中的节点对 $f(x)$ 的总贡献为 $(cnt[z]-cnt[y])z$；

依此，我们可以 $O(n)$ 复杂度内求出所有点 $f(x)$ 的相关值；

代码

队友代码如下

#include
using namespace std;
const int N = 1e6+7;
int sz[N],five[N],two[N],fa[N],n,tot,head[N];
typedef long long ll;
struct node{
	int lg2,lg5;
	node(){lg2=lg5=0;}
	node(int x,int y){
		lg2 = x;
		lg5 = y;
	}
	node operator+(const node &rhs){
		return node(lg2+rhs.lg2,lg5+rhs.lg5);
	}
	node operator-(const node &rhs){
		return node(lg2-rhs.lg2,lg5-rhs.lg5);
	}
	node operator*(int rhs){
		return node(lg2*rhs,lg5*rhs);
	}
	void print(){
		cout << min(lg2,lg5) << '\n';
	}
}sum[N];
node calc(int u){
	node x = node(two[u],five[u]);
	node fx = node(two[fa[u]],five[fa[u]]);
	return (x-fx)*sz[u];
}
struct Edge{
	int to,nxt;
}e[N<<1];
inline void addEdge(int u,int v){
	e[++tot].nxt = head[u];
	head[u] = tot;
	e[tot].to = v;
}
void dfs(int u){
	sz[u] = 1;
	for(int i=head[u];i;i=e[i].nxt){
		int v = e[i].to;
		if(v==fa[u])	continue;
		fa[v] = u;
		dfs(v);
		sz[u] += sz[v];
	}
}
void dfs2(int u){
	sum[u] = sum[fa[u]] + calc(u);
	for(int i=head[u];i;i=e[i].nxt){
		int v = e[i].to;
		if(v==fa[u])	continue;
		dfs2(v);
	}
}
int main(){
	int T;
	cin >> n >> T;
	for(int i=1;i<=n;++i){
		int x = i;
		while(~x&1)	two[i] ++, x >>= 1;
		while(x%5==0)	five[i] ++,x /= 5;
	}
	for(int i=1;i<n;++i){
		int u,v;	cin >> u >> v;
		addEdge(u,v);
		addEdge(v,u);
	}
	dfs(1);
	dfs2(1);
	while(T--){
		int u;	cin >> u;
		sum[u].print();
	}
}
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

J Jellyfish and its dream

思路

考虑循环序列中相邻两数的情况：相等对（00,11,22），上升对（01,12,20）,上升对（02,10,21），我们的最终目标是将所有部分变为相等对；

单个上升对可以通过一次变换变为相等对，同时使该对左侧的下降对变为相等对，在这个过程中，上升对和下降对一一对应；
如果该上升对左侧也是上升对，经操作后，左侧变为下降对；
如果左侧是相等对，则可以直接略过，认为整个相等对均变换为上升对的右侧数字；

在上述过程中，如果仅存在上升对和相等对，则可以均变为相等对，如果存在下降对，则上升对数量需要大于等于下降对；

代码

#include 
using namespace std;
int a[1000006],b[1000006];
void solve()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    b[0] = (a[0] - a[n - 1] + 3) % 3;
    for (int i = 1; i < n; i++)
        b[i] = (a[i] - a[i - 1] + 3) % 3;
    int c1 = 0, c2 = 0;
    for (int i = 0; i < n; i++)
    {
        if (b[i] == 1)
            c1++;
        else if (b[i] == 2)
            c2++;
    }
    if (c1 >= c2)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
}
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

M Maimai DX 2077

模拟

代码

注意对0的处理

#include 
using namespace std;
typedef long long ll;
double mk[4][5] = {
    {1, 1, 0.8, 0.5, 0}, {2, 2, 1.6, 1.0, 0}, {3, 3, 2.4, 1.5, 0}, {5, 5, 2.5, 2, 0}};
double mke[5] = {1, 0.5, 0.4, 0.3, 0};
int main()
{
    int tmp, sum = 0, sm3 = 0;
    double a, b, a0, b0;
    a = b = a0 = b0 = 0;
    for (int i = 0; i < 4; i++)
    {
        int sm = 0;
        for (int j = 0; j < 5; j++)
        {
            cin >> tmp;
            sm += tmp;
            a0 += tmp * mk[i][j];
            if (i == 3)
                b0 += tmp * mke[j];
        }
        a += sm * mk[i][0];
        if (i == 3)
            b += sm * mke[0], sm3 += sm;
        sum += sm;
    }
    printf("%.12lf", ((sum != 0) ? a0 / a * 100 : 100) + ((sm3 != 0) ? b0 / b : 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