B - 修仙时在做什么？有没有空？可以来炼丹吗？

题目链接

M姓出题人：这么老的idea怎么还没人做XD

考虑到本题的idea非常古老，所以在预估难度时设为中等题，然而现场没人过。题意本质上就是给出一个含$2^{18}$个结点的无向连通图，再指定其中$n$个点，求这$n$个指定点的两两之间的最短路的最小值。

接下来的讨论假定$n$个指定点的编号两两不同（如果出现相同编号的话答案就是$0$）。我们不妨考虑二进制分组。枚举二进制位$0 \sim 17$，对每个枚举出的二进制位$2^k$，我们将这$n$个点按照编号对应的二进制位$2^k$为$0$还是$1$分成两组，从一组往另一组跑多起点最短路，然后取个最小值就没了，总复杂度$O(18n \log n)$。

为什么这样做是正确的呢？考虑答案一定是某个编号为$u$的结点到某个编号为$v$的结点的最短路，而$u \neq v$，则他们一定在某个二进制位上是不相同的。当我们按照前述操作枚举到这个不相同的二进制位时，$u$和$v$一定会分到不同组中，因此跑完多起点最短路后一定会计算出全局最小值，于是这题就做完了。

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int maxn = 2e5;
const int maxm = 18;
const int maxV = 1<<maxm;
const int INF = 0x3f3f3f3f;
const int P = 19260817;
int cost[maxV][maxm];
int start[maxn], mark[maxV], ans = INF, cc = INF, n;

inline LL PowMod(LL a, LL b) { LL r=1; while(b) { if(b&1) r=r*a%P; a=a*a%P, b>>=1; } return r; }

void init()
{
    for (int s = 0; s < maxV; ++s) {
        for(int i = 0; i < maxm; ++i)
        {
            cost[s][i] = PowMod( max(s,s^(1<<i))%P, 1<<i ) % P + 1;
        }
    }
}
struct node
{
    int u,dis;
    node(int _u=0, int _dis = 0): u(_u), dis(_dis){}
    bool operator <(const node& nn) const
    {
        return dis > nn.dis;
    }
};
priority_queue<node>que;
int dis[maxV];
void solve(int mask)
{
    while(!que.empty()) que.pop();
    for (int i = 0; i < maxV; ++i) dis[i] = INF;
    for (int i = 0; i < n; ++i)
        if(start[i] >> mask & 1) 
        {
            dis[start[i]] = 0;
            que.push(node(start[i], 0));
        }
    while(!que.empty())
    {
        node tmp = que.top(); que.pop();
        int u = tmp.u, d = tmp.dis;
        if(d >= ans) return;
        if(d != dis[u]) continue;
        if(d && mark[u])
        {
            ans = d;
            return;
        }
        for(int i = 0; i < maxm; ++i)
            if(dis[u^(1<<i)] > d + cost[u][i])
            {
                dis[u^(1<<i)] = d + cost[u][i];
                que.push(node(u^(1<<i), dis[u^(1<<i)]));
            }
    }
}
int main()
{
    init();
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) 
    {
        scanf("%d", &start[i]);
        if(mark[start[i]]==1) exit( puts("0")*0 );
        mark[start[i]] = 1;
    }
    for (int i = 0; i < maxm; ++i) solve(i);
    printf("%d\n",ans);
    return 0;
}

F - 翻牌游戏

题目链接

这是一道打表找规律概率DP题。其实这题的数据范围可以出很大，但在某C姓出题人的极力阻止下改成了现在这个范围，也就是说允许直接交概率DP （说到底还是因为CC handsome!）。

设$f[i][k]$表示当前有$i$对对子完全没有翻开过、$k$个对子已经翻开过恰好一张时，在最佳策略下翻完所有牌所需操作数的期望值。那么我们对每个状态有以下两种操作：

• 选两张都没有翻过的牌翻开；
• 选一张翻过的牌和一张没翻过的牌翻开。

仔细讨论每种操作下的转移即可，时间复杂度$O(n^2)$，然后你就会发现$ANS = 2n-1$。此外你还会发现，第二个操作只有在恰好剩两张牌翻过两张牌没翻过时才会进行。

其实这题可以出更难，因为通过打表可以发现$f[n][m] = 2n-1+\frac{3}{2}m+\frac{m}{2(2n+m)}$。。。不过为了提升参赛体验，就不出这么自闭了。

// CC!
#include<bits/stdc++.h>

using namespace std;

typedef double DB;

const int maxn = 5000;

DB f[maxn+5][maxn+5];
bool vi[maxn+5][maxn+5];

DB dfs(int n, int m) {
    if(vi[n][m]) return f[n][m];
    vi[n][m] = 1;
    if(n==0 && m==0) return f[n][m] = 0;

    f[n][m] = 1e9;
    int hd = n*2+m;

    // nn策略
    if(hd>=2) {
        DB tmp = 0;
        if(n>=1) tmp += DB(n*2.0) / (hd*(hd-1.0)) * (dfs(n-1,m)+1); // 2张未知且相同
        if(n>=2) tmp += (2.0*n*(2.0*n-2.0)) / DB(hd*(hd-1.0)) * (dfs(n-2,m+2)+1); // 2张未知但不同
        if(m>=2) tmp += DB(m*(m-1.0)) / DB(hd*(hd-1.0)) * (dfs(n,m-2)+3); // 2张已知
        if(n>=1 && m>=1) tmp += DB(4.0*n*m) / DB(hd*(hd-1.0)) * (dfs(n-1,m)+2); // 1张已知1张未知
        f[n][m] = min(f[n][m], tmp);
    }

    // nm策略
    if(m>0) {
        DB tmp = 0;
        tmp += 1.0 / DB(hd) * (dfs(n,m-1)+1); // 2张已知且相同
        if(m>=2) tmp += (m-1.0) / DB(hd) * (dfs(n,m-1)+2); // 2张已知但不同
        if(n>=1) tmp += (2.0*n) / DB(hd) * (dfs(n-1,m+1)+1); // 1张未知1张已知
        f[n][m] = min(f[n][m], tmp);
    }

    return f[n][m];
}

