Codeforces Round #361 div2
Codeforces Round #361 div2
熙世
发布于 2019-07-14 13:47:39
发布于 2019-07-14 13:47:39
ProblemA(Codeforces Round 689A):
题意：
给一个手势， 问这个手势是否是唯一。
思路：
暴力， 模拟将这个手势上下左右移动一次看是否还在键盘上即可。
代码：
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 <stack>
10 #include <queue>
11 #include <string>
12 #include <vector>
13 #include <fstream>
14 #include <iterator>
15 #include <iostream>
16 #include <algorithm>
17 using namespace std;
18 #define LL long long
19 #define INF 0x3f3f3f3f
20 #define MOD 1000000007
21 #define eps 1e-6
22 #define MAXN 10
23 #define MAXM 100
24 #define dd {cout<<"debug"<<endl;}
25 #define pa {system("pause");}
26 #define p(x) {printf("%d\n", x);}
27 #define pd(x) {printf("%.7lf\n", x);}
28 #define k(x) {printf("Case %d: ", ++x);}
29 #define s(x) {scanf("%d", &x);}
30 #define sd(x) {scanf("%lf", &x);}
31 #define mes(x, d) {memset(x, d, sizeof(x));}
32 #define do(i, x) for(i = 0; i < x; i ++)
33 #define dod(i, x, l) for(i = x; i >= l; i --)
34 #define doe(i, x) for(i = 1; i <= x; i ++)
35 int n;
36 int row[MAXN] = {4, 1, 1, 1, 2, 2, 2, 3, 3, 3};
37 int col[MAXN] = {2, 1, 2, 3, 1, 2, 3, 1, 2, 3};
38 int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
39 char str[MAXN];
40
41 bool move_one_step(int d)
42 {
43 for(int i = 0; i < n; i ++)
44 {
45 int x = str[i] - '0';
46 if((d == 2 || d == 3) && x == 0) return false;
47 if(row[x] + dir[d][0] < 1 || col[x] + dir[d][1] < 1 || col[x] + dir[d][1] > 3)
48 return false;
49 if(x != 8 && (row[x] + dir[d][0] > 3))
50 return false;
51 }
52 return true;
53 }
54
55 void get_ans()
56 {
57 bool flag = false;
58 for(int d = 0; d < 4; d ++)
59 {
60 if(move_one_step(d)) flag = true;
61 }
62 printf(flag ? "NO\n" : "YES\n");
63 }
64
65 int main()
66 {
67 scanf("%d", &n);
68 scanf("%s", str);
69
70 get_ans();
71 return 0;
72 }Problem_B(Codeforces Round 689B):
题意：
有n个城市， 第i个城市到第j个城市需要消耗abs(i - j)的能量， 然后每个城市可以转移到另一个城市， 只需要一个能量， 转移是单向的。
问从第一个城市到各个城市所需要的最少能量。
思路：
每次只有三个选择， 即（1、向左走一步， 2、向右走一步， 3、移动到另一个城市）。
以第一个城市为起点， bfs一遍， 即可得到从第一个城市到所有城市所需要的最少能量。
代码：
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 <stack>
10 #include <queue>
11 #include <string>
12 #include <vector>
13 #include <fstream>
14 #include <iterator>
15 #include <iostream>
16 #include <algorithm>
17 using namespace std;
18 #define LL long long
19 #define INF 0x3f3f3f3f
20 #define MOD 1000000007
21 #define eps 1e-6
22 #define MAXN 200010
23 #define MAXM 100
24 #define dd {cout<<"debug"<<endl;}
25 #define pa {system("pause");}
26 #define p(x) {printf("%d\n", x);}
27 #define pd(x) {printf("%.7lf\n", x);}
28 #define k(x) {printf("Case %d: ", ++x);}
29 #define s(x) {scanf("%d", &x);}
30 #define sd(x) {scanf("%lf", &x);}
31 #define mes(x, d) {memset(x, d, sizeof(x));}
32 #define do(i, x) for(i = 0; i < x; i ++)
33 #define dod(i, x, l) for(i = x; i >= l; i --)
34 #define doe(i, x) for(i = 1; i <= x; i ++)
35 int n;
36 int a[MAXN];
37 int step[MAXN];
38 bool vis[MAXN];
39
40 void update(int pos)
41 {
42 for(int i = pos + 1; i <= n; i ++)
43 step[i] = min(step[i], step[pos] + (i - pos));
44 for(int i = 1; i < pos; i ++)
45 step[i] = min(step[i], step[pos] + pos - i);
46 }
47
48 void show()
49 {
50 for (int i = 1; i <= n; i ++)
51 printf("%d ", step[i]);
52 printf("\n");
53 }
54
55 void bfs()
56 {
57 queue <int> Q;
58 Q.push(1);
59 step[1] = 0;
60 while (!Q.empty())
61 {
62 int cnt = Q.front();
63 Q.pop();
64
65 if(vis[cnt]) continue;
66
67 vis[cnt] = true;
68
69 //left
70 if(step[cnt - 1] > step[cnt] + 1 && cnt - 1 > 0)
71 {
72 step[cnt - 1] = step[cnt] + 1;
73 if(!vis[cnt - 1])
74 Q.push(cnt - 1);
75 }
76
77 //right
78 if(step[cnt + 1] > step[cnt] + 1 && cnt + 1 <= n)
79 {
80 step[cnt + 1] = step[cnt] + 1;
81 if(!vis[cnt + 1])
82 Q.push(cnt + 1);
83 }
84
85 //move
86 if(a[cnt] != cnt)
87 {
88 if(step[a[cnt]] > step[cnt] + 1)
89 {
90 step[a[cnt]] = step[cnt] + 1;
91 if(!vis[a[cnt]])
92 Q.push(a[cnt]);
93 }
94 }
95 }
96 }
97
98 int main()
99 {
100 scanf("%d", &n);
101 mes(vis, false);
102 mes(step, 0x3f);
103 for (int i = 1; i <= n; i ++)
104 {
105 scanf("%d", &a[i]);
106 // step[i] = i - 1;
107 }
108
109 bfs();
110 show();
111 return 0;
112 }Problen_C(Codeforces Round 689C):
题意：
有四个小偷， 假设第一个小偷偷了a块巧克力， 那么第二个小偷则偷了a*k块， 第三个a*k*k块，第四个a*k*k*k个。
然而所有小偷的背包都有一个容量n， 现在给你一个m， 表示小偷们恰好有m种可能偷法。
求满足上述条件的n， n为恰好满足上述条件的最大的背包容量n， 要使得n尽可能的小。
思路：
最值最大/小化， 典型的二分。
由于a, k, n 都是未知的， 先来看一下它们的关系：
第四个小偷偷到a*k^3块巧克力， 是四个小偷里偷到的最多的。
假设现在已知n， 那么如果n/(x^3) > 0, 说明这个x是一个满足条件的k。
然后再看a, a = n / (x^3), 那么从1 ~ a 条件n/(x^3)都是成立的。
所以， 当k = x时， 有n/(x^3)种方案。
那么， 可以知道， 如果n已知， 则可以求出其方案数。
这里就可以二分n， 找到一个满足的n， 然后在这个范围内去找到最小的n.
代码：
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 <stack>
10 #include <queue>
11 #include <string>
12 #include <vector>
13 #include <fstream>
14 #include <iterator>
15 #include <iostream>
16 #include <algorithm>
17 using namespace std;
18 #define LL long long
19 #define INF 0x7ffffffffffffff
20 #define MOD 1000000007
21 #define eps 1e-6
22 #define MAXN 1000010
23 #define MAXM 100
24 #define dd {cout<<"debug"<<endl;}
25 #define pa {system("pause");}
26 #define p(x) {printf("%d\n", x);}
27 #define pd(x) {printf("%.7lf\n", x);}
28 #define k(x) {printf("Case %d: ", ++x);}
29 #define s(x) {scanf("%d", &x);}
30 #define sd(x) {scanf("%lf", &x);}
31 #define mes(x, d) {memset(x, d, sizeof(x));}
32 #define do(i, x) for(i = 0; i < x; i ++)
33 #define dod(i, x, l) for(i = x; i >= l; i --)
34 #define doe(i, x) for(i = 1; i <= x; i ++)
35 LL m;
36
37 LL check(LL n)
38 {
39 LL sum = 0;
40 for (LL i = 2; ; i ++)
41 {
42 if (n < i * i * i) return sum;
43
44 sum = sum + n / (i * i * i);
45 }
46 return sum;
47 }
48
49 LL get_ans(LL &mid)
50 {
51 LL l = 1, r = INF;
52 LL num = 0;
53
54 while (l < r)
55 {
56 mid = (l + r + 1) / 2;
57 num = check(mid);
58 if (num == m) return num;
59 if (num > m) r = mid - 1;
60 else l = mid + 1;
61 }
62 return num == m ? num : -1;
63 }
64
65 int main()
66 {
67 scanf("%lld", &m);
68 LL n = 0, mid;
69 LL m1 = get_ans(mid);
70 if(m1 != m) printf("-1\n");
71 else
72 {
73 for(LL i = 2; ; i ++)
74 {
75 if(i * i * i > mid) break;
76 n = max(n, mid / (i * i * i) * (i * i * i));
77 }
78 printf("%lld\n", n);
79 }
80 return 0;
81 }Problem_D(CodeForces 689D):
题意：
有两个长度为n的数列a, b。
找出下列子序列的个数：
在[l, r]这个区间内， a数列的最大值 == b数列的最小值。
思路：
求最大最小值， 可以用RMQ, 线段树。
又不涉及修改， 可以使用RMQ, 查询为O(1)， 预处理复杂度为O(nlogn)
先将a, b 数列进行处理。
然后， 枚举左端点， 然后再找到满足条件的 右端点的范围， 计算求和即可。
代码：
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 <stack>
10 #include <queue>
11 #include <string>
12 #include <vector>
13 #include <fstream>
14 #include <iterator>
15 #include <iostream>
16 #include <algorithm>
17 using namespace std;
18 #define LL long long
19 #define INF 0x3f3f3f3f
20 #define MOD 1000000007
21 #define eps 1e-6
22 #define MAXN 200010
23 #define MAXM 21
24 #define dd {cout<<"debug"<<endl;}
25 #define pa {system("pause");}
26 #define p(x) {printf("%d\n", x);}
27 #define pd(x) {printf("%.7lf\n", x);}
28 #define k(x) {printf("Case %d: ", ++x);}
29 #define s(x) {scanf("%d", &x);}
30 #define sd(x) {scanf("%lf", &x);}
31 #define mes(x, d) {memset(x, d, sizeof(x));}
32 #define do(i, x) for(i = 0; i < x; i ++)
33 #define dod(i, x, l) for(i = x; i >= l; i --)
34 #define doe(i, x) for(i = 1; i <= x; i ++)
35 int n;
36 int a[MAXN], b[MAXN];
37 int mx_a[MAXN][MAXM], mi_b[MAXN][MAXM];
38 int p[MAXM], flog[MAXN];
39
40 void init()
41 {
42 p[0] = 1, flog[0] = -1;
43 for(int i = 1; i < MAXM; i ++) p[i] = 2 * p[i - 1];
44 for(int i = 1; i <= n; i ++) flog[i] = (i & (i - 1)) ? flog[i - 1] : (flog[i - 1] + 1);
45
46 for(int i = 1; i <= n; i ++) mx_a[i][0] = a[i];
47 for(int j = 1; j < MAXM; j ++)
48 for(int i = 1; i <= n; i ++)
49 if(i + p[j] - 1 <= n)
50 mx_a[i][j] = max(mx_a[i][j - 1], mx_a[i + p[j - 1]][j - 1]);
51
52 for(int i = 1; i <= n; i ++) mi_b[i][0] = b[i];
53 for(int j = 1; j < MAXM; j ++)
54 for(int i = 1; i <= n; i ++)
55 if(i + p[j] - 1<= n)
56 mi_b[i][j] = min(mi_b[i][j - 1], mi_b[i + p[j - 1]][j - 1]);
57 }
58
59 int get_mx_a(int l, int r)
60 {
61 int k = flog[r - l + 1];
62 return max(mx_a[l][k], mx_a[r - p[k] + 1][k]);
63 }
64
65 int get_mi_b(int l, int r)
66 {
67 int k = flog[r - l + 1];
68 return min(mi_b[l][k], mi_b[r - p[k] + 1][k]);
69 }
70
71 int min_l(int pos)
72 {
73 int l, r, mid;
74 l = pos - 1, r = n + 1;
75 while(r - l > 1)
76 {
77 mid = (l + r) >> 1;
78 if(get_mx_a(pos, mid) >= get_mi_b(pos, mid)) r = mid;
79 else l = mid;
80 }
81 return r;
82 }
83
84 int max_r(int pos)
85 {
86 int l, r, mid;
87 l = pos - 1, r = n + 1;
88 while(r - l > 1)
89 {
90 mid = (l + r) >> 1;
91 if(get_mx_a(pos, mid) > get_mi_b(pos, mid)) r = mid;
92 else l = mid;
93 }
94 return r;
95 }
96
97 int main()
98 {
99 scanf("%d", &n);
100 for(int i = 1; i <= n; i ++)
101 scanf("%d", &a[i]);
102 for(int i = 1; i <= n; i ++)
103 scanf("%d", &b[i]);
104
105 init();
106
107 LL ans = 0;
108 for(int i = 1; i <= n; i ++)
109 {
110 int l = min_l(i);
111 int r = max_r(i);
112 ans = ans + (r - l);
113 }
114 printf("%I64d\n", ans);
115 return 0;
116 }Problem_E(CodeForces 689E):
题意：
f([l, r])表示区间[l, r]内元素个数：r - l + 1
现在给n个区间， 求这n个区间任选k个， 将其求交集运算后的f值。
求出所有情况的f值之和。
思路：
先考虑每个点， 假设已知这个点被x个区间覆盖， 那么， 这个点被计算的次数就是C(x, k)次。
求出所有点的情况即可。 再拓展一下， 如果连续y个点的覆盖数是一样的， 那么就可以得出这y个点被计算的总次数是 y * C(x, k)
利用求前缀和的思路来处理这个点， 左右端点+-1.
这里左端点-1 其实是将整个区间往前移动了一下， 相当于是从0开始。
代码：
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 <stack>
10 #include <queue>
11 #include <string>
12 #include <vector>
13 #include <fstream>
14 #include <iterator>
15 #include <iostream>
16 #include <algorithm>
17 using namespace std;
18 #define LL long long
19 #define INF 0x3f3f3f3f
20 #define MOD 1000000007
21 #define eps 1e-6
22 #define MAXN 200010
23 #define MAXM 100
24 #define dd {cout<<"debug"<<endl;}
25 #define pa {system("pause");}
26 #define p(x) {printf("%d\n", x);}
27 #define pd(x) {printf("%.7lf\n", x);}
28 #define k(x) {printf("Case %d: ", ++x);}
29 #define s(x) {scanf("%d", &x);}
30 #define sd(x) {scanf("%lf", &x);}
31 #define mes(x, d) {memset(x, d, sizeof(x));}
32 #define do(i, x) for(i = 0; i < x; i ++)
33 #define dod(i, x, l) for(i = x; i >= l; i --)
34 #define doe(i, x) for(i = 1; i <= x; i ++)
35 LL n, k;
36 LL f[MAXN];
37 LL fac[MAXN], fack[MAXN];
38 map <LL, LL> mp;
39 vector <LL> v;
40
41 LL qpow(LL x, LL k)
42 {
43 LL res = 1;
44 while(k)
45 {
46 if(k & 1) res = res * x % MOD;
47 x = x * x % MOD;
48 k >>= 1;
49 }
50 return res;
51 }
52
53 LL inv(LL a, LL x)
54 {
55 return qpow(a, x - 2);
56 }
57
58 LL C(LL n, LL m)
59 {
60 if(n < m || m < 0) return 0;
61 return ((fac[n] * fack[n - m] % MOD) * fack[m]) % MOD;
62 }
63
64 void init()
65 {
66 fac[0] = fack[0] = 1;
67 for(int i = 1; i < MAXN; i ++)
68 {
69 fac[i] = (fac[i - 1] * i) % MOD;
70 fack[i] = inv(fac[i], MOD);
71 }
72 mp.clear();
73 v.clear();
74 }
75
76 int main()
77 {
78 init();
79 LL l, r;
80 scanf("%lld %lld", &n, &k);
81 for(int i = 1; i <= n; i ++)
82 {
83 scanf("%lld %lld", &l, &r);
84 mp[l - 1] ++;
85 v.push_back(l - 1);
86
87 mp[r] --;
88 v.push_back(r);
89 }
90
91 sort(v.begin(), v.end());
92
93 LL ans = 0, num = 0, pre_pos = - 1e9 - 10, cnt_pos, len;
94 int vlen = v.size();
95 for(int i = 0; i < vlen; i ++)
96 {
97 cnt_pos = v[i];
98 len = cnt_pos - pre_pos;
99 if(num >= k)
100 ans = (ans + len * C(num, k) % MOD) % MOD;
101 if(pre_pos != cnt_pos)
102 {
103 pre_pos = cnt_pos;
104 num = num + mp[cnt_pos];
105 }
106 }
107 printf("%lld\n", ans);
108 return 0;
109 }本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2016-07-13 ，如有侵权请联系 cloudcommunity@tencent.com 删除
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号