BestCoder Round #36 （HDU5198 HDU5199 HDU5200 HDU5201）

发表于 | 更新于 | 分类于 ， | 评论数： | 阅读次数：

水题四发。 HDU5201 m个猴子要分n个桃子。要使得第一个猴子分到的是最多的。 也就是求\(x_1+x_2+\cdots+x_m=n\),而且满足\(x_1>x_2,x_1>x_3,\cdots,x_1>x_m\)有多少个非负整数解。 做法是枚举+容斥。 枚举假如第一个猴子分到x个。那就是要在后面m-1个猴子里面分n-x个桃子，而且每个猴子分到的要小于x。 这是个经典的容斥问题。 具体推导不细说了，写写公式就出来了。就是要求0个大于等于x的分法有多少种。

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
/* ***************

Author        :kuangbin

Created Time  :2015/4/6 14:34:46

File Name     :E:\2014ACM\Bestcoder\BC36\D.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

const int MOD = 1e9+7;

long long inv(long long a,long long m){

	if(a == 1)return 1;

	return inv(m%a,m)*(m-m/a)%m;

}

const int MAXN = 200010;

int f[MAXN],rf[MAXN];

long long C(int n,int m){

	return (long long)f[n]*rf[m]%MOD*rf[n-m]%MOD;

}

long long calc(int x,int n,int m){

	if(m == 0)return 1;

	if(n == 0)return 0;

	long long ans = 0;

	for(int i = 0;i*x <= m && i <= n;i++){

		long long tmp = C(n,i)*C(m-i*x + n-1,n-1)%MOD;

		if(i%2 == 0)ans = (ans+tmp)%MOD;

		else ans = (ans-tmp+MOD)%MOD;

	}

	return ans;

}

int main()

{

    //freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    f[0] = 1;

	for(int i = 1;i <= 200000;i++)f[i] = (long long)f[i-1]*i%MOD;

	rf[200000] = inv(f[200000],MOD);

	for(int i = 200000;i >= 1;i--)rf[i-1] = (long long)rf[i]*i%MOD;

	int T;

	int n,m;

	scanf("%d",&T);

	while(T--){

		scanf("%d%d",&n,&m);

		int ans = 0;

		for(int i = 1;i <= n;i++){

			ans = (ans+calc(i,m-1,n-i))%MOD;

		}

		printf("%d\n",ans);

	}

    return 0;

}
[HDU5200](http://acm.hdu.edu.cn/showproblem.php?pid=5200) 离线乱搞。从大到小离线，树从大到小加入。 如果加入的两边为空，块加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
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
128
129
/* ***************

Author        :kuangbin

Created Time  :2015/4/6 15:59:08

File Name     :E:\2014ACM\Bestcoder\BC36\C.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

const int MAXN = 100010;

struct Node{

	int x,index;

	bool operator <(const Node &b)const{

		return x > b.x;

	}

}node[MAXN];

int a[MAXN];

int b[MAXN];

bool cmp(int i,int j){

	return a[i] > a[j];

}

int ans[MAXN];

bool vis[MAXN];

int main()

{

    //freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    int n,q;

	while(scanf("%d%d",&n,&q) == 2){

		for(int i = 1;i <= n;i++){

			scanf("%d",&a[i]);

			b[i] = i;

		}

		sort(b+1,b+n+1,cmp);

		for(int i = 0;i < q;i++){

			scanf("%d",&node[i].x);

			node[i].index = i;

		}

		sort(node,node+q);

		int cnt = 0;

		memset(vis,false,sizeof(vis));

		int j = 1;

		for(int i = 0;i < q;i++){

			while(j <= n && a[b[j]] > node[i].x){

				if(!vis[b[j]-1] && !vis[b[j]+1])cnt++;

				else if(vis[b[j]-1] && vis[b[j]+1])cnt--;

				vis[b[j]] = true;

				j++;

			}

			ans[node[i].index] = cnt;

		}

		for(int i = 0;i < q;i++)

			printf("%d\n",ans[i]);

	}

    return 0;

}

HDU5199 开了个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
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
/* ***************

Author        :kuangbin

Created Time  :2015/4/6 16:26:59

File Name     :E:\2014ACM\Bestcoder\BC36\B.cpp

 ************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

//适用于正负整数

template <class T>

inline bool scan_d(T &ret) {

	char c; int sgn;

	if(c=getchar(),c==EOF) return 0; //EOF

	while(c!='-'&&(c<'0'||c>'9')) c=getchar();

	sgn=(c=='-')?-1:1;

	ret=(c=='-')?0:(c-'0');

	while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');

	ret*=sgn;

	return 1;

}

inline void out(int x) {

	if(x>9) out(x/10);

	putchar(x%10+'0');

}

int main()

{

	//freopen("in.txt","r",stdin);

	//freopen("out.txt","w",stdout);

	int n,m;

	while(scanf("%d%d",&n,&m) == 2){

		map<int,int>mp;

		int a;

		while(n--){

			scan_d(a);

			mp[a]++;

		}

		while(m--){

			scan_d(a);

			if(mp.count(a)){

				printf("%d\n",mp[a]);

				mp[a] = 0;

			}

			else printf("0\n");

		}

	}

	return 0;

}

HDU5198 水题，不能多说。

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
/* ***************

Author        :kuangbin

Created Time  :2015/4/6 16:34:50

File Name     :E:\2014ACM\Bestcoder\BC36\A.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

char str[1000];

int main()

{

    //freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    while(scanf("%s",str) == 1){

		int n = strlen(str);

		if(n%3){

			printf("NO\n");

			continue;

		}

		bool flag = true;

		for(int i = 1;i < n/3;i++)

			if(str[i] != str[i-1])

				flag = false;

		for(int i = n/3+1;i < n/3*2;i++)

			if(str[i] != str[i-1])

				flag = false;

		for(int i = n/3*2+1;i < n;i++)

			if(str[i] != str[i-1])

				flag = false;

		if(str[0] == str[n/3] || str[n/3] == str[n/3*2] || str[0] == str[n/3*2])

			flag = false;

		if(flag)printf("YES\n");

		else printf("NO\n");

	}

    return 0;

}
------ 本文结束------
  • 本文作者： kuangbin
  • 本文链接： 578.html
  • 版权声明： 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处！
0%