Codeforces Round 981 (Div. 3)
A. Sakurako and Kosuke
Sakurako and Kosuke decided to play some games with a dot on a coordinate line. The dot is currently located in position \(x=0\). They will be taking turns, and Sakurako will be the one to start.
On the \(i\)-th move, the current player will move the dot in some direction by \(2\cdot i-1\) units. Sakurako will always be moving the dot in the negative direction, whereas Kosuke will always move it in the positive direction.
In other words, the following will happen:
- Sakurako will change the position of the dot by \(-1\), \(x = -1\) now
- Kosuke will change the position of the dot by \(3\), \(x = 2\) now
- Sakurako will change the position of the dot by \(-5\), \(x = -3\) now
- \(\cdots\)
They will keep on playing while the absolute value of the coordinate of the dot does not exceed \(n\). More formally, the game continues while \(-n\le x\le n\). It can be proven that the game will always end.
Your task is to determine who will be the one who makes the last turn.
按照题意进行枚举就行
#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define TLE (double)clock() / CLOCKS_PER_SEC <= 0.95
#define int long long
#define double long double
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int N = 1e6 + 5, M = 1e6 + 5, S = 1e6 + 5, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;
int a, b, x;
void solve()
{
int n;
cin>>n;
int flag = 1;
int st =0;
for(int i=1;st<=n&&st>=-n;i+=2){
if(flag ==1){
st-=i;
}
else{
st+=i;
}
flag*=-1;
}
if(flag == -1){
cout<<"Sakurako"<<endl;
}
else{
cout<<"Kosuke"<<endl;
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
cin >> T;
for (int i = 1; i <= T; i++)
{
solve();
}
return 0;
}
B. Sakurako and Water
During her journey with Kosuke, Sakurako and Kosuke found a valley that can be represented as a matrix of size \(n \times n\), where at the intersection of the \(i\)-th row and the \(j\)-th column is a mountain with a height of \(a_{i,j}\). If \(a_{i,j} < 0\), then there is a lake there.
Kosuke is very afraid of water, so Sakurako needs to help him:
- With her magic, she can select a square area of mountains and increase the height of each mountain on the main diagonal of that area by exactly one.
More formally, she can choose a submatrix with the upper left corner located at \((i, j)\) and the lower right corner at \((p, q)\), such that \(p-i=q-j\). She can then add one to each element at the intersection of the \((i + k)\)-th row and the \((j + k)\)-th column, for all \(k\) such that \(0 \le k \le p-i\).
Determine the minimum number of times Sakurako must use her magic so that there are no lakes.
按照对角线枚举元素就行，统计整个矩阵每一条主对角线上小于零的数里最小的（这样收益最大），加起来取绝对值
#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define TLE (double)clock() / CLOCKS_PER_SEC <= 0.95
#define int long long
#define double long double
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int N = 1000, M = 1e6 + 5, S = 1e6 + 5, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;
int arr[N][N];
void solve() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> arr[i][j];
}
}
vector<int> max_operations(2 * n, 0);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (arr[i][j] < 0) {
int operations_needed = -arr[i][j];
int diag_index = i - j + (n - 1);
max_operations[diag_index] = max(max_operations[diag_index], operations_needed);
}
}
}
int total_operations = accumulate(max_operations.begin(), max_operations.end(), 0);
cout << total_operations << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
cin >> T;
for (int i = 1; i <= T; i++)
{
solve();
}
return 0;
}
C. Sakurako's Field Trip
Even in university, students need to relax. That is why Sakurakos teacher decided to go on a field trip. It is known that all of the students will be walking in one line. The student with index \(i\) has some topic of interest which is described as \(a_i\). As a teacher, you want to minimise the disturbance of the line of students.
The disturbance of the line is defined as the number of neighbouring people with the same topic of interest. In other words, disturbance is the number of indices \(j\) (\(1 <j < n\)) such that \(a_j = a_{j + 1}\).
In order to do this, you can choose index \(i\) (\(1\le i\le n\)) and swap students at positions \(i\) and \(n-i+1\). You can perform any number of swaps.
Your task is to determine the minimal amount of disturbance that you can achieve by doing the operation described above any number of times.
只能交换对称元素。我们可以想一下，假设交换两个元素，是不会将干扰变大的。我们可以加一些限制条件，使得交换尽可能减小干扰。
我们遍历前一半元素。假设我们只在当前元素与前一个元素相等（或者对称元素与对称元素的后一个相等）的情况下交换元素。因为前面的元素都是判断过的，不会再变换，交换当前的元素就有可能减少干扰（交换过来的不相等的情况）
#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define TLE (double)clock() / CLOCKS_PER_SEC <= 0.95
#define int long long
#define double long double
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int N = 1e6 + 5, M = 1e6 + 5, S = 1e6 + 5, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;
int a, b, x;
int arr[N];
void solve()
{
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>arr[i];
}
arr[n+1]=0;
for(int i=1;i<=n/2;i++){
if(arr[i]==arr[i-1]||arr[n-i+1]==arr[n-i+2])
swap(arr[i],arr[n-i+1]);
}
int ans = 0;
for(int i=1;i<=n;i++){
if(arr[i]==arr[i+1]){
ans++;
}
}
cout<<ans<<endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
cin >> T;
for (int i = 1; i <= T; i++)
{
solve();
}
return 0;
}
D. Kousuke's Assignment
After a trip with Sakurako, Kousuke was very scared because he forgot about his programming assignment. In this assignment, the teacher gave him an array \(a\) of \(n\) integers and asked him to calculate the number of non-overlapping segments of the array \(a\), such that each segment is considered beautiful.
A segment \([l,r]\) is considered beautiful if \(a_l + a_{l+1} + \dots + a_{r-1} + a_r=0\).
For a fixed array \(a\), your task is to compute the maximum number of non-overlapping beautiful segments.
需要注意的是，使用map和set而不是unordered_map和unordered_set。因为unordered_map每个位置存储的是一个链表，产生哈希冲突的时候访问速度会退化。本人被100000个相同的数据hack了，望周知
这个题要找出不重叠的和为零的区间。我们想两个状态
- 一个区间，结束的越早，它对于后续区间的影响的越少，因为重叠的可能降低了
- 假设我们选择了一个区间，那么为了保证不重叠，我们需要使用flag记录这次选择区间的右端点，下次选择区间的时候区间的左端点必须大于flag才能保证不重叠
依照这个思路就可以实现。实现细节上，我们使用一个哈希表。键值为前缀和，值为这个前缀和对应的下标。我们在遍历的过程中，如果找到了一个之前出现过的前缀和，那么这段区间的和就是零。由于从零开始枚举前缀和，相当于枚举右端点，我们再记录一下flag就可以了
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#define int long long
using namespace std;
struct Segment {
int left;
int right;
};
int maxBeautifulSegments(const vector<int>& a) {
int n = a.size();
map<long long, int> prefixSumIndex;
vector<Segment> segments;
long long currentSum = 0;
prefixSumIndex[0] = -1; // 初始前缀和为0的索引
int lastEnd = -1; // 用于存储上一个区间的右端点
int count = 0; // 记录不重叠区间的数量
// 找到所有和为零的区间并进行选择
for (int i = 0; i < n; ++i) {
currentSum += a[i]; // 更新前缀和
if (prefixSumIndex.find(currentSum) != prefixSumIndex.end()) {
int startIndex = prefixSumIndex[currentSum];
// 计算当前区间
Segment newSegment = {startIndex + 1, i};
// 检查是否与之前的区间不重叠
if (newSegment.left > lastEnd) {
count++; // 选择这个区间
lastEnd = newSegment.right; // 更新上一个结束位置
}
}
// 更新前缀和的索引
prefixSumIndex[currentSum] = i;
}
return count;
}
signed main() {
int t;
cin >> t; // 输入测试组数
while (t--) {
int n;
cin >> n; // 输入数组大小
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i]; // 输入数组元素
}
int result = maxBeautifulSegments(a);
cout << result << endl; // 输出每组的最大不重叠美丽段数量
}
return 0;
}