int main() {
    int _; scanf("%d", &_);
    while(_--) {
        int n; scanf("%d", &n);
        printf("%.2f\n", dfs(n,0) );
    }
    return 0;
}

H - Parco_Love_GCD

题目链接

这题原本的时间限制要更小，主要是为了卡掉RMQ的做法。但考虑到大家的参赛体验，就还是给多了时间让RMQ过了（现在来看或许不应该放水）。

两种做法。第一种做法是RMQ进行$O(n \log n \log 10^9)$的预处理搞出区间GCD值，然后每次就可以$O(\ log 10^9)$回答任意区间的GCD值。之后为了计算所有区间的GCD值之和，我们考虑$O(n)$枚举区间左端点，然后每次右端点从左往右二分+RMQ找到第一个会让区间GCD变化的位置，并累加答案。注意到右端点从左往右扫的过程中，GCD至多只会变化$O(\log 10^9)$次，所以这样做总复杂度就变成了$O(n \log n \log^2 10^9)$。

第二种做法是CDQ分治，也就是原本的正解。我们用函数$Solve(l,r)$来计算$[l,r]$的所有子区间的GCD之和。在每一层$Solve(l,r)$中，令$mid = \lfloor \frac{l+r}{2} \rfloor$，然后让左端点从$mid$往$l$扫，记录算出的GCD值及对应出现次数并扔到一个map里，同理让右端点从$mid+1$往$r$扫，将计算出的GCD值出现次数信息扔到另一个map里。现在我们有了两个map，他们的大小均不超过$O(\log 10^9)$，于是就可以$O(\log^2 10^9)$枚举两个map里的东西，同时$O(\log 10^9)$算一下GCD统计答案。

算一下第二种做法的复杂度。端点左右扫加上GCD以及map的复杂度后，所需的总复杂度为$O(n \log n \log 10^9)$。枚举map里的东西时，因为$Solve(1,n)$所涉及到的所有区间个数是$O(n)$级别的，所以这部分总复杂度为$O(n \log^3 10^9)$。综上CDQ分治的复杂度为$O(n (\log n \log 10^9 + \log ^3 10^9))$。

这里只贴CDQ分治的代码：

#include<bits/stdc++.h>

using namespace std;

#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,a,b) for(int i=a; i<=b; ++i)
#define PER(i,a,b) for(int i=a; i>=b; --i)
#define MP make_pair
#define PB push_back
#define fi first
#define se second
typedef long long LL;
typedef double DB;

const int maxn = 5e5;
const int maxV = 1e9;
const int P = 1e9+7;

LL Gcd(LL a, LL b) { return b ? Gcd(b,a%b) : a; }

map<int,int> s1, s2;
int n, ai[maxn+5];
LL ans = 0;

inline void Add(LL &a, LL b) { a+=b; if(a>=P) a-=P; }

void Solve(int l, int r) {
    if(l==r) { Add(ans, ai[l]); return; }
    int mid = (l+r)>>1;
    s1.clear();
    s2.clear();

    int now = 0;
    for(int i = mid; i >= l; --i) {
        now = Gcd(now, ai[i]);
        ++s1[now];
    }

    now = 0;
    for(int i = mid+1; i <= r; ++i) {
        now = Gcd(now, ai[i]);
        ++s2[now];
    }

    for(auto pp : s1) {
        for(auto qq : s2) {
            Add(ans, Gcd(pp.fi, qq.fi) * pp.se % P * qq.se % P);
        }
    }

    Solve(l, mid);
    Solve(mid+1, r);
}

int main() {
    scanf("%d", &n);
    assert(1<=n && n<=maxn);
    REP(i,1,n) scanf("%d", ai+i);
    Solve(1,n);
    printf("%lld\n", ans);
    return 0;
}

K - Parco_Love_String

题目链接

本题时间限制及数据范围继续放水，出题人现在就是很后悔_(:3」∠)_

第一种做法是Hash后STL乱搞，没什么好说的，唯一要注意的是现场专门卡掉了map，需要unordered_map或者pb_ds才能通过，但牛客上是没有卡map的。

第二种做法是SAM（后缀自动机）乱搞。问题的核心就是给出$A, B$两个串，如何快速$B$的每个子串在$A$中的出现次数之和。我们考虑对$A$建SAM，通过经典的Fail树结点基数排序后就可以算出SAM中每个结点对应的那个（那些）串在整个$A$串中的出现次数（代码中记为occ）。此外，对于每个SAM上每个结点的$len$成员（在标程代码中是val），预处理出它在SAM中对应的那个长度为$len$的串的所有子串在整个$A$串的出现次数之和（代码中记为sum）。然后拿$B$串在SAM上跑一遍顺便计个数就可以算出答案了，具体计数方法参考代码。总时间复杂度$O(n^2)$，比Hash不知道高到哪里去。

