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.

題目大意:選擇一段連續(xù)區(qū)間,且區(qū)間和是一個素數(shù),給你一個必須包含的數(shù)字, 結(jié)果返回所得區(qū)間的長度.

本場唯一過的一道題…(太菜了),總的來說,題目中說讓我們尋找區(qū)間和是一個素數(shù), 那么我們必定以所給必須包含元素做討論:

1. 如果所給數(shù)字為非負(fù)數(shù)

假設(shè)給我們的數(shù)字為num,首先我們明確一點那就是, 三個及三個以上的連續(xù)正整數(shù)之和必定不是素數(shù), 這個很容易想到. 因為 所以我們首先想到的是了答案長度為這兩種情況,所以也就是 判定 ,,這三者是否為素數(shù). 這也是最簡單的情況.
如果以上三種情況不可取,那么我們會想到利用0左邊的區(qū)間來抵消右邊的區(qū)間來達(dá)到左邊的正整數(shù)個數(shù)不超過2, 也就是對于num如果不滿足以上三種情況簡單, 那么我們可以將左區(qū)間擴(kuò)展到, 來使區(qū)間和歸零, 然后重新重復(fù)對下一個元素來判斷上述簡單的三種情況.

2. 如果所給數(shù)字為正數(shù)

假定給定的數(shù)字為, 將數(shù)字右端加上來使區(qū)間歸零,然后按照1中的情況繼續(xù)來求解即可.

另外,關(guān)于素數(shù)的判斷,我們可以用素數(shù)篩也可以使用快速判斷素數(shù)模板.

#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, 需要構(gòu)造一個數(shù)組c, 這樣的數(shù)組可以被分割成m個區(qū)間后,每個區(qū)間的中位數(shù)為bi, 且數(shù)組是由1,2,3…n構(gòu)成的,且唯一,你需要判斷時候可以構(gòu)造出這樣的數(shù)組.

思路 :中位數(shù)可以將區(qū)間分成許多子區(qū)間,可以假設(shè)最大子區(qū)間找出最大的子區(qū)間長度, 然后如果剩余區(qū)間的長度之和小于其他的區(qū)間長度, 那么一定存在解,直接輸出‘yes’

如果大于其他的區(qū)間長度, 那么就會多余,其中代表最初子區(qū)間的長度,代表其他區(qū)間的長度總和, 那么我們求得小于最大區(qū)間最小值, 也就是最大長度塊前面的塊數(shù), 我們將最大區(qū)間里面的多余數(shù)字全部放在前面塊的末尾, 這樣前面的塊依然滿足中位數(shù)的條件, 所以對于這種情況我們直接判斷 和的大小就可以了.

#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;
    }
}