头部背景图片
Decaku 's Blog |
Decaku 's Blog |

2014 ICPC 北京站

A:

$sort一下,注意除法转乘法因为浮点数的运算误差$


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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct Node
{
int t,p;
} e[10005],e_2[10005];
bool cmp(Node x, Node y)
{
return x.t<y.t;
}
bool cmp2(Node x,Node y)
{
return 1ll*x.p*y.t>1ll*y.p*x.t;
}
int main()
{
int T,n;
scanf("%d",&T);
for(int Time=1; Time<=T; Time++)
{
scanf("%d",&n);
for(int i=1; i<=n; i++)
scanf("%d %d",&e[i].t,&e[i].p);
sort(e+1,e+n+1,cmp);
for(int i=2; i<=n; i++)
{
e_2[i].t=e[i].t-e[i-1].t;
e_2[i].p=abs(e[i].p-e[i-1].p);
}
sort(e_2+2,e_2+1+n,cmp2);
double x=1;
printf("Case #%d: %.2lf\n",Time,x*e_2[2].p/e_2[2].t);
}
}

K:

树状数组差分乱搞。


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
53
54
55
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;

int n,tree[maxn];
int lowbit(int x)
{
return x&(-x);
}

void add(int k,int d)
{
for(int i=k; i<=n; i+=lowbit(i))
{
tree[i]+=d;
}
}

int sigma(int k)
{
int res=0;
while(k>0)
{
res+=tree[k];
k-=lowbit(k);
}
return res;
}

int t,tem,ans,id[maxn];
int main()
{
scanf("%d",&t);
for(int time=1; time<=t; time++)
{
memset(tree,0,sizeof(tree));
ans=0;
scanf("%d",&n);
for(int i=1; i<=n; i++)
{
scanf("%d",&tem);
id[tem]=i;
add(i,1);
}
for(int i=n; i>0; i--)
{
if(sigma(id[i])!=i)
{
ans++;
add(id[i],-1);
}
}
printf("Case #%d: %d\n",time,ans);
}
}

H:

$两数异或以后不会大于它们的和,直接暴力dp。$


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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn=1<<20;
ll a[1<<21],dp[2][1<<21];
ll t,n,m;
int main()
{
scanf("%lld",&t);
for(ll time=1; time<=t; time++)
{
scanf("%lld %lld",&n,&m);
memset(a,0,sizeof(a));
for(ll i=1; i<=n; i++)
scanf("%lld",&a[i]);

for(ll i=0; i<maxn*2; i++)
{
if(a[1]==i)
dp[1][i]=1;
else
dp[1][i]=0;
}
dp[1][0]=1;

ll tem=0,ans=0;
for(ll i=2; i<=n; i++)
{
for(ll j=0; j<maxn*2; j++)
{
dp[tem][j]=dp[1-tem][j]+dp[1-tem][j^a[i]];
}
tem=1-tem;
}
for(ll i=m;i<maxn;i++)
ans+=dp[1-tem][i];
printf("Case #%lld: %lld\n",time,ans);
}
}

I:

算圆环的交转换到算圆的交,然后套模板就好。


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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<bits/stdc++.h>
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
int t;
double R,r,x_1,y_1,x_2,y_2;

int sgn(double x)
{
if(fabs(x)<eps)
return 0;
if(x<0)
return -1;
else
return 1;
}
struct Point
{
double x,y;
Point() {}
Point(double _x,double _y)
{
x=_x;
y=_y;
}
double distance(Point p)
{
return hypot(x-p.x,y-p.y);
}
};

struct circle
{
Point p;
double r;
circle() {}
double area()
{
return pi*r*r;
}
int relationship(circle v)
{
double d=p.distance(v.p);
if(sgn(d-r-v.r)>0)
return 5;
if(sgn(d-r-v.r)==0)
return 4;
double l=fabs(r-v.r);
if(sgn(d-r-v.r)<0 && sgn(d-l)>0)
return 3;
if(sgn(d-l)==0)
return 2;
if(sgn(d-l)<0)
return 1;
}

double areacircle(circle v)
{
int rel=relationship(v);
if(rel>=4)
return 0.0;
if(rel<=2)
return min(area(),v.area());
double d=p.distance(v.p);
double hf=(r+v.r+d)/2.0;
double ss=2*sqrt(hf*(hf-r)*(hf-v.r)*(hf-d));
double a1=acos((r*r+d*d-v.r*v.r)/(2.0*r*d));
a1=a1*r*r;
double a2=acos((v.r*v.r+d*d-r*r)/(2.0*v.r*d));
a2=a2*v.r*v.r;
return a1+a2-ss;
}
};
int main()
{
scanf("%d",&t);
circle A,a,B,b;
for(int time=1; time<=t; time++)
{
scanf("%lf %lf",&r,&R);
scanf("%lf %lf",&x_1,&y_1);
scanf("%lf %lf",&x_2,&y_2);
A.p=a.p=Point(x_1,y_1);
B.p=b.p=Point(x_2,y_2);
A.r=B.r=R;
a.r=b.r=r;
double ans=0;
ans=ans+A.areacircle(B)-A.areacircle(b)*2+a.areacircle(b);
printf("Case #%d: %.6lf\n",time,ans);
}
}

D:

$区间dp$


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
#include<bits/stdc++.h>
using namespace std;
const int inf=2e9;
int t,n;
int dp[205][205],a[205],b[205];
int main()
{
scanf("%d",&t);
for(int time=1;time<=t;time++)
{
for(int i=0; i<205; i++)
for(int j=i; j<205; j++)
dp[i][j]=inf;
scanf("%d",&n);
for(int i=1; i<=n; i++)
scanf("%d",&a[i]);
for(int i=1; i<=n; i++)
scanf("%d",&b[i]);
a[0]=b[0]=a[n+1]=b[n+1]=0;

for(int len=1; len<=n; len++)
{
for(int s=1; s+len-1<=n; s++)
{
int e=s+len-1;
for(int mid=s; mid<=e; mid++)
{
dp[s][e]=min(dp[s][e],dp[s][mid-1]+dp[mid+1][e]+a[mid]+b[s-1]+b[e+1]);
}
}
}
printf("Case #%d: %d\n",time,dp[1][n]);
}
}

未完待续。。。

avatar Decaku 很菜但也很想carry