现场还有人用KMP也过了，大家可以自行思考，这里只贴SAM代码。

#include<bits/stdc++.h>

using namespace std;

#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,a,b) for(int i=a; i<=b; ++i)
#define PER(i,a,b) for(int i=a; i>=b; --i)
#define MP make_pair
#define PB push_back
#define fi first
#define se second
typedef long long LL;
typedef double DB;

const int maxn = 1000, c_size = 26;

struct State {
    int val;
    LL sum, occ;
    int par, go[c_size];
    void init() { val = 0, sum = 0, occ = 0, par = -1, mem(go,-1); }
}que[maxn*2+5];
int root, last;
int tot;

void Extend(int w) {
    int p = last, np = tot++;
    que[np].init();
    que[np].val = que[p].val+1;
    que[np].occ = 1;
    while(p!=-1 && que[p].go[w]==-1)
        que[p].go[w] = np, p = que[p].par;
    if(p == -1) que[np].par = root;
    else {
        int q = que[p].go[w];
        if(que[p].val+1 == que[q].val) que[np].par = q;
        else {
            int nq = tot++;
            que[nq] = que[q];
            que[nq].val = que[p].val+1;
            que[nq].occ = 0;
            que[np].par = que[q].par = nq;
            while(p!=-1 && que[p].go[w]==q)
                que[p].go[w] = nq, p = que[p].par;
        }
    }
    last = np;
}


char str[maxn+5];
LL f[maxn+5];
int cont[maxn+5], S[maxn*2+5];

int main() {
    scanf("%s", str+1);
    int n = strlen(str+1);
    for(int kk = 1; kk < n; ++kk) {
        root = last = 0;
        tot = 1, que[0].init();
        for(int i = 1; i <= kk; ++i) Extend(str[i]-'a');
        for(int i=0; i<=kk; ++i) cont[i] = 0;
        for(int i=0; i<tot; ++i) ++cont[que[i].val];
        for(int i=1; i<=kk; ++i) cont[i] += cont[i-1];
        for(int i=tot-1; i>=1; --i) S[--cont[que[i].val]] = i;
        for(int i = tot-1; i >= 1; --i) {
            int x = S[i];
            que[que[x].par].occ += que[x].occ;
        }
        for(int i = 1; i < tot; ++i) {
            int x = S[i];
            que[x].sum = que[que[x].par].sum;
            que[x].sum += LL(que[x].val-que[que[x].par].val) * que[x].occ;
        }
        int p = root;
        int now = 0;
        f[kk] = 0;
        for(int i = kk+1; i <= n; ++i) {
            int w = str[i]-'a';
            if(que[p].go[w] != -1) {
                p = que[p].go[w];
                ++now;
            }
            else {
                while(p!=-1 && que[p].go[w]==-1) p = que[p].par;
                if(p == -1) p = root, now = 0;
                else {
                    now = que[p].val+1;
                    p = que[p].go[w];
                }
            }
            if(now>0) {
                f[kk] += que[que[p].par].sum;
                f[kk] += LL(now - que[que[p].par].val) * que[p].occ;
            }
        }
    }
    int _; scanf("%d", &_);
    while(_--) {
        int kk; scanf("%d", &kk);
        printf("%lld\n", f[kk]);
    }
    return 0;
}

题目链接

这是一道经典题目改编，原题是dreamoon出的NTU-WF选拔赛D题（题目链接）。

不难发现，修复时所产生的花费，可以分解为一系列有向简单路径上结点权值之和。因此由期望的线性性可知，要求总花费的期望值，我们只需分别计算$n^2$条有向简单路径对总花费产生贡献的期望值。

对于树上一条有向简单路径$u \rightarrow v$，设该路径长度为$d \ (0 \leq d \leq n-1)$（也就是说有$d$条边，$d+1$个结点），路径上所有结点权值为$S$，那么结论就是：这条简单路径对总花费产生贡献的期望值为$\frac{S}{d}$ 。

为什么这个结论是正确的呢？首先要注意到，对于任意一个边修复顺序，交换除有向路径$u \rightarrow v$上的$d$条边以外的任意边的修复顺序，不影响有向路径$u \rightarrow v$对总花费的贡献。进一步分析我们发现，对于$u \rightarrow v$上的$d$条边，只有当连接着结点$u$的那条边是这$d$条边中最后一个被修复的边时，有向路径$u \rightarrow v$才会对总花费产生大小恰为$S$的贡献。不难证明“连接$u$的那条边在路径上的$d$条边中最后被修复”这一事件发生的概率为$\frac{1}{d}$，因此有向路径$u \rightarrow v$对最终总花费产生贡献的期望值就是$\frac{S}{d}$。

于是问题转化成，求树上所有有向路径的$\frac{\text{结点权值和}}{\text{路径长度}}$的和，而这可以通过树分治NTT计算。简单来说就是：我们每次找一个重心，对于重心的每个儿子对应的子树处理出两个值$cnt_i$和$val_i$，分别表示该子树中深度为$i$的结点个数，以及所有“深度为$i$的结点到该子树跟结点路径上的所有结点的权值之和”的和（如果没听懂就去看代码，反正我也应该听不懂）。于是我们对每棵子树都搞出了两个多项式。在每次计算跨越重心的贡献时，我们只需要合理利用$cnt_i$和$val_i$对应的多项式进行一波奥妙重重的NTT计数就统计出相应答案了，这之后再把这两棵子树的$cnt_i, val_i$分别合并即可。

