The 2019 Asia Nanchang First Round Online Programming Contest

传送门

A. Enju With math problem

题意：

给出\(a_1,\cdots,a_{100}\)，满足\(a_i\leq 1.5*10^8\)。

现在问是否存在一个\(pos\)，满足：

\[\forall x\in [1,100],a_x=\varphi(x+pos-1)
\]

思路：

假设素数间隔没有超过\(100\)，那就很简单，直接枚举\(a_i\)，判断\(a_i+1\)是否为素数，反解出\(pos\)再来逐一验证即可。
但是素数间隔很可能是超过\(100\)的。
因为\(\varphi\)为积性函数，所以考虑两个素数的乘积形式，假设为\(p*q\)，并且一定存在一个较小的素数\(p\)，乘以\(q\)可以让结果落在对应区间。

至于为什么，还是考虑素数间隔总体来说是比较小的，平均为\(logn\)级别，所以将一个素数乘以某个较小的数能大概率落到连续区间内...(好吧，我在口胡)

所以直接枚举一个较小的素数，然后利用欧拉函数性质，反解出\(pos\)，同样逐一验证即可。

注意及时break是一个比较重要的减枝，不然可能会T。

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 105;

namespace Miller_Rabin{

    ll mul(ll a, ll b, ll p) {

        a %= p, b %= p;

        ll ans = 0;

        while(b) {

            if(b & 1) {

                ans = ans + a;

                if(ans > p) ans -= p;

            }

            a = a + a;

            if(a > p) a -= p;

            b >>= 1;

        }

        return ans;

    }

    ll qp(ll a, ll b, ll p) {

        ll ans = 1; a %= p;

        while(b) {

            if(b & 1) ans = mul(ans, a, p);

            a = mul(a, a, p);

            b >>= 1;

        }

        return ans;

    }

    bool check(ll a, ll n, ll x, ll t) {

        ll ans = qp(a, x, n);

        ll last = ans;

        for(int i = 1; i <= t; i++) {

            ans = mul(ans, ans, n);

            if(ans == 1 && last != 1 && last != n - 1) return true;

            last = ans;

        }

        if(ans != 1) return true;

        return false;

    }

    bool go(ll n) {

        if(n == 1 || (n & 1) == 0) return false;

        if(n == 2) return true;

        ll x = n - 1, t = 0;

        while((x & 1) == 0) {x >>= 1, ++t;}

        srand(time(NULL));

        for(int i = 0; i < 8; i++) {

            ll a = rand() % (n - 1) + 1;

            if(check(a, n, x, t)) return false;

        }

        return true;

    }

}

int T, n;

int a[N];

int getphi(int x) {

    int ans = x;

    for(int i = 2; 1ll * i * i <= x; i++) {

        if(x % i == 0) {

            ans = ans / i * (i - 1);

            while(x % i == 0) x /= i;

        }

    }

    if(x > 1) ans = ans / x * (x - 1);

    return ans;

}

bool gao1() {

    int p = -1;

    for(int i = 1; i <= n; i++) {

        if(Miller_Rabin::go(a[i] + 1)) {

            p = a[i] + 2 - i;

            int f = 1;

            for(int j = 1; j <= n; j++) {

                if(a[j] != getphi(p + j - 1)) {

                    f = 0; break;

                }

            }

            if(f) {

                cout << "YES" << '\n' << p << '\n';

                return true;

            }

        }

    }

    return false;

}

const int prime[10] = {0, 2, 3, 5, 7, 11, 13};

void gao2() {

    int p = -1;

    for(int i = 1; i <= 4; i++) {

        for(int j = 1; j <= n; j++) {

            if(a[j] % (prime[i] - 1)) continue;

            int tmp = a[j] / (prime[i] - 1) + 1;

            if(Miller_Rabin::go(tmp)) {

                p = 1ll * tmp * prime[i] + 1 - j;

                int f = 1;

                for(int k = 1; k <= n; k++) {

                    if(a[k] != getphi(k + p - 1)) {

                        f = 0; break;

                    }

                }

                if(f) {

                    cout << "YES" << '\n' << p << '\n';

                    return;

                }

            }

        }

    }

    cout << "NO" << '\n';

}

