http://codeforces.com/problemset/problem/77/B 高中概率题... 算一下面积就行
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
| #include<bits/stdc++.h>
using namespace std;
double a,b;
void work()
{
cin>>a>>b;
double s,v;
s=0;
v=0;
if(b==0)
{
cout<<1<<endl;
return;
}
if(a==0)
{
cout<<0.5<<endl;
return;
}
s=2.0*a*b;
if(4*b>=a)
{
v=(b+b-1.0/4.0*a)*a/2.0;
}
else
{
v=4*b*b/2.0;
}
printf("%.10lf\n",1.0-v/s);
}
int main()
{
int T;
cin>>T;
while(T--) work();
return 0;
}
|
http://codeforces.com/problemset/problem/203/D 感觉是一道阅读题... 题目还是挺简单的，就是小球反弹来反弹去... 看着模拟就行？
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<bits/stdc++.h>
using namespace std;
double a,b,m;
double vx,vy,vz;
double t;
int main()
{
cin>>a>>b>>m;
cin>>vx>>vy>>vz;
t=m*1.0/fabs(vy);
vx*=t;
vz*=t;
vx+=a/2.0;
if(vx<0)
{
while(vx<=(-2.0*a))
{
vx+=2.0*a;
}
if(vx<(-a))
{
vx+=a;
vx=a+vx;
}
else
{
vx=fabs(vx);
}
}
else
{
while(vx>=2.0*a)
{
vx-=2.0*a;
}
if(vx>a)
{
vx=2*a-vx;
}
}
while(vz>=2.0*b)
{
vz-=2.0*b;
}
if(vz>b)
{
vz=2.0*b-vz;
}
printf("%.10lf %.10lf",vx,vz);
return 0;
}
|
http://codeforces.com/problemset/problem/405/D 感觉老是没有充分利用题目特点... 我开始的思路是，把这个问题先进行简化，就能简化成一个背包，然后就显到背包的思路中难以自拔... 其实只要看清题目特点，发现对称的数对答案的贡献是相同的，这样的话，这个题目的贪心就十分明显了orz
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
| #include<bits/stdc++.h>
using namespace std;
long long n;
long long x[1000010]={};
bool p[1000010]={};
long long u;
long long o;
queue<int> ans;
int main()
{
scanf("%I64d",&n);
for(int i=1;i<=n;i++)
{
scanf("%I64d",&x[i]);
p[x[i]]=1;
u+=x[i]-1;
}
o=0;
for(int i=1;i<=n;i++)
{
if(p[1000000+1-x[i]]==0)
{
o+=x[i]-1;
p[1000000+1-x[i]]=1;
ans.push(1000000+1-x[i]);
}
}
for(int i=1;i<=1000000;i++)
{
if(p[i]==0&&p[1000001-i]==0&&o+999999<=u)
{
o+=999999;
ans.push(i);
ans.push(1000001-i);
p[i]=1;
p[1000001-i]=1;
}
}
printf("%d\n",ans.size());
while(!ans.empty())
{
printf("%d ",ans.front());
ans.pop();
}
return 0;
}
|
http://codeforces.com/problemset/problem/346/B 动态规划 \(dp[i][j][k]\) 代表第一个串匹配到i，第二个串匹配到j，结尾长度为k的串和virus的前k个字母相同 然后状态转移的时候要用到kmp
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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
| #include<bits/stdc++.h>
using namespace std;
int dp[110][110][110];
string s1,s2,v;
struct pp
{
int a,b,c;
} pr[110][110][110]={};
int ans;
int sa,sb,sc;
int p[110]={};
struct tt
{
int a,b,c,d;
} q[1010]={};
int l=0;
int main()
{
cin>>s1>>s2>>v;
p[1]=0;
int j=0;
for(int i=2;i<=v.size();i++)
{
while(j>0&&v[j]!=v[i-1]) j=p[j];
if(v[j]==v[i-1]) j++;
p[i]=j;
}
for(int i=1;i<=s1.size();i++)
{
for(int j=1;j<=s2.size();j++)
{
if(s1[i-1]==s2[j-1])
{
for(int k=0;k<v.size()-1;k++)
{
if(v[k]==s1[i-1])
{
if(dp[i][j][k+1]<dp[i-1][j-1][k]+1)
{
dp[i][j][k+1]=dp[i-1][j-1][k]+1;
pr[i][j][k+1].a=i-1;
pr[i][j][k+1].b=j-1;
pr[i][j][k+1].c=k;
}
}
else
{
int u=k;
while(u>0&&v[u]!=s1[i-1]) u=p[u];
if(v[u]==s1[i-1]) u++;
if(dp[i][j][u]<dp[i-1][j-1][k]+1)
{
dp[i][j][u]=dp[i-1][j-1][k]+1;
pr[i][j][u].a=i-1;
pr[i][j][u].b=j-1;
pr[i][j][u].c=k;
}
}
}
if(v[v.size()-1]!=s1[i-1])
{
int u=v.size()-1;
while(u>0&&v[u]!=s1[i-1]) u=p[u];
if(v[u]==s1[i-1]) u++;
if(dp[i][j][u]<dp[i-1][j-1][v.size()-1]+1)
{
dp[i][j][u]=dp[i-1][j-1][v.size()-1]+1;
pr[i][j][u].a=i-1;
pr[i][j][u].b=j-1;
pr[i][j][u].c=v.size()-1;
}
}
}
else
{
for(int k=0;k<v.size();k++)
{
if(dp[i][j][k]<dp[i-1][j][k])
{
dp[i][j][k]=dp[i-1][j][k];
pr[i][j][k].a=i-1;
pr[i][j][k].b=j;
pr[i][j][k].c=k;
}
}
}
if(j!=s2.size())
for(int k=0;k<v.size();k++)
{
if(dp[i][j+1][k]<dp[i][j][k])
{
dp[i][j+1][k]=dp[i][j][k];
pr[i][j+1][k].a=i;
pr[i][j+1][k].b=j;
pr[i][j+1][k].c=k;
}
}
}
}
sa=s1.size();
sb=s2.size();
for(int k=0;k<v.size();k++)
{
if(dp[s1.size()][s2.size()][k]>ans)
{
ans=dp[s1.size()][s2.size()][k];
sc=k;
}
}
if(ans==0)
{
cout<<0;
return 0;
}
while(sa!=0)
{
l++;
q[l].a=sa;
q[l].b=sb;
q[l].c=sc;
q[l].d=dp[sa][sb][sc];
pp mid;
mid=pr[sa][sb][sc];
sa=mid.a;
sb=mid.b;
sc=mid.c;
}
for(int i=l;i>=1;i--)
{
if(q[i].d>q[i+1].d)
{
cout<<s1[q[i].a-1];
}
}
return 0;
}
|
http://codeforces.com/problemset/problem/14/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
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
| #include<bits/stdc++.h>
using namespace std;
vector<int> e[210];
bool v[210][210]={};
int d[210][210]={};
int o[210][210]={};
bool h[210][210];
int n;
bool cmp(int a,int b)
{
return a>b;
}
int ff(int x,int y)
{
if(v[x][y]==1) return d[x][y];
v[x][y]=1;
vector<int> p;
int tt=0;
for(int i=0;i<e[y].size();i++)
{
if(e[y][i]!=x)
{
p.push_back(ff(y,e[y][i]));
o[x][y]=max(o[x][y],o[y][e[y][i]]);
}
}
if(p.size()==0) return 0;
sort(p.begin(),p.end(),cmp);
d[x][y]=p[0]+1;
tt+=p[0]+1;
if(p.size()>=2) tt+=p[1]+1;
o[x][y]=max(o[x][y],tt);
return d[x][y];
}
int main()
{
cin>>n;
for(int i=1;i<n;i++)
{
int a,b;
cin>>a>>b;
h[a][b]=1;
h[b][a]=1;
e[a].push_back(b);
e[b].push_back(a);
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(h[i][j]==1)
{
ff(i,j);
}
}
}
int ans=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(h[i][j]==1)
{
ans=max(ans,o[i][j]*o[j][i]);
}
}
}
cout<<ans;
return 0;
}
|