需要注意的是，在计算某个分治出来的连通块的答案时，必须将子树按照对应多项式的大小排序，然后从小到大依次计算，否则会TLE（专门构造了卡未排序做法的数据，不过dreamoon出的那题没有卡掉未排序做法）。在有排序的做法下，处理每个连通块的时间复杂度为$O(size \log n)$，因此整个做法的复杂度为$O(n \log n \log n)$。

#include<bits/stdc++.h>

using namespace std;

#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,a,b) for(int i=a; i<=b; ++i)
#define PER(i,a,b) for(int i=a; i>=b; --i)
#define MP make_pair
#define PB push_back
#define fi first
#define se second
typedef long long LL;
typedef double DB;

const int maxn = 1e5;
const int maxa = 1e5;

const LL P = ((7 * 17) << 23) + 1, gg = 3;
const int maxL = 1<<17;

inline LL PowMod(LL a, LL b) { LL r=1; while(b) { if(b&1) r=r*a%P; a=a*a%P, b>>=1; } return r; }
LL A[maxL+5], B[maxL+5];
void NTT(LL *a, int len, int type) {
    int i, j, k, l;
    for(i=1, j=len>>1; i<len-1; ++i) {
        if(i<j) swap(a[i], a[j]);
        k = len>>1;
        while(j>=k)
            j -= k, k >>= 1;
        j += k;
    }
    LL var, step, u, v;
    for(l=2; l<=len; l<<=1) {
        step = PowMod(gg, (P-1)/l);
        for(k=0; k<len; k+=l) {
            var = 1;
            for(i=k; i<k+l/2; ++i) {
                u = a[i], v = var*a[i+l/2] % P;
                a[i] = (u+v) % P;
                a[i+l/2] = (u-v+P) % P;
                var = var*step % P;
            }
        }
    }
    if(type == -1) {
        for(i=1; i<len/2; ++i) swap(a[i], a[len-i]);
        LL inv = PowMod(len, P-2);
        for(i=0; i<len; ++i) a[i] = a[i]*inv % P;
    }
}

int n, ai[maxn+5];
LL inv[maxn+5];
LL ans = 0;

vector<int> G[maxn+5];
int que[maxn+5], fa[maxn+5], sz[maxn+5], msz[maxn+5];
bool ban[maxn+5];
int FindRoot(int x) {
    int s = 1, t = 1;
    que[1] = x, fa[x] = 0;
    while(s <= t) {
        x = que[s++], sz[x] = 1, msz[x] = 0;
        for(auto v : G[x])
            if(!ban[v] && v!=fa[x])
                que[++t] = v, fa[v] = x;
    }
    for(int i = t; i >= 1; --i) {
        x = que[i], msz[x] = max(msz[x], t-sz[x]);
        if((msz[x]<<1) <= t) return x;
        sz[fa[x]] += sz[x], msz[fa[x]] = max(msz[fa[x]], sz[x]);
    }
    assert(false);
    return 0;
}

int id[maxn+5];
vector<int> cnt[maxn+5], val[maxn+5];
void Mul(int a, int b) {
    int l1 = cnt[a].size();
    int l2 = val[b].size();
    int len = 1;
    while(len < l1+l2-1) len <<= 1;
    assert(len<=maxL);
    REP(i,0,l1-1) A[i] = cnt[a][i];
    REP(i,l1,len-1) A[i] = 0;
    REP(i,0,l2-1) B[i] = val[b][i];
    REP(i,l2,len-1) B[i] = 0;
    NTT(A,len,1), NTT(B,len,1);
    REP(i,0,len-1) A[i] = A[i]*B[i] % P;
    NTT(A,len,-1);
    REP(i,1,len-1) ans = (ans + A[i] * inv[i]) % P;
}

void dfs(int x, int p, int d, int sum, vector<int> &c, vector<int> &v) {
    sum = (sum + ai[x]) % P;
    for(auto y : G[x]) if(y!=p && !ban[y]) {
        dfs(y, x, d+1, sum, c, v);
    }
    if(d+1 > c.size()) {
        c.resize(d+1);
        v.resize(d+1);
    }
    ++c[d], v[d] = (v[d]+sum) % P;
}

void Solve(int x) {
    x = FindRoot(x);
    int tot = 1;
    cnt[0].resize(1), val[0].resize(1);
    cnt[0][0] = 1, val[0][0] = ai[x];
    id[0] = 0;
    for(auto y : G[x]) if(!ban[y]) {
        cnt[tot].clear(), val[tot].clear();
        dfs(y, x, 1, 0, cnt[tot], val[tot]);
        id[tot] = tot;
        ++tot;
    }
    sort(id, id+tot, [&](const int &a, const int &b){ return cnt[a].size() < cnt[b].size(); });
    for(int i = 0; i+1 < tot; ++i) {
        Mul(id[i], id[i+1]);
        Mul(id[i+1], id[i]);
        for(int k = 0; k < cnt[id[i+1]].size(); ++k)
            val[id[i+1]][k] = (val[id[i+1]][k] + LL(ai[x])*cnt[id[i+1]][k]) % P;
        for(int k = 0; k < cnt[id[i]].size(); ++k) {
            cnt[id[i+1]][k] = (cnt[id[i+1]][k] + cnt[id[i]][k]) % P;
            val[id[i+1]][k] = (val[id[i+1]][k] + val[id[i]][k]) % P;
        }
        cnt[id[i]].clear(), val[id[i]].clear();
    }
    cnt[id[tot-1]].clear(), val[id[tot-1]].clear();
    ban[x] = 1;
    for(auto y : G[x]) if(!ban[y]) Solve(y);
}

