CF补题 981-Div.3-20241226
Dashboard - Codeforces Round 981 (Div. 3) - Codeforces
A：
题目大意：\(x\) 从 \(0\) 开始，轮流将 \(x\) 前后移动 \(i*2-1\)， 求最后移动出 $-n,n $ 的 $ i$
#include <iostream>
#include <math.h>
using namespace std;
int main()
{
int T;
cin >> T;
while (T--)
{
int n;
int x = 0;
cin >> n;
int i = 0;
for (i = 1; x >= -n && x <= n; i++)
x += (2 * i - 1) * pow(-1, i);
if (i % 2 == 1) cout << "Kosuke" << endl;
else cout << "Sakurako" << endl;
}
return 0;
}
转化方程为每次移动 \((2*i-1)*(-1)^i\) 个单位，最后对操作数 $ i$ 取余
B：
题目大意：给定一个矩阵，每次可以选取任意一条正斜线，使斜线上的数 \(+1\) ，求矩阵所以元素都大于 \(0\) 的操作数
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int a[505][505];
int dg[1010];//所有斜线上最小元素
int main()
{
int T;
cin >> T;
while (T--)
{
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
dg[j - i + n] = min(dg[j - i + n], a[i][j]);//贪心更新
}
}
int ans = 0;
for (int i = 1; i < 2 * n; i++) ans -= dg[i];//累加答案
cout << ans << endl;
memset(dg, 0, sizeof dg);//多测清空
}
return 0;
}
贪心策略，每次记录当前输入的元素，更新该斜线上的最小值，最后所有斜线上的数之和，即所有的最大负数和 $ \sum_i^n min(dg_i)$
即至少操作这么多次，才能满足条件
C：
题目大意：给定一个序列，每次可以交换第 \(i\) 和第 \(n-i+1\) 个位置上的数，求使得序列上的元素满足任意 \(a_j=a_{j+1}\) 的最小组合
#include <iostream>
using namespace std;
int a[200010];
int main()
{
int T;
cin>>T;
while (T--){
int n;
cin>>n;
for (int i=1;i<=n;i++) cin>>a[i];
int l=2,r=n-1;
while (r>l){
if (a[l]==a[l-1]||a[r]==a[r+1])
swap(a[l],a[r]);
l++;r--;
}
int ans=0;
for (int i=2;i<=n;i++)
if (a[i]==a[i-1]) ans++;
cout<<ans<<endl;
}
return 0;
}
双指针，贪心（？
两个指针从左右两边开始移动，如果存在 \(a_i=a_{i-1}\) 就交换，当前局部的最优解可以推出全局的最优解（？
证明有：
设序列 1 4 3 5 1 1 3 （干扰度为 \(1\)） ，定义l=1,r=n-2，此时序列中 a[l]=4,a[r]=1，不交换。两个指针向中间移动。移动后 a[l]=3,a[r]=1，r与后一个元素相同，交换 l 与 r ，序列为 1 4 1 5 3 1 3 全局干扰度减 \(1\) ，以此类推。。。
设序列 3 1 3 2 2 3 3 （干扰度为 \(2\)），定义l=1,r=n-2，此时序列中 a[l]=1,a[r]=3 ，r和后一个元素相同，若 l 与 r 交换，序列变为 3 3 3 2 2 1 3 ，l 与前一个元素相同，则全局的干扰度没有变化。两个指针向中间移动，l与前一个元素相同，交换 l 与 r 有3 3 2 2 3 1 3 ，全局的干扰度不变。 最终全局最优的干扰度就为 \(2\)
归纳发现，如果满足交换条件的 l 和 r ，就一定要交换，交换后全局解一定不劣，要么为优要么不变
D：
题目描述：给出一段序列，计算不重叠区间 l,r 使得 \(\sum _{i=l}^r a_i=0\) 的最大区间个数
#include <iostream>
#include <map>
#include <set>
using namespace std;
long long a, b, ans;
set<long long> mem;
void init(void) {
mem.clear();
b = 0;
mem.insert(0);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T;
cin >> T;
while (T--) {
ans = 0;init();
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a;
b += a;
if (mem.count(b)) {
ans++;
init();
}
else
mem.insert(b);
}
cout << ans << endl;
}
return 0;
}
前缀和+贪心，每个区间右端点越靠左越优，如果某元素前缀和与前面已经记录的相同，答案 +\(1\)
使用集合set来记录前缀和，注意要首项要加入 \(0\) ，因为序列头为 \(0\) 时，也可以算作答案区间
数据量较大时关同步流可以明显加速
- 不开
long long见祖宗