int main() {

    ios::sync_with_stdio(false); cin.tie(0);

    cin >> T; n = 100;

    while(T--) {

        for(int i = 1; i <= n; i++) cin >> a[i];

        bool f = gao1();

        if(!f) gao2();

    }

    return 0;

}

B. Fire-Fighting Hero

题意：

这个题意有点绕，简单来说，就是给出一个点\(S\)和一个点集\(V\)，现在要求\(S\)和\(V\)到所有点最短路最大值的最小值。

思路：

显然从\(S\)出发只需要跑一次最短路即可。
那么对于点集\(V\)呢？因为我们可以看作同时从每个点集中的点出发，那么将其初始\(d\)赋为\(0\)就好了。

详见代码：

Code

#include<bits/stdc++.h>

typedef long long ll;

typedef unsigned long long ull;

typedef double db;

const int MAXN = 1e3+5,MAXM = 1e6+5,MOD = 1e9+7,INF = 0x3f3f3f3f,N=100050;

const ll INFL = 0x3f3f3f3f3f3f3f3f;

const db eps = 1e-9;

#define lson o<<1,l,m

#define rson o<<1|1,m+1,r

#define mid l + ((r-l)>>1)

#define rep(i,a,b) for(register int i=(a);i<=(b);i++)

#define pii pair<int,int>

#define vii vector<pii>

#define vi vector<int>

using namespace std;

struct Edge{

    int v,w,next;

}e[MAXM];

int t,n,m,S,k,C,x,y,w;

int head[MAXN],cnt;

bool vis[MAXN];

ll d[MAXN];

inline void addEdge(int u,int v,int w){

    e[++cnt]={v,w,head[u]};head[u]=cnt;

}

priority_queue<pair<ll,int>> q;

int main(){

    ios::sync_with_stdio(false);cin.tie(0);

    //freopen("../A.in","r",stdin);

    //freopen("../A.out","w",stdout);

    cin>>t;

    while(t--){

        cin>>n>>m>>S>>k>>C;

        for(int i=1;i<=n;i++)d[i]=INFL;

        for(int i=1;i<=n;i++)vis[i]=0;

        for(int i=1;i<=k;i++){

            cin>>x;

            q.push({0,x});

            d[x]=0;

        }

        for(int i=1;i<=n;i++)head[i]=0;

        cnt=0;

        for(int i=1;i<=m;i++){

            cin>>x>>y>>w;

            addEdge(x,y,w);addEdge(y,x,w);

        }

        while(q.size()){

            pair<ll,int> x=q.top();q.pop();

            int u=x.second;

            if(vis[u])continue;

            vis[u]=1;

            for(int i=head[u];i;i=e[i].next){

                int v=e[i].v;

                if(d[v] > d[u]+e[i].w){

                    d[v]=d[u]+e[i].w;

                    q.push({-d[v],v});

                }

            }

        }

        ll T=0;

        for(int i=1;i<=n;i++)T=max(T,d[i]);

        q.push({0,S});

        for(int i=1;i<=n;i++)d[i]=INFL;

        for(int i=1;i<=n;i++)vis[i]=0;

        d[S]=0;

        while(q.size()){

            pair<ll,int> x=q.top();q.pop();

            int u=x.second;

            if(vis[u])continue;

            vis[u]=1;

            for(int i=head[u];i;i=e[i].next){

                int v=e[i].v;

                if(d[v] > d[u]+e[i].w){

                    d[v]=d[u]+e[i].w;

                    q.push({-d[v],v});

                }

            }

        }

        ll H=0;

        for(int i=1;i<=n;i++){

            H=max(H,d[i]);

        }

        if(H<=T*C){

            cout<<H<<'\n';

        }else cout<<T<<'\n';

    }

    return 0;

}

C. Hello 2019

题意：

给出一个串\(T\)，现在有多个询问，对于每个询问，需要回答区间中最少删除多少个数，使得区间里面不含\(8102\)，但是含\(9102\)这样的子序列。

思路：

\(cf\)上面的一个原题...和那道题的做法一样，只是我们把串反过来处理即可。

Code

#include<bits/stdc++.h>