int main() {
    inv[1] = 1;
    REP(i,2,maxn) inv[i] = (P - P/i) * inv[P%i] % P;
    scanf("%d", &n);
    REP(i,1,n) scanf("%d", ai+i);
    for(int i = 1, u,v; i < n; ++i) {
        scanf("%d%d", &u, &v);
        G[u].PB(v);
        G[v].PB(u);
    }
    Solve(1);
    ans = ans*2 % P;
    printf("%lld\n", ans);
    return 0;
}

G - 铁树开花

题目链接

本题是防AK题，原因不在于思维度高，而在于码量大……（标程在压过代码量的情况下200+行，不过牛客同步赛上杭电在比赛刚结束不久就通过了这题，并且他们准AK，非常强悍）

这题是把两个idea强行拼在一起的产物 （于是也间接导致数据极其难造）。第一个idea来自Google Kick Start 2019 Round A P3 Contention，也就是计算$\max( \min_{1 \leq i \leq m}(cnt_i) )$的方法。不妨考虑倒着染色，假设现在还有$i$种花的顺序没有确定，并且他们一定都是在前$i$步开花，那么我们先让他们都在树上开花染色，并且对于每朵花记录一个$temp_k$值，表示树上只由这一种花染过色的结点的个数。之后，我们只要选择$temp_k$最大的那朵花，让它在第$i$步开花，并用$temp_k$更新一下$\min_{1 \leq i \leq m}(cnt_i)$即可。如此反复做$n$次后就可以算出$\max( \min_{1 \leq i \leq m}(cnt_i) )$的值，这是一个贪心，仔细思考一下就会发现是对的。

下一个问题是，如何在每一轮快速计算$temp_k$。注意到开花半径最大不超过$2$，这给了我们乱搞的余地。我们考虑对树定根，然后按照深度建线段树，即把所有深度相同的结点放在连续的一段区间当中。然后对每个结点，我们记录以下它的所有深度为$1$的子结点对应的区间，然后在记录一下它的所有深度为$2$的子结点对应的区间，于是经过一番仔细的分类讨论后，你会发现每次开花染色或撤销操作只需要涉及$O(\log n)$个区间。由于需要记录当某个结点只被一朵花染色时，这朵花具体是哪个，所以可能还需要对结点多维护一个set，于是单次染色或撤销操作就变成了$O(\log n \log m)$。因此你就可以倒着做，让每朵花都在树上染色，然后每一轮找出最大的$temp_k$及其对应的花，然后把这朵花撤掉即可，具体实现看代码。

但是这样还没完，因为题目要求字典序最小的操作顺序 （主要是因为数据不好造才强行加了这个特技增加题目复杂度），不过有了上面的一系列操作后，求字典序最小其实很简单。我们正着开花，每次选择没开过的花里面满足$temp_k \geq \max( \min_{1 \leq i \leq m}(cnt_i) )$且编号最小的那朵花开花即可。时间复杂度自己算算吧。。。

#include<bits/stdc++.h>

using namespace std;

#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,a,b) for(int i=a; i<=b; ++i)
#define PER(i,a,b) for(int i=a; i>=b; --i)
#define MP make_pair
#define PB push_back
#define fi first
#define se second
#define lson (x<<1)
#define rson (x<<1|1)
#define mid ((l+r)>>1)
typedef long long LL;
typedef double DB;
typedef pair<int,int> pii;

const int maxn = 1e5;
const int maxM = 2e4;
const int maxnode = maxn<<2;

int n, m;
int DFN = 0, dfn[maxn+5], fa[maxn+5];
vector<int> vec[maxn+5];
int L1[maxn+5], R1[maxn+5], L2[maxn+5], R2[maxn+5];
int pt[maxM+5], dd[maxM+5];
int cnt[maxM+5];
bool dead[maxM+5];
vector<int> G[maxn+5];
priority_queue<pair<int,int>> q;

int tr[maxnode+5], lz[maxnode+5];
set<int> cov[maxnode+5];

void dfs(int x, int p, int dis) {
    fa[x] = p;
    vec[dis].PB(x);
    for(auto y : G[x]) if(y!=p) {
        dfs(y,x, dis+1);
    }
}

void dfs2(int x, int p) {
    L1[x] = L2[x] = n+1;
    R1[x] = R2[x] = 0;
    for(auto y : G[x]) if(y!=p) {
        dfs2(y,x);
        L1[x] = min(L1[x], dfn[y]);
        R1[x] = max(R1[x], dfn[y]);
        L2[x] = min(L2[x], L1[y]);
        R2[x] = max(R2[x], R1[y]);
    }
}

void reBuild(int x, int l, int r) {
    tr[x] = lz[x] = 0;
    assert(cov[x].size()==0);
    if(l<r) {
        reBuild(lson, l, mid);
        reBuild(rson, mid+1, r);
    }
}

void PushDown(int x) {
    lz[lson]+=lz[x], tr[lson]+=lz[x];
    lz[rson]+=lz[x], tr[rson]+=lz[x];
    lz[x] = 0;
}

