7.26第三次多校

Posted by Cww97 on 2016-07-26

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/52037211
目前有01,03,10,11,烂尾了
官方题解

1001
不用高精度,,,超过44E就TAT了
longlong就够了
注意0的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<cstdio>
#include<cmath>
#include<iostream>
#include<string>
using namespace std;
int main(){
string st;
while (cin>>st){
if (st.length()>10) puts("TAT");
else {
long long n=0;
for (int i=0;i<st.length();i++){
n = n*10 + (st[i]-'0');
}
//printf("n=%I64d\n",n);
if (!n)puts("TAT");
else {
int ans=0;
for (;n>1;ans++){
n= (long long)floor((sqrt(n)));
}
if (ans<6)printf("%d\n",ans);
else puts("TAT");
}
}
}
return 0;
}

1002_hdu5273
这里写图片描述
官方题解讲的略简单

某题解
这题意思就是让你先列出一个hi的排列,然后如果满足(hi>hi-1 and hi>hi+1)的值为1,那么c[i]这个值就能取,然后我们把第一个样例的全部情况列出来,模拟一下答案,发现公式就是(c[1]+c[n])/3+(c[2]+…+c[n-1])/2;

某题解+1
然后对这个全排列进行分析,对i这个位置,
如果在中间的话,相邻就有两个元素,就是三个元素的全排列,有3!=6种情况,然而只有大的在中间,两个小的在左右这种情况有效,排列两种,所以所有情况中是1/3是符合的,所以对期望的贡献值是Ci/3;
如果在两端的话,相邻就是一个元素了,2!=2,只有一种情况符合,所以贡献Ci/2,
之后对1进行一下特判,答案就出来了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<cstdio>
using namespace std;
double c[1010];
int main(){
int n;
while (scanf("%d",&n)==1){
for (int i=1;i<=n;i++)scanf("%lf",&c[i]);
if (n==1)printf("%.6lf\n",c[1]);
else {
double ans=(c[1]+c[n])/2.0;
for (int i=2;i<=n-1;i++)ans+=c[i]/3.0;
printf("%.6lf\n",ans);
}
}
return 0;
}

1003
重点在骑士和皇后的情况
骑士可以找规律或者dp搞出来
皇后我这么搞然后挂了,cdm说一看表就是个威佐夫博弈
http://blog.csdn.net/y990041769/article/details/21694007
看了下,打表发现问题
表张这样
这里写图片描述
跑debug里的代码
这里写图片描述

然后出来这个
这里写图片描述
不知道为什么,,,
感觉像威佐夫博弈,然而图有点出入,
最不明所以的是这么写还A了,我的天

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
const int N=1007;
int h[N][N];
bool q[N][N];

void Init(){
memset(h,0,sizeof(h));
for (int i=1;i<N-5;i+=3){
h[i][i]=-1;
h[i+2][i+1]=h[i+1][i+2]=1;
}

memset(q,1,sizeof(q));
for (int i=1,j=1;max(i,j)<N-5;i+=2,j++)q[i][j]=0;
for (int i=1,j=1;max(i,j)<N-5;i++,j+=2)q[i][j]=0;
}

double phi = (1 + sqrt(5)) / 2.0;
void debug(){
for (int i=1;i<=30;i++){
for (int j=1;j<=30;j++){
bool ok=((min(i-1, j-1) != (int)(phi*abs(i-j))));
if (ok!=q[i][j])printf("[%d][%d]->%d\n",i,j,ok);
}
}
}

int main(){
//freopen("fuck.in","r",stdin);
int T,type,n,m;
scanf("%d",&T);
Init();
//debug();
while (T--){
scanf("%d%d%d",&type,&n,&m);
if (type==1) puts((n&m&1)?"G":"B");
if (type==2) puts((n==m )?"G":"B");
if (type==3){
if (h[n][m]== 0)puts("D");
if (h[n][m]== 1)puts("B");
if (h[n][m]==-1)puts("G");
}
if (type==4){
puts((min(n-1,m-1)!=(int)(phi*abs(n-m)))?"B":"G");
}//puts((q[n][m])?"B":"G");
}
return 0;
}

1010
这里写图片描述
这里写图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<cstdio>
#include<iostream>
using namespace std;

int main(){
int a,v1,v2;
while (scanf("%d%d%d",&a,&v1,&v2)==3){
if(!a)puts("0.0000000000");
else if (v1<=v2)puts("Infinity");
else {
double ans=a*v1*1.0/(v1*v1-v2*v2);
printf("%.10lf\n",ans);
}
}
return 0;
}

1011
10W数据,,平方过?
当时的想法是先写个暴力T一发再说,,
然后莫名其妙就A了
cw分析的不错:因为距离差最多只有200000种可能。所以最多只运行200001次。。。。所以没有平方那么多,。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
const int N=100007;
bool vis[N<<1];
int ax[N],ay[N];
int n,m;

bool work(){
memset(vis,0,sizeof(vis));
for (int i=1;i<=n;i++)
scanf("%d%d",&ax[i],&ay[i]);
for (int i=1;i<=n;i++)if(ax[i]<=m&&ay[i]<=m){
for (int j=1;j<i;j++)if(ax[j]<=m||ay[j]<=m){
int d=abs(ax[i]-ax[j])+abs(ay[i]-ay[j]);
if (vis[d])return 1;
else vis[d]=1;
}
}
return 0;
}

int main(){
//freopen("fuck.in","r",stdin);
int T;scanf("%d",&T);
while (T--){
scanf("%d%d",&n,&m);
if (work())puts("YES");
else puts("NO");
}
return 0;
}