typedef long long ll;

typedef unsigned long long ull;

typedef double db;

const int MAXN = 2e5+5,MAXM = 1e6+5,MOD = 998244353,INF = 0x3f3f3f3f;

const ll INFL = 0x3f3f3f3f3f3f3f3f;

const db eps = 1e-9;

#define lson o<<1,l,m

#define rson o<<1|1,m+1,r

#define mid l + ((r-l)>>1)

#define rep(i,a,b) for(register int i=(a);i<=(b);i++)

#define pii pair<int,int>

#define vii vector<pii>

#define vi vector<int>

using namespace std;

int n,q,l,r;

char s[MAXN];

struct Matrix{

    int v[5][5];

    Matrix(){

        memset(v,0x3f,sizeof(v));

    }

    Matrix operator *(const Matrix &B)const{

        Matrix ans;

        for(int i=0;i<5;i++){

            for(int j=0;j<5;j++){

                for(int k=0;k<5;k++){

                    ans.v[i][j] = min(ans.v[i][j],v[i][k] + B.v[k][j]);

                }

            }

        }

        return ans;

    }

}f[MAXN<<2],ans;

inline void pushUp(int o){

    f[o] = f[o<<1]*f[o<<1|1];

}

void build(int o,int l,int r){

    if(l==r){

        for(int i=0;i<5;i++)f[o].v[i][i]=0;

        if(s[l]=='2'){

            f[o].v[0][0]=1;f[o].v[0][1]=0;

        }else if(s[l]=='0'){

            f[o].v[1][1]=1;f[o].v[1][2]=0;

        }else if(s[l]=='1'){

            f[o].v[2][2]=1;f[o].v[2][3]=0;

        }else if(s[l]=='9'){

            f[o].v[3][3]=1;f[o].v[3][4]=0;

        }else if(s[l]=='8'){

            f[o].v[3][3]=1;f[o].v[4][4]=1;

        }

        return ;

    }

    int m=mid;

    build(lson);build(rson);

    pushUp(o);

}

Matrix query(int o,int l,int r,int L,int R){

    if(l>=L&&r<=R){

        return f[o];

    }

    int m=mid;

    if(R<=m)return query(lson,L,R);

    if(L>m)return  query(rson,L,R);

    return query(lson,L,R)*query(rson,L,R);

}

int main(){

    ios::sync_with_stdio(false);

    //freopen("../A.in","r",stdin);

    //freopen("../A.out","w",stdout);

    cin>>n>>q;

    cin>>(s+1);

    reverse(s+1,s+1+n);

    build(1,1,n);

    for(int i=1;i<=q;i++){

        cin>>l>>r;

        l = n-l+1;

        r = n-r+1;

        ans=query(1,1,n,r,l);

        if(ans.v[0][4]>n)cout<<"-1\n";

        else cout<<ans.v[0][4]<<'\n';

    }

    return 0;

}

E. Magic Master

模拟题，没什么好说的，倒过来模拟即可。

可以使用双端队列来搞，速度很快，因为双端队列可以支持随机访问。

Code

#include <cstdio>

#include <cstring>

#include <cmath>

#include <cassert>

#include <algorithm>

#include<map>

#define REP(r,x,y) for(register int r=(x); r<y; r++)

#define REPE(r,x,y) for(register int r=(x); r<=y; r++)

#ifdef sahdsg

#define DBG(...) printf(__VA_ARGS__)

#else

#define DBG(...) (void)0

#endif

using namespace std;

typedef long long LL;

typedef pair<LL, LL> pll;

#define MAXN 307

int a[40000007]; int sz; int SZ;

const int hd=0, ed=1;

int nxt[40000007],prv[40000007];

int N,M,Q;

inline void lk(int l, int r) {

	nxt[l]=r; prv[r]=l;

}

inline void addf(bool k, int l) {

	a[sz+2]=l;

	lk(sz+2,nxt[hd]);

	lk(hd,sz+2);

	sz++;

}

inline void mvf() {

	int t=prv[ed];

	lk(prv[t],nxt[t]);

	lk(t,nxt[hd]);

	lk(hd,t);

	return;

}

