2018-05-24
先跑一个最小生成树,然后任选一个点为根,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;
}
每一行独立,先预处理出所有的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;
}
超级预处理题,用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;
}
枚举所有阴珠的排序,根据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;
}
给一个单元格里加一条线,那么他所在的行与列均会被锁定。而整个矩形稳定的条件显然就是每一行每一列均被锁定,类比于这一行与这一列被连起来了。那么问总共有多少种方案,等效于一个{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;
}
四面体内切球公式了解一下
球心坐标
内切球半径
\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;
}