Reku
0%

Codeforces Div 2 D 天梯 46——50

Posted on Edited on In Views: Valine:

http://codeforces.com/problemset/problem/142/B 贪心...真的是很看智商的一个东西啊... 为什么我就想不到呢orz 如果n=1，显然所有都能摆上 如果n=2，显然每4列分成组，然后前两列摆满 这两个情况都非常傻逼...随便就能想到...问题就是剩下的情况... 如果n>=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
25
26
27
#include<bits/stdc++.h>
using namespace std;
int n,m;
int ans;
int tt;
int main()
{
	cin>>n>>m;
	if(n>m) swap(n,m);
	if(n==1)
	{
		cout<<m;
		return 0;
	}
	if(n==2)
	{
		ans=m/4;
		ans*=4;
		m=m%4;
		if(m>=1) ans+=2;
		if(m>=2) ans+=2;
		cout<<ans;
		return 0;
	}
	cout<<n*m/2+(n*m)%2;
	return 0;
}

http://codeforces.com/problemset/problem/272/D 比较简单的一个排列组合 唯一的问题就是排列数有可能太大了，爆long long 其实只要边算边除边取余就可以了 通过这道题学会了auto的用法，感觉很厉害的样子

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
#include<bits/stdc++.h>
using namespace std;
map<long long,long long> ha;
long long a[100010]={};
long long b[100010]={};
long long n;
long long t;
long long ans;
long long x;
long long m;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		ha[a[i]]++;
	}
	for(int i=1;i<=n;i++)
	{
		cin>>b[i];
		ha[b[i]]++;
		if(b[i]==a[i]) t++;
	}
	cin>>m;
	ans=1;
	for(auto i=ha.begin();i!=ha.end();i++)
	{	
		for(long long j=1;j<=i->second;j++)
		{
		
			x=j;
			while(t>0&&x%2==0)
			{
				x/=2;
				t--;
			}
			ans*=x;
			ans%=m;
		}	
	}
	cout<<ans;
	return 0;
}

http://codeforces.com/problemset/problem/9/D 动态规划 \(dp[i][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
#include<bits/stdc++.h>
using namespace std;
int n,h;
long long dp[36][36]={};
bool v[36]={};
long long ans;
void ff(int x)
{
	if(v[x]==1) return;
	v[x]=1;
	if(x==1)
	{
		dp[1][1]=1;
		return;
	}
	if(x==0)
	{
		dp[0][0]=1;
		return;
	}
	int a,b;
	for(int i=1;i<=x;i++)
	{
		a=i-1;
		b=x-i;
		ff(a);
		ff(b);
		for(int k=0;k<=a;k++)
		{
			for(int u=0;u<=b;u++)
			{
				dp[x][max(k,u)+1]+=dp[a][k]*dp[b][u];
			}
		}
	}
	return;
}
int main()
{
	cin>>n>>h;
	ff(n);
	for(int i=h;i<=n;i++)
	{
		ans+=dp[n][i];
	}
	cout<<ans;
	return 0;
}