inline void op() {

	prv[hd]=hd, nxt[ed]=ed;

	sz=0; lk(hd,ed); SZ=0;

	int now=Q-1;

	for(register int i=N; i>=1; i--) {

		if(sz!=SZ) {

			int t=M%(sz-SZ);

			if(t) {

				int r=ed;

				REP(i,0,t) {

					r=prv[r];

				}

				lk(prv[ed],nxt[hd]);

				lk(prv[r],ed);

				lk(hd,r);

			}

		}

		addf(true,i);

	}

}

int k[107],K[107];

map<int,int> mp;

int main()

{

    #ifdef sahdsg

    freopen("in.txt","r",stdin);

    #endif // sahdsg

	int T; scanf("%d", &T);

	while(0<T--) {

		scanf("%d%d%d", &N,&M,&Q);

		op();

		REP(i,0,Q) {

			scanf("%d", &k[i]);

			K[i]=k[i];

		}

		int cnt=0,p=0;

		mp.clear();

		sort(K,K+Q);

		for(int i=nxt[hd]; i!=ed; i=nxt[i]) {

			p++;

			if(K[cnt]==p) mp[p]=a[i],cnt++;

		}

		REP(i,0,Q) {

			printf("%d\n", mp[k[i]]);

		}

	}

}

G. Pangu Separates Heaven and Earth

愉快签到。

Code

#include<bits/stdc++.h>

typedef long long ll;

typedef unsigned long long ull;

typedef double db;

const int MAXN = 1e5+5,MAXM = 1e6+5,MOD = 1e9+7,INF = 0x3f3f3f3f,N=100050;

const ll INFL = 0x3f3f3f3f3f3f3f3f;

const db eps = 1e-9;

#define lson o<<1,l,m

#define rson o<<1|1,m+1,r

#define mid l + ((r-l)>>1)

#define rep(i,a,b) for(register int i=(a);i<=(b);i++)

#define pii pair<int,int>

#define vii vector<pii>

#define vi vector<int>

using namespace std;

int t,n;

int main(){

    ios::sync_with_stdio(false);cin.tie(0);

    //freopen("../A.in","r",stdin);

    //freopen("../A.out","w",stdout);

    cin>>t;

    while(t--){

        cin>>n;

        if(n==1)cout<<"18000\n";

        else cout <<"0\n";

    }

    return 0;

}

H. The Nth Item

题意：

定义递推式：

\[\begin{aligned}
F(0) = 0&, F(1) = 1\\
F(n)=3*F(n-1)&+2*F(n-2),(n\geq 2)
\end{aligned}
\]

现在给出\(Q\)组询问，\(Q\leq 10^7\)，对于每次询问，回答\(F(n),n\leq 10^{18}\)。

思路：

一开始打了个表找循环节，打到5000w都没出来；
后面灵光一现，从\(MOD\)往前面打，找出循环节\(P=\frac{MOD-1}{2}\)。
那么对于每次询问，直接上\(BM\)或者矩阵快速幂即可，加个记忆化就能过了。

P.S:矩阵快速幂的话可以用\(k\)进制快速幂，然后预处理转移矩阵的\(1,2,\cdots,2^k\)即可。这样的话每次询问大概就是\(2*2*3\)的复杂度。

题解的做法大概就是利用特征根法解得通项，然后预处理出快速幂，对于每次询问直接算就行了。

因为通项有个\(\sqrt{17}\)，解决办法就是二次剩余。

Code

#include<bits/stdc++.h>

#define rep(i,a,n) for (int i=a;i<n;i++)

#define SZ(x) ((int)(x).size())

const int MAXN = 2e5 + 5, INF = 0x3f3f3f3f, MOD = 998244353, P = 499122176;

using namespace std;

#define lson o<<1,l,m

#define rson o<<1|1,m+1,r

#define mid l + ((r-l)>>1)

#define pb push_back

typedef vector<int> VI;

typedef long long ll;

ll powMOD(ll a, ll b) {

    ll ans = 1;

    for (; b; b >>= 1, a = a * a%MOD)if (b & 1)ans = ans * a%MOD;

    return ans;

}

namespace linear_seq {

    const int N = 10010;

