Reku
0%

Codeforces Div 2 C 天梯 31——35

Posted on Edited on In Views: Valine:

http://codeforces.com/problemset/problem/264/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
#include<bits/stdc++.h>
using namespace std;
int ans[1000010]={};
int l,r;
string s;
int main()
{
	cin>>s;
	l=0; r=s.size()+1;
	for(int i=0;i<s.size();i++)
	{
		if(s[i]=='l')
		{
			r--;
			ans[r]=i;
		}
		else
		{
			l++;
			ans[l]=i;
		}
	}
	for(int i=1;i<=s.size();i++) printf("%d\n",ans[i]+1);
	return 0;
}

http://codeforces.com/problemset/problem/149/C 感觉是个傻逼题... 我觉得怎么搞都能过... 根本不会乱搞了一下，竟然过了...真是傻逼题... 

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
#include<bits/stdc++.h>
using namespace std;
struct pp
{
	int a,num;
} p[100010];
bool v[100010]={};
int n;
int ma;
int h[100010]={};
bool cmp(pp x,pp y)
{
	return x.a<y.a;
}
int o;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&p[i].a);
		p[i].num=i;
		ma=max(p[i].a,ma);
	}
	sort(p+1,p+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		h[i]=h[i-1]+p[i].a;
	}
	o=n/2;
	for(int i=0;i<=n;i++)
	{
		int x,y;
		y=h[i+o]-h[i];
		x=h[n]-y;
		if(abs(y-x)<=ma)
		{
			cout<<o<<endl;
			for(int j=i+1;j<=i+o;j++) cout<<p[j].num<<" ",v[p[j].num]=1;
			cout<<endl;
			break;
		}
	}
	cout<<n-o<<endl;
	for(int i=1;i<=n;i++)
	{
		if(v[i]==0) cout<<i<<" ";
	}
	cout<<endl;
	return 0;
}
http://codeforces.com/problemset/problem/225/C 动态规划 d[i][0][j]和d[i][1][j]分别表示现在算到第i列，然后已经形成了连续j列的.或者* 然后直接动态规划就行 然后需要用一下前缀最值，减一个时间维度... 预处理有些烦 
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
#include<bits/stdc++.h>
using namespace std;
int n,m,x,y;
char c;
int d[1010][2][1010]={};
int mi[1010][2]={};
int p[2][1010]={};
int ans;
int main()
{
	cin>>n>>m>>x>>y;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>c;
			if(c=='.') p[0][j]++;
			else p[1][j]++;
		}
	}
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=y;j++)
		{
			d[i][0][j]=1147483600;
			d[i][1][j]=1147483600;
		}
		mi[i][0]=1147483600;
		mi[i][1]=1147483600;
	}
	ans=1147483600;
	d[1][0][1]=p[0][1];
	d[1][1][1]=p[1][1];
	if(x==1)
	{
		mi[1][0]=p[0][1];
		mi[1][1]=p[1][1];
	}
	if(m==1)
	{
		cout<<min(p[0][1],p[1][1])<<endl;
		return 0;
	}
	for(int i=2;i<=m;i++)
	{
		for(int j=1;j<=y;j++)
		{
			if(j==1)
			{
				d[i][0][j]=min(mi[i-1][1]+p[0][i],d[i][0][j]);
				d[i][1][j]=min(mi[i-1][0]+p[1][i],d[i][1][j]);
			}
			else
			{
				d[i][0][j]=min(d[i-1][0][j-1]+p[0][i],d[i][0][j]);
				d[i][1][j]=min(d[i-1][1][j-1]+p[1][i],d[i][1][j]);
			}
			if(j>=x)
			{
				mi[i][1]=min(d[i][1][j],mi[i][1]);
				mi[i][0]=min(d[i][0][j],mi[i][0]);
			}
			if(i==m&&j>=x)
			{	
				ans=min(d[i][0][j],ans);
				ans=min(d[i][1][j],ans);
			}
		}
	}
	cout<<ans;
	return 0;
}
http://codeforces.com/problemset/problem/18/C 傻逼题 前缀和瞎搞搞就行 
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
#include<bits/stdc++.h>
using namespace std;
int n;
int a[100010]={};
int h[100010]={};
int ans=0;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++)
	{
		h[i]=h[i-1]+a[i];
	}
	if(h[n]%2)
	{
		cout<<0;
		return 0;
	}
	for(int i=1;i<n;i++)
	{
		if(h[i]==h[n]/2)
		{
			ans++;
		}
	}
	cout<<ans;
	return 0;
}
http://codeforces.com/problemset/problem/348/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
#include<bits/stdc++.h>
using namespace std;
long long n;
long long a[100010]={};
bool pa(long long x)
{
	long long h=0;
	for(int i=1;i<=n;i++)
	{
		h+=(x-a[i]);
	}
	if(h>=x) return 1;
	return 0;
}
int main()
{
	cin>>n;
	long long l=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		l=max(l,a[i]);
	}
	
	long long r=2147483600;
	while(l<r)
	{
		long long mid=(l+r)/2;
		if(pa(mid)==1) r=mid;
		else l=mid+1;
	}
	cout<<r;
	return 0;
}