A. Destroying Towers
题意
给出一个数组 a ，对于每个 ，使后面的数字小于等于 ，使其最后成为非递增序列，问最后的数组之和
思路
按题意模拟，若 ，则 ，否则，不管，最后求出数组之和
代码
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;
void solve() {
LL n;
cin >> n;
vector<LL> a(n + 1, 0);
for (LL i = 1; i <= n; ++i) {
cin >> a[i];
}
a[0] = INF;
LL ans = 0;
for (LL i = 1; i <= n; ++i) {
if (a[i] > a[i - 1]) {
a[i] = a[i - 1];
}
ans += a[i];
}
cout << ans << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
LL T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
B. Annoying the Ghost
题意
给出两个数组 a 和 b，可以任意交换 a 数组中相邻两个数字，使其任意的 都满足 ，求最小的交换次数
思路
可以贪心的去想，若当前 ，则直接在后面去找第一个满足 的数字，交换 i 和 j
其原理是，因为 b 是严格递增的排列，所以如果当前的 满足 ，若与后面的 交换，若 ，只会让更小的 对应更大的 ，更劣；若 ，会让小对小，大对大，但本来当前的 就满足 ，而 （一定是，否则无法交换， 因为 ），不会更优。而如果当前的 满足 ，只需找到后面第一个满足 的数值交换即可，就会回到上一种讨论，同时满足交换次数最小
或者我们可以感性地想一想，如果当前的 过小，那么他适合当前的 刚好，反正后面的 只会更大，让更小的对应更大的，不优；如果当前的 过大，如果也满足 ，那更好，后面更小的 更容易满足 ，留给其余的 去匹配，但如果不满足，那就让最近的 来满足
代码
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;
void solve() {
LL n;
cin >> n;
vector<LL> a(n + 1, 0), b(n + 1, 0);
for (LL i = 1; i <= n; ++i) {
cin >> a[i];
}
for (LL i = 1; i <= n; ++i) {
cin >> b[i];
}
LL ans = 0;
for (LL i = 1; i <= n; ++i) {
if (a[i] > b[i]) {
LL id = 0;
for (LL j = i + 1; j <= n; ++j) {
if (a[j] <= b[i]) {
id = j;
break;
}
}
if (!id) {
cout << -1 << endl;
return;
}
for (LL j = id; j > i; --j) {
swap(a[j], a[j - 1]);
}
ans += id - i;
}
}
cout << ans << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
LL T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
C. Duck Surplus
题意
给出一个大小为 n 的数组 a ，只有当 ，时，才可以进行操作，将 替换成 ，使其最后成为一个非递减序列，问最后 最小为多少
思路
可以手玩一下样例，我们发现，对于 3 2 1 这组，可以抽象为 a b c (a > b > c)
若从后往前依次交换，则为
a b c
a c b +c
c a + c b +c
c b + c a + b + 2c
若从前往后依次交换，则为
a b c
b a + b c
b c a + b + c
c b + c a + b + c
更广泛一点
对于 a[1] > a[2] > a[3] > ... > a[n]
最优的交换结果为
a[n] a[n] + a[n - 1] a[n] + a[n - 1] + a[n - 2] ... (a[n] + a[n - 1] + ... a[1])
而对于样例 3 1 4 2，分别有两组递减的子序列 3 1 和 4 2，处理顺序为
先分别处理每组内部，再进行组与组之间的操作
3 1 4 2
3 1 2 6
1 4 2 6
1 2 6 6
但如果是 4 1 4 2，先后再前
4 1 4 2
4 1 2 6
1 5 2 6
1 2 7 6
1 2 7 13
先前再后
4 1 4 2
1 5 4 2
1 5 2 6
1 2 7 13
结果一样，都不优
如果不按组与组之间先进行操作，而是按顺序来，只要前一个大于当前这个，就进行操作，否则，不管
4 1 4 2
1 5 4 2
1 4 9 2
1 4 2 11
很优，按这个思路再回去看 3 1 4 2
3 1 4 2
1 4 4 2
1 4 2 6
1 2 6 6
代码
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;
void solve()
{
LL n;
cin >> n;
vector<LL> a(n + 2, 0);
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
}
LL ans = 0;
for (LL i = 1; i <= n; ++i)
{
if (a[i] < a[i - 1])
{
a[i] += a[i - 1];
}
ans = a[i];
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
LL T;
cin >> T;
while (T--)
{
solve();
}
return 0;
}
D. Fullmetal Bitchemist
题意
任意的相邻两个 00 可以替换为 1，相邻的 11 可以替换为 0，若最后能化成一个字符，则定义其为美丽的。给出一个字符串，问其有多少个子串是美丽的
思路
既然 00 -> 1，那不如就把所有的 0 -> 11, 1-> 1，都转换成 1
0 -> 11
00 -> 1111
000 -> 10/01 -> 111
0000 -> 11
1 -> 1
11 -> 0
111 -> 01/10
1111 -> 00 -> 1
11111 -> 001 -> 11 -> 0发现， 1 的个数对 3 取模，余数为零则为不美丽，其余为美丽，但有一种情况除外 01010 以及 10101，即为交替串的情况，余数不为零，但没有相邻的两个可以约掉，所以仍为不美丽。又发现，只要交替串中间出现一次相邻两个相同，可以被约掉，就要重新计数，比如 10101011 约掉后变为 0，相当于从相邻的两个 1 处断开，重新计数，所以，每个 i 前面的交替串的长度是已知的，加上 dp[i][1] 和 dp[i][2] （dp[i][j] 定义为讨论前 i 个字符串，最后约掉结果为 j 的子串个数，该子串为 ）的基础上，减去交替串的贡献即为最终答案
找规律，关于交替串的贡献（前提是余数不为 0 才会有贡献）
1 -> 0
10 -> 0
101 -> 1
1010 -> 1
10101 -> 2
101010 -> 2
1010101 -> 3
10101010 -> 3
x = (len - 1) / 2如果你想多一点，可能会想如果一开始是交替串，但如果中间只要有一次相邻的相同，但约掉之后仍为交替串，比如 10110 -> 1000 -> 101 ，这种子串做出的贡献我们并没有减去，不是吗？
你手玩一下就会发现，只要中间有一次相邻的两个相同，并且余数不为零，就一定是美丽的
就拿 10110 来说，他其实也可以是 10110 -> 1000 -> 110 -> 00 -> 1
再比如 101011 -> 10100 -> 1011 -> 100 -> 0
再比如 1010010 -> 101110 -> 10010 -> 1110 -> 100 -> 11 -> 0
所以只要有相邻的相同，就直接断开，前面的都可以为答案做出贡献，不用减去
代码
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;
void solve() {
LL n;
cin >> n;
vector<vector<LL>> dp(n + 1, vector<LL>(5, 0));
string s;
cin >> s;
s = "#" + s;
LL ans = 0;
LL len = 0;
for (LL i = 1; i <= n; ++i)
{
if (s[i] != s[i - 1]) {
++len;
}
else {
len = 1;
}
LL k;
if (s[i] == '1') {
k = 1;
}
else {
k = 2;
}
dp[i][k] = 1;
for (LL j = 0; j < 3; ++j) {
dp[i][j] += dp[i - 1][(j - k + 3) % 3];
}
ans += dp[i][1] + dp[i][2] - (len - 1) / 2;
}
cout << ans << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
LL T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
E. Permutation Commutation
题意
有两个数组，数组 a 为排列，将数组 b 中的 -1 替换成 1 到 n 中的数字，使其最后也成为一个排列，并且对于任意的 ，都满足 ，问是否存在可行的替换方式，若有，输出字典序最小的替换方式
思路
我感觉我最后还是没有想太清楚，先不管，理解多少写多少
对于一个确定的 ，可以推出 a[b[i]] = b[a[i]]，即可以推出在 b 数组中，下一个数的位置为 a[i] ，值为 a[b[i]] ；根据新确定的 , j = a[i]，可以推出 a[b[a[i]] = b[a[a[i]]] ，（相当于 a[b[j]] = b[a[j]]）又因为 b[a[i]] = a[b[i]]，所以 a[a[b[i]]] = b[a[a[i]]，即再下一个数的位置为 a[a[i]]，值为 a[a[b[i]]]；依次递推下去，位置为 a[a[a[i]]]，值为 a[a[a[b[i]]]] . . . 位置和数值都分别在沿着各自的环依次往下跳。所以，只要 确定，则在 数值对应的 a 数组中所形成的环上每个位置都可以确定。（有个小结论，对于排列来说，一定能够形成环，不会有链的存在）。所以，可以先将能够确定的环确定下来，将最后剩余的环进行一一匹配
我当时一直没想通，我认为只要最后将用掉的数排除掉，在剩下的数中找最小的那个赋值给下标最小，仍未赋值的 不就行了吗，但是，对拍出了反例，我们必须要进行环长相同的配对
eg.
n = 12
idx 1 2 3 4 5 6 7 8 9 10 11 12
a[i] 10 5 3 8 6 2 12 1 4 9 7 11
b[i] -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 2
所形成的环有：
1 10 9 4 8
2 5 6
3
7 12 11
根据 b[12] = 2，可以推出
a[b[12]] = b[a[12]] = 5 -> b[11] = 5;
a[b[11]] = b[a[11]] = 6 -> b[7] = 6;
a[b[7]] = b[a[7]] = 2 -> b[12] = 2;
idx 1 2 3 4 5 6 7 8 9 10 11 12
a[i] 10 5 3 8 6 2 12 1 4 9 7 11
b[i] -1 -1 -1 -1 -1 -1 6 -1 -1 -1 5 2
位置还剩的环为：
1 10 9 4 8
2 5 6
3
数值还剩的环为：
1 10 9 4 8
3
7 12 11
如果按我最初的想法，直接从剩下的选取最小的数填入到第一个 b[i] = -1 中，则 b[2] = 3
a[b[2]] = b[a[2]] = 3 -> b[5] = 3;
a[b[5]] = b[a[5]] = 3 -> b[6] = 3;
a[b[6]] = b[a[6]] = 3 -> b[2] = 3;
这就是没考虑环长所带来的问题，3 所对应的环长为 1, 2 所对应的环长为 3（2， 5， 6），每时每刻位置和数值都在沿着环跳到下一个，若环长不对应，则会出现重复数字
正确的操作应该是 （2， 5， 6） 对应 （7， 12， 11），则 b[2] = 7
a[b[2]] = b[a[2]] = 12 -> b[5] = 12;
a[b[5]] = b[a[5]] = 11 -> b[6] = 11;
a[b[6]] = b[a[6]] = 7 -> b[2] = 7;代码
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & (-x))
#define endl '\n'
typedef long long LL;
#define PLL pair<LL, LL>
const LL MOD = 998244353;
const LL MAX = 1e6 + 100;
const LL INF = 0x3f3f3f3f3f3f3f;
void solve() {
LL n;
cin >> n;
vector<LL> a(n + 1), b(n+ 1);
map<LL, LL> mp;
for (LL i = 1;i <= n; ++i) {
cin >> a[i];
mp[a[i]] = i;
}
for (LL i = 1;i <= n; ++i) {
cin >> b[i];
}
vector<LL> vis(n+ 1, 0);
for (LL i = 1; i <= n; ++i) {
if (vis[i] || b[i] == -1) continue;
LL x = i;
while (!vis[x]) {
LL s = a[b[x]];
if (b[a[x]] != -1 && b[a[x]] != s) {
cout << "NO" << endl;
return;
}
b[a[x]] = s;
vis[x] = 1;
x = a[x];
}
}
vector<LL> cnt(n + 1, 0);
for (LL i = 1; i <= n; ++i) {
if (b[i] == -1)
continue;
cnt[b[i]]++;
if (cnt[b[i]] > 1) {
cout << "NO" << endl;
return;
}
}
vector<int> vis1(n + 1, 0), vis2(n + 1, 0);
vector<vector<int>> c1(n + 1), c2(n + 1);
for (int i = 1; i <= n; ++i) {
if (b[i] != -1 || vis1[i]) continue;
int x = i, len = 0;
while (!vis1[x]) {
++len;
vis1[x] = 1;
x = a[x];
}
c1[len].push_back(i);
}
for (int i = 1; i <= n; ++i) {
if (cnt[i] || vis2[i])
continue;
int x = i, len = 0;
while (!vis2[x]) {
++len;
vis2[x] = 1;
x = a[x];
}
c2[len].push_back(i);
}
for (int len = 1; len <= n; ++len) {
for (int i = 0; i < c1[len].size(); ++i) {
int x = c1[len][i], y = c2[len][i];
// cout << len << " " << x << " " << y << endl;
while (b[x] == -1) {
b[x] = y;
x = a[x];
y = a[y];
}
}
}
cout << "YES" << endl;
for (LL i = 1; i <= n; ++i) {
cout << b[i] << " ";
}
cout << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
LL T;
cin >> T;
while (T--) {
solve();
}
return 0;
}