    ll res[N], base[N], _c[N], _md[N];

    vector<int> Md;

    void mul(ll *a, ll *b, int k) {

        rep(i, 0, k + k) _c[i] = 0;

        rep(i, 0, k) if (a[i]) rep(j, 0, k) _c[i + j] = (_c[i + j] + a[i] * b[j]) % MOD;

        for (int i = k + k - 1; i >= k; i--) if (_c[i])

            rep(j, 0, SZ(Md)) _c[i - k + Md[j]] = (_c[i - k + Md[j]] - _c[i] * _md[Md[j]]) % MOD;

        rep(i, 0, k) a[i] = _c[i];

    }

    int solve(ll n, VI a, VI b) { // a 系数 b 初值 b[n+1]=a[0]*b[n]+...

        ll ans = 0, pnt = 0;

        int k = SZ(a);

        assert(SZ(a) == SZ(b));

        rep(i, 0, k) _md[k - 1 - i] = -a[i]; _md[k] = 1;

        Md.clear();

        rep(i, 0, k) if (_md[i] != 0) Md.push_back(i);

        rep(i, 0, k) res[i] = base[i] = 0;

        res[0] = 1;

        while ((1ll << pnt) <= n) pnt++;

        for (int p = pnt; p >= 0; p--) {

            mul(res, res, k);

            if ((n >> p) & 1) {

                for (int i = k - 1; i >= 0; i--) res[i + 1] = res[i]; res[0] = 0;

                rep(j, 0, SZ(Md)) res[Md[j]] = (res[Md[j]] - res[k] * _md[Md[j]]) % MOD;

            }

        }

        rep(i, 0, k) ans = (ans + res[i] * b[i]) % MOD;

        if (ans < 0) ans += MOD;

        return ans;

    }

    VI BM(VI s) {

        VI C(1, 1), B(1, 1);

        int L = 0, m = 1, b = 1;

        rep(n, 0, SZ(s)) {

            ll d = 0;

            rep(i, 0, L + 1) d = (d + (ll)C[i] * s[n - i]) % MOD;

            if (d == 0) ++m;

            else if (2 * L <= n) {

                VI T = C;

                ll c = MOD - d * powMOD(b, MOD - 2) % MOD;

                while (SZ(C) < SZ(B) + m) C.pb(0);

                rep(i, 0, SZ(B)) C[i + m] = (C[i + m] + c * B[i]) % MOD;

                L = n + 1 - L; B = T; b = d; m = 1;

            }

            else {

                ll c = MOD - d * powMOD(b, MOD - 2) % MOD;

                while (SZ(C) < SZ(B) + m) C.pb(0);

                rep(i, 0, SZ(B)) C[i + m] = (C[i + m] + c * B[i]) % MOD;

                ++m;

            }

        }

        return C;

    }

    int gao(VI a, ll n) {

        VI c = BM(a);

        c.erase(c.begin());

        rep(i, 0, SZ(c)) c[i] = (MOD - c[i]) % MOD;

        return solve(n, c, VI(a.begin(), a.begin() + SZ(c)));

    }

};

VI f;

void pre() {

    int a = 0, b = 1, c;

    f.push_back(a); f.push_back(b);

    for(int i = 1; i <= 2; i++) {

        c = 2 * a + 3 * b; f.push_back(c);

        a = b; b = c;

    }

}

int q;

ll n;

unordered_map <int, int> mp;

int main() {

    ios::sync_with_stdio(false); cin.tie(0);

    pre();

    cin >> q >> n;

    int ans = linear_seq :: gao(f, n);

    int last = ans;

    for(int i = 2; i <= q; ++i) {

        n = n ^ (1ll * last * last);

        int now = n % P;

        if(mp[now]) {

            last = mp[now];

        } else last = linear_seq :: gao(f, n % P);

        ans ^= last;

        mp[now] = last;

    }

    cout << ans;

    return 0;

}

巴特西

The 2019 Asia Nanchang First Round Online Programming Contest

A. Enju With math problem

B. Fire-Fighting Hero

C. Hello 2019

E. Magic Master

G. Pangu Separates Heaven and Earth

H. The Nth Item

最新文章

热门文章