void Upd(int x, int l, int r, int v) {
    if(tr[x]>1) return;
    if(cov[x].size()) v = *cov[x].begin();
    if(l==r) {
        if(tr[x]==0) tr[x] = n+10;
        else if(tr[x]==1) {
            assert(1<=v && v<=n);
            ++cnt[v];
            q.push( pair<int,int>(cnt[v],v) );
            tr[x] = n+10;
        }
    }
    else {
        PushDown(x);
        Upd(lson, l, mid, v);
        Upd(rson, mid+1, r, v);
        tr[x] = min(tr[lson], tr[rson]);
    }
}

void Add(int x, int l, int r, int ll, int rr, int v) {
    if(ll<=l && r<=rr) {
        ++tr[x], ++lz[x];
        cov[x].insert(v);
    }
    else {
        PushDown(x);
        if(ll<=mid) Add(lson, l, mid, ll, rr, v);
        if(mid<rr) Add(rson, mid+1, r, ll, rr, v);
        tr[x] = min(tr[lson], tr[rson]);
    }
}

void Sub(int x, int l, int r, int ll, int rr, int v) {
    if(ll<=l && r<=rr) {
        --tr[x], --lz[x];
        auto it = cov[x].find(v);
        assert(it != cov[x].end());
        cov[x].erase(it);
    }
    else {
        PushDown(x);
        if(ll<=mid) Sub(lson,l, mid, ll, rr, v);
        if(mid<rr) Sub(rson, mid+1, r, ll, rr, v);
        tr[x] = min(tr[lson], tr[rson]) + lz[x];
    }
}

void Mod(int l, int r, int v, int o) {
    if(l>r) return;
    if(o==1) Add(1, 1, n, l, r, v);
    else Sub(1, 1, n, l, r, v);
}

void Draw(int id, int o) {
    assert(o==1 || o==-1);
    int x = pt[id], kk = dd[id];
    if(kk==0) Mod(dfn[x], dfn[x], id, o);
    else if(kk==1) {
        Mod(L1[x], R1[x], id, o);
        Mod(dfn[x], dfn[x], id, o);
        if(fa[x]!=0) Mod(dfn[fa[x]], dfn[fa[x]], id, o);
    }
    else {
        Mod(L1[x], R1[x], id, o);
        Mod(L2[x], R2[x], id, o);
        if(fa[x]!=0) {
            int y = fa[x];
            Mod(L1[y], R1[y], id, o);
            Mod(dfn[y], dfn[y], id, o);
            if(fa[y]!=0) Mod(dfn[fa[y]], dfn[fa[y]], id, o);
        }
        else Mod(dfn[x], dfn[x], id, o);
    }
}

priority_queue<int> q2;

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1, u,v; i < n; ++i) {
        scanf("%d%d", &u, &v);
        G[u].PB(v); G[v].PB(u);
    }
    dfs(1,0,1);
    REP(i,1,n) {
        for(auto x : vec[i]) dfn[x] = ++DFN;
    }
    dfs2(1,0);
    REP(i,1,m) {
        scanf("%d%d", pt+i, dd+i);
        Draw(i,1);
    }
    REP(i,1,m) q.push( pair<int,int>(0,i) );
    Upd(1, 1, n, -1);
    int ans = n+10;
    REP(i,1,m) {
        while(dead[q.top().se] || cnt[q.top().se]!=q.top().fi) q.pop();
        ans = min(ans, q.top().fi);
        int x = q.top().se; q.pop();
        assert(1<=x && x<=m);
        dead[x] = 1;
        Draw(x,-1);
        Upd(1, 1, n, -1);
    }

    reBuild(1,1,n);
    while(!q.empty()) q.pop();
    REP(i,1,m) cnt[i] = 0, dead[i] = 0, Draw(i,1), q.push( pair<int,int>(0,i) );
    Upd(1, 1, n, -1);
    int gao = 0;
    REP(i,1,m) {
        while(gao < m) {
            while(dead[q.top().se] || cnt[q.top().se]!=q.top().fi) q.pop();
            if(q.top().fi < ans) break;
            q2.push( -q.top().se );
            dead[q.top().se] = 1;
            q.pop(); ++gao;
        }
        int x = -q2.top();
        q2.pop();
        Draw(x,-1);
        Upd(1, 1, n, -1);
    }

    printf("%d\n", ans);
    int tmp_sum = 0;
    REP(i,1,m) printf("%d\n", cnt[i]), tmp_sum += cnt[i];

    return 0;
}

J - 单身狗救星

题目链接

把题目中的公式化简后，问题就转化成：给出二维平面内$n$个点，再给$m$个询问点，对每个询问点输出$n$个点中和它形成斜率最大的那个点的编号。

据出题人说这个idea去年jls在牛客多校上出过，做法是搞两遍凸包。我们把所有$n+m$点按照先$x$坐标后$y$坐标的顺序排个序，然后按照新顺序扫一遍，同时维护一个动态凸包。当我们扫到点是前$n$个定点之一，就把这个点加进凸包里；如果我们扫到的点是后$m$个询问点之一，我们就在凸包上二分找一个使得斜率最大的定点，并更新这个询问点的答案。

做完之后，再将所有点关于原点翻转，之后再做一遍上述操作即可。总时间复杂度$O((n+m) \log n)$。

