2016多校联合训练一

2018-05-24

A.Abandoned country

先跑一个最小生成树，然后任选一个点为根，dfs出每条边左右的点数a,b。 $a \times b \times val$即为这条边的贡献,总贡献 $sum /(n*(n-1)/2)$即为答案

/*
 * Author:  JiangYu
 * Created Time:  2018/5/24 15:02:39
 * File Name: A.cpp
 */
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
#define PB push_back
#define X first
#define Y second
#define FI first
#define SE second
#define inf 0x3f3f3f3f
#define FOR(i,a,b) for(int i = a; i <= b; ++i)
#define FORD(i,a,b) for(int i = b; i >= a; --i)
#define ALL(x) x.begin(),x.end()
#define REP(i,a) for(int i = 0; i < a; ++i)
#define DEP(i,a) for(int i = a-1; i >= 0; --i)
#define CLR(a) memset(a, 0, sizeof a)
const int N = 1e5 + 1024;
const int M = N * 10;
int n, m;
ll ans = 0;
struct edge{
    int u, v, val, nex;
}ed[M], e[N<<1];
int cnt = 0;
int son[N], fa[N], head[N];
bool vis[N];
int fin(int k) {
    if(k != fa[k]) fa[k] = fin(fa[k]);
    return fa[k];
}
void add(int from, int to, int val) {
    e[cnt].u = from;
    e[cnt].v = to;
    e[cnt].val = val;
    e[cnt].nex = head[from];
    head[from] = cnt++;
}
bool cmp(const edge& t, const edge& o){
    return t.val < o.val;
}
ll tmp;
void dfs(int u, int fa) {
    son[u] = 1;
    for(int i = head[u]; ~i; i = e[i].nex) {
        int v = e[i].v;
        if(v == fa) continue;
        dfs(v, u);
        son[u] += son[v];
        tmp += 1ll* (n - son[v]) * son[v] * e[i].val;
    }
}
void init() {
    
    scanf("%d%d", &n, &m);
    cnt  = 0;
    for(int i = 1; i <= n; ++i) fa[i] = i, son[i] = 0, vis[i] = 0, head[i] = -1;
    for(int i = 1; i <= m; ++i) {
        scanf("%d%d%d", &ed[i].u, &ed[i].v, &ed[i].val);
    } 
    sort(ed+1, ed+1+m, cmp);
}
void solve() {
    ans = 0;
    int sum = 0;
    for(int i = 1; i <= m; ++i) {
        int fx = fin(ed[i].u);
        int fy = fin(ed[i].v);
        if(fx == fy) continue;
        else {
            sum++;
            fa[fx] = fy;
            ans += ed[i].val;
            add(ed[i].u, ed[i].v, ed[i].val);
            add(ed[i].v, ed[i].u, ed[i].val);
        }
        if(sum == n-1) break;
    }
    tmp = 0;
    dfs(1, 0);
    
}
void prin() {
    printf("%lld ", ans);
    printf("%.2f\n", 1. * tmp * 2 / n / (n-1) );
}
int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        init();
        solve();
        prin();
    }
    return 0;
}

B.Chess

每一行独立，先预处理出所有的sg函数，然后异或起来就好了

/*
 * Author:  JiangYu
 * Created Time:  2018/5/24 15:36:02
 * File Name: B.cpp
 */
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
#define PB push_back
#define X first
#define Y second
#define FI first
#define SE second
#define inf 0x3f3f3f3f
#define FOR(i,a,b) for(int i = a; i <= b; ++i)
#define FORD(i,a,b) for(int i = b; i >= a; --i)
#define ALL(x) x.begin(),x.end()
#define REP(i,a) for(int i = 0; i < a; ++i)
#define DEP(i,a) for(int i = a-1; i >= 0; --i)
#define CLR(a) memset(a, 0, sizeof a)
const int N = 1<<21; 
int sg[N];
int get(int x) {
    if(sg[x] != -1) return sg[x];
    int vis[50] = {0}, nex = -1;
    for(int i = 0; i < 20; ++i) {
        if(x <(1<<i)) break;
        
        //if(x == 2) cout << (1<<i)<< endl;
        if((x&(1<<i)) == 0) {
            nex = i;
            //if(x==2)
            //cout << nex;
        }
        else if(nex != -1) {
            //if(x==2) cout<< x-(1<<i)+(1<<nex)<<endl;
            vis[get(x^(1<<i)^(1<<nex))] = 1;
        }
    }
    for(int i = 0; ; i++) {
        if(!vis[i]) return sg[x] = i;
    }
}
int main() {
    int t;
    memset(sg, -1, sizeof sg);
    FOR(i, 0, 21) sg[(1<<i)-1] = 0;
    
    FOR(i, 0, N-1) sg[i] = get(i);
    
    scanf("%d", &t);
    while(t--) {
        int n;
        scanf("%d", &n);
        int ans = 0;
        for(int i = 1; i <= n; ++i) {
            int num;
            scanf("%d", &num);
            int state = 0;
            for(int j = 1; j <= num; ++j) {
                int pos;
                scanf("%d", &pos);
                state += 1<<(20-pos);
            }
            //cout << state<<endl;
            //cout << sg[state]<<endl;
            ans ^= sg[state];
        }
        if(ans) puts("YES");
        else puts("NO");
    }
    return 0;
}

