8/11
2016 Multi-University Training Contest 1
最小生成树+线性期望 A Abandoned country（BH）
题意：
1. 求最小生成树 2. 求在某一棵最小生成树任意两点的最小距离的期望值。
思路：
首先题目说了边权值都是不同的，所以最小生成树唯一。那么只要统计出最小生成树的每一条边在“任意两点走经过它“的情况下所贡献的值，发现在一棵树里，一条边所贡献的次数为，sz[v]表示v子树包括节点v的个数。如下图所示，红边所贡献的次数即为”选一个蓝点再选一个绿点“的方案数。
代码：
#include <bits/stdc++.h>
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<pair<int, int> > 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<tot; ++i) {
int u = edges[i].u, v = edges[i].v, w = edges[i].w;
int fu = Find (u), fv = Find (v);
if (fu == fv) continue;
sum += w;
rt[fv] = fu;
edge[u].push_back ({v, w});
edge[v].push_back ({u, w});
}
printf ("%I64d %.2f\n", sum, solve ());
}
return 0;
}
状态压缩+博弈 B Chess（BH）
题意：
有n*20的格子，某些格子上有棋子，A和B轮流操作，可以一个棋子放到右边第一个空位置，不能操作者输，A先操作，问输赢。
思路：
这是简单的Nim问题，状态压缩，算出所有状态的sg值。看完训练指南的内容再结合代码应该能懂了吧。
代码：
#include <bits/stdc++.h> 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<<i)) {
int j = i - 1;
while (j >= 0 && (u & (1<<j))) j--;
if (j >= 0) {
int v = u ^ (1<<i) ^ (1<<j);
vis[sg[v]] = 1;
}
}
}
for (int i=0; ; ++i) {
if (!vis[i]) return i;
}
} void init() {
memset (sg, -1, sizeof (sg));
int x = 0;
sg[0] = 0;
//预处理对于所有必输态赋值为0
for (int i=0; i<20; ++i) {
x |= (1<<i);
sg[x] = 0;
}
for (int i=1; i<(1<<20); ++i) {
if (sg[i] == -1) sg[i] = mex (i);
}
} int main() {
init ();
int T;
scanf ("%d", &T);
while (T--) {
int n;
scanf ("%d", &n);
int ans = 0;
for (int i=1; i<=n; ++i) {
int m;
scanf ("%d", &m);
int tmp = 0;
for (int j=1; j<=m; ++j) {
int x;
scanf ("%d", &x);
//为了从小到大递推，和计算机二进制数方向相同
tmp |= (1<<(20-x));
}
ans ^= sg[tmp];
}
printf ("%s\n", ans > 0 ? "YES" : "NO");
}
return 0;
}
最短路？搜索？不会 C Game
数论（区间GCD问题）D GCD（BH）
题意：
1. 区间[l, r]的GCD值 2. 问有多少个区间的GCD值为gcd
思路：
第一个操作线段树或者ST都可以做，第二个问题的关键点是
简单来说，就是固定右端点R，然后左端点往左边移动，查询GCD，如果相同就跳到这个GCD所对应的区间的左端点（并且维护这个gcd现在的区间的两端点的位置），因为一个数的质因数最多有log(x)个，而且求GCD是递减的过程，所以跳跃的次数是log级的。
本场比赛就因为这题坑了好久，GCD的性质不够了解。学习资料
代码：
#include <bits/stdc++.h> 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 | 1 int 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<int, long long> 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 Necklace（BH）
题意：
有n颗阳属性的珠子和n颗阴属性的珠子，给了m条规则，就是某些阳珠子和阴珠子不能相邻，问2*n颗串成项链后最少几颗会违反规则。
思路：
先枚举阴珠子的排列顺序（固定第一个不动，因为是环）。然后对于某一个排列，问题可以转换为”阳珠子如何插如使得不违反规则的珠子最多“，这个用匈牙利算法解决，时间复杂度为
。卿学姐DFS剪个枝也能过？数据水了吧
代码：
#include <bits/stdc++.h> int n, m; std::vector<int> 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 PowMod（CYD）
2016多校训练一 PowMod，hdu5728（欧拉函数+指数循环节）
题意：
求 时，ans=
mod p,ans的值，其中n的每个素因子的幂次都是1，
是欧拉函数。
思路：
解题分两部分完成，第一部分首先求出k，有公式
（素数p是n的一个质因子）
由此可以递归求出k的值，f(n,m)=(p的欧拉值)*f(n/p,m)+f(n,m/p)。
第二部分的无限次幂，由公式
不断求欧拉值最终使值变得有限。
代码：
#include <bits/stdc++.h>
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<n;i++)
{
if(!vis[i])
{
pri[tot++]=i;
phi[i]=i-1;
}
for(int j=0;j<tot && i*pri[j]<n;j++)
{
vis[i*pri[j]]=true;
if(i%pri[j]==0)
{
phi[i*pri[j]]=phi[i]*pri[j];
break;
}
else
phi[i*pri[j]]=phi[i]*(pri[j]-1);
}
}
sum[0]=0;
for(int i=1;i<N;i++)
sum[i]=(sum[i-1]+phi[i])%M;
} ll Pow(ll a,ll n,ll mod)
{
ll ans=1;
while(n)
{
if(n&1)
{
ans=ans*a%mod;
}
a=a*a%mod;
n>>=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<tot;i++)
{
if(!vis[n])
{
a[rear++]=n;
break;
}
if(n%pri[i]==0)
{
a[rear++]=pri[i];
n/=pri[i];
}
}
} ll f(int pos,ll n,ll m)
{
if(n==1)
return sum[m];
if(m==0)
return 0;
return ((a[pos]-1)*f(pos-1,n/a[pos],m)%M+f(pos,n,m/a[pos]))%M;
} int main()
{
init();
ll n,m,p;
while(scanf("%I64d%I64d%I64d",&n,&m,&p)!=EOF)
{
rear=0;
resolve(n);
ll k=f(rear-1,n,m);
ll ans=solve(k,p);
printf("%I64d\n",ans%p);
}
return 0;
}
UPD：二分图连通图计数 不会 H Rigid Frameworks （BH）（51Nod原题）
题意：
给n*m的格子，可以加上斜线，问有多少种方案使得整个格子不能倾斜，也就是不能像下图一样：
思路：
网上写的不错的解题报告。问题的关键点是模型转换成二分图的连通计数，然后就是所有方案减去不符合的方案数。
代码：
#include <bits/stdc++.h> 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<i; ++j) {
C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
}
}
//dp[n][m][k]表示n行m列取k个斜线
for (int i=1; i<=10; ++i) {
dp[i][0][0] = i == 1 ? 1 : 0;
for (int j=1; j<=i; ++j) {
for (int k=1; k<=i*j; ++k) {
dp[i][j][k] = C[i*j][k];
for (int ii=1; ii<=i; ++ii) {
for (int jj=0; jj<=j; ++jj) {
int kb = std::min (k, ii * jj);
for (int kk=0; kk<=kb; ++kk) {
if (f (ii, jj, kk) && (i-ii)*(j-jj)>=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 <bits/stdc++.h> typedef long long ll;
const int MOD = 1e9 + 7;
const int N = 16;
int dp[2][1<<N];
int f[N+1][N+1], g[N+1][N+1][1<<N], ans[N+1][N+1]; void add_mod(int &a, int b) {
a += b;
if (a >= 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<n; ++i) {
for (int j=0; j<m; ++j) {
cur ^= 1;
memset (dp[cur], 0, sizeof (dp[cur]));
for (int s=0; s<limit; ++s) {
if (dp[cur^1][s] == 0) continue;
//s状态第j位是已填
if (s & (1<<j)) {
if (j && !(s&(1<<(j-1)))) {
//往左放
add_mod (dp[cur][s^(1<<(j-1))], dp[cur^1][s]);
}
//不放
add_mod (dp[cur][s^(1<<j)], dp[cur^1][s]);
} else {
//往上放
add_mod (dp[cur][s^(1<<j)], dp[cur^1][s]);
}
}
}
}
//保存方案数
f[n][m] = dp[cur][limit-1];
}
} //容斥原理，乘法原理
std::vector<int> 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<limit; ++s) {
lens.clear ();
int last = -1, num = 0;
for (int i=0; i<m-1; ++i) {
if (s & (1<<i)) {
lens.push_back (i-last);
last = i;
num++;
}
}
lens.push_back (m-1-last);
int &now = g[n][m][s]; //f[n][len1]*f[n][len2]*...
now = 1;
for (int i=0; i<lens.size (); ++i) {
int len = lens[i];
now = (ll) now * f[n][len] % MOD;
}
//如果有横分割线，一定减去
for (int i=1; i<n; ++i) {
ll up = g[i][m][s];
ll down = 1; //g[n-i][m][s]
for (int j=0; j<lens.size (); ++j) {
int len = lens[j];
down = (ll) down * f[n-i][len] % MOD;
}
add_mod (now, -(ll) up * down % MOD);
}
if (num & 1) add_mod (ans[n][m], -now);
else add_mod (ans[n][m], now);
}
}
}
} int main() {
init ();
int n, m;
while (scanf ("%d%d", &n, &m) == 2) {
if (n < m) std::swap (n, m);
printf ("%d\n", ans[n][m]);
}
return 0;
}
树的同构判断 不会 J Subway
三维计算几何 K tetrahedron（BH，CYD）
题意：
求四面体的内切圆的坐标和半径。
思路：
求半径公式：，体积和三角形面积有函数可以算。
求圆心坐标公式：，三个坐标系分开算就可以了。
代码：
#include <bits/stdc++.h>
const double EPS = 1e-10;
int dcmp(double x) {
return fabs (x) < EPS ? 0 : x < 0 ? -1 : 1;
}
struct Point3 {
double x, y, z;
Point3(double x=0, double y=0, double z=0) : x(x), y(y), z(z) {}
};
typedef Point3 Vector3;
Vector3 operator - (Point3 A, Point3 B) {
return Vector3 (A.x-B.x, A.y-B.y, A.z-B.z);
}
//叉积
Vector3 Cross(Vector3 A, Vector3 B) {
return Vector3 (A.y*B.z-A.z*B.y, A.z*B.x-A.x*B.z, A.x*B.y-A.y*B.x);
}
double Dot(Vector3 A, Vector3 B) {
return A.x*B.x+A.y*B.y+A.z*B.z;
}
double Volume6(Point3 A, Point3 B, Point3 C, Point3 D) {
return Dot (D-A, Cross (B-A, C-A));
}
double Length(Vector3 A) {
return sqrt (Dot (A, A));
}
Point3 A, B, C, D;
void solve() {
double v6 = Volume6 (A, B, C, D);
Vector3 BC = C - B, BD = D - B, BA = A - B, CA = A - C, CD = D - C;
Vector3 n = Cross (BC, BD);
if (dcmp (Dot (BA, n)) == 0) {
puts ("O O O O");
return ;
}
v6 = fabs (v6);
double SABC = Length (Cross (BA, BC)) * 0.5;
double SBAD = Length (Cross (BA, BD)) * 0.5;
double SBCD = Length (Cross (BC, BD)) * 0.5;
double SCAD = Length (Cross (CD, CA)) * 0.5;
double SS = SABC + SBAD + SBCD + SCAD;
//V = SS * R * (1/3)
double R = v6 / 2 / SS; //(1/3)
Point3 O;
O.x = (A.x*SBCD + B.x*SCAD + C.x*SBAD + D.x*SABC) / SS;
O.y = (A.y*SBCD + B.y*SCAD + C.y*SBAD + D.y*SABC) / SS;
O.z = (A.z*SBCD + B.z*SCAD + C.z*SBAD + D.z*SABC) / SS;
printf ("%.4f %.4f %.4f %.4f\n", O.x, O.y, O.z, R);
}
int main() {
while (scanf ("%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf", &A.x, &A.y, &A.z, &B.x, &B.y, &B.z, &C.x, &C.y, &C.z, &D.x, &D.y, &D.z) == 12) {
solve ();
}
return 0;
}