Reku
0%

Codeforces Div 2 D 天梯 6——10

Posted on Edited on In Views: Valine:

http://codeforces.com/problemset/problem/448/D 二分查找，感觉似乎还是挺直观的？... 就是从头扫到尾，算一下小于目标值的数量p，找到第一个＜k的p就行，明显的二分查找 

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,m,k;
bool pa(long long x)
{
	long long ans=0;
	for(int i=1;i<=n;i++)
	{
		if(x%i==0)
		{
			ans+=min((x-1)/i,m);
		}
		else
		{
			ans+=min(x/i,m);
		}
	}
	if(ans<k) return 1;
	return 0;
}
int main()
{
	cin>>n>>m>>k;
	long long l=0;
	long long r=250000000000ll;
	while(l<r)
	{
		long long mid=(l+r)/2+1;
		if(pa(mid)) l=mid;
		else r=mid-1;
	}
	cout<<l<<endl;
	return 0;
}

http://codeforces.com/problemset/problem/489/D 试图n*n用bitset莽一下，结果失败了... 可能是因为常数太大了...

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;
bitset<3010> e[3010];
bitset<3010> q[3010];
bitset<3010> t;
bitset<3010> u;
long long n,m;
long long a,b;
long long ans;
int main()
{
	scanf("%I64d%I64d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%I64d%I64d",&a,&b);
		e[a][b]=1;
		q[b][a]=1;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(i!=j)
			{
				t=e[i]&q[j];
				b=t.count();
				ans+=b*(b-1);
			}
		}
	}
	printf("%I64d",ans/2);
	return 0;
}

其实只要每个点向后走两步就行...每条边最多算两次，所以不会超时... codeforces养成了我经常用stl的坏习惯...

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;
vector<long long> e[3010];
long long h[3010][3010]={};
long long n,m;
long long a,b;
long long ans;
queue<int> q;
int main()
{
	scanf("%I64d%I64d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%I64d%I64d",&a,&b);
		e[a].push_back(b);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<e[i].size();j++)
		{
			long long p=e[i][j];
			for(int k=0;k<e[p].size();k++)
			{
				if(e[p][k]!=i)
				{
					h[i][e[p][k]]++;
				}
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			b=h[i][j];
			if(b!=0) ans+=b*(b-1);
		}
	}
	printf("%I64d\n",ans/2);
	return 0;
}

http://codeforces.com/problemset/problem/118/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
#include<bits/stdc++.h>
#define mod 100000000
using namespace std;
long long n1,n2,k1,k2;
long long d[110][110][2]={};
long long ans;
int main()
{
	cin>>n1>>n2>>k1>>k2;
	d[0][0][0]=1;
	d[0][0][1]=1;
	for(int i=0;i<=n1;i++)
	{
		for(int j=0;j<=n2;j++)
		{
			for(int k=1;k<=k1;k++)
			{
				if(i-k>=0)
				{
					d[i][j][0]+=d[i-k][j][1];
					d[i][j][0]%=mod;
				}
			}
			for(int k=1;k<=k2;k++)
			{
				if(j-k>=0)
				{
					d[i][j][1]+=d[i][j-k][0];
					d[i][j][1]%=mod;
				}
			}
		}
	}
	ans=d[n1][n2][1]+d[n1][n2][0];
	ans%=mod;
	cout<<ans;
	return 0;
}

http://codeforces.com/problemset/problem/246/D 就是看一下相邻节点... 用map判一下重就行 

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
#include<bits/stdc++.h>
using namespace std;
int c[100010]={};
int n,m;
int a,b;
vector<int> e[100010];
map<pair<int,int>,bool> ha;
pair<int,int> p;
int q[100010]={};
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&c[i]);
		p=make_pair(c[i],c[i]);
		ha[p]=1;
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&a,&b);
		e[a].push_back(b);
		e[b].push_back(a);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<e[i].size();j++)
		{
			p=make_pair(c[i],c[e[i][j]]);
			if(ha[p]==0)
			{
				ha[p]=1;
				q[c[i]]++;
			}
		}
	}
	a=-1;
	for(int i=1;i<=100000;i++)
	{
		p=make_pair(i,i);
		if(q[i]>a&&ha[p]==1)
		{
			b=i;
			a=q[i];
		}
	}
	cout<<b<<endl;
	return 0;
}

http://codeforces.com/problemset/problem/276/D 其实我们只要知道最大的两个数，结尾肯定10...00和01...11 所以就找l到r之间的这两个数就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long l,r;
	cin>>l>>r;
	long long t;
	long long a,b;
	t=0;
	for(long long i=62;i>=0;i--)
	{
		b=1ll<<i;
		a=b-1ll;
		if(a+t>=l&&b+t<=r)
		{
			cout<<b*2ll-1ll<<endl;
			return 0;
		}
		if(r>=b+t) t+=b;
	}
	cout<<0<<endl;
	return 0;
}