2019中国大学生程序设计竞赛（CCPC） - 网络选拔赛

目录

1001 ^&^
1002 array
1003 K-th occurrence
1004 path
1005 huntian oy
1006 Shuffle Card
1007 Windows Of CCPC
1008 Fishing Master
1009 Kaguya
1010 Touma Kazusa‘s function
1011 sakura

1001 ^&^

首先贪心，能不加就不加，只有两个都是1的时候才需要C。
可能最后导致C是0，这样要或上两个lowbit里面比较小的那个。

比如：

1011010
0100100

这个的话，假如或上1，就破坏了结果的最小性（结果从0变成了1）。

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


int main() {
#ifdef Yinku
    freopen("Yinku.in", "r", stdin);
#endif // Yinku
    int T;
    scanf("%d", &T);
    while(T--) {
        unsigned int A, B;
        scanf("%u%u", &A, &B);
        unsigned int C = 0;
        for(int i = 31; i >= 0; --i) {
            unsigned int bitmask = 1u << i;
            if((A & bitmask) && (B & bitmask))
                C |= bitmask;
        }
        if(C == 0)
            C |= min((A & -A), (B & -B));
        printf("%u\n", C);
    }
    return 0;
}

1002 array

xy说，反序建树，不在前面出现那就要么在后面出现，要么在前面被删除的集合里面出现。

貌似很有道理，因为题目问的是，[1,r]区间内不出现的第一个>=k的数，既然不在[1,r]里面出现就一定，要么在[r+1,n]里面出现，要么在[1,r]里面出现但是被删除了。
注意到要是反过来建立主席树的话，删除一个数就不需要改动主席树里的任何东西。

因为，要在[r+1,n]中寻找大于等于k的第一个数或者在被删除的集合中寻找大于等于k的第一个数，而这两个集合的并集恰好就是除去[1,r]中剩余的所有元素的集合。

那么根据这个思路用两个简单操作凑出一个静态主席树，常数略大。

#include<bits/stdc++.h>
#define mid ((l+r)>>1)
using namespace std;
typedef long long ll;

namespace FastIO {
#define BUF_SIZE 1000000
    bool IOError = 0;
    inline char NextChar() {
        static char buf[BUF_SIZE], *pl = buf + BUF_SIZE, *pr = buf + BUF_SIZE;
        if(pl == pr) {
            pl = buf, pr = buf + fread(buf, 1, BUF_SIZE, stdin);
            if(pr == pl) {
                IOError = 1;
                return -1;
            }
        }
        return *pl++;
    }
#undef BUF_SIZE

    inline bool Blank(char c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t';
    }

    template<class T> inline void Read(T &x) {
        char c;
        while(Blank(c = NextChar()));
        if(!IOError) {
            for(x = 0; '0' <= c && c <= '9'; c = NextChar())
                x = (x << 3) + (x << 1) + c - '0';
        }
    }

    template<class T> inline void Read2(T &x) {
        char c;
        bool f = 0;
        while(Blank(c = NextChar()));
        if(!IOError) {
            if(c == '-') {
                f = 1;
                c = NextChar();
            }
            for(x = 0; '0' <= c && c <= '9'; c = NextChar())
                x = (x << 3) + (x << 1) + c - '0';
        }
        if(f)
            x = -x;
    }

    template<class T> inline void PutChar(T x) {
        if(x > 9)
            PutChar(x / 10);
        putchar(x % 10 + '0');
    }

    template<class T> inline void Write(T &x) {
        PutChar(x);
        putchar('\n');
    }

    template<class T> inline void Write2(T &x) {
        if(x<0){
            putchar('-');
            PutChar(-x);
        }
        else
            PutChar(x);
        putchar('\n');
    }
}

using namespace FastIO;

const int MAXN = 100000 + 5;
int T[MAXN], tcnt;
int cnt[MAXN * 20], L[MAXN * 20], R[MAXN * 20];

int a[MAXN];

inline void init() {
    tcnt = 0;
}

inline int build(int l, int r) {
    int rt = ++tcnt;
    cnt[rt] = 0;
    if(l < r) {
        L[rt] = build(l, mid);
        R[rt] = build(mid + 1, r);
    }
    return rt;
}

inline int update(int pre, int l, int r, int x) {
    int rt = ++tcnt;
    R[rt] = R[pre];
    L[rt] = L[pre];
    cnt[rt] = cnt[pre] + 1;
    if(l < r) {
        if(x <= mid)
            L[rt] = update(L[pre], l, mid, x);
        else
            R[rt] = update(R[pre], mid + 1, r, x);
    }
    return rt;
}

const int INF = 1e9;

//查询[u+1,v]中排名为rk的数
inline int query1(int u, int v, int l, int r, int rk) {
    //比整个区间的数都多，那是INF
    if(rk > cnt[v] - cnt[u])
        return INF;
    //直到进入一个叶子
    while(l < r) {
        int tmp = cnt[L[v]] - cnt[L[u]];
        if(tmp < rk) {
            //整个左子树加起来的数量都是<rk，所以这个排名在右子树中
            rk -= tmp;
            u = R[u], v = R[v], l = mid + 1;
        } else {
            u = L[u], v = L[v], r = mid;
        }
    }
    //最后到达了一个叶子
    return l;
}

//查询[u+1,v]中值不超过va的数的个数
inline int query2(int u, int v, int l, int r, int va) {
    int res = 0;
    while(l < r && va < r) {
        if(mid <= va) {
            //整个左子树都是<=va
            res += cnt[L[v]] - cnt[L[u]];
            u = R[u], v = R[v], l = mid + 1;
        } else
            u = L[u], v = L[v], r = mid;
    }
    if(va >= l)
        res += cnt[v] - cnt[u];
    return res;
}

int n;

//[1,r]里面出现的第一个>=k的数,INF表示不存在
inline int Query(int r, int k) {
    int rk = query2(T[1 - 1], T[r], 1, n, k - 1);
    return query1(T[1 - 1], T[r], 1, n, rk + 1);
}

set<int> s;

int main() {
#ifdef Yinku
    freopen("Yinku.in", "r", stdin);
#endif // Yinku
    int Ti;
    Read(Ti);
    while(Ti--) {
        int m;
        Read(n),Read(m);
        for(int i = 1; i <= n; ++i)
            Read(a[i]);
        //反向建树
        init();
        T[0] = build(1, n);
        for(int i = n, j = 1; i >= 1; --i, ++j)
            T[j] = update(T[j - 1], 1, n, a[i]);
        s.clear();
        s.insert(n + 1);
        int LastAns = 0;
        int op, pos, r, k;
        while(m--) {
            Read(op);
            if(op == 1) {
                Read(pos);
                pos ^= LastAns;
                s.insert(a[pos]);

            } else {
                Read(r),Read(k);
                r ^= LastAns;
                k ^= LastAns;
                LastAns = Query(n - r, k);
                LastAns = min(LastAns, *s.lower_bound(k));
                Write(LastAns);
            }
        }
    }
    return 0;
}

1004 path

直接暴力找前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\n", ans[query[i]]);
        }
    }
    return 0;
}

1005 huntian oy

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

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

很明显把i提前：
\(\sum\limits_{i=1}^{n}i\varphi(i)\space - \space \sum\limits_{j=1}^{i}j[gcd(i,j)==1]\)

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

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

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

即：
\(-\frac{1}{2}+\frac{1}{2}\sum\limits_{i=1}^{n}i\varphi(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\n", 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);
    }
}