The 2019 Asia Nanchang First Round Online Programming Contest

E. Magic Master

比赛的时候xy用链表弄了一个，赛后发现deque更快，可能原因是deque内存中连续。总之deque是一种高效的数据结构，甚至可以随机访问随机删除，自动管理的分块数组？只不过不能手动在块上维护信息就是麻烦点。

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

deque<int> dq;

int main() {
    int T;
    scanf("%d", &T);
    for(int ti = 1; ti <= T; ++ti) {
        int n, m;
        scanf("%d%d", &n, &m);
        dq.push_back(n);
        for(int i = n - 1; i >= 1; --i) {
            for(int mi = 1; mi <= m; ++mi) {
                dq.push_back(dq.front());
                dq.pop_front();
            }
            dq.push_back(i);
        }

        int Q;
        scanf("%d", &Q);
        for(int qi = 1, q; qi <= Q; ++qi) {
            scanf("%d", &q);
            printf("%d\n", dq[n - q]);
        }
        dq.clear();
    }
    return 0;
}

B. Fire-Fighting Hero

理解错题意了，出题方有点东西。在新的题意背景下所有的消防队是同一个单源出发的，只需要找一个超级源连一条权为0的边即可。

A. Enju With math problem

先暴力判前200个质数防止后面出些小东西。

看起来是要先拉出1.5e8的那几个为数不多的质数，检测一下他们周围是不是有，花的复杂度不高。然后把所有这些质数乘以2得到一些合数2p，那么（除了22=4以外）根据欧拉函数的积性性质，他们的欧拉函数一定是phi(2p)=phi(2)phi(p)，根据这些合数定位再找一遍。

根据下面这个验证程序可以知道，当进行了多次筛之后可以保证每个区间都至少包含一个这样的数。

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

const int MAXN = 1e8 + 5e7;
bool np[MAXN + 5];
bool _2p[MAXN + 5], _3p[MAXN + 5];
bool _5p[MAXN + 5], _7p[MAXN + 5];
bool _11p[MAXN + 5], _17p[MAXN + 5];
int p[8444396 + 5], ptop;
void sieve() {
    np[1] = 1;
    ptop = 0;
    for(int i = 2; i <= MAXN; ++i) {
        if(!np[i]) {
            p[++ptop] = i;
        }
        for(int j = 1; j <= ptop; ++j) {
            ll t = i * p[j];
            if(t > MAXN)
                break;
            np[t] = 1;
            if(i % p[j] == 0)
                break;
        }
    }
    //printf("ptop=%d\n",ptop);
    for(int i = 1; i <= ptop; ++i) {
        if(2ll * p[i] > MAXN)
            break;
        _2p[p[i] * 2] = 1;
    }
    for(int i = 1; i <= ptop; ++i) {
        if(3ll * p[i] > MAXN)
            break;
        _3p[p[i] * 3] = 1;
    }
    for(int i = 1; i <= ptop; ++i) {
        if(5ll * p[i] > MAXN)
            break;
        _5p[p[i] * 5] = 1;
    }
    for(int i = 1; i <= ptop; ++i) {
        if(7ll * p[i] > MAXN)
            break;
        _7p[p[i] * 7] = 1;
    }
    for(int i = 1; i <= ptop; ++i) {
        if(11ll * p[i] > MAXN)
            break;
        _11p[p[i] * 11] = 1;
    }
    for(int i = 1; i <= ptop; ++i) {
        if(17ll * p[i] > MAXN)
            break;
        _17p[p[i] * 17] = 1;
    }
    int maxdis = 0, pre = 2;
    for(int i = 3; i <= MAXN; ++i) {
        if((!np[i]) || _2p[i] || _3p[i] || _5p[i] || _7p[i] || _11p[i] || _17p[i]) {
            maxdis = max(maxdis, i - pre);
            pre = i;
        }
    }
    printf("maxdis=%d\n", maxdis);
}

int main() {
    sieve();

    return 0;
}

C. Hello 2019

这个看起来就像早上的wrong那道题。

The 2019 Asia Nanchang First Round Online Programming Contest

原文：https://www.cnblogs.com/Inko/p/11489007.html