一场有趣的cf比赛
Before the Beginning
转载请将本段放在文章开头显眼处，如有二次创作请标明。
原文链接：https://www.codein.icu/cfedu96/
C
可以发现，答案一定是 $2$.
考虑将最大的与其他值合并，合并后得到新的最大值，然后依次合并，最终一定会得到 $2$.
特判 $n = 1$ 的情况。
int main()
{
read(T);
while(T--)
{
read(n);
if(n == 1) printf("1\n");
else
{
puts("2");
int last = n;
for(int i = n - 1;i;--i) printf("%d %d\n",i,last),last = (i + last + 1) / 2;
}
}
return 0;
}A
给定 $n$，求 $3x + 5y + 7z = n$ 的一组解。
随便枚举一下。
int T,n;
int main()
{
read(T);
while(T--)
{
read(n);
for(int i = 0;3 * i <= n;++i)
for(int j = 0;3 * i + 5 * j <= n;++j)
for(int k = 0;3 * i + 5 * j + 7 * k <= n;++k)
if(3 * i + 5 * j + 7 * k == n)
{
printf("%d %d %d\n",i,j,k);
goto end;
}
printf("-1\n");
continue;
end:;
}
return 0;
}B
可以发现，倒水一定是一杯全部倒入另一杯较好。
倒完一次之后，最小值一定是零，只需要最大化最大值即可。
将次大的不断倒入最大的。
int T,n,k;
long long a[maxn];
int main()
{
read(T);
while(T--)
{
read(n),read(k);
for (int i = 1; i <= n; ++i) read(a[i]);
std::sort(a + 1,a + 1 + n);
long long ans = a[n];
for (int i = 1; i <= k; ++i) ans += a[n - i];
printf("%lld\n", ans);
}
return 0;
}D
每次选择一个字符删除，然后删除前缀一整段相同的字符。
一整段字符会被一次删掉，此外还要额外删一个字符。
可以想到，如果选择的单个字符是整段中的一个的话，并不会使答案更劣。
因此优先挑选整段中的字符，直到整段被删成单个字符。
随后每次消耗两个单个字符。
考虑可能最后不足两个单个字符，发现没啥关系，答案照样记即可。
#include <cstdio>
#include <algorithm>
#include <ctype.h>
const int maxn = 2e5 + 100;
int T,n;
char s[maxn];
int f[maxn],st[maxn],top,r[maxn];
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
scanf("%s",s + 1);
top = 0;
for (int i = 1; i <= n; ++i)
{
f[i] = 1;
if (s[i] == s[i - 1]) f[i] += f[i - 1], f[i - 1] = 0;
}
for (int i = 1; i <= n; ++i) if(f[i]) st[++top] = f[i],r[top] = i;
int p = 1,now = 1,ans = 0;
while(now <= top)
{
++ans;
if(p < now) p = now;
while(p <= top && st[p] == 1) ++p;
if(p <= top) --st[p],++now;
else now += 2;
}
printf("%d\n",ans);
}
return 0;
}E
交换相邻，容易想到逆序对。
对于样例的：
icpcsguru
urugscpci
考虑对于目标串中每个字符，来自原串的哪个字符。
目标串出现第 $i$ 次的某字符 $x$，一定是从原串中第 $i$ 次出现的字符 $x$ 移动来的。
要证明这个贪心结论的正确性
对于这么多种情况，按原序都不劣于按逆序。
感性理解一下。
那么就可以这样处理出目标串中每个字符来自于哪个位置，随后统计逆序对即可。
const int maxn = 5e5 + 100;
int n;
char s[maxn],t[maxn];
int sum[maxn];
inline int lowbit(int x){return x & -x;}
int ask(int x)
{
int res = 0;
for (; x > 0; x -= lowbit(x)) res += sum[x];
return res;
}
void add(int x, int k) { for (; x <= n; x += lowbit(x)) sum[x] += k; }
queue<int> q[30];
int to[maxn];
int main()
{
read(n);
read(s + 1);
for (int i = 1; i <= n; ++i) s[i] = s[i] - 'a' + 1, q[s[i]].push(i);
for (int i = 1; i <= n; ++i) t[i] = s[n - i + 1];
long long ans = 0;
for (int i = 1; i <= n; ++i)
{
to[i] = q[t[i]].front();
q[t[i]].pop();
ans += ask(n) - ask(to[i]);
add(to[i],1);
}
printf("%lld\n",ans);
return 0;
}F
明明是 $O(n)$ 的贪心题，却用数据范围欺骗参赛者。
对于一波怪物，只有两个选择：扔掉上次剩下的弹夹，或是不扔。
如果上次剩余的子弹数量足够通过该关，那么就可以省下一个弹夹，否则必须扔掉上次的弹夹，而更换新的弹夹。
贪心结论：如果能不扔弹夹，就不扔弹夹。
对于一波怪物，如果剩余子弹不够，则必须扔。而剩余子弹够，可以选择扔或不扔。
如果扔了的话，是为了剩下更多的子弹给后面用。但是同样可以选择在后面子弹不足时再扔，能让那时拥有更多子弹。
因此总是不扔。
那么每波怪物最少需要多少剩余子弹，才能节省一个弹夹呢？
由于两波怪物端点可能会相交，因此定义：
$f(i)$ 为允许在 $(l_i,r_i]$ 中换弹，第 $i$ 波在 $l_i$ 处的最少剩余子弹。
计算需要多少子弹才能通过关卡，初始有 $need = a_i$
如果 $r_i = l_{i+1}$，那么 $need$ 还要加上 $f(i + 1)$
$f(i) = need – (r_i – l_i) \times k$，随后模拟贪心即可。
const int maxn = 2e3 + 100;
int n, k, l[maxn], r[maxn], a[maxn], f[maxn];
int main()
{
read(n), read(k);
for (int i = 1; i <= n; ++i) read(l[i]), read(r[i]), read(a[i]);
for (int i = n; i; --i)
{
int need = a[i];
if (r[i] == l[i + 1]) need += f[i + 1];
if (1ll * (r[i] - l[i] + 1) * k < need) { puts("-1"); return 0; }
f[i] = max(0ll, need - 1ll * (r[i] - l[i]) * k);
}
long long ans = 0;
int now = k;
for (int i = 1; i <= n; ++i)
{
if (now < f[i]) ans += now, now = k;
ans += a[i];
now = (((now - a[i]) % k) + k) % k;
}
printf("%lld\n", ans);
return 0;
}