目录
Codeforces Round 981 (Div. 3)
分析
这场整体发挥都不好, 虽然题也抽象, 但是对于这些题完全没必要卡这么久. 正常至少能看到 \(\mathbf{F}\)
A
思路
因为边界 \(n\) 管辖 \(\pm\), 而 Sakurako 管辖 \(\{-1,-3,-5,-7...\}\), Kosuke 管辖 \(\{2,4,6,...\}\), 也就是说 Sakurako 管辖奇数, Kosuke 管辖偶数.
代码
void func(void)
{
int n;
cin >> n;
cout << (n&1 ? "Kosuke\n" : "Sakurako\n");
}
B
思路
翻译题意后可知, 每次操作对一个子正方形的主对角线(左上到右下)都 \(+1\).
那么对于边长为 \(n\) 的正方形, 每次只需要操作 \(2n-1\) 条线(从左下或者右上点的边长 \(\le n\) 的正方形), 因为对于每条主对角线, 如果首尾相接就可以连起来, 那么可以将操作合并.
并且因为只需要让所有数为 \(+\), 所以只需统计每条上负数的最大值即可, 最后求和.
卡题原因
一时间没想到怎么处理对角线, 居然卡了半个小时.
注: 事实上下列代码也非常丑陋. 完全不符合我的代码风格.
代码
void func(void)
{
int n,ans = 0;
cin >> n;
vector<vector<int>> a(n+2,vector<int>(n+2));
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
{
int stp; cin >> stp;
if(stp < 0) a[i][j] = -stp;
}
}
for(int i=2;i<=n;++i)
{
int stp = 0;
int x = i,y = 1;
while(x <= n)
{
stp = max(stp,a[x][y]);
x++, y++;
}
ans += stp;
}
for(int i=1;i<=n;++i)
{
int stp = 0;
int x = 1,y = i;
while(y <= n)
{
stp = max(stp,a[x][y]);
x++, y++;
}
ans += stp;
}
cout << ans << '\n';
}
C
思路
贪心
因为每个元素只能和对称元素交换, 所以可以把原始串拆成两部分 —— \(1 \sim n/2, (n+1)/2 \sim n\), 如果奇数串, 因为对称轴元素无法交互, 所以不用处理.
虽然题意描述是 \(a_j = a_{j+1}\) 扰动指数增加, 但是按 \(a_j = a_{j-1}\) 判断也可以, 那么对称轴左侧向左判, 右侧向右判断也无影响, 若是到了对称轴:
- 若是奇数, 中间数不变化, 所以不影响结果.
- 若是偶数, 分界点左右数互相判断, 也无影响.
设\(fi(i) = n - i + 1\)
那么每次只需要判断 \(i - 1\) 和 \(fi(i-1)\), \(i\) 和 \(fi(i)\).
设\(a_{i-1} = x_0, a_{fi(i-1)} = y_0, a_{i} = x_1, a_{fi(i)} = y_1\)
- 若 \(x_0 = y_0\), 那么 \(x_1, y_1\) 在什么位置都不影响结果.
- 若 \(x_1 = y_1\), 那么 \(x_0, y_0\) 在什么位置都不影响结果.
- 若 \(x_0 = x_1\), 那么交换\(x_1, y_1\), 使得两个 \(x\) 不接触.
- 若 \(y_0 = y_1\), 那么交换\(x_1, y_1\), 使得两个 \(y\) 不接触.
卡题原因
分析觉得需要尽量减少连续序列长度, 但是长度实际并没有影响.
code
int fi(int k)// 计算反转后的串
{
return (n-k+1);
}
void func(void)
{
cin >> n;
vector<int> a(n+1),t(n+1);// 其实也没有新开的必要, 因为每次也是判断交换后的前一个数
vector<PII> b(n/2+1);
for(int i=n;i>=1;--i) cin >> a[i];// 并没有反读的必要
for(int i=1;i<=n/2;++i)
{
b[i].x = a[i],b[i].y = a[fi(i)];
}
int ans = 0;
t[(n+1)/2] = a[(n+1)/2];
for(int i=1;i<=n/2;++i)
{
t[i] = b[i].x,t[fi(i)] = b[i].y;
if(t[i-1] == t[fi(i)+1] || b[i].x == b[i].y) continue;
if(b[i].x == t[i-1] || b[i].y == t[fi(i)+1])
{
swap(t[i],t[fi(i)]);
}
}
for(int i=1;i<=n;++i) if(t[i] == t[i-1]) ans ++;
cout << ans << '\n';
}
D
思路
前缀和 贪心
前缀和维护上一次为 \(0\) 区间尾的下一个点开始到当前节点的前缀和.
贪心寻找每次最先出现的满足区间, 这样对后续区间的影响最小, 因为其尽可能靠左, 占用元素更少.
卡题原因
完全没想到在线, 还是抄小秦的才明白.
代码
void func(void)
{
int n,ans = 0,sum = 0;
cin >> n;
vector<int> a(n);
map<int,int> mp;
for(auto &i : a) cin >> i;
for(int i=0;i<n;++i)
{
sum += a[i];
mp[sum] ++;
if(mp[sum] == 2 || sum == 0)
{
ans ++;
sum = 0;
mp.clear();
}
}
cout << ans << '\n';
}
E
思路
对于每个 \(i\), 可以通过 \(a_i\) 找到指向的元素, 那么互相指向的元素就可以构成一个环.
根据题意, 大小 \(\le 2\) 的环满足条件, 题面需要所有环 \(\le 2\).
可以计算, 一个 $> 2 $ 的环, 需要 \((size-1) / 2\) 次操作才能满足条件.
所以只需要计算每个环的操作此时, 求和即可.
wa原因
bitset开小了, 搞错了开法, <>内的是实际元素大小.
为什么小数据还一直报wa, 搞得我以为是模拟错了. 要不是看小秦代码对拍, 当晚都补不出来.
code
void func(void)
{
int n;
cin >> n;
vector<int> a(n+1);
for(int i=1;i<=n;++i) cin >> a[i];
bitset<N/32> vis;
int tp = 1,ans = 0,p = 0;
for(int i=1;i<=n;++i)
{
if(vis[i]) continue;
vis[i] = true;
tp = i, p = a[tp];
vis[p] = true;
int cnt = 1;
while(p != tp)
{
p = a[p];
cnt ++;
vis[p] = true;
}
ans += (cnt-1)/2;
}
cout << ans << '\n';
}