2019 计蒜之道 初赛 第一场

题目链接：传送门

A. 商汤的AI伴游小精灵

• 数据范围：$n(5000)$n(5000)
• 首先这是一颗联通树，$O(n^2)$O(n2)枚举删除的两个点，他们对答案的贡献是出度和
• 若选择了一个根节点，贡献要减一；若两点相邻，贡献也要减一
• 本题个人感觉不能$O(n)$O(n)写，很多人都是错误的写法，但是没被叉掉。。。

int main() {
    n = read();
    for(int i = 1, a, b; i < n; ++i) {
        a = read(), b = read();
        ar[a][b] = ar[b][a] = 1;
        ++ du[a];
    }
    int ans = 1;
    for(int i = 1; i <= n; ++i) {
        int tmp = 1 + du[i];
        if(i == 1) -- tmp;
        ans = max(ans, tmp);
        for(int j = i + 1; j <= n; ++j) {
            tmp = 1 + du[i] + du[j];
            if(i == 1) -- tmp;
            if(ar[i][j]) -- tmp;
            ans = max(ans, tmp);
        }
    }
    printf("%d\n", ans);
    return 0;
}

B. 商汤AI园区的n个路口（简单）

• 数据范围：$1\le n\le m\le 50$1≤n≤m≤50，且保证是一条链。
• $dp[i][j]$dp[i][j]表示第$i$i个路口频段为$j$j时，前$1-i$1−i的路段均合法的方案数。
• $O(nm^2)$O(nm2)转移即可，枚举路口$i$i和$i-1$i−1的频段。
• 答案是$\sum_{i=1}^{m} dp[n][i]$∑i=1m​dp[n][i]

int main() {
    n = read(), m = read();
    for(int i = 2,a ,b, c; i <= n; ++i) {
        a = read(), b = read(), c = read();
        ar[b] = c;
    }
    for(int i = 1; i <= m; ++i) dp[1][i] = 1;
    for(int i = 2; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            for(int k = 1; k <= m; ++k) {
                if(__gcd(j, k) != ar[i]) dp[i][j] = (dp[i][j]+dp[i-1][k])%mod;
            }
        }
    }
    LL ans = 0;
    for(int i = 1; i <= m; ++i) ans = (ans + dp[n][i])%mod;
    printf("%lld\n", (ans+mod)%mod);
    return 0;
}

C. 商汤AI园区的n个路口（中等）

• 题目和上面一样，数据范围：$1\le n\le m\le 1000$1≤n≤m≤1000，是一颗树。
• 考虑树$dp$dp，$dp[u][i]$dp[u][i]表示路口$u$u的频段是$i$i时，$u$u的子树路线均合法的方案数
• 显然$dp[u][i]$dp[u][i]的贡献是他所有儿子合法方案数的乘积。
• 然后你会发现固定$x$x满足$gcd(x,y)=w,1\lt w$gcd(x,y)=w,1<w的$y$y不会超过$log(m)$log(m)个
• 考虑链$(u,v,w)$(u,v,w)，计算$dp[u][i]$dp[u][i]：先提前累加出$\sum_{i=1}^m dp[v][i]$∑i=1m​dp[v][i]作为$v$v暂时的贡献，然后枚举$w$w的倍数$j$j，减去$gcd(i,j)=w$gcd(i,j)=w的方案数即可。
• 复杂度：$O(nmlog(m))$O(nmlog(m))

#include<bits/stdc++.h>
#define fi first
#define se second
#define endl '\n'
#define BASE_MAX 62
#define mk make_pair
#define o2(x) (x)*(x)
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define clr(a,b) memset((a),(b),sizeof((a)))
#define iis std::ios::sync_with_stdio(false); cin.tie(0)
#define my_unique(x) sort(all(x)),x.erase(unique(all(x)),x.end())
using namespace std;
#pragma optimize("-O3")
typedef long long LL;
typedef pair<int, int> pii;
inline LL read() {
  LL x = 0;int f = 0;char ch = getchar();
  while (ch < '0' || ch > '9') f |= (ch == '-'), ch = getchar();
  while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
  return x = f ? -x : x;
}
inline void write(LL x) {
    if(x == 0) { putchar('0'), putchar('\n'); return;}
    if(x < 0) { putchar('-'); x = -x;}
    static char s[23];int l = 0;
    while(x != 0) s[l++] = x % 10 + 48, x /= 10;
    while(l) putchar(s[--l]);
    putchar('\n');
}
int lowbit(int x) { return x & (-x); }
template<class T> T big(const T& a1,const T& a2) { return a1>a2?a1:a2; }
template<typename T, typename ...R> T big (const T& f,const R& ...r) { return big(f, big (r...)); }
template<class T> T sml(const T& a1,const T& a2) { return a1<a2?a1:a2; }
template<typename T, typename ...R> T sml (const T& f,const R& ...r) { return sml(f, sml (r...)); }
void debug_out() { cerr << '\n'; }
template<typename T, typename ...R> void debug_out (const T& f,const R& ...r) { cerr << f << " "; debug_out (r...); }
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]: ", debug_out(__VA_ARGS__);

const int INF = 0x3f3f3f3f;
const LL INFLL = 0x3f3f3f3f3f3f3f3fLL;
const int HMOD[] = {1000000007, 1000000009};
const LL BASE[] = {1572872831, 1971536491};
const int MXN = 1e3 + 7;
const int mod = 1e9 + 7;
int n, m;
int ar[MXN];
LL dp[MXN][MXN];
std::vector<pii > mp[MXN];
void dfs(int u, int ba) {
    int ye = 1, fir = 1;
    for(auto x: mp[u]) {
        if(x.fi == ba) continue;
        ye = 0;
        dfs(x.fi, u);
        //debug(u, x.fi)
        LL all = 0;
        for(int i = 1; i <= m; ++i) all = (all+dp[x.fi][i])%mod;
        for(int i = 1; i <= m; ++i) {
            LL tmp = all;
            if(__gcd(i, x.se) == x.se) {
                for(int j = x.se; j <= m; j += x.se) {
                    if(__gcd(j,i)==x.se) tmp -= dp[x.fi][j], tmp %= mod;
                }
            }
            if(fir) dp[u][i] = tmp;
            else dp[u][i] = tmp*dp[u][i]%mod;
        }
        if(fir) fir = 0;
    }
    if(ye) for(int i = 1; i <= m; ++i) dp[u][i] = 1;
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("E://ADpan//in.in", "r", stdin);
    //freopen("E://ADpan//out.out", "w", stdout);
#endif
    n = read(), m = read();
    for(int i = 2,a ,b, c; i <= n; ++i) {
        a = read(), b = read(), c = read();
        mp[a].eb(mk(b, c));
        mp[b].eb(mk(a, c));
    }
    dfs(1, -1);
    LL ans = 0;
    for(int i = 1; i <= m; ++i) ans = (ans + dp[1][i]) % mod;
    printf("%lld\n", (ans+mod)%mod);
    return 0;
}

D. 商汤AI园区的n个路口（困难）

• 数据范围：$1\le n\le m\le 100000$1≤n≤m≤100000，是一颗树。
• 题解：莫比乌斯反演