为什么这样做是对的呢？简单口胡一下，当扫到某个询问点时，所有在其左侧的定点（也就是$x$座标小于它的点）一定都被包含在下凸包或者就在下凸包上。现在我们找到了下凸包上的斜率最大点，假设凸包内有一点能使得斜率更大，那么画画图就会发现一定能在凸包上找到另一个点使得斜率比这个凸包内点还要大，这样就出现了矛盾。所以这样操作一定能找到每个询问点左侧使其斜率最大的点，而对于右侧的情况，沿原点翻转再算一遍就出来了。

// hls tql
#include <bits/stdc++.h>
#define ll long long

using namespace std;

struct node {
    ll x, y;
    int ty, id;
    node() {}
    node(ll _x, ll _y, int _ty, int _id)
        : x(_x), y(_y), ty(_ty), id(_id) {}
    void init(int _ty, int _id) {
        scanf("%lld%lld", &x, &y);
        ty = _ty;
        id = _id;
    }
    node operator-(const node &b) const {
        return node(x - b.x, y - b.y, 0, 0);
    }
    ll operator^(const node &b) const {
        return x * b.y - y * b.x;
    }
    bool operator<(const node &b) const {
        return x == b.x ? y < b.y : x < b.x;
    }
};

const int MAXN = 1e5 + 10;
node a[MAXN], b[MAXN], cc[MAXN << 1];
int ans[MAXN], que[MAXN], lim;

bool judge(node a, node b, node c) {
    ll tmp = (b - a) ^ (a - c);
    return tmp == 0 ? c.id < b.id : tmp > 0;
}

void solve() {
    int las = 0;
    for (int i = 1; i <= lim; i++) {
        if (cc[i].ty == 1) {
            while (las > 1 && ((cc[i] - cc[que[las]]) ^ (cc[que[las]] - cc[que[las - 1]])) > 0)
                las--;
            que[++las] = i;
        } else {
            if (!las)
                continue;
            int l = 1, r = las;
            while (l < r) {
                int mid = (l + r) >> 1;
                if (((cc[i] - cc[que[mid + 1]]) ^ (cc[que[mid + 1]] - cc[que[mid]])) > 0)
                    r = mid;
                else
                    l = mid + 1;
            }
            if (ans[cc[i].id] == -1 || judge(b[cc[i].id], a[ans[cc[i].id]], a[cc[que[l]].id]))
                ans[cc[i].id] = cc[que[l]].id;
        }
    }
}

int main() {
    int n, q;
    scanf("%d%d", &n, &q);
    lim = n + q;
    for (int i = 1; i <= lim; i++) {
        if (i <= n) {
            a[i].init(1, i);
            cc[i] = a[i];
        } else {
            b[i - n].init(2, i - n);
            cc[i] = b[i - n];
        }
    }
    memset(ans, -1, sizeof(ans));
    sort(cc + 1, cc + lim + 1);
    solve();
    reverse(cc + 1, cc + lim + 1);
    for (int i = 1; i <= lim; i++) {
        cc[i].x = -cc[i].x;
        cc[i].y = -cc[i].y;
    }
    solve();
    for (int i = 1; i <= q; i++)
        printf("%d\n", ans[i]);
}

A - NB群友

题目链接

问题可以转化成求“积$\leq R$的数的个数” $-$ “积$\leq (L-1)$的数的个数”，于是我们可以dfs枚举$2 \sim 9$每个数字出现的次数，然后再组合数统计一下答案，剪剪枝就能过。

#include<bits/stdc++.h>

using namespace std;

#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,a,b) for(int i=a; i<=b; ++i)
#define PER(i,a,b) for(int i=a; i>=b; --i)
#define MP make_pair
#define PB push_back
#define fi first
#define se second
typedef long long LL;
typedef double DB;

const int maxT = 50;
const int P = 1e9+7;
const LL MaxInt = (1LL<<32) - 1;

LL Fac[100], InvFac[100];
LL C[100][100];
int cnt[20];

LL lim;
LL dfs(LL now, int pt) {
    if(pt<=1) {
        int s = 0;
        LL ret = 1;
        REP(i,2,9) {
            s += cnt[i];
            ret = ret * C[s][cnt[i]] % P;
        }
        if(s==0) return 0LL;
        return ret;
    }
    LL ret = 0;
    cnt[pt] = 0;
    while(now <= lim) {
        ret = (ret + dfs(now, pt-1)) % P;
        now *= pt, ++cnt[pt];
    }
    return ret;
}

int main() {
    C[0][0] = 1;
    for(int i = 1; i <= 50; ++i) {
        C[i][0] = C[i][i] = 1;
        for(int k = 1; k < i; ++k) C[i][k] = (C[i-1][k] + C[i-1][k-1]) % P;
    }
    int _; scanf("%d", &_);
    while(_--) {
        LL a,b;
        scanf("%lld%lld", &a, &b);
        lim = b;
        LL sb = dfs(1,9);
        lim = a-1;
        LL sa = dfs(1,9);
        LL ans = (sb - sa + P) % P;
        printf("%lld\n", ans);
    }
    return 0;
}

C - 六学家的困惑

题目链接

此题出题人对此题的定位是签到题，但组题人表示好像不怎么签到。。。

正解是贪心，然而现场很多人的贪心策略是直接比较两根管子四个端点处的数字大小，然后取最大的那个数，于是就WA了。考虑下面这个例子：

595
575

