Codeforces Round #313 (Div. 2)
Codeforces Round #313 (Div. 2)
大半年没有打Codeforces ， 昨天开始恢复打Codeforces， 简直是， 欲语泪先流啊。
手残到爆的写错了范围， 手残的数漏了条件， 简直不能直视， 最坑爹的是， E题没时间写代码了。
Problem_A:
题意：
给n个数， 每个数可以用无限次， 求用这些数的和表示不出来的最小的正整数， 没有则输出 -1.
思路：
如果这n个数里面有1， 那么一定可以表示所有数， 没有1的话， 最小的正整数就是1
代码：
1 #include <cmath>
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 #include <ctime>
6 #include <set>
7 #include <map>
8 #include <list>
9 #include <queue>
10 #include <string>
11 #include <vector>
12 #include <fstream>
13 #include <iterator>
14 #include <iostream>
15 #include <algorithm>
16 using namespace std;
17 #define LL long long
18 #define MAXN 1000010
19 #define MOD 1000000007
20 #define eps 1e-6
21 int n;
22
23 int main()
24 {
25 bool flag = false;
26 scanf("%d",&n);
27 for(int i = 0; i < n; i ++)
28 {
29 int x;
30 scanf("%d", &x);
31 if(x == 1) flag = true;
32 }
33 printf("%d\n",flag? -1 : 1);
34 return 0;
35 }
36 Problem_B:
题意：
给三个矩形a, b, c。 问是否能将b和c放入a中。
思路：
无非四种状态。
1）都横着放。
2）都竖着放。
3）一横一竖。
①¬， 竖的放在横着的下面。
②|-，竖的放在横着的旁边。
4）连接在一起。
①--， 横着连在一起。
②| ， 竖着连在一起。
代码如下：
1 #include <cmath>
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 #include <ctime>
6 #include <set>
7 #include <map>
8 #include <list>
9 #include <queue>
10 #include <string>
11 #include <vector>
12 #include <fstream>
13 #include <iterator>
14 #include <iostream>
15 #include <algorithm>
16 using namespace std;
17 #define LL long long
18 #define MAXN 4
19 #define MOD 1000000007
20 #define eps 1e-6
21 int a[MAXN], b[MAXN];
22 void show()
23 {
24 printf("fuck\n");
25 }
26 bool is_ok()
27 {
28 //1) =
29 if(max(a[1], a[2]) <= a[0] && (b[1] + b[2]) <= b[0]) return true;
30 //2)-- && |
31 if((a[1] + a[2] <= a[0]) && max(b[1], b[2]) <= b[0]) return true;
32 if((a[1] + a[2] <= b[0]) && max(b[1], b[2]) <= a[0]) return true;
33 //3)||
34 if((b[1] + b[2] ) <= a[0] && (max(a[1], a[2]) <= b[0])) return true;
35 //4)|-
36 if((b[1] + a[2] <= a[0]) && ((a[1] >= b[2]? a[1] : b[2]) <= b[0])) return true;
37 if((b[2] + a[1] <= a[0]) && ((a[2] >= b[1]? a[2] : b[1]) <= b[0])) return true;
38 //5)-|
39 if(((a[1] >= b[2]? a[1] : b[2]) <= a[0]) && (b[1] + a[2] <= b[0])) return true;
40 if(((a[2] >= b[1]? a[2] : b[1]) <= a[0]) && (b[2] + a[1] <= b[0])) return true;
41 return false;
42 }
43
44 int main()
45 {
46 for(int i = 0; i < 3; i ++)
47 scanf("%d %d",&a[i], &b[i]);
48 printf(is_ok()?"YES\n":"NO\n");
49 return 0;
50 }Problem_C:
题意：
给一个内角均为120°的六边形（不一定是正六边形）， 问， 能将其分割成多少个单位三角形。
思路：
将这个六边形的平行边延长， 相交于三点， 构成一个三角形， 可以证明这个三角形为等边三角形。
因为六边形内角均为120°， 得到三个红色三角形的两个内角为60°， 所以得大三角形的三个顶角均为60°。
所以， 等边三角形的边长为：(a1 + a2 + a3) = (a1 + a6 + a5) = (a1 + a2 + a6) = (a3 + a4 + a5) =....
三角形每行有f(x)个单位三角形， x为每行底边长.
f(x) = x + x - 1 = 2 * x - 1;
f(1) = 1;
f(x + 1) - f(x) = 2(x + 1) - 1 - (2 * x - 1)
= 2
得， 解为：s(len) = f(1) + f(2) + ... + f(len), len 为等边三角形边长。
=(1 + 2 * x - 1) * x / 2
=x ^ 2
所以， 边长为n 的等边三角形所含单位三角形数为 s(n)。
题目所有的六边形所含单位三角形数为：s(n) - f(a1) - f(a3) - f(a5)。
即， 减去三个角的等边三角形， 剩下的就是六边形所包含的
代码如下：
1 #include <cmath>
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 #include <ctime>
6 #include <set>
7 #include <map>
8 #include <list>
9 #include <queue>
10 #include <string>
11 #include <vector>
12 #include <fstream>
13 #include <iterator>
14 #include <iostream>
15 #include <algorithm>
16 using namespace std;
17 #define LL long long
18 #define MAXN 7
19 #define MAXM 4000
20 #define MOD 1000000007
21 #define eps 1e-6
22 int a[MAXN];
23 int fac[MAXM];
24 void init()
25 {
26 fac[0] = 1;
27 for(int i = 1; i < MAXM; i++)
28 fac[i] = i * i;
29 }
30
31 int main()
32 {
33 init();
34 for(int i = 1; i <= 6; i ++)
35 scanf("%d",&a[i]);
36 int ans = fac[a[1] + a[2] + a[3]] - fac[a[1]] - fac[a[3]] - fac[a[5]];
37 printf("%d\n",ans);
38 return 0;
39 }Problem_D:
题意：
给两个字符串a,b， 判断它们是否等价。
等价的定义：
满足下列条件之一的就是等价。
1）a == b
2）将字符串a， 分成两部分长度相等的子串a1, a2， b 分成两部分长度相等的子串b1, b2， 满足下列条件之一
①a1 == b1 并且 a2 == b2
②a1 == b2 并且 a2 == b1
思路：
暴力模拟查找， 也可以hash之后再找， 降低查找的复杂度为O(1)。
队友写了一发hash， 我直接暴力的。
暴力模拟注意string , cin 会超时， 需要用char[] , scanf()。
代码如下：
1 #include <cmath>
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 #include <ctime>
6 #include <set>
7 #include <map>
8 #include <list>
9 #include <queue>
10 #include <string>
11 #include <vector>
12 #include <fstream>
13 #include <iterator>
14 #include <iostream>
15 #include <algorithm>
16 using namespace std;
17 #define LL long long
18 #define MAXN 2000010
19 #define MOD 1000000007
20 #define eps 1e-6
21 char str_a[MAXN], str_b[MAXN];
22 bool dfs(int pos_a, int pos_b, int len)
23 {
24 if(!strncmp(str_a + pos_a, str_b + pos_b, len)) return true;
25 if(len & 1) return false;
26 int sub_len = len / 2;
27 return (dfs(pos_a , pos_b, sub_len) && dfs(pos_a + sub_len, pos_b + sub_len, sub_len))
28 || (dfs(pos_a + sub_len, pos_b , sub_len) && dfs(pos_a , pos_b + sub_len, sub_len));
29 }
30
31 int main()
32 {
33 scanf("%s %s", str_a, str_b);
34 printf(dfs(0, 0, strlen(str_a)) ? "YES\n" : "NO\n");
35 return 0;
36 }Problem_E：
题意：
给一个h*w的棋盘， 只能往右走， 往下走， 有n个黑格子， 黑格子不能走，问从左上角走到右下角有多少种方案数。
思路：
组合数学书上的一个例题，原题只是背景不同。
这里利用减法原理， 求出所有经过黑格子的方案数， 再用总的方案数减去就得到答案。
sum = C(h - 1 + w - 1, h - 1)
设dp[i] 为从左上角不经过任何黑格子走到第i个黑格子的方案数，
dp[i] = C(x[i] - 1 + y[i] - 1, x[i] - 1) - sigma(x[j] <= x[i] && y[j] <= y[i]) dp[j] * C(x[i] - x[j] + y[i] - y[j], x[i] - x[j])
红色部分为（1，1）到（x[i]，y[[i]）这个矩形区域内， 经过黑格子到（i，j）的方案数。
则经过第i个黑格子到达右下角的方案数为：dp[i] * C(h - x[i] + w - y[i], w - [i])。
再用sum 减去所有的dp[i]即可。
代码如下：
1 #include <cmath>
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 #include <ctime>
6 #include <set>
7 #include <map>
8 #include <list>
9 #include <queue>
10 #include <string>
11 #include <vector>
12 #include <fstream>
13 #include <iterator>
14 #include <iostream>
15 #include <algorithm>
16 using namespace std;
17 #define LL long long
18 #define MAXN 2020
19 #define MAXM 500010
20 #define MOD 1000000007
21 #define eps 1e-6
22 int w, h, n;
23 LL dp[MAXN];
24 LL fac[MAXM], fack[MAXM];
25 struct node
26 {
27 int x;
28 int y;
29 };
30 struct node f[MAXN];
31 bool cmp(struct node x, struct node y)
32 {
33 if(x.x == y.x) return x.y < y.y;
34 return x.x < y.x;
35 }
36 LL qpow(LL x, LL k)
37 {
38 LL res = 1;
39 while(k)
40 {
41 if(k & 1) res = res * x % MOD;
42 x = x * x % MOD;
43 k >>= 1;
44 }
45 return res;
46 }
47 LL C(LL n, LL m)
48 {
49 if(m < 0 || m > n) return 0;
50 return fac[n] * fack[m] % MOD * fack[n-m] % MOD;
51 }
52 void init()
53 {
54 fac[0] = fack[0] = fac[1] = fack[1] = 1;
55 for(int i = 2; i < MAXM; i ++)
56 {
57 fac[i] = fac[i-1] * i % MOD;
58 fack[i] = qpow(fac[i], MOD - 2);
59 }
60 }
61
62 int main()
63 {
64 init();
65 scanf("%d %d %d", &h, &w, &n);
66 for(int i = 0; i < n; i ++)
67 scanf("%d %d",&f[i].x, &f[i].y);
68 memset(dp, 0, sizeof(dp));
69 sort(f, f + n, cmp);
70 //ans = C(h + w - 2, h - 1)
71 //dp[i] = C(f[i].x + f[i].y - 2, f[i].x - 1) - dp[j] * C(f[i].x - f[j].x + f[i].y - f[j].y, f[i].x - f[j].x)
72 //ans -= dp[i] * C(h - f[i].x + w - f[i].y, h -f[i].x)
73 LL ans = C(h + w - 2, h - 1);
74 for(int i = 0; i < n; i ++)
75 {
76 dp[i] = C(f[i].x + f[i].y - 2, f[i].x - 1);
77 for(int j = 0; j < i; j ++)
78 if(f[j].x <= f[i].x && f[j].y <= f[i].y)
79 {
80 dp[i] -= (dp[j] * C(f[i].x - f[j].x + f[i].y - f[j].y, f[i].x - f[j].x));
81 dp[i] = (dp[i] + MOD) % MOD;
82 }
83 ans = ((ans - (dp[i] * C(h - f[i].x + w - f[i].y, h - f[i].x))) % MOD + MOD) % MOD;
84 }
85 printf("%I64d\n", ans);
86 return 0;
87 }