Codeforces Round 963 (Div. 2)

前言

看完小胖夺冠就来打打比赛，可能出题人也没想到有几千人卡在了 D 题，比赛时想到了二分想到了用 dp 想到了性质但是可惜卡在了状态转移。

Standings：1497

题目链接：Dashboard - Codeforces Round 963 (Div. 2) - Codeforces

A. Question Marks

题意：

一张试卷有 4n 个题目，每个选项 "A" "B" "C" "D" 都是其中 n 个题目的答案。给出 Tim 的考场答案，问最多能答对多少题。

思路：

贪心，尽可能让 Tim 所写的答案就是标准答案，但是每个选项最多只能计 n 个。

#include<cstdio>
#include<cstring>
using namespace std;int T,n,a[5],ans;
char s[10005];int min(int x,int y) { return x < y ? x : y ; }int main()
{scanf("%d",&T);while (T --){memset(a,0,sizeof a),ans = 0;scanf("%d",&n);scanf("%s",s + 1);for (int i = 1;i <= n * 4;++ i)if(s[i] >= 'A' && s[i] <= 'D') ++ a[s[i] - 'A'];for (int i = 0;i < 4;++ i) ans += min(a[i],n);printf("%d\n",ans);}return 0;
}

B. Parity and Sum

题意：

给一个长度为 n 的序列 a ，每次可以选择两个奇偶性不同的数，并让较小的那个数变成这两个数之和，问使得序列中所有数奇偶性相同时最小的操作数。

思路：

特判一下原序列就合法的情况，剩下的情况显然我们只能把所有数都变成奇数。

贪心，每次用最大的那个奇数和某个比他小的偶数操作，然后更新奇数的最大值，这样每次改变奇偶性需要的操作数是 1 且是最小的。上一步完成后如果目前最大的奇数仍然小于一些偶数，那就随便用一个奇数和最大的那个偶数操作两次，会得到一个大于所有偶数的奇数，接下来把剩下的偶数都操作一下即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;#define N 200005int T,n;
long long ans,a[N];int main()
{scanf("%d",&T);while (T --){scanf("%d",&n),ans = 0ll;for (int i = 1;i <= n;++ i) scanf("%lld",&a[i]);sort(a + 1,a + n + 1);long long mx = -1ll;for (int i = n; i ;-- i)if(a[i] & 1){mx = a[i];break;}if(mx == -1ll){printf("0\n");continue;}int flag = 0;for (int i = 1;i <= n;++ i)if(!(a[i] & 1)){if(flag){++ ans;continue;}if(mx > a[i]){mx += a[i];++ ans;}else{flag = 1;ans += 2ll;}}printf("%lld\n",ans);}return 0;
}

C. Light Switches

题意：

公寓里有 n 盏灯，每盏灯有个安装时间 $a_i$ ，在安装那一刻起 k 分钟内灯亮，k 分钟后起的又一个 k 分钟内灯灭，交替进行。即在 $a_i$ ， $a_i$ + k ， $a_i$ + 2k ， $a_i$ + 3k ...... 时刻灯的状态会发生改变，问最早在哪一刻所有的灯都发亮。

思路：

所有灯的周期都是 k 分钟，我们可以从这里入手。也就是说在最后一盏灯安装之后，每隔 2k 分钟所有灯的状态集合都是一样的。于是我们只需考虑在最后那盏灯安装后的 2k 分钟里灯的状态。容易求出每盏灯在这个时间内亮灯的区间，求一下交集即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;#define N 200005int T,n,k,l,r,flag,a[N];int cross(int x,int y)
{if(x > r || y < l) return 0;if(x > l) l = x;if(y < r) r = y;return 1;
}int main()
{scanf("%d",&T);while (T --){scanf("%d%d",&n,&k);for (int i = 1;i <= n;++ i) scanf("%d",&a[i]);sort(a + 1,a + n + 1);l = 0,r = k - 1,flag = 1;for (int i = 1,p,q;i <= n;++ i){int now = a[n] - a[i];if((now / k) & 1){now = now % k;p = k - now;q = k - now + k - 1;}else{now = now % k;p = 0;q = k - now - 1;}flag = cross(p,q);if(!flag) break;}if(!flag) printf("-1\n");else printf("%d\n",a[n] + l);}return 0;
}

D. Med-imize

题意：

给一个长度为 n 的序列 a ，你需要进行若干次操作，每次删掉序列中连续的 k 个数，直到序列的长度小于等于 k 。求最后剩下的序列中，中位数的最大值（这里中位数定义为长度为 n 的序列从小到大排序后第 $\lfloor \frac{n + 1}{2} \rfloor$ 大的数）。

思路：

首先肯定不能用排序求中位数，这样太慢。

我们可以二分中位数的值，判断剩下的序列中大于等于这个值的数最多有多少个，如果超过了一半就说明这个值是合法的。根据题意，剩下序列的长度是确定的：m = (n - 1) % k + 1 ，简单观察可知题目实际上是要挖掉若干段不相交的长度为 k 的区间。那么剩下数列中相邻的两个数要么在原数列中就是相邻的，要么在原数列的下标相差若干个 k 。

依次可以得到一条关键线索：原数列中下标为 i 的数（下标从 0 开始）要是留下来，它在最终数列中的下标一定是 i % k 。这样我们就可以 dp 了，设 $f_i$ 表示最终数列中 0 ~ i 位可以产生大于 x 的数的最多个数。

时间复杂度：O（n log(max - min)）

#include<cstdio>
#include<cstring>
using namespace std;#define N 500005int T,n,k,m,a[N],f[N],ans;int min(int x,int y) { return x < y ? x : y ; }int max(int x,int y) { return x > y ? x : y ; }int check(int x)
{for (int i = 0;i < m;++ i) f[i] = 0;for (int i = 0;i < n;++ i)f[i % k] = max(f[i % k],(i % k) ? (f[i % k - 1] + (a[i] >= x)) : (a[i] >= x));return (f[m - 1] >= m - (m + 1) / 2 + 1);
}int main()
{scanf("%d",&T);while (T --){scanf("%d%d",&n,&k),m = (n - 1) % k + 1,ans = 0;int l,r;l = 1e9,r = 1;for (int i = 0;i < n;++ i) scanf("%d",&a[i]),l = min(l,a[i]),r = max(r,a[i]);while (l <= r){int mid = (l + r) >> 1;if(check(mid)) l = mid + 1,ans = mid;else r = mid - 1;}printf("%d\n",ans);}return 0;
}

后面的题待补。