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%