D.GCD

超级预处理题，用rmq预处理f[i][j] 为从i开始，往后$2^j$个数的gcd，则 $a_i……a_j$的gcd为 gcd(f[i][k], f[r-(1«k)+1][k]), k为log2(r-l+1). 同时因为gcd为单调不增，每次至少/2，所以gcd的数量为nlog2(n)。可以枚举左端点 i 从1-n，对每个i，二分右端点，计算每种gcd值的数量，用map存下来

/*
 * Author:  JiangYu
 * Created Time:  2018/5/24 22:37:54
 * File Name: D.cpp
 */
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
#define PB push_back
#define X first
#define Y second
#define FI first
#define SE second
#define inf 0x3f3f3f3f
#define FOR(i,a,b) for(int i = a; i <= b; ++i)
#define FORD(i,a,b) for(int i = b; i >= a; --i)
#define ALL(x) x.begin(),x.end()
#define REP(i,a) for(int i = 0; i < a; ++i)
#define DEP(i,a) for(int i = a-1; i >= 0; --i)
#define CLR(a) memset(a, 0, sizeof a)
const int N = 1e5 + 1024;
int f[N][20];
int a[N];
int n, m;
int gcd(int a, int b) {
    return b ? gcd(b, a%b) : a;
}
void rmq() {
    for(int i = 1; i <= n; ++i) f[i][0] = a[i];
    for(int i = 1; i < 18; ++i) {
        for(int j = 1; j <= n; ++j) {
            if(j + (1<<i) - 1 <= n) {
                f[j][i] = gcd(f[j][i-1], f[j+(1<<i-1)][i-1]);
            }
        }
    }
}
int look(int l, int r) {
    int k = (int) log2((double) (r-l+1));
    return gcd(f[l][k], f[r-(1<<k)+1][k]);
}
map<int, ll> mp;
void Set() {
    mp.clear();
    for(int i = 1; i <= n; ++i) {
        int g = f[i][0], j = i;
        while(j <= n) {
            int l = j, r = n;
            while(l < r) {
                int mid = (l + r + 1) >> 1;
                if(look(i, mid) == g) l = mid;
                else r = mid - 1;
            }
            mp[g] += l - j + 1;
            j = l + 1;
            g = look(i, j);
        }
    }
}
int main() {
    int t, l, r;
    int cas = 1;
    scanf("%d", &t);
    while(t--) {
        printf("Case #%d:\n", cas++);
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &a[i]);
        }
        rmq();
        Set();
        scanf("%d", &m);
        for(int i = 1; i <= m; ++i) {
            scanf("%d%d", &l, &r);
            int g = look(l, r);
            printf("%d %I64d\n", g, mp[g]);
        }
    }
    return 0;
}

E.Necklace

枚举所有阴珠的排序，根据ban掉的边建立反图，然后跑一遍最大匹配，即为不会被影响的阳珠数量，找最大的就好

