比赛链接 / 官方题解链接
A. Most Unstable Array
Solution
如果 $n=1$，那么答案只能是 $0$.
如果 $n=2$，那么最优构造是 $[0,m]$，答案是 $m$.
如果 $n>2$，那么最优构造是 $[0,m,0,\cdots,0]$，答案是 $2m$.
Code
>folded1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
int T, n, m;
int main(){
for(read(T); T; T--){
read(n, m);
if(n == 1) puts("0");
else if(n == 2) printf("%d\n", m);
else printf("%d\n", m << 1);
}
return 0;
}
|
B. Two Arrays And Swaps
Solution
$a$ 从小到大排序，$b$ 从大到小排序，然后能交换就交换。
Code
>folded1
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;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
const int N = 35;
int T, n, k, a[N], b[N];
int main(){
for(read(T); T; T--){
read(n, k);
int sum = 0;
for(int i = 1; i <= n; i++) read(a[i]), sum += a[i];
for(int i = 1; i <= n; i++) read(b[i]);
sort(a+1, a+n+1);
sort(b+1, b+n+1);
reverse(b+1, b+n+1);
for(int i = 1; i <= k; i++){
if(a[i] >= b[i]) break;
sum += b[i] - a[i];
}
printf("%d\n", sum);
}
return 0;
}
|
C. Board Moves
Solution
推一波公式就可以了：$ans=8\times\frac{\left\lfloor n/2\right\rfloor\cdot\left(\left\lfloor n/2\right\rfloor+1\right)\cdot\left(2\left\lfloor n/2\right\rfloor+1\right)}{6}$.
Code
>folded1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
int T, n;
int main(){
for(read(T); T; T--){
read(n);
LL k = n / 2;
printf("%lld\n", k * (k + 1) * (2 * k + 1) / 6 * 8);
}
return 0;
}
|
D. Constructing the Array
Solution
递归填这个数列，把填的位置和填之前的 $0$ 的块长记录下来，排序后就是 $1\sim n$ 的填写顺序。
Code
>folded1
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
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
const int N = 200005;
int T, n;
struct Node{
int pos, len;
bool operator < (const Node &A) const{
return len == A.len ? pos > A.pos : len < A.len;
}
};
priority_queue<Node> q;
void solve(int l, int r){
if(l > r) return;
q.push((Node){(l + r) >> 1, r - l + 1});
solve(l, (l + r) / 2 - 1);
solve((l + r) / 2 + 1, r);
}
int main(){
for(read(T); T; T--){
read(n);
solve(1, n);
vi ans(n+5);
int now = 0;
while(!q.empty()){
ans[q.top().pos] = ++now;
q.pop();
}
for(int i = 1; i <= n; i++)
printf("%d ", ans[i]);
puts("");
}
return 0;
}
|
E. K-periodic Garland
Solution
把原序列按照下标模 $k$ 的余数分组，那么一个合法序列的所有 $1$ 一定同时出现在某一组中。
枚举每一组作为 $1$ 出现的组，其他组的所有元素置为 $0$。对于组内的元素，我们要将其转换为一段连续的 $0$ 接上一段连续的 $1$ 再接上一段连续的 $0$ 的形式，询问最小转换次数。这可以 dp 解决。
复杂度：$O(k\cdot\frac{n}{k})=O(n)$
Code
>folded1
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
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
const int N = 2000005;
int T, n, k, dp[N][3], sum[N];
char s[N];
int main(){
for(read(T); T; T--){
int ans = 1e9;
read(n, k);
scanf("%s", s+1);
dp[0][0] = dp[0][1] = dp[0][2] = 1e9;
for(int i = 1; i <= n; i++){
sum[i] = sum[i-1] + (s[i] == '1');
dp[i][0] = dp[i][1] = dp[i][2] = 1e9;
}
for(int i = n + 1; i <= n + k; i++){
sum[i] = sum[n];
dp[i][0] = dp[i][1] = dp[i][2] = 1e9;
}
for(int i = 1; i <= k; i++){
int j = i;
for(j = i; j <= n; j += k){
if(j == i){
dp[j][0] = (s[j] == '1') + sum[j-1];
dp[j][1] = (s[j] == '0') + sum[j-1];
}
else{
dp[j][0] = min(dp[j][0], dp[j-k][0] + (s[j] == '1') + sum[j-1] - sum[j-k]);
dp[j][1] = min(dp[j][1], min(dp[j-k][0], dp[j-k][1]) + (s[j] == '0') + sum[j-1] - sum[j-k]);
dp[j][2] = min(dp[j][2], min(dp[j-k][1], dp[j-k][2]) + (s[j] == '1') + sum[j-1] - sum[j-k]);
}
}
dp[j][0] = min(dp[j][0], dp[j-k][0] + sum[j-1] - sum[j-k]);
dp[j][1] = min(dp[j][1], min(dp[j-k][0], dp[j-k][1]) + sum[j-1] - sum[j-k]);
dp[j][2] = min(dp[j][2], min(dp[j-k][1], dp[j-k][2]) + sum[j-1] - sum[j-k]);
ans = min(ans, min(dp[j][0], min(dp[j][1], dp[j][2])));
}
printf("%d\n", ans);
}
return 0;
}
|
F. Decreasing Heights
Solution
在一条满足答案的路径中，一定有至少一个格子的数没有被减，因为如果所有数都被减了，那么全都加上最小的减数后仍是符合要求的路径且答案更优。
枚举这个数字没变的格子，由于到达每个格子的步数其实是确定的（例如，$(2,3)$ 一定是走 $5$ 步到达的），所以我们可以知道走过每个格子的话这个格子上面应该填多少。然后就是一个简单的从 $(0,0)$ 到 $(n,m)$ 的 dp了。
复杂度：$O(n^4)$
Code
>folded1
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
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
const int N = 105;
int T, n, m;
LL a[N][N], t[N][N], dp[N][N];
int main(){
for(read(T); T; T--){
LL ans = 1e18;
read(n, m);
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
read(a[i][j]);
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
for(int ii = 0; ii < n; ii++){
for(int jj = 0; jj < m; jj++){
t[ii][jj] = a[ii][jj] - (ii + jj - i - j);
dp[ii][jj] = 1e18;
}
}
if(t[0][0] < a[i][j]) continue;
dp[0][0] = t[0][0] - a[i][j];
for(int ii = 0; ii < n; ii++){
for(int jj = 0; jj < m; jj++){
if(ii && t[ii][jj] >= a[i][j])
dp[ii][jj] = min(dp[ii][jj], dp[ii-1][jj] + t[ii][jj] - a[i][j]);
if(jj && t[ii][jj] >= a[i][j])
dp[ii][jj] = min(dp[ii][jj], dp[ii][jj-1] + t[ii][jj] - a[i][j]);
}
}
ans = min(ans, dp[n-1][m-1]);
}
}
printf("%lld\n", ans);
}
return 0;
}
|