20180901南京网络赛题解

A. An Olympian Math Problem

签到题，输出n-1即可。

J. Sum

MEANING

对于一个数n，对其质因数分解，f(n)为其指数为1质因数的数量乘2，如果某一质因数指数为3或以上，f(n)=0，特别的，f(1) = 1。
求(S(n)=sum_{i=1}^nf(i))

SOLUTION

2e7的数据范围，考虑线性解法欧拉筛。prime[i]为保存的第i个素数。v[i]为当前枚举的数最小质因数。然后再用一个数组num[i]表示数i的最小质因数的指数。
首先要理解欧拉筛的原理，然后对于欧拉筛中枚举的第i个数：
（1）如果是质数，f[i] = 2。
对于枚举的素数prime[j]:
if prime[j]<i：f[i*prime[j]] = f[i]*2;
if prime[j]i：f[i*prime[j]] = f[i]/2;
（2）如果是合数，f[i] 已知。
对于枚举的素数prime[j]:
if prime[j]<v[i]：f[i*prime[j]] = f[i]*2;
if prime[j]v[i]：f[i*prime[j]] 在num[i]大于等于3时为0.否则为f[i]/2;

CODE

#define FILE_IN() freopen("C:\Users\dmt\Desktop\in.txt","r",stdin);
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 20000005;

ll f[MAXN];
int v[MAXN],prime[MAXN],num[MAXN];

void primes() {
    memset(v,0,sizeof(v));
    int m = 0;
    for(int i=2; i<=MAXN-3; i++) {
        if(v[i]==0) {
            v[i] = i;
            prime[++m] = i;
            f[i] = 2;
            num[i] = 1;
        }
        for(int j=1; j<=m; j++) {
            if(prime[j]>v[i]||prime[j]>(MAXN-3)/i)break;
            v[i*prime[j]] = prime[j];
            if(prime[j]<v[i]){num[i*prime[j]] = 1;f[i*prime[j]] = f[i]*2;}
            else {
                num[i*prime[j]] = num[i]+1;
                if(num[i*prime[j]]<=2)f[i*prime[j]] = f[i]/2;
                else f[i*prime[j]] = 0;
            }
        }
    }
}

int main() {
//    FILE_IN();
    fill(f,f+MAXN,1);
    f[1] = 1;
    primes();
    for(int i = 2;i<=MAXN-5;i++)f[i]+=f[i-1];
    int T;
    for(scanf("%d",&T); T; T--) {
        int n;
        scanf("%d",&n);
        printf("%lld
",f[n]);
    }
    return 0;
}

L. Magical Girl Haze

MEANING

给一个有向图G(N,M)。你可以选择最多K条边使其权值为0，问顶点1到N的最短路。

SOLUTION

分层图最短路，每个点记录k个状态的最短路，跑dijkstra。

CODE

#define FILE_IN() freopen("C:\Users\dmt\Desktop\in.txt","r",stdin);
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100005;
const ll INF = 200000000000005ll;
struct edge{
    int v,nex,w;
}ed[MAXN*2];

int head[MAXN],tot,n,m,k;

void addedge(int u,int v,int w){
    tot++;
    ed[tot].v = v;
    ed[tot].w = w;
    ed[tot].nex = head[u];
    head[u] = tot;
}

ll d[MAXN][11];
bool vis[MAXN][11];
struct node{
    ll d;
    int ind,used;
};
bool operator <(node a,node b){
    return a.d>b.d;
}
priority_queue<node>q;

void dij(){
    for(int i=0;i<=n;i++)for(int j=0;j<=10;j++){d[i][j] = INF;vis[i][j]=0;}
    for(int i=0;i<=k;i++)d[1][i] = 0;
    q.push({0ll,1,0});
    while(q.size()){
        node cur = q.top();
        q.pop();
        int u = cur.ind,used = cur.used;
        if(vis[u][used])continue;
        vis[u][used] = 1;
        for(int i = head[u];i;i=ed[i].nex){
            int v = ed[i].v,w = ed[i].w;
            if(d[v][used]>d[u][used]+w){
                d[v][used] = d[u][used]+w;
                q.push({d[v][used],v,used});
            }
            if(used+1<=k&&d[v][used+1]>d[u][used]){
                d[v][used+1] = d[u][used];
                q.push({d[v][used+1],v,used+1});
            }
        }
    }
}

void init(){
    tot = 0;
    memset(head,0,sizeof head);
}

int main() {
//    FILE_IN();
    int T;
    for(scanf("%d",&T);T;T--){
        scanf("%d%d%d",&n,&m,&k);
        init();
        for(int i=0;i<m;i++){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            addedge(u,v,w);
        }
        dij();
        ll ans = INF;
        for(int i=0;i<=10;i++){
            ans  = min(ans,d[n][i]);
        }
        printf("%lld
",ans);
    }
    return 0;
}