目录
写在前面
补题地址：https://codeforces.com/gym/104128。
以下按个人向难度排序。
SUA 什么牛逼提妈的又被斩杀了，wenqizhi 大爹一个人爆切三道我和 dztlb 大神两个人分别在 AM 上调不出来坐牢真是纯纯的战犯
I 签到
显然当且仅当所有字符均相等才为完美回文。
字符集只有 26，直接做就行了。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
int T;
char s[N];
int a[300];
signed main(){
cin>>T;
while(T--){
scanf("%s",s+1);
int n=strlen(s+1);
for(int i=0;i<=100;++i) a[i]=0;
for(int i=1;i<=n;++i){
a[s[i]-'a']++;
}
int ans=ans=n;
for(int i=0;i<26;++i){
ans=min(ans,n-a[i]);
}
cout<<ans<<'\n';
}
return 0;
}
G 贪心，模拟
显然应当在保证数量大于 0 情况下，尽可能进行操作 -1。
发现这个操作对答案的分数有加有减的很麻烦啊，一个套路是考虑统一操作的形式。考虑先将所有操作均看做一次操作 1（即令分母分子同时加 1），发现操作 -1 可看成再额外对分子减 1，对分母减 2。考虑最终进行了 \(c\) 次操作 -1，则进行 \(n\) 次操作后，最终的答案可以表示为：
\[\frac{n + 1 - c}{n + 1 - 2c} \]保证上式分母时刻大于 0 即对应一种合法的操作方案。于是一个显然的想法是考虑直接贪心，尽量进行操作 -1，若发现此时进行操作 -1 后会导致上式不合法，则尝试将之前一次操作 -1 反悔即可。
赛时 wenqizhi 的思路是直接模拟上述转化，先将所有操作 0 均看做操作 1，然后考虑将当前的分母的值看做一张折线图，然后再倒序枚举折线图上的点，若当前点对应操作为 0，且在此之后的折线图上最小值至少为 2，则可以将当前的操作贪心地更改为操作 -1。
时间复杂度均为 \(O(n)\) 级别。
code by wenqizhi：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
int read()
{
int x = 0; bool f = false; char c = getchar();
while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
return f ? -x : x;
}
const int N = 1e6 + 5;
int n, a[N], pre[N], sufmn[N];
void solve()
{
n = read();
int b = 0;
for(int i = 1; i <= n; ++i)
{
a[i] = read();
pre[i] = pre[i - 1] + ((a[i] == 0) ? 1 : a[i]), b += (a[i] == -1);
}
sufmn[n] = pre[n];
if(pre[n] < 0){ printf("-1\n"); return ; }
for(int i = n - 1; i >= 1; --i)
{
sufmn[i] = min(pre[i], sufmn[i + 1]);
if(pre[i] < 0)
{
printf("-1\n");
return ;
}
}
int cnt = 0;
sufmn[n + 1] = 0x7fffffff;
for(int i = n; i >= 1; --i)
{
sufmn[i] = min(sufmn[i], sufmn[i + 1]);
if(a[i] == 0)
{
if(sufmn[i] >= 2) ++cnt, sufmn[i] -= 2;
}
}
int X = n - b - cnt + 1, Y = n - 2 * b - 2 * cnt + 1, mx = max(X, Y);
for(int i = 2; i <= mx; ++i)
while(X % i == 0 && Y % i == 0) X /= i, Y /= i;
printf("%d %d\n", X, Y);
}
int main()
{
int T = read();
while(T--) solve();
return 0;
}
反悔贪心：
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e6 + 10;
//=============================================================
int n;
//=============================================================
void getans(int ans_) {
int x = n + 1 - ans_, y = n + 1 - 2 * ans_;
int d = std::__gcd(x, y);
std::cout << x / d << " " << y / d << "\n";
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
std::cin >> n;
int cnt = 0, ans = 0, flag = 0;
for (int i = 1; i <= n; ++ i) {
int a; std::cin >> a;
if (a == 1) {
continue;
} else if (a == -1) {
if (2 * (ans + 1) < i + 1) ++ ans;
else if (cnt) -- cnt;
else flag = 1;
} else {
if (2 * (ans + 1) < i + 1) ++ ans, ++ cnt;
}
}
if (flag) std::cout << -1 << "\n";
else getans(ans);
}
return 0;
}
D 二分答案，枚举
显然答案有单调性，考虑二分答案。问题变为能否使序列中不小于 \(\operatorname{mid}\) 的数的数量不小于 \(k\)。
然后考虑被枚举操作的区间，仅需考虑区间中的 0 中有多少可以变成 1 即可。对于操作区间为 \([1, m]\) 时可以大力处理，然后发现当操作区间右移至 \([i, i + m - 1]\) 时，新加入的数 \(a_{i+m-1}\) 会变为 \(a_{i+m-1} + kd\)，原区间内的数均会减 \(d\)。
发现每一个数在操作区间内时，随区间右移其值是单调递减的，即每个数均会在操作区间左端点取 \(i\) 时变为不小于 \(k\)，又会在操作区间左端点取 \(i'(i'>i)\) 时变为小于 \(k\)，于是考虑将每个数的贡献 \(\plusmn 1\) 分别挂在这两个位置上，则每种操作区间的影响即可通过前缀和求得。
赛时 wenqizhi 大神原理大致如上但是用线段树实现的，一发过了但是看不懂呃呃呃呃：
code by wenqizhi：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
int read()
{
int x = 0; bool f = false; char c = getchar();
while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
return f ? -x : x;
}
const int N = 2e5 + 5;
int n, m, K;
ll c, d, a[N], A[N], b[N];
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
struct Segment
{
int sum[N << 2];
void update(int k, int l, int r, int pos, int val)
{
sum[k] += val;
if(l == r) return ;
int mid = (l + r) >> 1;
if(pos <= mid) update(ls(k), l, mid, pos, val);
else update(rs(k), mid + 1, r, pos, val);
}
int query(int k, int l, int r, int L, int R)
{
if(L <= l && r <= R) return sum[k];
int mid = (l + r) >> 1;
if(R <= mid) return query(ls(k), l, mid, L, R);
if(L > mid) return query(rs(k), mid + 1, r, L, R);
return query(ls(k), l, mid, L, R) + query(rs(k), mid + 1, r, L, R);
}
}T1, T2;
ll lazy;
int nn, mm;
bool check(ll mid)
{
int pos1 = upper_bound(A + 1, A + mm + 1, mid) - A - 1;
int pos2 = upper_bound(b + 1, b + nn + 1, mid - lazy) - b - 1;
int sum1 = T1.query(1, 1, mm, 1, pos1), sum2 = T2.query(1, 1, nn, 1, pos2);
if(sum1 + sum2 >= n - K + 1) return true;
else return false;
}
int main()
{
n = read(), K = read(), m = read(), c = read(), d = read();
for(int i = 1; i <= n; ++i) a[i] = read(), b[i] = a[i] + c + d * (i - 1), A[i] = a[i];
b[n + 1] = -0x7fffffffffffffff, b[n + 2] = 0x7fffffffffffffff;
sort(b + 1, b + n + 3);
nn = unique(b + 1, b + n + 3) - (b + 1);
A[n + 1] = -0x7fffffffffffffff, A[n + 2] = 0x7fffffffffffffff;
sort(A + 1, A + n + 3);
mm = unique(A + 1, A + n + 3) - (A + 1);
for(int i = 1; i <= m; ++i)
{
int id = lower_bound(b + 1, b + nn + 1, a[i] + c + d * (i - 1)) - b;
T2.update(1, 1, nn, id, 1);
}
for(int i = m + 1; i <= n; ++i)
{
int id = lower_bound(A + 1, A + mm + 1, a[i]) - A;
T1.update(1, 1, mm, id, 1);
}
ll ans = -0x7fffffffffffffff;
for(int i = m; i <= n; ++i)
{
ll l = -0x7ffffffffffff, r = 0x7ffffffffffff;
while(l < r)
{
ll mid = (l + r) >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
// printf("i = %d, l = %lld\n", i, l);
ans = max(ans, l);
if(i < n)
{
lazy -= d;
int lastid = i - m + 1;
int id = lower_bound(b + 1, b + nn + 1, a[lastid] + c + d * (lastid - 1)) - b;
T2.update(1, 1, nn, id, -1);
id = lower_bound(A + 1, A + mm + 1, a[lastid]) - A;
T1.update(1, 1, mm, id, 1);
lastid = i + 1;
id = lower_bound(b + 1, b + nn + 1, a[lastid] + c + d * (lastid - 1)) - b;
T2.update(1, 1, nn, id, 1);
id = lower_bound(A + 1, A + mm + 1, a[lastid]) - A;
T1.update(1, 1, mm, id, -1);
}
}
printf("%lld\n", ans);
return 0;
}
A 枚举，结论，二维前缀和
和 wenqizhi 大神讨论了下就直接会写了然而直到结束吃了 11 发都没过赛后一看是超级脑瘫错误呃呃
B DP，枚举
我和 dztlb 大神双人红温的时候，wenqizhi 大爹跑去开教练见面会了，到他回来我们也没调出来然后他一个人随便写写就又一发把这题过了唉唉真大神吧
M 计算几何，枚举，大力讨论
沟槽的题 corner case 这么多赛时从 WA30 搞到 WA50 再搞到 WA83 然后再也过不去了
写在最后
唉唉 wenqizhi 大爹太强了感觉我是纯飞物。
学到了什么：
- A：使用非常人类智慧的表达式，尝试简化特判——并非好事！