ICPC2021 Nanjing R 签到+铜牌题
补题链接：https://codeforces.com/gym/103470或https://www.luogu.com.cn/contest/143839
A.Oops, It’s Yesterday Twice More
n*m的矩阵里面每个格子都有一个袋鼠你可以通过在键盘上按下U、D、L、R按钮来控制袋鼠。袋鼠将根据您按下的按钮同时移动。具体而言，对于位于第i行和第j列的单元格，用（i，j）表示：
- 按钮U：如果i > 1，则它将移动到（i - 1，j）。否则，它将保持在相同的网格中。
- 按钮D：如果i < n，则它将移动到（i + 1，j）。否则，它将保持在相同的网格中。
- 按钮L：如果j > 1，则它将移动到（i，j - 1）。否则，它将保持在相同的网格中。
- 按钮R：如果j < n，则它将移动到（i，j + 1）。否则，它将保持在相同的网格中。
您需要构建一个仅由字符‘U’、‘D’、‘L’和‘R’组成的操作序列。应用该序列后，您必须确保每只袋鼠都聚集在特定的单元格（a，b）。操作序列的长度不能超过3(n - 1)。
签到题，想到可以在等于2(n-1)的步数将袋鼠全部聚集到四个角落中的任意一个角落，那么问题就转换成在n-1步数之内移到（a,b）点，只要贪心的选择到（a,b）点曼哈顿距离最小的那个角落就一定能保证在n-1步之内到达，可以假设最坏情况（中心点）来验证一下
M.Windblume Festival
给一个长度为n环形整数序列a,每次操作可以选择两个相邻的数，左边的数减去右边的数，删除右边的数，最后会剩下一个元素，要求最大化这个元素
有正有负或者有0的情况下一定无损，只需要对绝对值求和即可，如果全是正或者全是负数那么就要考虑将亏损降到最小，因为最后必定会剩下两个数，左边的数用于减去右边的数，对于全是正数而言，剩的一定是左边一个正数和右边一个负数，那么原本右边位置的数（设为k）就是亏损的数，要最小化亏损就需要右边原来的数最小，这样在最后就亏损了2k;对于负数而言也是类似（其实正负并没有关系），找出绝对值最小的负数（k），亏损的就是2abs（k））,注意特判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
using namespace std;
int n, a[N];
void solve() {
int sum = 0, min1 = 1e18, max1 = -1e18;
cin >> n;
bool flagP = false, flag0 = false, flagN = false;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
if (min1 > a[i]) min1 = a[i];
if (max1 < a[i]) max1 = a[i];
sum += abs(a[i]);
if (a[i] > 0)flagP = true;
if (a[i] == 0) flag0 = true;
if (a[i] < 0) flagN = true;
}
// cout<<min1<<' '<<min2<<' '<<max1<<' '<<max2<<endl;
if(n == 1) return cout<<a[1]<<endl,void();
if ((flagN && flagP) || flag0) {
cout << sum << endl;
} else if (flagP) {
cout << sum - abs(min1)*2 << endl;
} else {
cout << sum - abs(max1)*2 << endl;
}
}
signed main() {
cin.tie(nullptr), cout.tie(nullptr);
ios::sync_with_stdio(false);
int T = 1;
cin >> T;
while (T--) solve();
return 0;
}
C.Klee in Solitary Confinement
给定一个整数序列和一个可添加的数字，最多可以选择一个区间执行一次添加操作（可以不执行），求在执行或不执行操作的情况下，整个序列中众数的最大出现次数。
对于一个数a来说，他只能影响到a的个数以及a+k的个数，所以先记录下不执行操作情况下的最大众数，然后对于每个a+k，都需要找一个区间，对于一个区间+k那么原先的a的数量就减去一个，那么可以做一次从前往后的遍历，用一个数组cnt2记录下减去每一个位置上的数（a），再把a+k加上一，如果cnt2[a]变成了负数，那么就将它变成0，就相当于这前面的数都不进行+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
using namespace std;
int a[N], n, k, ans;
int cnt1[N], cnt2[N];
void solve() {
cin >> n >> k;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
a[i] += 2000000;
++cnt1[a[i]];
}
for (int i = 1; i <= n; ++i) {
--cnt2[a[i]];
++cnt2[a[i] + k];
cnt2[a[i]] = max(cnt2[a[i]], 0);
ans = max(ans, cnt2[a[i] + k] + cnt1[a[i] + k]);
}
cout << ans << endl;
}
signed main() {
cin.tie(nullptr), cout.tie(nullptr);
ios::sync_with_stdio(false);
int T = 1;
// cin>>T;
while (T--) solve();
return 0;
}
H.Crystalfly
在一棵树状结构中，每个顶点上有一定的权值，从1号点开始移动，到达一个顶点时，加上该点的权值。但是当移动到一个顶点时，它的相邻节点，相邻顶点上的权值会在t时间（1≤t≤3）过后变成0。求最大的权值之和。
很明显的树形dp。由于t很小，可以想象一下如果走到一个节点他的相邻节点就变成0那么就变成了最大独立集问题，可以发现当t≤2时其实是一样的，再考虑到只有一个节点p的儿子结点s1中t==3的节点才可以先去找另一个结点s2获取s2的权值并且不选他的儿子结点然后再返回来取s1结点和以它为根的子树的最大权值。
和最大独立集问题类似。dp[x][1] 记录子树 x 得到的最大值;dp[x][0]记录不取x的孩子所得到的最大值，dp[x][0] += dp[y][1] - a[y]，y属于x的儿子，
首先先求出dp[x][1] = max(dp[x][1],dp[x][0]+a[y]),然后若有一个儿子结点y的t[y] = 3,可以先走到另一个孩子节点y1去取再返回y取,这样就y1的孩子的权值就变成了0，即dp[y1][0],这种情况下的值就变成了不取x节点的最大值加上取这个y这个点的权值加上dp[y1][0]再减去多算的公共部分（dp[y1][1]-a[y1]），即dp[x][1]=max(dp[x][1],dp[x][0]+a[y]+dp[z][0]-(dp[z][1]-a[z]))
那么需要记录dp[z][0]-(dp[z][1]-a[z])的最大值，如果z==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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
using namespace std;
int n, ans, dp[N][2];
int a[N], t[N];
vector<int> edge[N];
void dfs(int u, int par) {
// dp[u][0] = a[u];
// if(t[u] == 2) dp[]
// int maxn11 = 0, maxn12 = 0, maxn21 = 0, maxn22 = 0;
dp[u][0] = a[u];
int pos1 = 0;
int maxn1 = -1, maxn2 = -1;
for (auto v : edge[u]) {
if (v == par)continue;
dfs(v, u);
dp[u][0] += dp[v][1] - a[v];
int temp = dp[v][0] - (dp[v][1] - a[v]);
if (temp > maxn1) maxn2 = maxn1, maxn1 = temp, pos1 = v;
else if (maxn2 < temp) maxn2 = temp;
}
dp[u][1] = dp[u][0];
for (auto v : edge[u]) {
if (v == par) continue;
dp[u][1] = max(dp[u][1], dp[u][0] + a[v]);
if (t[v] == 3) {
if (pos1 ^ v)dp[u][1] = max(dp[u][1], dp[u][0] + a[v] + maxn1);
else dp[u][1] = max(dp[u][1], dp[u][0] + a[v] + maxn2);
}
}
}
void solve() {
ans = 0;
cin >> n;
for (int i = 1; i <= n; ++i) edge[i].clear(), dp[i][1] = dp[i][0] = 0;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= n; ++i) cin >> t[i];
for (int i = 1, u, v; i < n; ++i) {
cin >> u >> v;
edge[u].push_back(v), edge[v].push_back(u);
}
dfs(1, 0);
cout << dp[1][1] << endl;
}
signed main() {
cin.tie(nullptr), cout.tie(nullptr);
ios::sync_with_stdio(false);
int T = 1;
cin >> T;
while (T--) solve();
return 0;
}
D.Paimon Sorting
给出一个排序算法（用伪代码表示）：1
2
3
4
5
6// 排序算法
SORT(A)
for i from 1 to n // n 是序列 A 的元素个数
for j from 1 to n
if a[i] < a[j] // a[i] 是序列 A 的第 i 个元素
Swap a[i] and a[j]
请你算出对于一个序列 $A=a_1,a_2,\cdots,a_n$ 的所有前缀 $A_k=a_1,a_2,\cdots,a_k$($1\le k\le n$)， $\operatorname{SORT}(A_k)$中的交换（Swap）操作将会被执行几次。
感觉比第四道好想一些。
因为程序都给你了，打表找规律就好了。
打表代码：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
//#define int long long
using namespace std;
typedef pair<int, int> PII;
int a[N], b[N], n;
int Sort(int x) {
int cnt = 0;
for (int i = 1; i <= x; ++i) b[i] = a[i];
for (int i = 1; i <= x; ++i)
for (int j = 1; j <= x; ++j) {
if (b[i] < b[j]) {
swap(b[i], b[j]);
cnt++;
}
}
return cnt;
}
void solve() {
// cin >> n;
// for (int i = 1; i <= n; ++i) cin >> a[i];
n = random(4, 6);
cout<<n<<endl;
for (int i = 1, t; i <= n; ++i) t = random(1,n),a[i] = t;
for (int i = 1; i <= n; ++i) cout << a[i] << ' ';
cout << endl;
for (int i = 1; i <= n; ++i) cout << Sort(i) << ' ';
cout << endl;
}
signed main() {
cin.tie(nullptr), cout.tie(nullptr);
ios::sync_with_stdio(false);
int T = 1;
cin >> T;
while (T--)
solve();
return 0;
}
规律倒不是很好找，具体来说：
设 maxn 为前 n−1 个数中的最大值
首先当 a[i] < maxn , ans += 前 n−1 个数中, 比当前数小的数的个数
当 a[i] = maxn时，答案不变
当 a[i] > maxn ans += 2 + maxn第二次出现后的数的个数
所以可以用树状数组等查询前面比当前数小的数的个数，ac代码：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
using namespace std;
struct BIT {
int n{};
int a[N]{}, tr[N]{};
void add(int u, int x) {
for (int i = u; i <= n; i += lowbit(i)) tr[i] += x;
}
int query(int u) {
int res = 0;
for (int i = u; i > 0; i -= lowbit(i)) res += tr[i];
return res;
}
};
int n, a[N];
bitset<N> st;
void solve() {
cin >> n;
st.reset();
BIT bit;
bit.n = n;
bool flag = false;
for (int i = 1; i <= n; ++i) cin >> a[i];
int ans = 0, cnt = 0, maxn;
bit.add(a[1], 1);
maxn = a[1];
st[a[1]] = true;
cout << ans;
for (int i = 2; i <= n; ++i) {
if (a[i] > maxn) {
maxn = a[i];
// int k = !st[a[i]];
// ans += 2 + st.count()-k;
ans += 2 + cnt;
flag = false;
cnt = 0;
} else if (a[i] == maxn) {
flag = true;
cnt += flag;
} else {
ans += bit.query(maxn) - bit.query(a[i]);
cnt += flag;
}
cout << ' '<< ans ;
if (!st[a[i]]) st[a[i]] = true, bit.add(a[i], 1);
}
cout << endl;
}
signed main() {
// freopen("input.txt", "r", stdin);
// freopen("my.txt", "w", stdout);
cin.tie(nullptr), cout.tie(nullptr);
ios::sync_with_stdio(false);
int T = 1;
cin >> T;
while (T--) solve();
return 0;
}
/*
hack:
input
1
5
1 2 2 1 3
stand:
0 2 2 3 7
input
1
8
3 3 1 7 8 3 6 1
stand:
0 0 1 5 7 9 11 15
input
1
7
4 6 6 4 2 7 3
stand
0 2 2 3 5 10 13
input
7
6 2 6 6 2 7 6
stand
0 1 1 1 2 7 8
*/
如果不重复那么规律还是比较好找的