http://codeforces.com/contest/442/problem/B 自己试图用调整法搞了半天...然而并没有推出来.... 后来参考了一下题解的式子... http://codeforces.com/blog/entry/12739 有个这个式子之后，这个问题就很好解决了，只要保持\(S\) 小于 1 就行了... 果然数学弱的一逼...
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
| #include<bits/stdc++.h>
using namespace std;
int n;
double p[110]={};
double u;
double p1,p0,t1,t0;
bool cmp(double x,double y)
{
return x>y;
}
double s;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>p[i];
u=max(u,p[i]);
}
if(u>=0.5)
{
printf("%.10lf",u);
return 0;
}
else
{
p1=0.0;
p0=1.0;
sort(p+1,p+n+1,cmp);
s=0.0;
for(int i=1;i<=n;i++)
{
if(s>=1.0) break;
p1=p1*(1-p[i])+p0*p[i];
p0=p0*(1-p[i]);
s+=p[i]/(1-p[i]);
}
}
printf("%.10lf",p1);
return 0;
}
|
http://codeforces.com/contest/446/problem/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
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
| #include<bits/stdc++.h>
using namespace std;
struct cmp{
bool operator ()(int &a,int &b){
return a<b;
}
};
priority_queue<int,vector<int>,cmp> qr;
priority_queue<int,vector<int>,cmp> qc;
long long r[1000010]={};
long long c[1000010]={};
long long n,m,k,t;
long long a[1010][1010]={};
long long p;
long long ans;
int main()
{
cin>>n>>m>>k>>t;
for(int i=1;i<=n;i++)
{
p=0;
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
p+=a[i][j];
}
qr.push(p);
}
for(int j=1;j<=m;j++)
{
p=0;
for(int i=1;i<=n;i++)
{
p+=a[i][j];
}
qc.push(p);
}
for(int i=1;i<=k;i++)
{
r[i]=r[i-1];
p=qr.top();
r[i]+=p;
qr.pop();
p-=m*t;
qr.push(p);
}
for(int i=1;i<=k;i++)
{
c[i]=c[i-1];
p=qc.top();
c[i]+=p;
qc.pop();
p-=n*t;
qc.push(p);
}
ans=-223372036854775808;
for(int i=0;i<=k;i++)
{
p=k-i;
ans=max(ans,r[i]+c[p]-p*i*t);
}
cout<<ans;
return 0;
}
|
http://codeforces.com/problemset/problem/274/B 从树的底部一直推到树的最上边 记录一下从这个节点往下所有节点都变成0的时候的，至少要做几次+1，至少要做几次-1 然后往上一个节点更新
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
| #include<bits/stdc++.h>
using namespace std;
long long v[100010]={};
vector<int> e[100010];
int a,b;
int n;
bool vis[100010]={};
int d[100010]={};
queue<int> q;
long long pbu[100010]={};
long long dbu[100010]={};
long long bian[100010]={};
int g,p;
int main()
{
scanf("%d",&n);
d[1]=1000;
for(int i=1;i<n;i++)
{
scanf("%d%d",&a,&b);
e[a].push_back(b);
e[b].push_back(a);
d[a]++;
d[b]++;
}
for(int i=1;i<=n;i++)
{
scanf("%I64d",&v[i]);
}
for(int i=1;i<=n;i++)
{
if(d[i]==1)
{
q.push(i);
vis[i]=1;
bian[i]=-v[i];
if(bian[i]<0) dbu[i]+=abs(v[i]);
else pbu[i]+=abs(v[i]);
}
}
while(!q.empty())
{
g=q.front();
q.pop();
for(int i=0;i<e[g].size();i++)
{
p=e[g][i];
if(vis[p]==0)
{
d[p]--;
int f=0;
if(pbu[g]>pbu[p])
{
f+=pbu[g]-pbu[p];
pbu[p]=pbu[g];
}
if(dbu[g]>dbu[p])
{
f-=dbu[g]-dbu[p];
dbu[p]=dbu[g];
}
bian[p]+=f;
if(d[p]==1)
{
vis[p]=1;
v[p]+=bian[p];
bian[p]=-v[p];
if(v[p]>0)
{
dbu[p]+=v[p];
}
else
{
pbu[p]+=abs(v[p]);
}
q.push(p);
}
}
}
}
v[1]+=bian[1];
if(v[1]>0)
{
dbu[1]+=v[1];
}
else
{
pbu[1]+=abs(v[1]);
}
cout<<dbu[1]+pbu[1];
return 0;
}
|
http://codeforces.com/problemset/problem/432/D 用到了好多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
| #include<bits/stdc++.h>
using namespace std;
string s;
int p[100010]={};
char b[100010]={};
int num[100010]={};
int t;
stack<int> an;
stack<int> nu;
int main()
{
cin>>s;
for(int i=1;i<=s.size();i++) b[i]=s[i-1];
p[1]=0;
int j=0;
for(int i=2;i<=s.size();i++)
{
while((j>0)&&(b[j+1]!=b[i])) j=p[j];
if(b[j+1]==b[i]) j++;
p[i]=j;
}
t=p[s.size()];
for(int i=1;i<=s.size();i++)
{
num[p[i]]++;
}
t=p[s.size()];
int o;
int pr;
for(int i=s.size();i>t;i--)
{
num[p[i]]+=num[i];
}
while(t!=0)
{
o=1+num[t];
an.push(t);
nu.push(o);
pr=t;
t=p[t];
for(int i=pr;i>t;i--)
{
num[p[i]]+=num[i];
}
}
cout<<an.size()+1<<endl;
while(!an.empty())
{
cout<<an.top()<<" "<<nu.top()<<endl;
an.pop();
nu.pop();
}
cout<<s.size()<<" "<<1<<endl;
return 0;
}
|
http://codeforces.com/problemset/problem/91/B 裸set题 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
| #include<bits/stdc++.h>
using namespace std;
int n;
int a[100010]={};
int ans[100010]={};
set<pair<int,int>> s;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
s.insert(make_pair(0,n+1));
for(int i=n;i>=1;i--)
{
set<pair<int,int>>::iterator p;
p=s.lower_bound(make_pair(a[i],i));
if(p==s.end())
{
p--;
if((*p).first==0)
{
ans[i]=-1;
s.insert(make_pair(a[i],i));
}
else
{
ans[i]=(*p).second-i-1;
}
}
else
{
p--;
if((*p).first!=0) ans[i]=(*p).second-i-1;
else
{
ans[i]=-1;
s.insert(make_pair(a[i],i));
}
}
}
for(int i=1;i<=n;i++)
{
printf("%d ",ans[i]);
}
return 0;
}
|