2018 Multi-University Training Contest 6

A.oval-and-rectangle

题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=6362

题意：在长半轴为a，短半轴为b的椭圆内部，以y=c（0<=c<=b）截取内接矩形，问矩阵周长的期望。

分析：

然后除以b，得到：2*b+pi*a。

直接输出答案即可。要求直接舍弃小数点七位之后，需要先减去0.0000005，再保留6位输出。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const double PI=acos(-1);
 4 int main(){
 5     srand((unsigned)time(NULL));
 6     int t;double a,b;scanf("%d",&t);
 7     while(t--){
 8         scanf("%lf%lf",&a,&b);
 9         double ans=2*b+PI*a;
10         ans-=0.0000005;
11         printf("%.6lf
",ans); 
12     }
13     return 0;
14 }

hdoj6362

I.Werewolf

题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=6370

题意：有n个人，若干个狼或羊，每个人说一句话，羊必须说真话，狼可真可假。问一定有多少个羊，多少个狼。

分析：1.当所有人为狼时，一定成立。所以一定没有铁羊。

2.那么只需要判断铁狼即可。在一个环内，若A指认B为狼，B指认C为羊，C指认A为人，那么B一定为铁狼。此外，指认铁狼为人的人一定为铁狼。由此，可以dfs+标记找出铁狼。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1e5+10;
 4 struct point{
 5     int x,w;
 6 }mp[maxn];
 7 int res,n;
 8 int vis[maxn],k[maxn];
 9 void dfs(int x){
10     vis[x]=-1;
11     if (mp[x].w==1)
12         vis[x]=mp[x].x;
13     else{
14         if (vis[mp[x].x]==0) dfs(mp[x].x);
15         vis[x]=vis[mp[x].x];
16         if (vis[x]==x || k[mp[x].x]==1){
17             k[x]=1;res++;
18         }
19     }
20 } 
21 int main(){
22     ios::sync_with_stdio(false);
23     cin.tie(0);cout.tie(0);
24     int t,x;
25     string ss;
26     cin >> t;
27     while (t--){
28         cin >> n;
29         for (int i=1;i<=n;i++){
30             cin >> x >> ss;
31             if (ss[0]=='w'){
32                 mp[i].w=1;mp[i].x=x;
33             }
34             else{
35                 mp[i].w=0;mp[i].x=x;
36             }
37         }
38         memset(vis,0,sizeof(vis));
39         memset(k,0,sizeof(k));
40         res=0;
41         for (int i=1;i<=n;i++)
42             if (!vis[i]) dfs(i);
43         cout << 0 << " " << res << endl;
44     }
45     return 0;
46 }

hdoj6370

L.Pinball

题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=6373

题意：一个小球从位置(x,y)处下落到斜率为b/a的斜坡上，问在斜坡上的碰撞次数。

分析：模拟。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const double g=9.8;
 4 double a,b,x,y;
 5 int main(){
 6     ios::sync_with_stdio(false);
 7     cin.tie(0);cout.tie(0);
 8     int tt;
 9     cin >> tt;
10     while (tt--){
11         cin >> a >> b >> x >> y;
12         double sin=b/sqrt(a*a+b*b);
13         double ax=g*sin;
14         double h=y+b*x/a;
15         double v0=sqrt(2*g*h);
16         double t=v0/g;
17         double v0x=v0*sin;
18         double aa=x*x,bb=(x*b/a)*(x*b/a),s0=sqrt(aa+bb);
19         int ans=0;
20         while (s0>0){
21             ans++;
22             double ss=2*t*v0x+2*ax*t*t;
23             s0=s0-ss;
24             v0x=v0x+2*ax*t;  //新的速度 
25         }
26         cout << ans << endl;
27     }
28     return 0;
29 }

hdoj6373