/*
 * Author:  JiangYu
 * Created Time:  2018/5/24 17:00:46
 * File Name: E.cpp
 */
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
#define PB push_back
#define X first
#define Y second
#define FI first
#define SE second
#define inf 0x3f3f3f3f
#define FOR(i,a,b) for(int i = a; i <= b; ++i)
#define FORD(i,a,b) for(int i = b; i >= a; --i)
#define ALL(x) x.begin(),x.end()
#define REP(i,a) for(int i = 0; i < a; ++i)
#define DEP(i,a) for(int i = a-1; i >= 0; --i)
#define CLR(a) memset(a, 0, sizeof a)
int n, m;
int g[20][20];
int ban[20][20];
int x[20], y[20];
bool used[20];
bool path(int u) {
    for(int i = 1; i <= n; ++i) {
        if(g[u][i] && !used[i]) {
            used[i] = 1;
            if(!y[i] || path(y[i])) {
                y[i] = u;
                x[u] = i;
                return 1;
            }
        }
    }
    return 0;
}
int pe[20];
void fin() {
    int ans = 10;
    for(int i = 1; i <= n; ++i) pe[i] = i;
    do{
        CLR(x), CLR(y);    
        CLR(g);
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= n; ++j) {
                int px, py;
                if(i == 1) px = pe[i], py = pe[n];
                else px = pe[i], py = pe[i-1];
                
                if(ban[j][px] || ban[j][py]) continue;
                g[i][j] = 1;
            }
        }
        
        int sum = 0;
        for(int i = 1; i <= n; ++i) {
            //cout << pe[i];
            CLR(used);
            if(path(i)) sum++;
        }
        ans = min(ans, n - sum);
        
    }while(next_permutation(pe+2, pe+n+1));
    printf("%d\n", ans);
}
int main() {
    while(cin>> n>>m) {
        if(n == 0) {
            puts("0");
            continue;
        }
        CLR(ban);
        
        for(int i = 1; i <= m; ++i) {
            int u, v;
            cin >> u>> v;
            ban[u][v] = 1;
        }
        fin();
    }
    return 0;
}

G.Rigid Frameworks

给一个单元格里加一条线，那么他所在的行与列均会被锁定。而整个矩形稳定的条件显然就是每一行每一列均被锁定，类比于这一行与这一列被连起来了。那么问总共有多少种方案，等效于一个{n+m}的二分图，所有点均联通的方案数。其次，每个格子可以选择0,1,2条线，共三种情况。所以不考虑是否合法，共有$ 3^{n * m} $种连法。单纯的考虑合法的数量显然十分困难，但是考虑不合法的数量则没有那么麻烦了。因为只要二分图里任意一个点未联通，则这种情况就是非法的。

设想，固定一个点1，他所在的联通块必须包含所有点才是一个合法情况。那么我们可以设计出这样一个式子： $ dp[n][m] = 3^{n \times m} - C[n-1][i-1] \times C[m][j] \times dp[i][j] \times 3^{(n-i) \times (m-j)} $ 从n-1个点中选出i-1个点（因为点1已经被固定了），从m个点中选出j个点，用这i，j个点组成连通块的数量就是 $C[n-1][i-1] \times C[m][j] $ ，i+j大小的连通块有dp[i][j]个合法的存在方案，同时，下面的n-i个点和m-j个点有 $3^{(n-i) \times (m-j)} $个组合方式。

重复一下：$固定一个点，枚举这个点所处连通块的情况，只要这个连通块不包含二分图中所有的点，则当前的二分图一定是不连通的，一定是非法方案。$

/*
 * Author:  JiangYu
 * Created Time:  2018/5/24 23:47:47
 * File Name: G.cpp
 */
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
#define PB push_back
#define X first
#define Y second
#define FI first
#define SE second
#define inf 0x3f3f3f3f
#define FOR(i,a,b) for(int i = a; i <= b; ++i)
#define FORD(i,a,b) for(int i = b; i >= a; --i)
#define ALL(x) x.begin(),x.end()
#define REP(i,a) for(int i = 0; i < a; ++i)
#define DEP(i,a) for(int i = a-1; i >= 0; --i)
#define CLR(a) memset(a, 0, sizeof a)
const int MOD = 1e9 + 7; 
const int N = 20;
ll fact[N*N], c[N][N], dp[N][N];

