2016 Multi-University Training Contest 1

http://acm.hdu.edu.cn/search.php?field=problem&key=2016+Multi-University+Training+Contest+1&source=1&searchmode=source

1001 Abandoned country

题意：n个数 m条边 求最小生成树，和最小生成树上任意两点之间的平均距离

思路：最小生成树上任意两点之间的平均距离=总的距离/点的对数

总的距离=所有路径中每条边出现的次数*权值

所有路径每条边出现的次数=该点为根树的节点数*（n-该点为根树的节点数）

点的对数为=n*(n-1)/2;

prim邻接表：O(elogv)

K邻接表：O(eloge)

  1 // #pragma comment(linker, "/STACK:102c000000,102c000000")
  2 #include <iostream>
  3 #include <cstdio>
  4 #include <cstring>
  5 #include <sstream>
  6 #include <string>
  7 #include <algorithm>
  8 #include <list>
  9 #include <map>
 10 #include <vector>
 11 #include <queue>
 12 #include <stack>
 13 #include <cmath>
 14 #include <cstdlib>
 15 // #include <conio.h>
 16 using namespace std;
 17 #define clc(a,b) memset(a,b,sizeof(a))
 18 #define inf 0x3f3f3f3f
 19 #define lson l,mid,rt<<1
 20 #define rson mid+1,r,rt<<1|1
 21 const int N = 1e5+10;
 22 const int M = 1e6+10;
 23 const int MOD = 1e9+7;
 24 #define LL long long
 25 #define mi() (l+r)>>1
 26 double const pi = acos(-1);
 27 
 28 void fre() {
 29     freopen("in.txt","r",stdin);
 30 }
 31 
 32 // inline int r() {
 33 //     int x=0,f=1;char ch=getchar();
 34 //     while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
 35 //     while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}return x*f;
 36 // }
 37 
 38 struct Edge{
 39     int u,v,w;
 40     int next;
 41     Edge(int u_=0,int v_=0,int w_=0):u(u_),v(v_),w(w_){}
 42     bool operator < (const Edge &rhs) const{
 43         return w>rhs.w;
 44     }
 45 }e2[N*2],e1[M*2];
 46 
 47 int tot,n,m;
 48 int h1[N],h2[N];
 49 double dp[N];
 50 int sum[N];
 51 
 52 void init(){
 53      clc(h1,-1);
 54      tot=0;
 55      clc(dp,0);
 56 }
 57 
 58 void add1(int u,int v,int w){
 59     e1[tot].v=v;
 60     e1[tot].w=w;
 61     e1[tot].next=h1[u];
 62     h1[u]=tot++;
 63 }
 64 void add2(int u,int v,int w){
 65      e2[tot].u=u;
 66      e2[tot].v=v;
 67      e2[tot].w=w;
 68      e2[tot].next=h2[u];
 69      h2[u]=tot++;
 70 }
 71 int d[N];
 72 bool vis[N];
 73 priority_queue<Edge>q;
 74 LL  prim(){
 75     LL ans;
 76     ans=0;
 77     while(!q.empty())q.pop();
 78     q.push(Edge(-1,1,0));
 79     clc(vis,0);
 80     for(int i=1;i<=n;++i) d[i]=inf,h2[i]=-1,vis[i]=0;
 81     tot=0;
 82     d[1]=0;
 83     int cnt=0;
 84     while(!q.empty()){
 85        Edge tmp=q.top();
 86        q.pop();
 87        if(vis[tmp.v])continue;
 88        if(tmp.u!=-1){
 89          add2(tmp.u,tmp.v,tmp.w);
 90          add2(tmp.v,tmp.u,tmp.w);
 91        }
 92        ans+=tmp.w;
 93        vis[tmp.v]=true;
 94        ++cnt;
 95        if(cnt==n)break;
 96        for(int i=h1[tmp.v];~i;i=e1[i].next){
 97           int v=e1[i].v;
 98           if(vis[v])continue;
 99           int w=e1[i].w;
100           if(d[v]>w){
101             d[v]=w;
102             q.push(Edge(tmp.v,v,d[v]));
103           }
104        }
105     }
106     return ans;
107 }
108 
109 
110 void dfs(int u,int f){
111     sum[u]=1;
112     for(int i=h2[u];~i;i=e2[i].next){
113         int v=e2[i].v;
114         if(v==f) continue;
115         dfs(v,u);
116         sum[u]+=sum[v];
117         dp[u]+=dp[v]+1.0*e2[i].w*sum[v]*(n-sum[v]);
118     }
119 }
120 int main(){
121     // fre();
122     int T;
123     scanf("%d",&T);
124     while(T--){
125         scanf("%d%d",&n,&m);
126         init();
127         for(int i=0;i<m;i++){
128             int u,v,w;
129             scanf("%d%d%d",&u,&v,&w);
130             add1(u,v,w);
131             add1(v,u,w);
132         }
133         LL ans=prim();
134         dfs(1,-1);
135         double q=(double)n*(n-1)/2;
136         printf("%I64d %.2f
",ans,dp[1]/q);
137     }
138     return 0;
139 }
View Code

 1004 GCD

题意：n个数，q次询问，输出数组中有多少对区间的gcd = l到r的gcd

思路：官方题解

我们注意观察gcd(a_{l},a_{l+1},...,a_{r})gcd(a​l​​,a​l+1​​,...,a​r​​)，当l固定不动的时候，r=l...nr=l...n时，我们可以容易的发现,随着rr的増大，gcd(a_{l},a_{l+1},...,a_{r})gcd(a​l​​,a​l+1​​,...,a​r​​)是递减的，同时gcd(a_{l},a_{l+1},...,a_{r})gcd(a​l​​,a​l+1​​,...,a​r​​)最多 有log 1000,000,000log 1000,000,000个不同的值，为什么呢？因为a_{l}a​l​​最多也就有log 1000,000,000log 1000,000,000个质因数

所以我们可以在log级别的时间处理出所有的以L开头的左区间的gcd(a_{l},a_{l+1},...,a_{r})gcd(a​l​​,a​l+1​​,...,a​r​​) 那么我们就可以在n log 1000,000,000n log 1000,000,000的时间内预处理出所有的gcd(a_{l},a_{l+1},...,a_{r})gcd(a​l​​,a​l+1​​,...,a​r​​)然后我们可以用一个map来记录，gcd值为key的有多少个 然后我们就可以对于每个询问只需要查询对应gcd(a_{l},a_{l+1},...,a_{r})gcd(a​l​​,a​l+1​​,...,a​r​​)为多少，然后再在map 里面查找对应答案即可.

 1 // #pragma comment(linker, "/STACK:102c000000,102c000000")
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <sstream>
 6 #include <string>
 7 #include <algorithm>
 8 #include <list>
 9 #include <map>
10 #include <vector>
11 #include <queue>
12 #include <stack>
13 #include <cmath>
14 #include <cstdlib>
15 // #include <conio.h>
16 using namespace std;
17 #define clc(a,b) memset(a,b,sizeof(a))
18 #define inf 0x3f3f3f3f
19 #define lson l,mid,rt<<1
20 #define rson mid+1,r,rt<<1|1
21 const int N = 1e5+10;
22 const int M = 1e6+10;
23 const int MOD = 1e9+7;
24 #define LL long long
25 #define mi() (l+r)>>1
26 double const pi = acos(-1);
27 
28 void fre() {
29     freopen("in.txt","r",stdin);
30 }
31 
32 // inline int r() {
33 //     int x=0,f=1;char ch=getchar();
34 //     while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
35 //     while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}return x*f;
36 // }
37 #define pb push_back
38 #define mk make_pair
39 typedef pair<int,int> PII;
40 int a[N];
41 int n,q;
42 vector<PII>g[N];
43 map<int,LL>mp;
44 void GCD(){
45     for(int i=1;i<=n;i++){
46         int last=0;
47         for(int j=0;j<(int)g[i-1].size();j++){
48             int u=g[i-1][j].first,v=g[i-1][j].second;
49             int tem=__gcd(u,a[i]);
50             if(tem==last) continue;
51             last=tem;
52             g[i].pb(mk(tem,v));
53         }
54         if(last!=a[i]) g[i].pb(mk(a[i],i));
55         for(int j=0;j<(int)g[i].size();j++)
56             mp[g[i][j].first]+=(j==(int)g[i].size()-1 ? i+1:g[i][j+1].second)-g[i][j].second;
57     }
58 }
59 int main(){
60     // fre();
61     int T;
62     scanf("%d",&T);
63     for(int cas=1;cas<=T;cas++){ 
64         scanf("%d",&n);
65         for(int i=1;i<=n;i++) scanf("%d",&a[i]);
66         mp.clear();
67         for(int i=0;i<=n+1;i++) g[i].clear();
68         GCD();
69         printf("Case #%d:
",cas);
70         scanf("%d",&q);
71         while(q--){
72             int l,r;
73             scanf("%d%d",&l,&r);
74             int k;
75             for(k=0;k<(int)g[r].size();k++){
76                 if(g[r][k].second>l) break;
77             }
78             printf("%d %I64d
",g[r][k-1].first,mp[g[r][k-1].first]);
79         }
80     }
81     return 0;
82 }
View Code

 1002Chess

题意：n*20的棋盘，给你n行，每行m个，每位选手把棋子移到右边第一个空的位置，移不动则输，问先手是否必赢

思路：预处理sg函数

 1 // #pragma comment(linker, "/STACK:102c000000,102c000000")
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <sstream>
 6 #include <string>
 7 #include <algorithm>
 8 #include <list>
 9 #include <map>
10 #include <vector>
11 #include <queue>
12 #include <stack>
13 #include <cmath>
14 #include <cstdlib>
15 // #include <conio.h>
16 using namespace std;
17 #define clc(a,b) memset(a,b,sizeof(a))
18 #define inf 0x3f3f3f3f
19 #define lson l,mid,rt<<1
20 #define rson mid+1,r,rt<<1|1
21 const int N = 1e5+10;
22 const int M = 1e6+10;
23 const int MOD = 1e9+7;
24 #define LL long long
25 #define mi() (l+r)>>1
26 double const pi = acos(-1);
27 
28 void fre() {
29     freopen("in.txt","r",stdin);
30 }
31 
32 // inline int r() {
33 //     int x=0,f=1;char ch=getchar();
34 //     while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
35 //     while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}return x*f;
36 // }
37 int sg[1<<20];
38 int vis[25];
39 void SG(){
40     for(int i=1;i<(1<<20);i++){
41         clc(vis,-1);
42         int last=-1;
43         for(int j=0;j<20;j++){
44             if(!((i>>j)&1)) last=j;
45             if(((i>>j)&1)){
46                 if(last!=-1){
47                     vis[sg[i^(1<<last)^(1<<j)]]=1;//当前状态能转移到的
48                 }
49             }
50         }
51         int j=0;
52         while(vis[j]!=-1) j++;
53         sg[i]=j;
54     }
55 }
56 
57 int main(){
58     // fre();
59     SG();
60     int T;
61     int n,m;
62     scanf("%d",&T);
63     while(T--){
64        scanf("%d",&n);
65        int ans=0;
66        for(int i=1;i<=n;i++){
67            int tem=0;
68            scanf("%d",&m);
69            for(int j=0;j<m;j++){
70               int x;
71               scanf("%d",&x);
72               tem^=1<<(20-x);
73            }
74            ans^=sg[tem];
75        }
76        if(ans) puts("YES");
77        else puts("NO");
78     }
79     return 0;
80 }
View Code

 1011

题意：计算四面体内接圆的圆心和半径

思路：

1.题解是直接套公式；

2.网上很多都是根据这个公式 四面体的内心坐标公式及其应用 求出来的。

海伦公式为：S = sqrt(s1* (s1-a) * (s1-b)*(s1-c))，其中s1表示的是三角形的周长的一半。
最后求内切球的球心，公式为：
ansx=( Sabc*a[4].x+Sabd*a[3].x + Sacd*a[2].x+Sbcd*a[1].x)/S; 
ansy=( Sabc*a[4].y+Sabd*a[3].y + Sacd*a[2].y+Sbcd*a[1].y)/S; 
ansz=( Sabc*a[4].z+Sabd*a[3].z + Sacd*a[2].z+Sbcd*a[1].z)/S; 
其中S为表面积。
3.计算几何公式太多，根本不可能背完，真正比赛的时候还是要自己推导公式，所以，这题可以先求半径，再求坐标；
半径：内心与四个面可形成的四面体与四面体体积关系可以求出半径
圆心：把三个平面按半径方向平移半径长度后，两个平面得到交线，三个平面得到点
  1 // #pragma comment(linker, "/STACK:102c000000,102c000000")
  2 #include <iostream>
  3 #include <cstdio>
  4 #include <cstring>
  5 #include <sstream>
  6 #include <string>
  7 #include <algorithm>
  8 #include <list>
  9 #include <map>
 10 #include <vector>
 11 #include <queue>
 12 #include <stack>
 13 #include <cmath>
 14 #include <cstdlib>
 15 // #include <conio.h>
 16 using namespace std;
 17 #define clc(a,b) memset(a,b,sizeof(a))
 18 #define inf 0x3f3f3f3f
 19 #define lson l,mid,rt<<1
 20 #define rson mid+1,r,rt<<1|1
 21 const int N = 1e5+10;
 22 const int M = 1e6+10;
 23 const int MOD = 1e9+7;
 24 #define LL long long
 25 #define mi() (l+r)>>1
 26 double const pi = acos(-1);
 27 const double eps = 1e-8;
 28 void fre() {
 29     freopen("in.txt","r",stdin);
 30 }
 31 
 32 // inline int r() {
 33 //     int x=0,f=1;char ch=getchar();
 34 //     while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
 35 //     while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}return x*f;
 36 // }
 37 
 38 
 39 int dcmp(double x){
 40     return fabs(x)<eps ? 0 : (x<0 ? -1:1);
 41 }
 42 
 43 struct Point {
 44     double x, y, z;
 45     Point (double _x = 0, double _y = 0, double _z = 0) : x(_x), y(_y), z(_z) {}
 46     void input () {
 47         scanf ("%lf%lf%lf", &x, &y, &z);
 48     }
 49     void output () {
 50         printf ("%.2f %.2f %.2f
", x, y, z);
 51     }
 52     bool operator == (const Point &b) const {
 53         return dcmp (x-b.x) == 0 && dcmp (y-b.y) == 0 && dcmp (z-b.z) == 0;
 54     }
 55     double len2 () {
 56         return x*x+y*y+z*z;
 57     }
 58     double len () {
 59         return sqrt (x*x + y*y + z*z);
 60     }
 61     Point operator - (const Point &b) const {
 62         return Point (x-b.x, y-b.y, z-b.z);
 63     }
 64     Point operator + (const Point &b) const {
 65         return Point (x+b.x, y+b.y, z+b.z);
 66     }
 67     Point operator * (const double &k) const {
 68         return Point (x*k, y*k, z*k);
 69     }
 70     Point operator / (const double &k) const {
 71         return Point (x/k, y/k, z/k);
 72     }
 73     double operator * (const Point &b) const {
 74         return x*b.x+y*b.y+z*b.z;
 75     }
 76     Point operator ^ (const Point &b) const {
 77         return Point (y*b.z-z*b.y, z*b.x-x*b.z, x*b.y-y*b.x);
 78     }
 79     double rad (Point a, Point b) {//两向量的夹角
 80         Point p = (*this);
 81         return acos (((a-p)*(b-p)) / (a.distance (p)*b.distance (p)));
 82     }
 83     Point trunc (double r) {
 84         double l = len ();
 85         if (!dcmp (l)) return *this;
 86         r /= l;
 87         return Point (x*r, y*r, z*r);
 88     }
 89     double distance (Point p) {
 90         return Point (x-p.x, y-p.y, z-p.z).len ();
 91     }
 92 };
 93 
 94 struct Line {
 95     Point s, e;
 96     Line () {}
 97     Line (Point _s, Point _e) {
 98         s = _s, e = _e;
 99     }
100     void input () {
101         s.input ();
102         e.input ();
103     }
104     void output () {
105         cout << "line:" << endl;
106         s.output ();
107         e.output ();
108     }
109     double len () {
110         return (e-s).len ();
111     }
112     double point_to_line (Point p) {//点到直线的距离
113         return ((e-s)^(p-s)).len () / s.distance (e);
114     }
115     Point prog (Point p) {//点在直线上的投影
116         return s+(((e-s)*((e-s)*(p-s))) / ((e-s).len2 ()));
117     }
118     bool Point_on_line (Point p) {//点在直线上
119         return dcmp (((s-p)^(e-p)).len ()) == 0 && dcmp ((s-p)*(e-p)) == 0;
120     }
121 };
122 
123 struct Plane {
124     Point a, b, c, o;
125     Plane () {}
126     Plane (Point _a, Point _b, Point _c) {
127         a = _a, b = _b, c = _c;
128         o = pvec ();
129     }
130     Point pvec () {//法向量
131         return (b-a)^(c-a);
132     }
133     Plane go (Point p, double x) {//平面沿p方向前进x距离
134         o = o.trunc (x);
135         double ang = a.rad (a+o, p);
136         if (ang >= pi/2) o = o*(-1);
137         return Plane (a+o, b+o, c+o);
138     }
139     bool point_on_plane (Point p) {//点在平面上
140         return dcmp ((p-a)*o) == 0;
141     }
142     double plane_angle (Plane f) {//两平面夹角
143         return acos (o*f.o)/(o.len ()*f.o.len ());
144     }
145     int line_cross_plane (Line u, Point &p) {//直线和平面的交点
146         double x = o*(u.e-a);
147         double y = o*(u.s-a);
148         double d = x-y;
149         if (dcmp (d) == 0) return 0;
150         p = ((u.s*x) - (u.e*y))/d;
151         return 1;
152     }
153     double area () {//三角形面积
154         double x1 = (a-b).len (), x2 = (a-c).len (), x3 = (b-c).len ();
155         double p = (x1+x2+x3)/2;
156         return sqrt (p*(p-x1)*(p-x2)*(p-x3));
157     }
158     Point point_to_plane (Point p) {
159         Line u = Line (p, p+o);
160         line_cross_plane (u, p);
161         return p;
162     }
163     int plane_cross_plane (Plane f, Line &u) {//平面交线
164         Point oo = o^f.o;
165         Point v = o^oo;
166         double d = fabs (f.o*v);
167         if (dcmp (d) == 0)
168             return 0;
169         Point q = a-(v*(f.o*(f.a-a))/d);
170         u = Line (q, q+oo);
171         return 1;
172     }
173 };
174 
175 Point A,B,C,D;
176 Plane p1,p2,p3,p4;
177 
178 int main(){
179     while(scanf("%lf%lf%lf",&A.x,&A.y,&A.z)==3){
180          B.input();C.input();D.input();
181          p1=Plane(A,B,C);
182          p2=Plane(A,B,D);
183          p3=Plane(A,C,D);
184          p4=Plane(B,C,D);
185          if(p1.point_on_plane(D)){
186              printf("O O O O
");
187              continue;
188          }
189          Point tmp=p1.point_to_plane(D);
190          double dis=(D-tmp).len();
191          double V=dis*p1.area();
192          double r=V/(p1.area()+p2.area()+p3.area()+p4.area());
193          p1=p1.go(D,r);
194          p2=p2.go(C,r);
195          p3=p3.go(B,r);
196          //叉积得到交线法向量,然后面上一点和法向量确定直线，与另一个平面相交得到交点，交线
197          Line l;
198          Point oo=p2.o^p3.o;
199          Point v = p2.o^oo;
200          l=Line(p2.a,p2.a+v);
201          Point p;
202          p3.line_cross_plane(l,p);
203          Line l2;
204          l2=Line(p,p+oo);
205          Point ans;
206          p1.line_cross_plane(l2,ans);
207 
208          printf("%.4f %.4f %.4f %.4f
",ans.x,ans.y,ans.z,r);
209     }
210     return 0;
211 }
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/ITUPC/p/5688865.html