2019中国大学生程序设计竞赛（CCPC）

直接暴力找前k短。假如是强行bfs插入的话会被爆空间。这个时候考虑一下问题的特性，其实是要前k短。那么对每个边排序，每个点插入最小的边。当这个边被弹出的时候再把兄弟边和后继点的最小边插进来，因为兄弟边和后继点的最小边肯定不会比当前边更好所以枚举顺序正确。而这样枚举的确也不会遗漏任何一个情况，不像那种根据长度暴力剪枝的做法，因为每个路径必定有一个开始的边，然后经过一系列的后继边，这样保证只要他足够小就会被算法枚举到。

单组复杂度 (O(n+m*logm+q+maxk*log(n+maxk))) ，按题目的规模近似 (O(nlogn)) 。

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

const int MAXN = 50000 + 5;

struct Edge {
    int v, w;
    bool operator<(const Edge& e)const {
        return w < e.w;
    }
} e;

vector<Edge> G[MAXN];

struct Path {
    ll len;
    int u, v;
    int id;
    bool operator<(const Path& p)const {
        return len > p.len;
    }
} p, tmp;

priority_queue<Path> pq;

void Init(int n) {
    for(int i = 1; i <= n; ++i)
        G[i].clear();
    while(!pq.empty())
        pq.pop();
}

int query[MAXN];
ll ans[MAXN];