int main() {
    int n = 11, m;
    fact[0] = 1;
    for(int i = 1; i <= n*n; ++i) fact[i] = fact[i-1] * 3 % MOD;
    c[0][0] = 1;
    for(int i = 1; i < N; ++i) {
        c[i][0] = c[i][i] = 1;
        for(int j = 1; j < i; ++j) {
            c[i][j] = (c[i-1][j] + c[i-1][j-1]) % MOD;
        }
    }
    for(int i = 1; i <= 10; ++i) {
        for(int j = 0; j <= 10; ++j) {
            dp[i][j] = fact[i*j];
            if(i == 1 && j == 0) dp[i][j] = 1;
            for(int k = 1; k <= i; ++k) {
                for(int l = 0; l <= j; ++l) {
                    if(i == k && j == l) continue;
                    dp[i][j] -= c[i-1][k-1]*c[j][l] % MOD * dp[k][l] % MOD * fact[(i-k)*(j-l)] % MOD;
                    dp[i][j] = (dp[i][j] % MOD + MOD) % MOD;
                }
            }
        }
    }
    while(cin>> n>> m) {
        cout << dp[n][m]<<endl;
    }
    return 0;
}

k.tetrahedron

四面体内切球公式了解一下

球心坐标

{\begin{aligned} x = \frac{s_{1} x_{1} + s_{2} x_{2} + s_{3} x_{3} + s_{4} x_{4}}{s_{1} + s_{2} + s_{3} + s_{4}} \\ y = \frac{s_{1} y_{1} + s_{2} y_{2} + s_{3} y_{3} + s_{4} y_{4}}{s_{1} + s_{2} + s_{3} + s_{4}} \\ z = \frac{s_{1} z_{1} + s_{2} z_{2} + s_{3} z_{3} + s_{4} z_{4}}{s_{1} + s_{2} + s_{3} + s_{4}} \end{aligned}

内切球半径 \begin{aligned} r \ = \ \frac{3V}{s_1+s_2+s_3+s_4}
\end{aligned}

面积可以用三维叉积求，体积则用混合积若体积为0，则内切球不存在

/*
 * Author:  JiangYu
 * Created Time:  2018/5/24 19:38:16
 * File Name: K.cpp
 */
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
#define PB push_back
#define X first
#define Y second
#define FI first
#define SE second
#define inf 0x3f3f3f3f
#define FOR(i,a,b) for(int i = a; i <= b; ++i)
#define FORD(i,a,b) for(int i = b; i >= a; --i)
#define ALL(x) x.begin(),x.end()
#define REP(i,a) for(int i = 0; i < a; ++i)
#define DEP(i,a) for(int i = a-1; i >= 0; --i)
#define CLR(a) memset(a, 0, sizeof a)
struct node{
    ll x, y, z;
}p[10];
node operator - (node a, node b) {
    return (node){b.x - a.x, b.y - a.y, b.z - a.z};
}
double dis(node a) {
    return sqrt(a.x*a.x + a.y*a.y + a.z*a.z);
}
node cross(node a, node b) {
    return (node) {a.y*b.z - b.y*a.z, a.z*b.x - a.x*b.z, a.x*b.y - a.y*b.x};
}
double dot(node a, node b) {
    return a.x*b.x + a.y*b.y + a.z*b.z;
}
double pointtoface(node c, node a, node b, node d) {
    node m = cross(b-a, d-a);
    return dot(m, c-a) / dis(m);    
}
void read(node &n) {
    cin>> n.x>> n.y>> n.z;
}
int main() {
    double s[5];
    while(cin>> p[1].x>> p[1].y>> p[1].z ) {
        read(p[2]), read(p[3]), read(p[4]);
        if(dot(cross(p[2] - p[1], p[3] - p[1]), p[4]) == 0) {
            printf("O O O O\n");
            continue;
        }
        double ts = 0;
        s[1] = dis(cross(p[3] - p[2], p[4] - p[2])) / 2;
        s[2] = dis(cross(p[3] - p[1], p[4] - p[1])) / 2;
        s[3] = dis(cross(p[2] - p[1], p[4] - p[1])) / 2;
        s[4] = dis(cross(p[3] - p[1], p[2] - p[1])) / 2;
        for(int i = 1; i <= 4; ++i) ts += s[i];
        double h = pointtoface(p[3], p[1], p[2], p[4]);
        double r =fabs(s[3] / ts * h);
        double x=(s[1]*p[1].x+s[2]*p[2].x+s[3]*p[3].x+s[4]*p[4].x)/ts;
        double y=(s[1]*p[1].y+s[2]*p[2].y+s[3]*p[3].y+s[4]*p[4].y)/ts;
        double z=(s[1]*p[1].z+s[2]*p[2].z+s[3]*p[3].z+s[4]*p[4].z)/ts;
        printf("%.4f %.4f %.4f %.4f\n",x,y,z,r); 
    }
    return 0;
}