8/11 

最小生成树+线性期望 A （BH）

题意：

　　1. 求最小生成树 2. 求在某一棵最小生成树任意两点的最小距离的期望值。

思路：

　　首先题目说了边权值都是不同的，所以最小生成树唯一。那么只要统计出最小生成树的每一条边在“任意两点走经过它“的情况下所贡献的值，发现在一棵树里，一条边所贡献的次数为，sz[v]表示v子树包括节点v的个数。如下图所示，红边所贡献的次数即为”选一个蓝点再选一个绿点“的方案数。

代码：

#include 
     
      using namespace std;typedef long long ll;const int N = 1e5 + 5;const int M = 1e6 + 5;struct Edge {    int u, v, w;    bool operator < (const Edge &rhs) const {        return w < rhs.w;    }}edges[M];int n, m;vector
      
       
         > edge[N];void init_edge() {    for (int i=1; i<=n; ++i) {        edge[i].clear ();    }}int rt[N];void init_DSU() {    for (int i=1; i<=n; ++i) {        rt[i] = i;    }}int Find(int x) {    return rt[x] == x ? x : rt[x] = Find (rt[x]);}int sz[N];ll sumw;void DFS2(int u, int fa) {    for (auto t: edge[u]) {        int v = t.first, w = t.second;        if (v == fa) continue;        sumw += (ll) w * (n - sz[v]) * sz[v];        DFS2 (v, u);    }}void DFS(int u, int fa) {    sz[u] = 1;    for (auto t: edge[u]) {        int v = t.first, w = t.second;        if (v == fa) continue;        DFS (v, u);        sz[u] += sz[v];    }}double solve() {    memset (sz, 0, sizeof (sz));    sumw = 0;    DFS (1, 0);    DFS2 (1, 0);    return ((double) sumw * 2 / n / (n - 1));}int main() {    int T;    scanf ("%d", &T);    while (T--) {        scanf ("%d%d", &n, &m);        init_DSU ();        int tot = 0;        for (int i=1; i<=m; ++i) {            int u, v, w;            scanf ("%d%d%d", &u, &v, &w);            edges[tot++] = (Edge) {u, v, w};        }        std::sort (edges, edges+tot);        init_edge ();        ll sum = 0;        for (int i=0; i
       
      
     

状态压缩+博弈 B （BH）　

题意：

　　有n*20的格子，某些格子上有棋子，A和B轮流操作，可以一个棋子放到右边第一个空位置，不能操作者输，A先操作，问输赢。

思路：

　　这是简单的Nim问题，状态压缩，算出所有状态的sg值。看完训练指南的内容再结合代码应该能懂了吧。

代码：

#include 
     
      int a[1005];int sg[(1<<20)+5];int vis[25];int mex(int u) {    memset (vis, 0, sizeof (vis));    for (int i=0; i<20; ++i) {        if (u & (1<
      
       = 0 && (u & (1<
       
        = 0) {                int v = u ^ (1<
        
          0 ? "YES" : "NO");    }    return 0;}
        
       
      
     

最短路？搜索？不会 C 

数论（区间GCD问题）D （BH）

题意：

　　1. 区间[l, r]的GCD值 2. 问有多少个区间的GCD值为gcd

思路：

　　第一个操作线段树或者ST都可以做，第二个问题的关键点是

　　简单来说，就是固定右端点R，然后左端点往左边移动，查询GCD，如果相同就跳到这个GCD所对应的区间的左端点（并且维护这个gcd现在的区间的两端点的位置），因为一个数的质因数最多有log(x)个，而且求GCD是递减的过程，所以跳跃的次数是log级的。

本场比赛就因为这题坑了好久，GCD的性质不够了解。

代码：

#include 
     
      const int N = 1e5 + 5;int a[N];int GCD(int a, int b) {    return b ? GCD (b, a % b) : a;}#define lson l, mid, o << 1#define rson mid + 1, r, o << 1 | 1int val[N<<2];void push_up(int o) {    val[o] = GCD (val[o<<1], val[o<<1|1]);}void build(int l, int r, int o) {    if (l == r) {        val[o] = a[l];        return ;    }    int mid = l + r >> 1;    build (lson);    build (rson);    push_up (o);}int query(int ql, int qr, int l, int r, int o) {    if (ql <= l && r <= qr) {        return val[o];    }    int mid = l + r >> 1, ret = 0;    if (ql <= mid) ret = GCD (ret, query (ql, qr, lson));    if (qr > mid) ret = GCD (ret, query (ql, qr, rson));    return ret;}int n;std::map
      
        mp;int pre[N];void init() {    for (int i=1; i<=n; ++i) {        pre[i] = i;    }    mp.clear ();}void prepare() {    build (1, n, 1);    for (int i=1; i<=n; ++i) {        int L = i, g = a[i];        while (L > 0) {            int R = L;            g = GCD (g, a[L]);            while (L > 1 && GCD (g, a[L-1]) == g) {                L = pre[L-1];                pre[R] = L;            }            mp[g] += (R - L + 1);             L--;        }    }}int main() {    int T;    scanf ("%d", &T);    for (int cas=1; cas<=T; ++cas) {        scanf ("%d", &n);        init ();                for (int i=1; i<=n; ++i) {            scanf ("%d", &a[i]);        }        prepare ();        int q;        scanf ("%d", &q);        printf ("Case #%d:\n", cas);        while (q--) {            int ql, qr;            scanf ("%d%d", &ql, &qr);            int g = query (ql, qr, 1, n, 1);            printf ("%d %I64d\n", g, mp[g]);        }    }    return 0;}
      
     

二分图匹配（匈牙利算法）E （BH）

题意：

　　有n颗阳属性的珠子和n颗阴属性的珠子，给了m条规则，就是某些阳珠子和阴珠子不能相邻，问2*n颗串成项链后最少几颗会违反规则。

思路：

　　先枚举阴珠子的排列顺序（固定第一个不动，因为是环）。然后对于某一个排列，问题可以转换为”阳珠子如何插如使得不违反规则的珠子最多“，这个用解决，时间复杂度为。卿学姐DFS也能过？数据水了吧

代码：

#include 
     
      int n, m;std::vector
      
        edges[10];bool no[10][10];int lk[10];bool vis[10];bool DFS(int u) {    for (auto v: edges[u]) {        if (!vis[v]) {            vis[v] = true;            if (lk[v] == -1 || DFS (lk[v])) {                lk[v] = u;                return true;            }        }    }    return false;}int hungary() {    int ret = 0;    memset (lk, -1, sizeof (lk));    for (int i=1; i<=n; ++i) {        memset (vis, false, sizeof (vis));        if (DFS (i)) ret++;    }    return ret;}int id[10];int solve() {    for (int i=1; i<=n; ++i) {        id[i] = i;    }    int ret = 0;    do {        for (int i=1; i<=n; ++i) edges[i].clear ();        for (int i=1; i<=n; ++i) {            for (int j=1; j<=n; ++j) {                if (!no[i][id[j]] && !no[i][id[(j+1>n?1:j+1)]]) {                    edges[i].push_back (j);                }            }        }        ret = std::max (ret, hungary ());    } while (std::next_permutation (id+2, id+1+n));  //[2,n]全排列    return ret;}int main() {    while (scanf ("%d%d", &n, &m) == 2) {        if (n == 0) {            puts ("0");            continue;        }        memset (no, false, sizeof (no));        for (int i=1; i<=m; ++i) {            int x, y;            scanf ("%d%d", &x, &y);            no[x][y] = true;        }        printf ("%d\n", n - solve ());    }    return 0;}
      
     

数论 G （CYD）

题意：

　　求  时，ans= mod p,ans的值，其中n的每个素因子的幂次都是1，是。

思路：

解题分两部分完成，第一部分首先求出k，有公式

  （素数p是n的一个质因子）

由此可以递归求出k的值，f(n,m)=(p的欧拉值)*f(n/p,m)+f(n,m/p)。

第二部分的无限次幂，由公式

 不断求欧拉值最终使值变得有限。

代码：

#include 
     
      using namespace std;const int M=1000000007;const int N=1e7+5;typedef long long ll;int pri[N],phi[N],tot;bool vis[N];ll sum[N];void init(){    int n=N;    tot=0;    memset(vis,false,sizeof vis);    phi[1]=1;    for(int i=2;i
      
       >=1;    }    if(ans==0)        ans+=mod;    return ans;}ll solve(ll k,ll mod){    if(mod==1)        return mod;    ll tmp=phi[mod];    ll up=solve(k,tmp);    ll ans=Pow(k,up,mod);    return ans;}int rear;int a[15];void resolve(ll n){    for(int i=0;i
      
     

UPD：二分图连通图计数 不会 H Rigid Frameworks （BH）（51Nod原题）

题意：

　　给n*m的格子，可以加上斜线，问有多少种方案使得整个格子不能倾斜，也就是不能像下图一样：

思路：

　　网上写的不错的。问题的关键点是模型转换成二分图的连通计数，然后就是所有方案减去不符合的方案数。

代码：

#include 
     
      typedef long long ll;const int MOD = 1e9 + 7;ll dp[15][15][105];ll pow_two[105];ll C[105][105];ll f(int a, int b, int c) {    if (a >= b) return dp[a][b][c];    return dp[b][a][c];}void init() {    pow_two[0] = 1;    for (int i=1; i<=100; ++i) pow_two[i] = pow_two[i-1] * 2 % MOD;    C[0][0] = 1;    for (int i=1; i<=100; ++i) {        C[i][0] = C[i][i] = 1;        for (int j=1; j
      
       =k-kk) {                                if (i == ii && j == jj) break;                                dp[i][j][k] = (dp[i][j][k] - C[i-1][ii-1] * C[j][jj] * f (ii, jj, kk) * C[(i-ii)*(j-jj)][k-kk] + MOD) % MOD;                            }                        }                    }                }            }        }    }}int main() {    init ();    int n, m;    while (scanf ("%d%d", &n, &m) == 2) {        if (n < m) std::swap (n, m);        ll ans = 0;        for (int i=1; i<=n*m; ++i) {            ans = (ans + dp[n][m][i] * pow_two[i]) % MOD;        }        printf ("%I64d\n", ans);    }    return 0;}
      
     

FFT 不会 I Shell Necklace

UPD2: 轮廓线DP+容斥原理 不会 I Solid Dominoes Tilings（BH）（51Nod原题）

题意：

　　有n*m的格子用1*2的小格子填充，问全部填充且不能完整分割的方案数。

思路：

　　轮廓线DP先求全部填充的方案数（训练指南P383），再用容斥原理减去完整分割的方案数。当时觉得容斥不好做，其实容斥只要依照“奇数减，偶数加”的原则算，这是关于列的主容斥，那么对于行就把全部不符合的都减去。

代码：

#include 
     
      typedef long long ll;const int MOD = 1e9 + 7;const int N = 16;int dp[2][1<
      
       = MOD) a -= MOD;    if (a < 0) a += MOD;}void init() {    for (int n=1; n<=N; ++n) {        for (int m=1; m<=N; ++m) {            //预处理n*m格子填满的方案数，轮廓线DP            int cur = 1;            memset (dp[cur], 0, sizeof (dp[cur]));            int limit = 1 << m;            dp[cur][limit-1] = 1;            for (int i=0; i
       

lens; for (int n=1; n<=N; ++n) { for (int m=1; m<=N; ++m) {

　　　　　　　//主容斥列 //竖线最多m-1条 int limit = 1 << (m-1); for (int s=0; s