最优的取球顺序应该是先取第一根管子的$5$，再取第一根管子的$9$。但如果使用上面的贪心策略，就有可能先取第二根管子的$5$，再取第二根管子的$7$，这样就错了。

正确做法应该是：在每次取球时，对于每根管子，分别从左往右读和从右往左读，这样就可以得到一共$4$个字符串。比较这$4$个字符串的字典序大小，取字典序最大的那个字符串的第一个字符对应的球即可。

单组数据复杂度$O(n^2)$。

// 邵老师牛逼!
#include<bits/stdc++.h>

using namespace std;

const int maxT = 14;
const int maxn = 40;

int cmp(char *s1, int p1, int d1, int n1, char *s2, int p2, int d2, int n2) {
    int n = min(n1,n2);
    for(int i = 1; i <= n; ++i) {
        if(s1[p1] < s2[p2]) return -1;
        if(s1[p1] > s2[p2]) return 1;
        p1+=d1, p2+=d2;
    }
    if(n1 < n2) return -1;
    if(n1 > n2) return 1;
    return 0;
}

int main() {
    int __; scanf("%d", &__);
    assert(1<=__ && __<=maxT);
    char s1[maxn+5], s2[maxn+5];
    char ans[maxn*2+5];
    for(int _ = 1; _ <= __; ++_) {
        scanf("%s%s", s1, s2);
        int l1 = 0, r1 = strlen(s1)-1;
        int l2 = 0, r2 = strlen(s2)-1;
        int n = r1+r2+2;
        for(int i = 0; i < n; ++i) {
            int di1 = 0, di2 = 0;
            if(cmp(s1, l1, 1, r1-l1+1, s1, r1, -1, r1-l1+1) >= 0) di1 = 1;
            else di1 = -1;

            if(cmp(s2, l2, 1, r2-l2+1, s2, r2, -1, r2-l2+1) >= 0) di2 = 1;
            else di2 = -1;

            int pt = 0, di = 0;
            if(cmp(s1, (di1==1)?l1:r1, di1, r1-l1+1, s2, (di2==1)?l2:r2, di2, r2-l2+1) >= 0)
                pt = 1, di = di1;
            else pt = 2, di = di2;
            char c = 0;
            if(pt==1) {
                if(di==1) ans[i] = s1[l1++];
                else ans[i] = s1[r1--];
            }
            else if(pt==2) {
                if(di==1) ans[i] = s2[l2++];
                else ans[i] = s2[r2--];
            }
        }
        ans[n] = '\0';
        printf("Case #%d: %s\n", _, ans);
    }
    return 0;
}

E - 数独挑战

题目链接

舞蹈链模板题。 这题出在校赛就是给大家爆搜的，听说过舞蹈链的选手可能会被唬住，没听过的选手直接大力剪枝莽一莽就过了。至于有些人的爆搜TLE了？那只能说明你们的剪枝不够优秀。。。

以下只给出爆搜代码：

#include<cstdio>
using namespace std;

int v[100][2],map[10][10];

bool judge(int x,int y,int k)
{
    for(int i=0;i<9;i++)
        if(map[i][y]==k||map[x][i]==k)
            return false;
    int dx=x-x%3,dy=y-y%3;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            if(map[dx+i][dy+j]==k)
                return false;
    return true;
}

int dfs(int n)
{
    if(n<0) return 1;
    for(int i=1;i<=9;i++)
    {
        int x=v[n][0],y=v[n][1];
        if(judge(x,y,i))
        {
            map[x][y]=i;
            if(dfs(n-1)) return 1;
            map[x][y]=0;
        }
    }
    return 0;
}

int main()
{
    int num=0;
    for(int i=0;i<9;i++)
        for(int j=0;j<9;j++)
        {
            scanf("%d",&map[i][j]);
            if(map[i][j]==0)
            {
                v[num][0]=i;
                v[num++][1]=j;
            }
        }
    dfs(num-1);
    for(int i=0;i<8;i++)
    {
        for(int j=0;j<8;j++)
            printf("%d ",map[i][j]);
        printf("%d\n",map[i][8]);
    }
    for(int j=0;j<8;j++)
        printf("%d ",map[8][j]);
    printf("%d",map[8][8]);
    return 0;
}

I - 炒股

题目连接

（据说某C姓出题人被这题卡了）

全场通过率第二高的题，贪心策略没什么好讲，看代码理解理解就懂了。唯一需要注意的是这题答案会爆int范围，因此需要用long long保存答案。

以下提供Python 3代码 （于是完全不用考虑爆int的问题了）：

n = int( input() )

pa = int( input() )
ans = 0
for i in range(1,n):
    a = int( input() )
    if(a>pa): ans += a-pa
    pa = a

print(ans)

L - 石头剪刀布

题目链接

由于觉得C题不够签到，为防止有队伍爆零而临时加的签到题 （然而仍然没防住）。

在这题上出现的错误包括但不限于：

• 拼错单词
• system("pause");
• #include "stdafx.h"

Emmm……我只能说，出题人尽力了。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    string str;
    cin >> n;
    while (n-- > 0) {
        cin >> str;
        if (str == "Scissors") cout << "Rock\n";
        if (str == "Rock") cout << "Paper\n";
        if (str == "Paper") cout << "Scissors\n";
    }
    return 0;
}

比赛链接

题目难度设置

题解汇总

A，C，E，I，L题解

B, F, H, K题解

D, G, J题解

总结