进阶题

1001题 Yes, Prime Minister 是的，首相

题目大意
给定连续的整数序列，输出序列上包含 $x$ 且区间和为质数的最短区间长度。

考察内容
数学，欧拉筛，二分查找

分析
等差数列求解区间和，可以证明，区间长度大于等于3时，只有抵消掉其余的部分留下一个或两个正整数时才能满足区间和为质数，只需要在这些情况里找出区间长度最小的方案。

$x > 0$ 时考虑 $x$ 为质数; $2 x ? 1$ 或 $2 x + 1$ 为质数; 抵消掉其余的部分，剩下一个质数或者两个相邻正整数相加为质数。
$x < 0$ 时则只需考虑抵消掉其余的部分，剩下一个质数或者两个相邻正整数相加为质数的情况。这种情况下通过线性筛筛出 $4 e 7$ 的质数，二分查找留下一个或两个的方案获得答案。

#include <bits/stdc++.h>
using namespace std;
const int N = 4e7 + 5;
int vis[N], p[N], p1[N];
void init() {
    vis[0] = vis[1] = 1;
    int i, j;
    for (i = 2; i < N; i++) {
        if (!vis[i]) p[++p[0]] = i;

        for (j = 1; j <= p[0]; j++) {
            if (i * p[j] >= N) break;
            vis[i * p[j]] = 1;
            if (i % p[j] == 0) break;
        }
    }

    for (i = 1; i <= 20000001; i++) {
        if (vis[2 * i + 1] == 0) p1[++p1[0]] = i;
    }
}
bool ok(int x) { return vis[x] == 0; }
int solve(int x) {
    int ans = -1;
    if (x > 0) {
        if (x == 1) return 2;
        if (ok(x)) return 1;
        if (ok(x + x + 1)) return 2;
        if (ok(x + x - 1)) return 2;
        ans = 2 * x + 1;
        x = x + 1;
        int a1 = p[lower_bound(p + 1, p + 1 + p[0], x) - p];
        int a2 = p1[lower_bound(p1 + 1, p1 + 1 + p1[0], x) - p1];
        if (a1 <= a2)
            ans = ans + 2 * (a1 - x) + 1;
        else
            ans = ans + 2 * (a2 - x) + 2;
    } else if (x == 0)
        return 3;
    else {
        x = -x;
        ans = 2 * x + 1;
        x = x + 1;

        int a1 = p[lower_bound(p + 1, p + 1 + p[0], x) - p];
        int a2 = p1[lower_bound(p1 + 1, p1 + 1 + p1[0], x) - p1];
        if (a1 <= a2)
            ans = ans + 2 * (a1 - x) + 1;
        else
            ans = ans + 2 * (a2 - x) + 2;
    }
    return ans;
}
signed main() {
    init();
    int T, x;
    cin >> T;
    while (T--) {
        cin >> x;
        cout << solve(x) << endl;
    }
}

1005题 Median 中位数

题目大意
给定整数 $1 ， 2 ， ? ， n$ 。把这些数字分成 $m$ 个不相交的集合，使第 $j$ 个集合的中位数为 $b_j$ 。确定这是否可能。
注：这题中，偶数个数的集合的中位数取中间两个数中较小的那个。

分析
显然 $b_1, b_2, · · · , b_m$ 这 $m$ 个数要放在 $m$ 个不同的集合中，剩下的 $n ? m$ 个数字要放到这 $m$ 个集合里且不影响每个集合的中位数。使用一个例子以方便说明：假设 $n = 6, m = 2, b_1 = 3, b_2 = 5$ ，那么 $1, 2, ? ? ?, n$ 这些数会被 $b$ 分成 1,2 、4、 6 这三段，且任意两段中的任意一对数字可以配对消掉。所以最后剩下的所有数字一定是同一段内的。

因此讨论两种情况：
? 如果长度最大的段的数字个数不大于其它段的数字个数之和，那么最终要么全部消掉，要么剩下一个，且剩下的这个数可以在任何一段内。如果会剩下，不妨将最后一段的数字剩下一个，此时再把最后一段的数字放到中位数最小的集合中即可满足题意，所以答案为 YES。
? 如果长度最大的段的数字个数大于其它段的数字个数之和，那么最终剩下的所有数字都在最大的这段内。设中位数小于这一段的最小值的集合的个数为 $x$ ，容易发现当且仅当 $x$ 不小于这一段剩下的数字个数时有解。
时间复杂度 $O (n)$ 。

官方解法：

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	int T;
	cin >> T;
	while (T--) {
		int n, m;
		cin >> n >> m;
		assert(m >= 1 && m <= n && n <= 100000);
		vector<int> f(n + 2);
		f[n + 1] = 1;
		while (m--) {
			int v;
			cin >> v;
			assert(v >= 1 && v <= n);
			assert(f[v] == 0);
			f[v] = 1;
		}
		vector<pair<int, int> > size;
		int have = 0;
		int count = 0;
		for (int i = 1; i <= n + 1; i++) {
			if (f[i]) {
				if (have) {
					size.push_back(make_pair(have, count));
				}
				have = 0;
				count += 1;
			}
			else {
				have += 1;
			}
		}
		sort(size.begin(), size.end());
		if (size.empty()) {
			cout << "YES\n";
			continue;
		}
		int sum = 0;
		for (auto s : size) {
			sum += s.first;
		}
		if (size.back().first <= sum - size.back().first + size.back().second) {
			cout << "YES\n";
		}
		else {
			cout << "NO\n";
		}
	}
	return 0;
}

dp：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
int n,m,b[N],f[N],g[N];

int main(){ 
	ios::sync_with_stdio(0); cin.tie(0);
	int t; cin>>t;
	while(t--){
		cin>>n>>m;
		for(int i=1;i<=m;i++){
			cin>>b[i];
		}
		sort(b+1,b+m+1);
		
		for(int i=1;i<=m;i++) f[i]=g[i]=0;
		for(int i=1;i<=m;i++){
			f[i]=f[i-1]+b[i]-b[i-1];
			int h1=max(0,b[i]-b[i-1]-f[i-1]-1);
			g[i]=h1+max(0,g[i-1]-(b[i]-b[i-1]-1));
		}
		if(b[m]+f[m]>=n && b[m]+g[m]<=n) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
}