题集链接；
E Everyone is bot
博弈论
思路
考虑n=10,p=3：
假设前7人均选择复读，则第8,9,10人均不选择复读，因为此三人任意一人选择复读，另外两人可以在下一轮接下，该人即被禁言；
同理，若前4人均选择复读，则第5,6,7,8,9,10人均不选择复读，因为此六人任意一人选择复读，就会有两人跟随，该人即被禁言，到达上面一种情况；
进一步地，若第一人选择复读，那么另外9人均不会选择复读；
每种情况删去了p人，即最后可能拿到奖励的为前 n%p 人，其余人均不敢复读；
代码
队友代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include <bits/stdc++.h>
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<<" ";
}
}
|
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 靠拢；
代码
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
| #include <bits/stdc++.h>
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();
}
}
|
H Here is an Easy Problem of Zero-chan
LCA
题意
定义f(x)=∏i=1nlca(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) 的相关值；
代码
队友代码如下
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
| #include<bits/stdc++.h>
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();
}
}
|
J Jellyfish and its dream
思路
考虑循环序列中相邻两数的情况：相等对（00,11,22），上升对（01,12,20）,上升对（02,10,21），我们的最终目标是将所有部分变为相等对；
单个上升对可以通过一次变换变为相等对，同时使该对左侧的下降对变为相等对，在这个过程中，上升对和下降对一一对应；
如果该上升对左侧也是上升对，经操作后，左侧变为下降对；
如果左侧是相等对，则可以直接略过，认为整个相等对均变换为上升对的右侧数字；
在上述过程中，如果仅存在上升对和相等对，则可以均变为相等对，如果存在下降对，则上升对数量需要大于等于下降对；
代码
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 <bits/stdc++.h>
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();
}
}
|
M Maimai DX 2077
模拟
代码
注意对0的处理
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 <bits/stdc++.h>
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));
}
|