第 46 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（南京），签到题5题
文章目录
- A.Oops, It's Yesterday Twice More
- M.Windblume Festival
- C.Klee in Solitary Confinement
- H.Crystalfly
- D.Paimon Sorting
补题链接：https://codeforces.com/gym/103470
A.Oops, It’s Yesterday Twice More
Oops, It’s Yesterday Twice More
Input file: standard input
Output file: standard output
Time limit: 1 second
Memory limit: 256 megabytes
After the great success in 2018, 2019, and 2020, Nanjing University of Aeronautics and Astronautics
(NUAA) will host the International Collegiate Programming Contest (ICPC) Nanjing regional for the
fourth time.
Team Power of Two and team Three Hold Two won the champion for Tsinghua University in 2018
and 2019. In 2020, team Inverted Cross from Peking University won the champion. In 2021, there are
around 700 teams including the defending champion participating in the contest. We are so excited
to see who will win this year!
Although we can’t gather in Nanjing this time due to the pandemic, we should still be grateful for the
hard work done by all staff and volunteers for this contest. Thank you all for your great contribution to
this contest!
In the 2018 contest, problem K, Kangaroo Puzzle, requires the contestants to construct an operation
sequence for the game:
The puzzle is a grid with n rows and m columns (1 ≤ n, m ≤ 20) and there are some (at least 2)
kangaroos standing in the puzzle. The player’s goal is to control them to get together. There are some
walls in some cells and the kangaroos cannot enter the cells with walls. The other cells are empty. The
kangaroos can move from an empty cell to an adjacent empty cell in four directions: up, down, left, and
right.
There is exactly one kangaroo in every empty cell in the beginning and the player can control the
kangaroos by pressing the button U, D, L, R on the keyboard. The kangaroos will move simultaneously
according to the button you press.
The contestant needs to construct an operating sequence of at most 5 × 104
steps consisting of U, D, L,
R only to achieve the goal.
In the 2020 contest, problem A, Ah, It’s Yesterday Once More, requires the contestants to construct
an input map to hack the following code of the problem described before:
#include <b i t s / s t d c++.h>
using namespace s t d ;
s t r i n g s = “UDLR” ;
int main ( )
{
s rand ( time (NULL ) ) ;
for ( int i = 1 ; i <= 50000; i++) pu tcha r ( s [ rand ( ) % 4 ] ) ;
return 0 ;
}
Now in the 2021 contest, Paimon prepares another version of the problem for you. You are given a grid
with n rows and n columns (2 ≤ n ≤ 500). All cells are empty and there is one kangaroo standing in each
cell.
Similarly, you can control the kangaroos by pressing the button U, D, L, R on the keyboard. The kangaroos
will move simultaneously according to the button you press. Specifically, for any kangaroo located in the
cell on the i-th row and the j-th column, indicated by (i, j):
- Button U: it will move to (i − 1, j) if i > 1. Otherwise, it will stay in the same grid.
Page 1 of 2 - Button D: it will move to (i + 1, j) if i < n. Otherwise, it will stay in the same grid.
- Button L: it will move to (i, j − 1) if j > 1. Otherwise, it will stay in the same grid.
- Button R: it will move to (i, j + 1) if j < n. Otherwise, it will stay in the same grid.
You need to construct an operating sequence consisting only of characters ‘U’, ‘D’, ‘L’, and ‘R’. After
applying it, you must make sure every kangaroo will gather at the specific cell (a, b). The length of the
operating sequence cannot exceed 3(n − 1).
Input
There is only one test case in each test file.
The first and only line of the input contains three integers n, a, b (2 ≤ n ≤ 500, 1 ≤ a, b ≤ n) indicating
the size of the grid and the target cell.
Output
Output a string consisting only of characters ‘U’, ‘D’, ‘L’ and ‘R’ in one line. And its length mustn’t
exceed 3(n − 1). It can be proved that the answer always exists.
Examples
standard input standard output
3 3 3 RRDD
4 3 2 DLDLDLUR
题目
- 给出一个n x n的网格，初始每个位置都有一个袋鼠。现在要通过UDLR控制上下左右移动（每次控制会让所有的袋鼠都对应的移动一个格子直到撞墙后不动）。
- 求构造一个移动方案，让所有的袋鼠都聚集到给出的（a,b）点上。
思路：
- 判断一下离四个顶点中的哪个角落比较近，先让所有的袋鼠走到角落。
- 再一起移动到（a,b）即可。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1010;
int main(){
int n, a, b; cin>>n>>a>>b;
int up = 0, dy = 0; //往上
int le = 0, dx = 0; //往左
if(a <= n/2){
up = 1; dy = a-1;
for(int i = 1; i < n; i++)cout<<"U";
}else{
up = 0; dy = n-a;
for(int i = 1; i < n; i++)cout<<"D";
}
if(b <= n/2){
le = 1; dx = b-1;
for(int i = 1; i < n; i++)cout<<"L";
}else{
le = 0; dx = n-b;
for(int i = 1; i < n; i++)cout<<"R";
}
if(up==1)for(int i = 1; i <= dy; i++)cout<<"D";
else for(int i = 1; i <= dy; i++)cout<<"U";
if(le==1)for(int i = 1; i <= dx; i++)cout<<"R";
else for(int i = 1; i <= dx; i++)cout<<"L";
return 0;
}
M.Windblume Festival
M. Windblume Festival
time limit per test3 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
The Windblume Festival in Mondstadt is coming! People are preparing windblumes for Barbatos and for those they love and adore. The Windblume Festival is also an opportunity to improve the relationships people have.
Source: Genshin Impact Official
During the festival, a famous game will be played every year, invented by Jean, the Acting Grand Master of the Knights of Favonius. In the game, n players numbered from 1 to n stand in a circle, each holding an integer with them. Each turn, one player will be removed. The game will end when there is only one player left.
For each turn, let k be the number of players remaining and ai be the integer player i holds. Two adjacent players, x and (xmodk+1) are selected and player (xmodk+1) is removed from the game. Player x’s integer will then change from ax to (ax−axmodk+1). Player y in this turn will become player (y−1) in the next turn for all x<y≤k, though the integer they hold will not change.
Jean wants to know the maximum possible integer held by the last remaining player in the game by selecting the players in each round optimally.
Input
There are multiple test cases. The first line of the input contains one integer T indicating the number of test cases. For each test case:
The first line contains one integer n (1≤n≤106) indicating the initial number of players.
The next line contains n integers ai (−109≤ai≤109) where ai is the integer held by player i at the beginning.
It is guaranteed that the sum of n of all test cases will not exceed 106.
Output
For each test case output one line containing one integer indicating the maximum possible integer.
Example
inputCopy
5
4
1 -3 2 -4
11
91 66 73 71 32 83 72 79 84 33 93
12
91 66 73 71 32 83 72 79 84 33 33 93
13
91 66 73 71 32 83 72 79 84 33 33 33 93
1
0
outputCopy
10
713
746
779
0
Note
For the first sample test case follow the strategy shown below, where the underlined integers are the integers held by the players selected in each turn.
{1–,−3,2,−4–––} (select x=4) → {−3,2,−5–––––} (select x=2) → {−3,7–––––} (select x=2) → {10}.
题目
- 给出n个数字，排成圆环。
- 每次操作可以选择一个数字，让他减去他的下一个数的值，并去掉他的下一个数。
- 问最后剩下的数字的最大值可能是多少。
思路：
- 因为n是1e6，且有多组数据，且状态和转移都较复杂，所以dp是不太可行的。需要一个线性的复杂度，所以盲猜可能是个结论题。
- 对样例找一下规律发现，数字有正有负时，最后结果就是把所有的数加起来取个绝对值（因为必定可以构造出一组方案让所有的负数正数先累加起来，然后让正-负合起来）
- 如果全正全负的时候，显然最后合并要牺牲掉某个值，那么一定是牺牲掉最小的最优，所以全部绝对值加起来减去2倍的最小绝对值即可（n=1时需要特判）。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
typedef long long LL;
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T; cin>>T;
while(T--){
LL n; cin>>n;
LL t;
if(n==1){
cin>>t;
cout<<t<<"\n";
continue;
}
LL x = 0, y = 0, sum = 0, mi = 1e18+10;
for(int i = 1; i <= n; i++){
cin>>t;
if(t>0)x = 1;
if(t<0)y = 1;
sum += abs(t);
mi = min(mi, abs(t));
}
if(x+y==2){
cout<<sum<<"\n";
}else{
cout<<sum-2*mi<<"\n";
}
}
return 0;
}
C.Klee in Solitary Confinement
C. Klee in Solitary Confinement
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
Since the traveler comes, People in Monstadt suddenly raise great interest in computer programming and algorithms, including Klee, the Spark Knight of the Knights of Favonius.
Source: Genshin Impact Official
Being sent to solitary confinement by Jean again, Klee decides to spend time learning the famous Mo’s algorithm, which can compute with a time complexity of O(n1.5) for some range query problem without modifications.
To check whether Klee has truly mastered the algorithm (or in fact making another bombs secretly), Jean gives her a problem of an integer sequence a1,a2,⋯,an along with some queries [li,ri] requiring her to find the mode number in the contiguous subsequence ali,ali+1,⋯,ari. The mode number is the most common number (that is to say, the number which appears the maximum number of times) in the subsequence.
With the help of Mo’s algorithm, Klee solves that problem without effort, but another problem comes into her mind. Given an integer sequence a1,a2,⋯,an of length n and an integer k, you can perform the following operation at most once: Choose two integers l and r such that 1≤l≤r≤n and add k to every ai where l≤i≤r. Note that it is OK not to perform this operation. Compute the maximum occurrence of the mode number of the whole sequence if you choose to perform (or not perform) the operation optimally.
Input
There is only one test case in each test file.
The first line of the input contains two integers n and k (1≤n≤106, −106≤k≤106) indicating the length of the sequence and the additive number.
The second line of the input contains n integers a1,a2,⋯,an (−106≤ai≤106) indicating the original sequence.
Output
Output one line containing one integer indicating the maximum occurrence of the mode number of the whole sequence after performing (or not performing) the operation.
Examples
inputCopy
5 2
2 2 4 4 4
outputCopy
5
inputCopy
7 1
3 2 3 2 2 2 3
outputCopy
6
inputCopy
7 1
2 3 2 3 2 3 3
outputCopy
5
inputCopy
9 -100
-1 -2 1 2 -1 -2 1 -2 1
outputCopy
3
Note
For the first sample test case, choose l=1 and r=2 and we’ll result in the sequence {4,4,4,4,4}. The mode number is obviously 4 which appears 5 times.
For the second sample test case, choose l=4 and r=6 and we’ll result in the sequence {3,2,3,3,3,3,3}. The mode number is 3 which appears 6 times.
For the fourth sample test case, choose not to perform the operation. The mode number is 1 and −2 which both appear 3 times.
题目
- 给出一个数组，我们可以选择一段区间加上 k (或者不加)。
- 求出现次数最多的数出现了几次。
思路：
- 预处理出每个数的个数，若k为0，直接输出最大的个数。
- 考虑修改给一些数+k让其他数的出现次数更多，如果对数x进行+k，那么x的贡献-1，x+k的贡献+1，那么答案 = max{原本次数+贡献次数}的最大值即可。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 4e6+10;
const int maxv = 2e6;
int a[maxn], cnt[maxn], add[maxn];
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n, k; cin>>n>>k;
int mx = 0;
for(int i = 1; i <= n; i++){
cin>>a[i]; a[i] += maxv;
cnt[a[i]]++; mx = max(mx, cnt[a[i]]);
}
if(k==0){ cout<<mx<<'\n'; return 0;}
for(int i = 1; i <= n; i++){
add[a[i]] = max(0, add[a[i]]-1);
add[a[i]+k]++;
mx = max(mx, cnt[a[i]+k]+add[a[i]+k]);
}
cout<<mx<<"\n";
return 0;
}
H.Crystalfly
H. Crystalfly
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Paimon is catching crystalflies on a tree, which are a special kind of butterflies in Teyvat. A tree is a connected graph consisting of n vertices and (n−1) undirected edges.
Pixiv ID: 93964680
There are initially ai crystalflies on the i-th vertex. When Paimon reaches a vertex, she can catch all the remaining crystalflies on the vertex immediately. However, the crystalflies are timid. When Paimon reaches a vertex, all the crystalflies on the adjacent vertices will be disturbed. For the i-th vertex, if the crystalflies on the vertex are disturbed for the first time at the beginning of the t′-th second, they will disappear at the end of the (t′+ti)-th second.
At the beginning of the 0-th second, Paimon reaches vertex 1 and stays there before the beginning of the 1-st second. Then at the beginning of each following second, she can choose one of the two operations:
Move to one of the adjacent vertices of her current vertex and stay there before the beginning of the next second (if the crystalflies in the destination will disappear at the end of that second she can still catch them).
Stay still in her current vertex before the beginning of the next second.
Calculate the maximum number of crystalflies Paimon can catch in 1010101010 seconds.
Input
There are multiple test cases. The first line of the input contains an integer T indicating the number of test cases. For each test case:
The first line contains an integer n (1≤n≤105) indicating the number of vertices.
The second line contains n integers a1,a2,⋯,an (1≤ai≤109) where ai is the number of crystalflies on the i-th vertex.
The third line contains n integers t1,t2,⋯,tn (1≤ti≤3) where ti is the time before the crystalflies on the i-th vertex disappear after disturbed.
For the next (n−1) lines, the i-th line contains two integers ui and vi (1≤ui,vi≤n) indicating an edge connecting vertices ui and vi in the tree.
It’s guaranteed that the sum of n of all the test cases will not exceed 106.
Output
For each test case output one line containing one integer indicating the maximum number of crystalflies Paimon can catch.
Example
inputCopy
2
5
1 10 100 1000 10000
1 2 1 1 1
1 2
1 3
2 4
2 5
5
1 10 100 1000 10000
1 3 1 1 1
1 2
1 3
2 4
2 5
outputCopy
10101
10111
Note
For the first sample test case, follow the strategy below.
During the 0-th second
Paimon arrives at vertex 1;
Paimon catches 1 crystalfly;
Crystalflies in vertices 2 and 3 are disturbed.
During the 1-st second
Paimon arrives at vertex 3;
Paimon catches 100 crystalflies.
During the 2-nd second
Paimon arrives at vertex 1;
Crystalflies in vertex 2 disappears.
During the 3-rd second
Paimon arrives at vertex 2;
Crystalflies in vertices 4 and 5 are disturbed.
During the 4-th second
Paimon arrives at vertex 5;
Paimon catches 10000 crystalflies;
Crystalflies in vertex 4 disappears.
For the second sample test case, the optimal strategy is the same with the first sample test case. Crystalflies in vertex 2 are scheduled to disappear at the end of the 3-rd (instead of the 2-nd) second, allowing Paimon to catch them.
题目
- 给出一个n个点（1e5），以1位根的树。每个点有价值为a[i]的蝴蝶。
- 你从点1出发抓蝴蝶，每一秒可以移动到相邻的一个点。当你第一次进入某个点后，其相邻点的蝴蝶就会在t[v]（1-3）秒后消失。
- 问你最多能抓到多少价值的蝴蝶。
思路：
- 当我们初次到达某个节点 u 时，它的所有儿子会被激活，由于 t[i]<=3 ，所以我们的决策只有两种。
一种是进入某个儿子 v 后继续向下，这样 x 的所有其它儿子的蝴蝶都无法被获取。
另一种是进入某个儿子 v 获取 av 后立即回到 x，然后进入另一个儿子 w 并获得 aw ，这要求 tw=3。 - 我们令 f[u] 表示节点 u 在我们进入之前所有蝴蝶都已经消失，同时它的孩子在我们进入 u 之前都未被激活，这棵子树的最优答案，那我们要求的最终答案就是f[1]+a[1] 。
- 我们令 G[u] 表示 u 的儿子集合， sum[u] 表示 u 的所有儿子 v 的 f[v] 值之和。考虑两种决策对应的转移.
第一种决策：f[u] = sum[u]+max{a[v]}, 从v走下去
第二种决策：f[u] = sum[u]-f[v]+sum[v]+a[v]+max{a[v0], v0!=v, v==3}， 拿一个除了v最大的, 再从v走下去,v需要==3
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 2e5+10;
vector<int>G[maxn];
LL a[maxn], t[maxn];
//f[x]:x的蝴蝶已经消失,儿子未被激活的最优答案. sum[x]=sum{f[y]}
LL f[maxn], sum[maxn];
void dfs(int x, int fa){
multiset<LL>se;
//1.进入y后一直向下, x所有儿子都不要了, 拿一个max{a[y]}, f[x] = sum[x]+mx{a[y]}
LL mx = 0;
for(int y : G[x]){
if(y==fa)continue;
dfs(y, x);
sum[x] += f[y];
mx = max(mx, a[y]);
if(t[y]==3)se.insert(a[y]);
}
f[x] = sum[x] + mx;
//2.对于t[y]==3,先拿一个其他的（除了他最大的），再从这里走下去
se.insert(-1e18);
for(int y: G[x]){
if(y==fa)continue;
if(t[y]==3)se.erase(se.find(a[y]));
f[x] = max(f[x], sum[x]+*se.rbegin()-f[y]+sum[y]+a[y]);
if(t[y]==3)se.insert(a[y]);
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T; cin>>T;
while(T--){
int n; cin>>n;
for(int i = 1; i <= n; i++)cin>>a[i];
for(int i = 1; i <= n; i++){
cin>>t[i];
sum[i] = f[i] = 0; G[i].clear();
}
for(int i = 1; i < n; i++){
int u, v; cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1, -1);
cout<<f[1]+a[1]<<"\n";
}
return 0;
}
D.Paimon Sorting
Paimon Sorting
Input file: standard input
Output file: standard output
Time limit: 1 second
Memory limit: 256 megabytes
Paimon just invents a new sorting algorithm which looks much like bubble sort, with a few differences. It
accepts a 1-indexed sequence A of length n and sorts it. Its pseudo-code is shown below.
Algorithm 1 The Sorting Algorithm
1: function Sort(A)
2: for i ← 1 to n do . n is the number of elements in A
3: for j ← 1 to n do
4: if ai < aj then . ai
is the i-th element in A
5: Swap ai and aj
6: end if
7: end for
8: end for
9: end function
If you don’t believe this piece of algorithm can sort a sequence it will also be your task to prove it. Anyway
here comes the question:
Given an integer sequence A = a1, a2, · · · , an of length n, for each of its prefix Ak of length k (that is, for
each 1 ≤ k ≤ n, consider the subsequence Ak = a1, a2, · · · , ak), count the number of swaps performed if
we call SORT(Ak).
Input
There are multiple test cases. The first line of the input contains an integer T indicating the number of
test cases. For each test case:
The first line contains an integer n (1 ≤ n ≤ 105
) indicating the length of the sequence.
The second line contains n integers a1, a2, · · · , an (1 ≤ ai ≤ n) indicating the given sequence.
It’s guaranteed that the sum of n of all test cases will not exceed 106
.
Output
For each test case output one line containing n integers s1, s2, · · · , sn separated by a space, where si
is
the number of swaps performed if we call SORT(Ai).
Please, DO NOT output extra spaces at the end of each line or your solution may be considered incorrect!
Example
standard input standard output
3
5
2 3 2 1 5
3
1 2 3
1
1
0 2 3 5 7
0 2 4
0
Page 1 of 1
题目
- T组数据，每次给出一个长度为n（1e5）的序列。
- 对于此序列的长度为1-n的前缀使用（题目给出的排序代码）进行排序，求分别需要多少次交换。
思路：
- 先考虑序列所有元素各不相同的情况。
可以用树状数组维护，前面比当前元素大的数的个数（去重后）。
- 接下来考虑存在相同元素的情况。
相等的元素是不会产生贡献的，因此vis去重特判掉即可。
若当前的非特殊元素a[i]等于上个特殊元素， 那么上个特殊元素会对该元素产生1的贡献，需要特判。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL N = 1e5+10;
LL a[N], n;
LL b[N], vis[N];
void add(LL x){while(x<=n){ b[x]++; x += x&(-x); } }
LL query(LL x){ LL res=0; while(x){ res+=b[x]; x-=x&(-x); } return res;}
int main(){
ios::sync_with_stdio(0), cin.tie(0),cout.tie(0);
LL T; cin>>T;
while(T--){
cin>>n;
for(LL i = 1; i <= n; i++){
cin>>a[i];
b[i] = vis[i] = 0;
}
cout<<0;
vis[a[1]] = 1; add(a[1]);
LL ok = 0, cnt = 0, ans = 0;
for(LL i = 2; i <= n; i++){
if(!vis[a[i]])vis[a[i]] = 1, add(a[i]);
if(a[i]==a[1])ok = 1;
cnt += ok-(ok?a[i]>a[1]:0);
if(a[i]>a[1]) ans += 1+cnt, swap(a[1],a[i]), cnt=ok=0;
ans += query(a[1])-query(a[i]);
cout<<" "<<ans;
}
cout<<"\n";
}
return 0;
}