首页 > 代码库 > 【解题报告】牡丹江现场赛之ABDIK ZOJ 3819 3820 3822 3827 3829
【解题报告】牡丹江现场赛之ABDIK ZOJ 3819 3820 3822 3827 3829
那天在机房做的同步赛，比现场赛要慢了一小时开始，直播那边已经可以看到榜了，所以上来就知道A和I是水题，当时机房电脑出了点问题，就慢了好几分钟，12分钟才A掉第一题。。。
A.Average Score
题目大意：给定A序列和B序列，长度分别是n和m，告诉你A序列中的n-1个数和B序列的m个数，求剩下的那个A序列中的数满足：将这个数从A序列移除，然后添加到B序列，使得A序列的平均值变小，B序列的平均值变大。求这个数的取值范围（是整数）
解题思路：求出A序列剩下的n-1个数的平均值，和B序列的平均值，答案就是这两个数之间的整数。
解题代码：
1 #include<stdio.h> 2 #include<math.h> 3 #include<string.h> 4 #include<iostream> 5 #include<algorithm> 6 #define FOR(i,n) for(i=0;i<(n);i++) 7 #define CLR(a) memset(a,0,sizeof(a)) 8 #define CIN(a) scanf("%d",&a) 9 using namespace std;10 int main()11 {12 int t,i;13 CIN(t);14 while(t--)15 {16 int n1,n2,s1=0,s2=0,a,b;17 CIN(n1);18 CIN(n2);19 for(i=1;i<n1;i++)20 {21 CIN(a);22 s1+=a;23 }24 for(i=0;i<n2;i++)25 {26 CIN(b);27 s2+=b;28 }29 if(s1%(n1-1)==0) s1=s1/(n1-1)-1;30 else s1=s1/(n1-1);31 s2=s2/n2+1;32 printf("%d %d\n",s2,s1);33 }34 return 0;35 }
I.Information Entropy
然后看I感觉很高大上的样子，看了好久没看懂，但是很多人做出来又不舍得放弃，于是就静下心来慢慢看，然后发现题目的意思大概就是把给的数据带入H(x)求答案就完了。。。但是如果出现P(xi)=0的情况的话就要用那个求极限的公式带，关于这个极限，由于把高数忘得一干二净，所以不知道怎么搞，后来用几何画板把函数图像画出来，发现那个值是0，然后就简单了。。。直接套公式。。
代码：
1 #include<stdio.h> 2 #include<math.h> 3 #include<string.h> 4 #include<iostream> 5 #include<algorithm> 6 #define FOR(i,n) for(i=0;i<(n);i++) 7 #define CLR(a) memset(a,0,sizeof(a)) 8 #define CIN(a) scanf("%d",&a) 9 using namespace std;10 int a[105];11 double (*f)(double) ;12 int main()13 {14 int t,i,x;15 char s[10];16 CIN(t);17 while(t--)18 {19 scanf("%d",&x);20 scanf("%s",s);21 for(i=0;i<x;i++)22 {23 scanf("%d",&a[i]);24 }25 if(strcmp(s,"bit")==0)26 {27 f=log2;28 }29 else if(strcmp(s,"nat")==0)30 {31 f=log;32 }33 else f=log10;34 double s=0;35 for(i=0;i<x;i++)36 {37 if(a[i]!=0) s+=((double)a[i]/100)*f((double)a[i]/100);38 }39 printf("%.12f\n",-s);40 }41 return 0;42 }
D.Domination
本着随波逐流的策略，就开始看过的人最多的D了。
题目大意：给定一个N*M的网格，开始随机往里面放棋子，知道任意一行任意一列都有棋子为止，求已经放置的棋子数的期望。
解题思路：概率DP，用dp[i][j][k]表示已经有i行，j列放过棋子，且总共放过k个棋子。对于某一状态，可以由四种状态扩展而来，可得状态转移方程：
转移方程：
if(i!=n||j!=m)dp[i][j][k]+=(1.0*i*j-(k-1))/(m*n-(k-1))*dp[i][j][k-1];//这个if是判断出前一状态已经是终点状态则不能扩展 dp[i][j][k]+=(1.0*i*(m-(j-1)))/(m*n-k+1)*dp[i][j-1][k-1]; dp[i][j][k]+=(1.0*j*(n-i+1))/(m*n-k+1)*dp[i-1][j][k-1]; dp[i][j][k]+=((1.0*n-i+1)*(m-j+1))/(m*n-k+1)*dp[i-1][j-1][k-1];
代码：
1 #include<stdio.h> 2 #include<math.h> 3 #include<string.h> 4 #include<iostream> 5 #include<algorithm> 6 #define FOR(i,n) for(i=0;i<(n);i++) 7 #define CLR(a) memset(a,0,sizeof(a)) 8 #define CIN(a) scanf("%d",&a) 9 using namespace std;10 double dp[51][51][2501];11 int main()12 {13 int t;14 int i,j,k,n,m;15 CIN(t);16 while(t--)17 {18 CIN(n);19 CIN(m);20 CLR(dp);21 dp[0][0][0]=1;22 for(i=1;i<=n;i++)23 {24 for(j=1;j<=m;j++)25 {26 for(k=1;k<=(i*j);k++)27 {28 if(i!=n||j!=m)dp[i][j][k]+=(1.0*i*j-(k-1))/(m*n-(k-1))*dp[i][j][k-1];29 dp[i][j][k]+=(1.0*i*(m-(j-1)))/(m*n-k+1)*dp[i][j-1][k-1];30 dp[i][j][k]+=(1.0*j*(n-i+1))/(m*n-k+1)*dp[i-1][j][k-1];31 dp[i][j][k]+=((1.0*n-i+1)*(m-j+1))/(m*n-k+1)*dp[i-1][j-1][k-1];32 //printf("dp[%d][%d][%d]=%.12f\n",i,j,k,dp[i][j][k]);33 }34 }35 }36 double s=0;37 for(k=0;k<=(n*m);k++)38 {39 s+=(dp[n][m][k]*k);40 }41 printf("%.12f\n",s);42 }43 return 0;44 }
做到这里的时候是4题都是1y，感觉自己屌屌的~
B.Building Fire Stations
这题题目读完在纸上画了半天，感觉会和最长链有关，于是大胆猜测是在最长链的四分分上，然后马上就否定了，后来感觉应该是先将整个树从最长链的中间拆开，再分别求最长链取中点。不会证明，但是又没有别的题可以搞，就直接按这个方法写了，然后数组开太小RE了一次，改了交就AC了。。Orz白错了一次。
求树的最长链当时是第一次写，之前知道方法，但是没写过，没想到一次就过了。方法是先在树中随便取一点，遍历树找到距离这个点最远的点，然后这一点就是最长链的一个端点了，然后再从这个点遍历一次求出另一个端点就是最长链的另一点啦。
关于断边，则直接用了一个标记即可。
代码：
1 #include<stdio.h> 2 #include<math.h> 3 #include<string.h> 4 #include<iostream> 5 #include<queue> 6 #include<algorithm> 7 #define FOR(i,n) for(i=0;i<(n);i++) 8 #define CLR(a) memset(a,0,sizeof(a)) 9 #define CIN(a) scanf("%d",&a) 10 using namespace std; 11 #include<stdio.h> 12 #include<string.h> 13 #define point_MAX 200005 14 #define edge_MAX 400005 15 struct EDGE 16 { 17 int to;/*指向的点*/ 18 int next;/*指向的下一条邻边*/ 19 int w;/*权值*/ 20 }edge[edge_MAX]; 21 int len;/*边的数量*/ 22 int point[point_MAX]; 23 void init()/*初始化*/ 24 { 25 len=0; 26 memset(point,0,sizeof(point)); 27 } 28 int add_edge(int a,int b,int w)/*添加由a指向b的权值为w的边*/ 29 { 30 len++; 31 edge[len].w=w; 32 edge[len].to=b; 33 edge[len].next=point[a]; 34 point[a]=len; 35 return 0;/*无重边，插入*/ 36 } 37 int del_edge(int a,int b) 38 { 39 int i; 40 for(i=point[a];edge[i].to!=b;i=edge[i].next); 41 edge[i].w=0; 42 43 for(i=point[b];edge[i].to!=a;i=edge[i].next); 44 edge[i].w=0; 45 46 return 0; 47 } 48 int bo[200005]; 49 int road[200002]; 50 int zuiyuandian(int start) 51 { 52 int t,k,i; 53 queue<int> q; 54 CLR(bo); 55 q.push(start); 56 bo[start]=1; 57 while(!q.empty()) 58 { 59 //printf("l"); 60 k=q.front(); 61 q.pop(); 62 63 for(i=point[k];i;i=edge[i].next) 64 { 65 if(edge[i].w!=0) 66 if(bo[edge[i].to]==0) 67 { 68 q.push(edge[i].to); 69 road[edge[i].to]=k; 70 bo[edge[i].to]=1; 71 } 72 } 73 } 74 return k; 75 } 76 int zuichang(int start) 77 { 78 int l,r,le,i; 79 l=zuiyuandian(start); 80 r=zuiyuandian(l); 81 int len=0; 82 for(i=r;i!=l;i=road[i]) {/*printf("%d->",i);*/len++;} 83 len/=2; 84 for(le=0,i=r;le<len;i=road[i],le++); 85 int a=i,b=road[i]; 86 87 del_edge(a,b); 88 89 l=zuiyuandian(a); 90 r=zuiyuandian(l); 91 len=0; 92 for(i=r;i!=l;i=road[i]) len++; 93 int ans1=len%2?len/2+1:len/2; 94 len/=2; 95 for(le=0,i=r;le<len;i=road[i],le++); 96 a=i; 97 98 l=zuiyuandian(b); 99 r=zuiyuandian(l);100 len=0;101 for(i=r;i!=l;i=road[i]) len++;102 int ans2=len%2?len/2+1:len/2;103 len/=2;104 for(le=0,i=r;le<len;i=road[i],le++);105 b=i;106 107 printf("%d %d %d\n",max(ans1,ans2),a,b);108 }109 int main()110 {111 int t,n,i;112 CIN(t);113 while(t--)114 {115 CIN(n);116 init();117 for(i=1;i<n;i++)118 {119 int a,b;120 CIN(a);121 CIN(b);122 add_edge(a,b,1);123 add_edge(b,a,1);124 }125 zuichang(1);126 }127 return 0;128 }
最后去搞H发现是一个模拟题，我想用map建立一棵树表示它然后查询但是超内存了Orz...一定是哪里姿势不够优美。。。SO，到最后也没搞出来，下次再搞了。
【解题报告】牡丹江现场赛之ABDIK ZOJ 3819 3820 3822 3827 3829
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。