Reku
0%

Codeforces Div 2 C 天梯 1——5

Posted on Edited on In Views: Valine:

http://codeforces.com/problemset/problem/489/C 贪心着选各个位数就行 最大和最小的贪心方法差不多，只是最小值倒着贪心的时候最后一位至少要留出1，而最大可以直接贪到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
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int m,s;
	int a;
	int p[101]={};
	cin>>m>>s;
	a=s;
	if(m==1&&s==0)
	{
		cout<<"0"<<" "<<"0";
		return 0;
	}
	if(m*9<s||s==0)
	{
		cout<<"-1"<<" "<<"-1";
		return 0;
	}
	int q=9;
	for(int i=1;i<=m;i++)
	{
		while(s-q<1) q--;
		s-=q;
		p[i]=q;
	}
	if(s!=0) p[m]+=s;
	for(int i=m;i>=1;i--) cout<<p[i];
	cout<<" ";
	q=9;
	s=a;
	for(int i=1;i<=m;i++)
	{
		while(s-q<0) q--;
		s-=q;
		p[i]=q;
	}
	for(int i=1;i<=m;i++) cout<<p[i];
	return 0;
}
http://codeforces.com/problemset/problem/466/C 找到所有可能的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
#include<bits/stdc++.h>
using namespace std;
long long u[500010]={};
long long h[500010]={};
long long hh=0;
long long f[500010]={};
long long s[500010]={};
long long nf=0,ns=0;
long long ans=0;
int n;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>u[i];
		h[i]=h[i-1];
		h[i]+=u[i];
		hh+=u[i];
	}
	if(hh%3!=0)
	{
		cout<<ans;
		return 0;
	}
	for(int i=1;i<n;i++)
	{
		if(h[i]==hh/3)
		{
			nf++;
			f[nf]=i;
		}
		if(h[i]==hh*2/3)
		{
			ns++;
			s[ns]=i;
		}
	}
	long long r=1;
	for(int i=1;i<=nf;i++)
	{
		while(s[r]<=f[i]&&r!=ns+1) r++;
		ans+=ns-r+1;
	}
	cout<<ans;
	return 0;
}
http://codeforces.com/problemset/problem/401/C 就是一个简单的贪心...不能有超过连续3个1，不能连续超过两个0，那就110或者10这么贪就行了 不过各种特殊情况似乎比较多，一遍写对真是个奇迹 
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;
int n,m;
int main()
{
	cin>>n>>m;
	if(n>m+1)
	{
		cout<<-1;
		return 0;
	}
	if(m-2*n>=3)
	{
		cout<<-1;
		return 0;
	}
	if(m==1&&n==0)
	{
		cout<<1;
		return 0;
	}
	if(m==2&&n==0)
	{
		cout<<11;
		return 0;
	}
	if(n==m+1)
	{
		n--;
		cout<<0;
	}
	while(m>n&&n!=0&&m!=0)
	{
		m-=2;
		n-=1;
		cout<<110;
	}
	if(m==1&&n==0)
	{
		cout<<1;
		return 0;
	}
	if(m==2&&n==0)
	{
		cout<<11;
		return 0;
	}
	while(m==n&&m!=0)
	{
		m--;
		n--;
		cout<<10;
	}
	return 0;
}
http://codeforces.com/problemset/problem/479/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
#include<bits/stdc++.h>
using namespace std;
pair<int,int> p[5010];
bool cmp(pair<int,int> a,pair<int,int> b)
{
	return a<b;
}
int n;
int a,b;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a>>b;
		p[i]=make_pair(a,b);
	}
	sort(p+1,p+n+1,cmp);
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		if(p[i].second>=ans)
		{
			ans=p[i].second;
		}
		else
		{
			ans=p[i].first;
		}
	}
	cout<<ans;
	return 0;
}
http://codeforces.com/problemset/problem/455/A 动态规划 dp[i]代表≤i的值都消去了，所产生的最大答案 通过dp[i-1]和dp[i-2]来转移 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
long long a[100010]={};
long long num[100010]={};
long long dp[100010]={};
long long ans;
long long n;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		num[a[i]]++;
	}
	for(int i=1;i<=100000;i++)
	{
		dp[i+1]=max(dp[i+1],dp[i-1]+i*num[i]);
		if(i-2>=0) dp[i+1]=max(dp[i+1],dp[i-2]+i*num[i]);
		ans=max(dp[i+1],ans);
	}
	cout<<ans;
	return 0;
}