Codeforces Round 981 (Div. 3) 2024.10.24 题解
A. Sakurako and Kosuke
题意：
\(Sakurako\)与\(Kosuke\)正在玩游戏，一个点在原点\(x=0\)的起始位置。
对于第\(i\)次操作，点会移动 \(2 \ast i -1\)步。
两人轮流操作，Sakurako先手，每次将点往负方向移动；Kosuke每次将点往正方向移动。
当点所在的位置\(|x|\)>\(n\)的时候，游戏结束，我们需要求解出是谁执行的最后一步操作。
输入：
第一行一个整数t，表示t组测试用例。\((1 \leq t \leq 100)\)
接下来没一行一个整数n，表示结束的临界点。\((1 \leq n \leq 100)\)
输出：
每一个测试用例输出一个人名\(Sakurako\)或者\(Kosuke\)表示谁执行的最后一步操作。
样例输入：
4
1
6
3
98
样例输出：
Kosuke
Sakurako
Kosuke
Sakurako
分析：
我们通过题目发现，对应第\(i\)步，点所处的位置\(x\)，有以下关系：
\(F(i) = \sum_{k = 1}^i{(-1)^i \ast (2 \ast i - 1) }\)
简单列举几项：\(-1,2,-3,4,-5,6,\ldots\)
简单来说，我们发现这个序列是一个奇数序列，那么我们不论正负，可以发现，奇数步的时候（也就是\(Sakurako\)执行完操作），他所在的位置一定是奇数；
同理，偶数步的时候（也就是\(Kosuke\)执行完操作），所在的位置一定是偶数。
那么接下来我们分析答案，可以知道如果\(n\)是奇数，那么最后一步执行操作后一定为偶数，也就是最后一步由\(Kosuke\)，相反就由\(Sakurako\)执行。
综上，只需要判断\(n\)的奇偶即可。
ac 代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
int a[N];
int t,n;
signed main() {
cin>>t;
while(t--){
cin>>n;
if(n%2)cout<<"Kosuke"<<endl;
else cout<<"Sakurako"<<endl;
}
return 0;
}
B. Sakurako and Water
题意：
给定一个\(n \ast n\)的矩阵，里面元素有正有负，可以进行如下操作：
选择一个正方形矩阵，使它主对角线元素均加\(1\)。
具体来说，选择一个左上角的坐标\((i,j)\)和右下角坐标\((p,q)\)，
他们满足：\(p-i=q-j\)。然后选择第\(i+k\)行，第\(j+k\)列的元素并加\(1\)。\((0 \leq k \leq p-i)\)。
求最少的操作次数，使得矩阵里面的元素均\(\geq 0\)。
输入：
第一行一个整数\(t\)，表示\(t\)组测试用例。\((1 \leq t \leq 200)\)
每组第一行一个整数\(n\)，表示矩阵的边长。\((1 \leq n \leq 500)\)
接下来的\(n\)行，每一行都有\(n\)个整数，对应矩阵中的元素\(a_{i,j}\)。\((-10^{5} \leq a_{i,j} \leq 10^{5})\)
样例输入：
4
1
1
2
-1 2
3 0
3
1 2 3
-2 1 -1
0 0 -1
5
1 1 -1 -1 3
-3 1 4 4 -4
-1 -1 3 0 -5
4 5 3 -3 -1
3 1 -3 -1 5
样例输出：
0
1
4
19
分析：
题意给的很清晰了，每次操作选取对角线，我们可以得到，如果在这条对角线上存在负数，那么需要执行\(+1\)操作。
但是一条对角线上的操作次数应该是负数当中最小的那个。
综上，枚举对角线，在每条对角线中找出负数中最小即可，之后再累加。
如何快速的枚举对角线？
对于上述，我们可以得到，他的主对角线均符合\(Y=X+b\)的形式，即斜率固定，那么我们可以用截距\(b\)来作为评判对角线的标准。
所以可以用一个一维数组例如\(b[i-j+n]\)来存储其对角线的目标值。方便快速求解。
ac 代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=550;
int a[N][N];
int d[N*2];
int t,n;
signed main(){
cin>>t;
while(t--){
cin>>n;
memset(d,0,sizeof d);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)cin>>a[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(a[i][j]<0){
d[i-j+n]=min(d[i-j+n],a[i][j]);
}
}
int ans=0;
for(int i=0;i<=2*n;i++)ans-=d[i];
cout<<ans<<endl;
}
return 0;
}
C. Sakurako's Field Trip
题意：
有\(n\)个整数，可以有如下操作：
每次选取\(i\)位置\((\)下标从\(1\)开始\()\)的数，可以选择索引为\(n-i+1\)的位置，并交换。
规定干扰值为相邻且值相同的元素，换句话讲，就是满足\(a_j=a_{j+1}\)的索引\(j\)的个数。\((1 \leq j \leq n)\)
求解出操作任意多次后，干扰值的最小值。
输入：
第一行一个整数\(t\)，表示\(t\)组测试用例。\((1 \leq t \leq 10^4)\)
每组的第一行一个整数\(n\)，表示数组的大小。\((2 \leq n \leq 10^5)\)
接下来一行包含\(n\)个整数 \(a_i\)。\((1 \leq a_i \leq n)\)
输出：
每组数据一行一个整数，表示干扰值的最小值。
样例输入：
9
5
1 1 1 2 3
6
2 1 2 2 1 1
4
1 2 1 1
6
2 1 1 2 2 4
4
2 1 2 3
6
1 2 2 1 2 1
5
4 5 5 1 5
7
1 4 3 5 1 1 3
7
3 1 3 2 2 3 3
样例输出：
1
2
1
0
0
1
1
0
2
分析：
由于是对称的，所以我们仅仅需要考虑一半就行了。
我们首先考虑什么时候可以换：
我们很容易得到，交换必须要满足\(a_i \neq a_{n-i+1}\)。因为如果二者相等，交换是无效的。
我们枚举一侧，从\(1\) ~ $\lfloor \frac{n}{2} \rfloor $。当对称位置不相等的情况下，我们仅需要考虑他与前一个位置是否相同，而不需要看后面。
因为后面下一次可以按照前一个的思路更新，所以只需要看单向。
交换结束后，再遍历数组，求出符合条件的索引个数。
ac 代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
int a[N];
int t,n;
unordered_map<int,int>A;
signed main() {
cin>>t;
while(t--){
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}
for(int i=1;i<n/2;i++){
if(a[i]!=a[n-i-1]){
if(a[i]==a[i-1]||a[n-i-1]==a[n-i])swap(a[i],a[n-i-1]);
}
}
int ans=0;
for(int i=1;i<n;i++)if(a[i]==a[i-1])ans++;
cout<<ans<<endl;
}
return 0;
}
D. Kousuke's Assignment
题意：
给定一个\(n\)个整数的数组\(a_1,a_2,a_3, \ldots ,a_n\)，需要求出一对索引\((l_i,r_i)\)满足\(\sum_{i = l_i}^{r_i}{a_i} = 0\)。
这些索引对必须要满足不重复不覆盖的条件。
求出满足条件的索引对的最大数。
输入：
第一行一个整数\(t\)，表示\(t\)组测试用例。\((1 \leq t \leq 10^4)\)
每组第一行一个整数\(n\)，表示数组大小。\((1 \leq n \leq 10^5)\)
接下来有\(n\)个整数\(a_i\)。\((-10^5 \leq a_i \leq 10^5)\)
输出：
每组一个整数，表示满足条件的索引对的最大数目。
样例输入：
3
5
2 1 -3 2 1
7
12 -4 4 43 -3 -5 8
6
0 -4 0 3 0 1
样例输出：
1
2
3
分析：
我们需要求出区间和为0的最大个数，并且这区间不能重复不能有覆盖的。
由于是区间和，我们很容易想到用前缀和来处理。
对于前缀和\(d[]\)中，如果存在两个相同的数，假设索引为\(i\)和\(j\)，有\(d_i=d_j\)，那么就说明\(\sum_{k = i}^{j}{a_k} = 0\)，即区间和为0。
所以这个问题就很简单了，我们只需要处理一下前缀和，然后再找相同的数即可，
如果已经选择了该区间，需要满足不重复的条件，后面不能再用，可以用一个变量来存储区间选取过的下标。
但由于存在以一个\(0\)开头的前缀，我们只需要下标从\(1\)开始存数据，同时枚举下标从\(0\)开始即可解决这个问题。
ac 代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
int a[N];
int t,n;
map<int,int>A;
signed main() {
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
A[0] = -1;
int q = 0;
int ans = 0;
int l = -1;
for (int i=1;i<=n;i++)
{
q+=a[i];
if(A.count(q))
{
if(A[q]>=l)
{
l=i;
A.clear();
A[q] = i;
ans++;
}
else A[q]=i;
}
else A[q] = i;
}
cout<<ans<<endl;
A.clear();
}
return 0;
}
E. Sakurako, Kosuke, and the Permutation
题意：
给定一个\(n\)个元素\(a_1,a_2,a_3, \ldots ,a_n\) 的全排列数组。
规定对于索引\(i\)，如果满足以下两个条件中任意一个条件，
- \(a_i=i\);
- \(a_{a_i}=i\)
就称这个数组是“简单的”。
对于原数组，并不一定符合上述条件，需要进行交换操作，使其成为“简单的”。
每一次操作可以选取一对索引\((i,j)\)，然后交换\(a_i\)和\(a_j\)。
求出最少需要进行多少次交换才能使数组是“简单的”。
输入：
第一行一个整数\(t\),表示\(t\)组测试用例。\((1 \leq n \leq 10^4)\)
每组的第一行一个整数\(n\)，表示数组的大小。\((2 \leq n \leq 10^6)\)
接下来一行包含\(n\)个整数 \(a_i\)，表示全排列。\((1 \leq a_i \leq n)\)
输出：
每组一个整数，表示操作的最少次数。
样例输入：
5
1 2 3 4 5
5
5 4 3 2 1
5
2 3 4 5 1
4
2 3 4 1
3
1 3 2
7
2 3 1 5 6 7 4
样例输出：
0
0
2
1
0
2
分析：
题目中给定的数据是全排列，我们需要让每个元素满足:
\(a_i = i\) 或者 \(a_{a_i}=i\)
第一个条件很好理解，就是\(元素值=下标\)。
第二个条件我们可以理解为一个对组\((x,y)\)。即\(a_{a_x}=x\)和\(a_{a_y}=y\)在数组满足“简单的”条件下，
这样的元素一定是成对出现的，且满足\(a_x=y\)和\(a_y=x\)。
| 索引 | x | \(\ldots\) | \(\ldots\) | \(\ldots\) | y | \(\ldots\) |
|---|---|---|---|---|---|---|
| a | y | \(\ldots\) | \(\ldots\) | \(\ldots\) | x | \(\ldots\) |
所以：如果存在符合条件二的，就一定有一对元素，满足\(a_x=y\)和\(a_y=x\)
那么我们直接采用暴力枚举，从左往右枚举。
如果满足以上条件，则不需要交换，否则就需要交换。
我们需要用一个数组来存储元素\(a_i\)在数组中处在\(i\)位置，即\(A_{a_i}=i\)可以完成初始化。
接下来我们考虑交换的情况：
条件1的交换：
找到\(a_i=i\)的元素，然后交换即可。那么\(a_i\)在哪儿？
由于我们预先存了各个元素在数组的下标，所以我们可以很快索引到他的下标为：\(A_{a_i}\)
那么接下来首先得交换下标\(A_{a_i}\)和\(A_i\)，保证更新到了下标，然后再交换数组值\(a_{A_{a_i}}\)和\(a_{A_i}\)
条件2的交换：
找到\(a_{a_i}=i\)的元素，然后交换即可。那么\(a_{a_i}\)在哪儿？
由于我们预先存了各个元素在数组的下标，所以我们可以很快索引到他的下标为：\(A_{a_{a_i}}\)
那么接下来首先得交换下标\(A_{a_{a_i}}\)和\(A_i\)，保证更新到了下标，然后再交换数组值\(a_{A_{a_{a_i}}}\)和\(a_{A_i}\)
那么我们来分析一下，哪种更优：
假设数组\(a=[3,2,4,5,1]\)
采用第一种：那么我们根据上面的结论可以分析出，如果并不存在这样的一对\((x,y)\)，就会每次交换直接给交换到\(i\)值，使得\(a_i=i\)。
分析下来，我们发现第一步交换后数组变为\(a=[1,2,4,5,3]\)
最后变为\(a=[1,2,3,5,4]\)
我们发现，数值为\(3\)的元素似乎对后面的元素产生了干扰，并不是最优，导致多交换了。
采用第二种：我们一步就可以实现\(a=[3,2,1,5,4]\)
只需要将\(a_{a_1}\)交换好正确，就可以保证完成，并且后续元素也不会受到前面元素的干扰。
综上我们的最优策略应该是暴力枚举不符合条件的然后按照条件\(2\)来交换处理，这样可以最优。
ac 代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
int a[N],A[N];
int t,n;
signed main() {
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
A[a[i]]=i;
}
int ans=0;
for(int i=1;i<=n;i++){
if(a[i]==i)continue;
if(a[a[i]]==i)continue;
swap(A[a[a[i]]],A[i]);
swap(a[A[a[a[i]]]],a[A[i]]);
ans++;
}
cout<<ans<<endl;
}
return 0;
}