1001. Prime Minister

Mr. Hacker's Department of Administrative Affairs (DAA) has infinite civil servants. Every integer is used as an id number by exactly one civil servant. Mr. Hacker is keen on reducing overmanning in civil service, so he will only keep people with consecutive id numbers in [l,r] and dismiss others.

However, permanent secretary Sir Humphrey's id number is x and he cannot be kicked out so there must be l≤x≤r. Mr. Hacker wants to be Prime Minister so he demands that the sum of people's id number ∑ri=li must be a prime number.

You, Bernard, need to make the reduction plan which meets the demands of both bosses. Otherwise, Mr. Hacker or Sir Humphrey will fire you.

Mr. Hacker would be happy to keep as few people as possible. Please calculate the minimum number of people left to meet their requirements.

A prime number p is an integer greater than 1 that has no positive integer divisors other than 1 and p.

题目大意:选择一段连续区间,且区间和是一个素数,给你一个必须包含的数字, 结果返回所得区间的长度.

本场唯一过的一道题…(太菜了),总的来说,题目中说让我们寻找区间和是一个素数, 那么我们必定以所给必须包含元素做讨论:

1. 如果所给数字为非负数

假设给我们的数字为num,首先我们明确一点那就是, 三个及三个以上的连续正整数之和必定不是素数, 这个很容易想到. 因为 所以我们首先想到的是了答案长度为这两种情况,所以也就是 判定 ,,这三者是否为素数. 这也是最简单的情况.
如果以上三种情况不可取,那么我们会想到利用0左边的区间来抵消右边的区间来达到左边的正整数个数不超过2, 也就是对于num如果不满足以上三种情况简单, 那么我们可以将左区间扩展到, 来使区间和归零, 然后重新重复对下一个元素来判断上述简单的三种情况.

2. 如果所给数字为正数

假定给定的数字为, 将数字右端加上来使区间归零,然后按照1中的情况继续来求解即可.

另外,关于素数的判断,我们可以用素数筛也可以使用快速判断素数模板.

#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#define maxn (2 * 10000005)
#define mem memset
using namespace std;
int prime[maxn] = {0};
int visit[maxn] = {0};
void Prime() {
    for (int i = 2; i <= maxn; i++) {
        if (!visit[i]) {
            prime[++prime[0]] = i;
        }
        for (int j = 1; j <= prime[0] && i * prime[j] <= maxn; j++) {
            visit[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                break;
            }
        }
    }
}
int main()
{
    int t;
    bool isfu = false;
    long long res= 1;
    scanf("%d", &t);
    Prime();
    while (t--)
    {
        int n;
        int cur;
        res = 1;
        isfu = false;
        scanf("%d", &n);
        if (n == 0) {printf("3\n"); continue;}
        else if(n==1){printf("2\n"); continue;}
        else if(n < 0){
            n = -n;
            res = 2 * n + 1;
            n = n+1;
            isfu = true;
            res++;
        }
        if(visit[n] == 0) {cout << res << endl; continue;}
        else if( !isfu && (visit[n+n+1] ==0 || visit[n+n-1] == 0)) {cout << 2 << endl; continue;}
        else if(isfu && visit[n+n+1] == 0) {cout << res + 1 << endl; continue;}
        else{
            if(!isfu) res += 2 * n;
            else  res += 1;
            cur = n + 1;
            while(true){
                if(visit[cur] == 0){
                    res += 1;
                    break;
                }else if(visit[cur + cur + 1] == 0){
                    res += 2;
                    break;
                }else{
                    res += 2;
                    cur = cur + 1;
                }
            }
        }
        cout << res << endl;
    }
    return 0;
}

1004. Median

Mr. docriz has n different integers 1,2,⋯,n. He wants to divide these numbers into m disjoint sets so that the median of the j-th set is bj. Please help him determine whether it is possible.

Note: For a set of size k, sort the elements in it as c1,c2,⋯,ck, the median of this set is defined as c⌊(k+1)/2⌋.

题意,给你n,m 并且给出m个bi, 需要构造一个数组c, 这样的数组可以被分割成m个区间后,每个区间的中位数为bi, 且数组是由1,2,3…n构成的,且唯一,你需要判断时候可以构造出这样的数组.

思路 :中位数可以将区间分成许多子区间,可以假设最大子区间找出最大的子区间长度, 然后如果剩余区间的长度之和小于其他的区间长度, 那么一定存在解,直接输出‘yes’

如果大于其他的区间长度, 那么就会多余,其中代表最初子区间的长度,代表其他区间的长度总和, 那么我们求得小于最大区间最小值, 也就是最大长度块前面的块数, 我们将最大区间里面的多余数字全部放在前面块的末尾, 这样前面的块依然满足中位数的条件, 所以对于这种情况我们直接判断 和的大小就可以了.

#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#define maxn (2 * 10000005)
#define mem memset
using namespace std;
vector<vector<int> > v;
int a[N];
int st[N];

int cnt;
void solve(){
    int n,m;
    cin >> n >> m;
    v.resize(m + 2);
    for(int i = 1;i <= cnt;i ++) v[i].clear();
    cnt = 1;
    for(int i = 1;i <= n;i ++) st[i] = 0;
    
    for(int i = 1;i <= m;i ++) {
        cin >> a[i];
        st[a[i]] = 1;
    }
    for(int i = 1;i <= n;i ++) {
        if(!st[i]) {
            v[cnt].push_back(i);
        }else if(v[cnt].size()){
            cnt ++;
        }
    }
    int maxn = 0;
    int sum = 0;
    int id = 0;
    for(int i = 1;i <= cnt;i ++) {
        int k = v[i].size();
        if(maxn < k) {
            id = i;
            maxn = k;
        }
        sum += k;
    }
    sum -= maxn;
    if(n == m) {
        cout << "YES" << endl;
        return;
    }
    if(maxn < sum) {
        cout << "YES" << endl;
        return;
    }
    maxn -= sum;
    int res = 0;
    for(int i = 1;i <= m;i ++) {
        if(a[i] < v[id][0]) res ++;
    }
    if(res >= maxn) {
        cout << "YES" << endl;
    }else {
        cout << "NO" << endl;
    }
}