int main() {
#ifdef Yinku
    freopen("Yinku.in", "r", stdin);
#endif // Yinku
    int T;
    scanf("%d", &T);
    while(T--) {
        int n, m, q;
        scanf("%d%d%d", &n, &m, &q);
        Init(n);
        while(m--) {
            int u;
            scanf("%d%d%d", &u, &e.v, &e.w);
            G[u].push_back(e);
        }
        for(int i = 1; i <= n; ++i) {
            if(G[i].size()) {
                sort(G[i].begin(), G[i].end());
                p.len = G[i][0].w;
                p.u = i;
                p.v = G[i][0].v;
                p.id = 0;
                pq.push(p);
            }
        }
        int maxquery = 0;
        for(int i = 1; i <= q; ++i) {
            scanf("%d", &query[i]);
            maxquery = max(maxquery, query[i]);
        }
        for(int i = 1; i <= maxquery; ++i) {
            p = pq.top();
            pq.pop();
            ans[i] = p.len;
            ll len = p.len;
            int u = p.u;
            int id = p.id;
            if(id + 1 < G[u].size()) {
                tmp.len = len - G[u][id].w + G[u][id + 1].w;
                tmp.u = u;
                tmp.v = G[u][id + 1].v;
                tmp.id = id + 1;
                pq.push(tmp);
            }

            int v = p.v;
            if(G[v].size()) {
                tmp.len = len + G[v][0].w;
                tmp.u = v;
                tmp.v = G[v][0].v;
                tmp.id = 0;
                pq.push(tmp);
            }
        }

        for(int i = 1; i <= q; ++i) {
            printf("%lld
", ans[query[i]]);
        }
    }
    return 0;
}

1005 huntian oy

zf知道后面那串东西当a,b互质的时候就是i-j，那么变成求 (sumlimits_{i=1}^{n}sumlimits_{j=1}^{i}(i-j)[gcd(i,j)==1]) 。

要求：
(sumlimits_{i=1}^{n}sumlimits_{j=1}^{i}(i-j)[gcd(i,j)==1])

很明显把i提前：
(sumlimits_{i=1}^{n}ivarphi(i)space - space sumlimits_{j=1}^{i}j[gcd(i,j)==1])

后面那个是求：
(sumlimits_{i=1}^{n}i[gcd(i,n)==1])

显然：
(sumlimits_{i=1}^{n}i[gcd(i,n)==1] = frac{n}{2}([n==1]+varphi(n)))

代进去得到：
(sumlimits_{i=1}^{n}ivarphi(i) - frac{i}{2}([i==1]+varphi(i)))

即：
(-frac{1}{2}+frac{1}{2}sumlimits_{i=1}^{n}ivarphi(i))

这个是卷个g=id就可以得到了。

写得太豪放了差点T了，收敛一点的话还是很稳的。

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

const int mod = 1e9 + 7;

int qpow(ll x, int n) {
    ll res = 1;
    while(n) {
        if(n & 1)
            res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}

const int inv2 = (mod + 1) >> 1;
const int inv6 = qpow(6, mod - 2);

const int MAXN = pow(1e9, 2.0 / 3.0);

int pri[MAXN + 10], pritop;
int pk[MAXN + 10];
ll sum[MAXN + 10];

void sieve(int n = MAXN) {
    sum[1] = 1;
    pk[1] = 1;
    for(int i = 2; i <= n; i++) {
        if(!pk[i]) {
            pri[++pritop] = i;
            pk[i] = i;
            sum[i] = 1ll * i * (i - 1);
            if(sum[i] >= mod)
                sum[i] %= mod;
        }
        for(int j = 1, t; j <= pritop && (t = i * pri[j]) <= n; j++) {
            if(i % pri[j]) {
                pk[t] = pk[pri[j]];
                sum[t] = sum[i] * sum[pri[j]] ;
                if(sum[t] >= mod)
                    sum[t] %= mod;
            } else {
                pk[t] = pri[j] * pk[i];
                if(t == pk[t]) {
                    sum[t] = 1ll * t * (t - t / pri[j]) ;
                    if(sum[t] >= mod)
                        sum[t] %= mod;
                } else {
                    sum[t] = sum[pk[t]] * sum[t / pk[t]] ;
                    if(sum[t] >= mod)
                        sum[t] %= mod;
                }
                break;
            }
        }
    }

    for(int i = 2; i <= n; i++) {
        sum[i] += sum[i - 1];
        if(sum[i] >= mod)
            sum[i] -= mod;
    }

}

inline int s1(int n) {
    ll t = (1ll * n * (n + 1)) >> 1;
    if(t >= mod)
        t %= mod;
    return t;
}

inline int s2(ll n) {
    ll t = n * (n + 1ll);
    if(t >= mod)
        t %= mod;
    t *= inv6;
    if(t >= mod)
        t %= mod;
    t *= (2ll * n + 1ll);
    if(t >= mod)
        t %= mod;
    return t;
}

unordered_map<int, int> Sum;

//杜教筛
inline int GetSum(int n) {
    if(n <= MAXN)
        return sum[n];
    else if(Sum.count(n))
        return Sum[n];
    //f*g=id的前缀和
    ll ret = s2(n);
    for(int l = 2, r; l <= n; l = r + 1) {
        r = n / (n / l);
        ll tmp = (s1(r) - s1(l - 1));
        if(tmp < 0)
            tmp += mod;
        tmp *= GetSum(n / l);
        if(tmp >= mod)
            tmp %= mod;
        ret -= tmp;
        if(ret < 0)
            ret += mod;
    }
    return Sum[n] = ret; // 记忆化
}

inline int Ans(int n) {
    ll tmp = GetSum(n) - 1;
    if(tmp < 0)
        tmp += mod;
    tmp *= inv2;
    if(tmp >= mod)
        tmp %= mod;
    return tmp;
}

int main() {
#ifdef Yinku
    freopen("Yinku.in", "r", stdin);
#endif // Yinku
    sieve();
    int t;
    scanf("%d", &t);
    while(t--) {
        int n, a, b;
        scanf("%d%d%d", &n, &a, &b);
        printf("%d
", Ans(n));
    }
}

1006 Shuffle Card

一个非常搞的签到题，一开始以为要用个Treap去手写一些结构，写到Remove的时候一想不是用个set就可以了吗？

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

set<pair<int, int> > s;
int p[100005];

int main() {
#ifdef Yinku
    freopen("Yinku.in", "r", stdin);
#endif // Yinku
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) {
        int ai;
        scanf("%d", &ai);
        p[ai] = i;
        s.insert({p[ai], ai});
    }
    int cur = 0;
    for(int i = 1; i <= m; ++i) {
        int ai;
        scanf("%d", &ai);
        s.erase({p[ai], ai});
        p[ai] = cur--;
        s.insert({p[ai], ai});
    }
    for(auto si : s) {
        printf("%d ", si.second);
    }
}

但最后发现直接把输入离线倒过来输出就行了？？？

1007 Windows Of CCPC

分形签到题，把队友演了几分钟，下次不管阶，直接算长度，想好再上机。

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

char g[1050][1050];
void draw(int x, int y, int len, char d1, char d2) {
    if(len == 1) {
        g[x][y] = d1;
        return;
    }
    len >>= 1;
    draw(x, y, len, d1, d2);
    draw(x, y + len, len, d1, d2);
    draw(x + len, y, len, d2, d1);
    draw(x + len, y + len, len, d1, d2);
}

int main() {
#ifdef Yinku
    freopen("Yinku.in", "r", stdin);
#endif // Yinku
    int T;
    scanf("%d", &T);
    for(int i = 1; i <= T; ++i) {
        int len;
        scanf("%d", &len);
        len = 1 << len;
        memset(g, 0, sizeof(g));
        draw(1, 1, len, 'C', 'P');
        for(int i = 1; i <= len; ++i)
            puts(g[i] + 1);
    }
    return 0;
}

1008 Fishing Master

当时一点都不会，zf力挽狂澜。看了一下一个比较好的思路是这样。

首先炖鱼的总时间是固定的，记为T，就是要合理安排去抓鱼的时间，也就是找一些空挡去抓鱼。那么每条鱼炖的时间就可以直接模k了，除以k的商就是额外抓鱼的次数。假如额外抓鱼的次数够了n-1次，那么答案就是T+k。否则一定会有某些鱼在炖的时候要去抓鱼而浪费锅时。

这里的贪心策略就是要浪费尽可能少的锅时，每条鱼的模k余数记为t，那么去抓鱼的时候会浪费k-t，找最小的几个浪费，直到补满额外抓鱼的次数。

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

const int MAXN = 1e5 + 5;
const int INF = 1e9;
int t[MAXN];

int main() {
#ifdef Yinku
    freopen("Yinku.in", "r", stdin);
#endif // Yinku
    int Ti;
    scanf("%d", &Ti);
    while(Ti--) {
        int n, k;
        scanf("%d%d", &n, &k);
        ll sum = 0, T = k;
        int mi = INF;
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &t[i]);
            T += t[i];
            sum += t[i] / k;
            mi = min(mi, t[i] / k);
            //计算额外抓鱼的次数
        }
        sum -= mi;
        //提供额外抓鱼次数最少的那条鱼先抓起来，不会更差
        if(sum >= n - 1) {
            printf("%lld
", T);
        } else {
            for(int i = 1; i <= n; ++i) {
                t[i] = k - (t[i] % k);
                //现在ti是每条鱼炖的时候去抓要浪费的锅的时间
            }
            sort(t + 1, t + 1 + n);
            int i = 1;
            while(sum < n - 1) {
                T += t[i];
                ++sum;
                ++i;
            }
            printf("%lld
", T);
        }
    }
    return 0;
}