A.Consecutive Sum
题目大意
给定一个长度为$n$的数组$a$，可做以下操作至多$k$次：
选择两个下标$i$和$j$，要求$i\ mod\ k=j\ mod\ k$，然后交换$a_i$和$a_j$
操作完后，任意选连续$k$个数，这些数的的和是你的分数，问分数最多是多少
解题思路
签到题
相当于把数组中的所有元素按除以$k$得到的余数分组，在每个组中取最大值加起来就可以
具体代码
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
| #include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
#include <set>
#include <vector>
typedef long long LL;
const LL N = 2e5 + 10;
const LL MOD = 1e9 + 7;
int n, m, q;
LL a[N];
LL c[N];
LL ans;
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int T = 1;
std::cin >> T;
while (T--)
{
memset(c, 0, sizeof c);
ans = 0LL;
std::cin >> n >> m;
for (int i = 1; i <= n; ++i)
{
std::cin >> a[i];
c[i % m] = std::max(c[i % m], a[i]);
}
for (int i = 0; i < m; ++i)
ans += c[i];
std::cout << ans << '\n';
}
return 0;
}
|
B.Rule of League
题目大意
有一场羽毛球比赛，$n$个玩家参与
比赛是这样进行的：先让玩家$1$和玩家$2$比，胜者和玩家$3$比，胜者和玩家$4$比，$\cdots$，一直这样比$n-1$轮
现在给出$x$和$y$，代表比赛结束后每名玩家的的胜场数要么是$x$要么是$y$
问比赛结果是否有可能满足$x$和$y$，如果能，输出可能的每轮的胜者
解题思路
$x$和$y$不能都大于$0$(考虑第一场比赛，玩家$1$和玩家$2$肯定有一个人以$0$胜场被淘汰)
同时显然$x$和$y$不能都等于$0$
那么就是说$x$和$y$中有一个是$0$，另一个大于$0$
若有$n$名玩家，比赛会进行$n-1$轮
那么只要$n-1$是$max(x,y)$的倍数就可以了
具体代码
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 <algorithm>
#include <cstring>
#include <map>
#include <set>
#include <vector>
typedef long long LL;
const LL N = 2e5 + 10;
const LL MOD = 1e9 + 7;
int n, m, q, x, y;
int a[N];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int T = 1;
std::cin >> T;
while (T--)
{
std::cin >> n >> x >> y;
if (!x && !y)
std::cout << -1 << '\n';
else if (x && y)
std::cout << -1 << '\n';
else
{
int t = std::max(x, y);
int rounds = n - 1;
if (!(rounds % t))
{
for (int i = 2; i <= n; i += t)
for (int j = 1; j <= t; ++j)
std::cout << i << ' ';
std::cout << '\n';
}
else
std::cout << -1 << '\n';
}
}
return 0;
}
|
C.Parity Shuffle Sorting
题目大意
给定长度为$n$的非负数组$a$，可执行下述操作若干次：
第一步：选择两个下标$l$和$r$
第二步：若$a_l+a_r$是奇数，那么令$a_r=a_l$，若$a_l+a_r$是偶数，那么令$a_l=a_r$
找到一种不超过$n$次的操作序列并输出(可证明一定存在这样的操作序列)，让$a$数组变成严格不下降序列，注意没有必要让操作次数尽可能小
解题思路
题干里特意强调了限制操作次数不超过$n$次，并且没有必要让操作次数尽可能小
不禁令人想到是不是正解的操作次数就是差不多$n$次
事实也确实如此，只要将序列变成常数列就可以了
操作次数最坏$n-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
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
| #include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
#include <set>
#include <vector>
typedef long long LL;
const LL N = 2e5 + 10;
const LL MOD = 1e9 + 7;
LL n, m, q, t;
LL a[N];
LL l[N], r[N];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int T = 1;
std::cin >> T;
while (T--)
{
m = 0;
std::cin >> n;
for (int i = 1; i <= n; ++i)
std::cin >> a[i];
if ((a[1] - a[n]) & 1)
t = a[n] = a[1], l[++m] = 1, r[m] = n;
else
t = a[1] = a[n], l[++m] = 1, r[m] = n;
if (t & 1)
for (int i = 2; i <= n - 1; ++i)
{
if (a[i] & 1)
a[i] = a[n], l[++m] = i, r[m] = n;
else
a[i] = a[1], l[++m] = 1, r[m] = i;
}
else
for (int i = 2; i <= n - 1; ++i)
{
if (a[i] & 1)
a[i] = a[1], l[++m] = 1, r[m] = i;
else
a[i] = a[n], l[++m] = i, r[m] = n;
}
if (n == 1)
std::cout << 0 << '\n';
else
{
std::cout << m << '\n';
for (int i = 1; i <= m; ++i)
std::cout << l[i] << ' ' << r[i] << '\n';
}
}
return 0;
}
|
D1.Zero-One (Easy Version)
题目大意
给了两个长度为$n$的$01$串$a$和$b$，可做以下操作任意次：
第一步：选择两个下标$l$和$r$
第二步：$a_l=1-a_l$，$a_r=1-a_r$(即两个都翻转)
每次操作都是有代价的，如果$r-l=1$，代价为$x$，否则代价为$y$
$Easy\ Version$保证$x\geq y$
输出让$a$变得和$b$一样的最小代价，若变不成一样输出$-1$
解题思路
先把$a$中需要翻转的下标都找出来，记$t$为需要翻转的个数
如果$t$为奇数，那么显然输出$-1$
下面考虑$t$为偶数：
因为保证了$x\geq y$，所以当$t\geq 4$时，肯定是都执行代价为$y$的操作(贪心)(这样的操作是一定存在的)
若$t=2$，如果需要翻转的下标不是连着的，还是执行$y$。如果是连着的，比较$x$和$y\times 2$(随便取第三个下标陪这两个下标执行两次)的大小，执行那个小的操作
具体代码
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
| #include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
#include <set>
#include <vector>
typedef long long LL;
const LL N = 2e5 + 10;
const LL MOD = 1e9 + 7;
LL n, m, q, x, y, t;
std::string a, b;
bool st[N];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int T = 1;
std::cin >> T;
while (T--)
{
t = 0;
std::cin >> n >> x >> y >> a >> b;
bool flag = false;
for (int i = 1; i <= n; ++i)
{
st[i] = a[i - 1] != b[i - 1];
if (st[i] && st[i - 1])
flag = true;
}
for (int i = 1; i <= n; ++i)
t += (LL)st[i];
if (t % 2 == 0)
{
if (flag && t == 2)
std::cout << std::min(y << 1, x) << '\n';
else
std::cout << (t * y >> 1) << '\n';
}
else
std::cout << -1 << '\n';
}
return 0;
}
|
D2.Zero-One (Hard Version)
题目大意
$n$的数据范围从$3000$变成$5000$，$x$和$y$的大小关系不再有限制
别的和$Easy\ Version$一样
解题思路
当$x\lt y$时，不能再贪心了
于是自然想到动态规划
$dp[l][r]$表示处理第$l$个到第$r$个需要翻转的位置的最小代价
具体代码
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
| #include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
#include <set>
#include <vector>
typedef long long LL;
const LL N = 5010;
const LL MOD = 1e9 + 7;
const LL INF = 1e18;
LL n, m, q, x, y, t;
char a[N], b[N];
LL dp[N][N];
std::vector<int> pos;
LL get(int l, int r)
{
if (l + 1 == r)
return std::min(2 * y, x);
else
return std::min(y, x * (r - l));
}
LL dfs(int l, int r)
{
if (l > r)
return 0;
if (dp[l][r] != -1)
return dp[l][r];
LL res = INF;
res = std::min(res, dfs(l + 1, r - 1) + get(pos[l], pos[r]));
res = std::min(res, dfs(l, r - 2) + get(pos[r - 1], pos[r]));
res = std::min(res, dfs(l + 2, r) + get(pos[l], pos[l + 1]));
return dp[l][r] = res;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int T = 1;
std::cin >> T;
while (T--)
{
std::cin >> n >> x >> y >> a + 1 >> b + 1;
pos.clear();
for (int i = 0; i <= n; ++i)
for (int j = 0; j <= n; ++j)
dp[i][j] = -1;
for (int i = 1; i <= n; ++i)
if (a[i] != b[i])
pos.push_back(i);
if (pos.size() & 1)
std::cout << -1 << '\n';
else if (pos.size() == 0)
std::cout << 0 << '\n';
else if (pos.size() == 2)
{
if (pos[1] - pos[0] == 1)
std::cout << std::min(y * 2, x) << '\n';
else
std::cout << std::min(y, x * (pos[1] - pos[0])) << '\n';
}
else
{
if (x >= y)
std::cout << pos.size() / 2 * y << '\n';
else
std::cout << dfs(0, pos.size() - 1) << '\n';
}
}
return 0;
}
|
E.Conveyor
题目大意
有一个网格。每个格子上都有传送带(初始方向均为向右)，每一秒，都会往格子$(0,0)$上放一个箱子。每一秒，对于所有的格子，如果其上面有箱子的话，则会将箱子移动到相应的方向。并且传送带的方向会改变(向右->向下->向右$\cdots$)
现在给出$t,x,y$，问第$t$秒的时候$(x,y)$这个格子上是否有箱子(从第$0$秒开始，且第$0$秒$(0,0)$已经有箱子了)
解题思路
知道做法后没有想到那么简单，属实是思维题了
记$a[i][j]$为t秒下，$(i,j)$这个格子上途径了多少个箱子
对于一个位于$(i,j)$的箱子，会往$(i,j+1)$送去$a[i][j]/2$上取整个箱子，往$(i+1,j)$送去$a[i][j]/2$下取整个箱子
注意对$a[0][0]$赋初值时，
1
| a[0][0] = std::max(t - (x + y) + 1LL, 0LL);
|
这是因为一个箱子到$(x,y)$也需要时间，达不到这些时间的箱子对当前情况是没有用的
具体代码
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
| #include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
#include <set>
#include <vector>
typedef long long LL;
const LL N = 150;
const LL MOD = 1e9 + 7;
const LL INF = 0x7f7f7f7f7f7f7f7f;
LL n, m, q, x, y, t;
LL a[N][N];
int cal(int t, int x, int y)
{
memset(a, 0, sizeof a);
a[0][0] = std::max(t - (x + y) + 1LL, 0LL);
for (int i = 0; i <= x; ++i)
for (int j = 0; j <= y; ++j)
{
a[i + 1][j] += a[i][j] / 2;
a[i][j + 1] += (a[i][j] + 1) / 2;
}
return a[x][y];
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int T = 1;
std::cin >> T;
while (T--)
{
std::cin >> t >> x >> y;
if (cal(t, x, y) > cal(t - 1, x, y))
std::cout << "YES" << '\n';
else
std::cout << "NO" << '\n';
}
return 0;
}
|