http://codeforces.com/problemset/problem/145/B 贪心 对结果有贡献的串就是47474747474.... 或者7474747474.... 然后随便贪贪，搞出最小值就可以了

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
#include<bits/stdc++.h>
using namespace std;
int a1,a2,a3,a4;
int ans[3000010]={};
int o;
int l;
int a,b;
int main()
{
	cin>>a1>>a2>>a3>>a4;
	a=a1;
	b=a2;
	if(abs(a3-a4)>1)
	{
		cout<<-1;
		return 0;
	}
	if(a3<a4)
	{
		for(int i=1;i<=max(a3,a4);i++)
		{
			l++;
			ans[l]=7;
			a2--;
			l++;
			ans[l]=4;
			a1--;
		}
		if(a3==a4)
		{
			l++;
			ans[l]=7;
			a2--;
		}
		if(a1<0||a2<0)
		{
			a1=a,a2=b;
			l=0;
			for(int i=1;i<=max(a3,a4);i++)
			{
				l++;
				ans[l]=4;
				a1--;
				l++;
				ans[l]=7;
				a2--;
			}
			if(a3==a4)
			{
				l++;
				ans[l]=4;
				a1--;
			}
		}
		if(a1<0||a2<0)
		{
			cout<<-1;
			return 0;
		}
	}
	else
	{
		for(int i=1;i<=max(a3,a4);i++)
		{
			l++;
			ans[l]=4;
			a1--;
			l++;
			ans[l]=7;
			a2--;
		}
		if(a3==a4)
		{
			l++;
			ans[l]=4;
			a1--;
		}
		if(a1<0||a2<0)
		{
			a1=a,a2=b;
			l=0;
			for(int i=1;i<=max(a3,a4);i++)
			{
				l++;
				ans[l]=7;
				a2--;
				l++;
				ans[l]=4;
				a1--;
			}
			if(a3==a4)
			{
				l++;
				ans[l]=7;
				a2--;
			}
		}
		if(a1<0||a2<0)
		{
			cout<<-1;
			return 0;
		}
	}
	for(int i=l;i>=1;i--)
	{
		if(ans[i]==7)
		{
			o=i;
			break;
		}
	}
	for(int i=1;i<=l;i++)
	{
		while(ans[i]==7&&o==i&&a2!=0)
		{
			a2--;
			cout<<7;
		}
		while(ans[i]==4&&a1!=0)
		{
			a1--;
			cout<<4;
		}
		cout<<ans[i];
	}
	return 0;
}

http://codeforces.com/problemset/problem/234/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
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
#include<bits/stdc++.h>
using namespace std;
#define N 107
 
int zero[N],vis[N],a[N];
int d[N][N];
int like[N],mlike[N];
map<int,int> mp;
 
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    int m,k,chang,i,j,maxilike,ka,maximlike;
    char ss[17];
    while(scanf("%d%d",&m,&k)!=EOF)
    {
        mp.clear();
        for(i=0;i<k;i++)
        {
            scanf("%d",&a[i]);
            mp[a[i]] = 1;
        }
        memset(zero,0,sizeof(zero));
        maxilike = maximlike = -10000;
        scanf("%d",&chang);
        for(i=0;i<chang;i++)
        {
            scanf("%s",ss);
            scanf("%d",&ka);
            for(j=0;j<ka;j++)
            {
                scanf("%d",&d[i][j]);
                if(d[i][j] == 0)
                    zero[i]++;
            }
            if(ka == m)
            {
                maxilike = max(maxilike,k);
                maximlike = max(maximlike,k);
                mlike[i] = k;
                like[i] = k;
            }
            else
            {
                int ca = 0;
                memset(vis,0,sizeof(vis));
                for(j=0;j<k;j++)
                    vis[a[j]] = 1;
                for(j=0;j<ka;j++)
                {
                    if(mp[d[i][j]])
                        ca++;
                    vis[d[i][j]] = 1;
                }
                int unvis = 0;
                for(j=1;j<=m;j++)
                {
                    if(!vis[j])
                        unvis++;
                }
                if(unvis < zero[i])
                {
                    like[i] = ca + zero[i] - unvis;
                    mlike[i] = ca + min(zero[i],k-ca);
                }
                else
                {
                    mlike[i] = ca + min(zero[i],k-ca);
                    like[i] = ca;
                }
                maxilike = max(maxilike,like[i]);
                maximlike = max(maximlike,mlike[i]);
            }
        }
        for(i=0;i<chang;i++)
        {
            if(like[i] >= maximlike || (like[i] >= maxilike && mlike[i] == maximlike))
            {
                if(like[i] >= maximlike)
                    printf("0\n");
                else
                {
                    int flag = 1;
                    for(j=0;j<chang;j++)
                    {
                        if(j!=i && like[i] < mlike[j])
                        {
                            flag = 0;
                            break;
                        }
                    }
                    if(flag)
                        printf("0\n");
                    else
                        printf("2\n");
                }
            }
            else if(mlike[i] < maxilike)
                printf("1\n");
            else
                printf("2\n");
        }
    }
    return 0;
}