5/5
这场打得真的不太好，可以说是GG了，然而题解还是要补上~~
题A Mike and Cellphone
题意：给你一个数字键盘，然后给你划过的串，然后问你存不存在同样的手势但是不一样的串，也就是这个串表示的手势是否唯一？
题解：这道题其实可以枚举出所有可能的唯一的手势情况，然后直接判断。但是这样很费时间去推导。既然数据量小，那么我们就可以枚举所有的偏移情况，也就是给定一个移动的向量，看模拟移动之后是否存在一个合法的串，如果有就说明不唯一，否则就唯一。显然这个向量（x，y）的x和y是在[-3,3]之间。因此，这道题本质上可以说是模拟题。
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 #define lson l, m, rt*2 6 #define rson m + 1, r, rt*2+1 7 #define xx first 8 #define yy second 9 10 typedef pair<int,int> pii; 11 typedef long long ll; 12 typedef unsigned long long ull; 13 14 int main() { 15 // freopen("case.in", "r", stdin); 16 int n; 17 cin >> n; 18 string s; 19 cin >> s; 20 for (int i = -3; i <= 3; i++) 21 for (int j = -3; j <= 3; j++) if (i != 0 || j != 0) { 22 // cout << i << ' ' << j << endl; 23 bool ok = 1; 24 for (int k = 0; k < n; k++) { 25 int r, c; 26 if (s[k] == '0') r = 3, c = 1; 27 else r = (s[k] - '1') / 3, c = (s[k] - '1') % 3; 28 r += i; 29 c += j; 30 if (!((r == 3 && c == 1) || (r >= 0 && r <= 2 && c >= 0 && c <= 2))) ok = 0; 31 } 32 if (ok) { puts("NO"); return 0; } 33 } 34 puts("YES"); 35 return 0; 36 } 代码君
题B Mike and Shortcuts
题意：给你1~n的门，然后可以花费|di - di+1|到达目的地，然后给你一个捷径，代表这个点可以花费一个能量到达，最后问你1到所有点的最短距离。
题解：这道题很简单，实际上就是一个最短路，每个点有三个门，左边、右边、捷径。然后就是类似spfa的找最短路。
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 const int maxn = 2e5 + 10, inf = 1 << 30; 6 int d[maxn], t[maxn], inq[maxn], n; 7 queue<int> q; 8 9 void go_que(int u, int v) { 10 if (v < 1 || v > n) return; 11 if (d[v] > d[u] + 1) { 12 d[v] = d[u] + 1; 13 if (!inq[v]) { 14 q.push(v); 15 inq[v] = 1; 16 } 17 } 18 } 19 20 int main() { 21 // freopen("case.in", "r", stdin); 22 cin >> n; 23 for (int i = 1; i <= n; i++) { 24 scanf("%d", t + i); 25 d[i] = inf; 26 } 27 q.push(1); 28 inq[1] = 1; 29 d[1] = 0; 30 while (!q.empty()) { 31 int x = q.front(); q.pop(); 32 inq[x] = 0; 33 go_que(x, t[x]); 34 go_que(x, x + 1); 35 go_que(x, x - 1); 36 } 37 for (int i = 1; i <= n; i++) { 38 printf("%d ", d[i]); 39 } 40 puts(""); 41 } 代码君
题C Mike and Chocolate Thieves
题意：给定一个m，然后问你存不存m个满足的只有4个元素的序列，使得每个相邻元素之间的倍数是k（k > 1），如果存在输出最大的数n，否则输出-1?
题解：这个数n越大，显然个数越多，利用单调性，我们二分一个答案n，然后计算n有多少个？怎么计算呢？显然个数有(n / 8) + (n / 27) + (n / 64)……
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 typedef long long ll; 6 const int maxn = 1e5 + 100; 7 8 9 ll get_num(ll x) { 10 ll ret = 0; 11 for (int i = 2; ; i++) { 12 ll tmp = 1ll * i * i * i; 13 if (tmp > x) break; 14 ret += x / tmp; 15 } 16 return ret; 17 } 18 19 int main() { 20 // freopen("case.in", "r", stdin); 21 ll m; 22 cin >> m; 23 ll L = 7, R = 1e16; 24 while (R - L > 1) { 25 ll M = (L + R) / 2; 26 if (get_num(M) >= m) R = M; else L = M; 27 } 28 if (get_num(R) == m) cout << R << endl; 29 else cout << -1 << endl; 30 return 0; 31 } 代码君
题D Friends and Subsequences
题意：给你两个数组a和b，个数均为n个，然后让你数有多少对[l,r]使得a里面元素的最大值和b里面元素的最小值相等。
题解：这里我们观察到这个最大值-最小值是单调的，所以对于下标为i的起点，得到最大值-最小值的结果是：（负数） 0 0 0 （正数），所以我们利用二分搜索可以得到lower_bound和upper_bound，然后这个长度即为以i为起点的区间个数。利用rmq，复杂度可以做到O（nlogn）。
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 #define lson l, m, rt*2 6 #define rson m + 1, r, rt*2+1 7 #define xx first 8 #define yy second 9 10 typedef pair<int,int> pii; 11 typedef long long ll; 12 typedef unsigned long long ull; 13 14 const int maxn = 2e5 + 100, maxm = 30; 15 int v[2][maxn], dp[2][maxn][maxm]; 16 int n; 17 18 void rmq_init() { 19 for (int i = 0; i < 2; i++) 20 for (int j = 0; j < n; j++) { 21 dp[i][j][0] = v[i][j]; 22 } 23 24 for (int j = 1; (1 << j) <= n; j++) { 25 for (int i = 0; i + (1 << j) - 1 < n; i++) { 26 dp[0][i][j] = max(dp[0][i][j - 1], dp[0][i + (1 << (j - 1))][j - 1]); 27 dp[1][i][j] = min(dp[1][i][j - 1], dp[1][i + (1 << (j - 1))][j - 1]); 28 } 29 } 30 } 31 32 int query(int index, int L, int R) { 33 int k = 0; 34 while(1 << (k + 1) <= R - L + 1) k++; 35 if (index == 0) return max(dp[0][L][k], dp[0][R - (1 << k) + 1][k]); 36 else return min(dp[1][L][k], dp[1][R - (1 << k) + 1][k]); 37 } 38 39 int main() { 40 // freopen("case.in", "r", stdin); 41 42 cin >> n; 43 for (int i = 0; i < 2; i++) 44 for (int j = 0; j < n; j++) { 45 scanf("%d", &v[i][j]); 46 } 47 rmq_init(); 48 ll res = 0; 49 for (int i = 0; i < n; i++) { 50 int L = i, R = n - 1; 51 int ansL = -1, ansR = -1; 52 while (L <= R) { 53 int M = (L + R) / 2; 54 int tmp = query(0, i, M) - query(1, i, M); 55 if (tmp >= 0) { 56 ansL = M; R = M - 1; 57 } else L = M + 1; 58 } 59 L = i, R = n - 1; 60 while (L <= R) { 61 int M = (L + R) / 2; 62 int tmp = query(0, i, M) - query(1, i, M); 63 if (tmp <= 0) { 64 ansR = M; L = M + 1; 65 } else R = M - 1; 66 } 67 if (ansL != -1 && ansR != -1) res += (ansR - ansL + 1); 68 } 69 cout << res << endl; 70 71 return 0; 72 } 代码君
题E Mike and Geometry Problem
题意：给你n个区间，任选k个区间，问你这k个区间相交的长度之和是多少？
题解：对于一段区间如果已知有x次相交，如果x >= k说明有C（x，k）个线段可以得到这个相交区间，所以先用map来离散表示区间，然后枚举每个区间，对于相交个数x，如果大于k的话，那么答案贡献就是C（x，k）*（区间的长度），这个做法类似于edu的一个题目，详见CF官方题解。
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 #define lson l, m, rt*2 6 #define rson m + 1, r, rt*2+1 7 #define xx first 8 #define yy second 9 10 typedef pair<int,int> pii; 11 typedef long long ll; 12 typedef unsigned long long ull; 13 14 const int maxn = 2e5 + 100, mod = 1e9 + 7; 15 map<int,int> mp; 16 ll f[maxn], c[maxn]; 17 18 ll quick(ll a, ll b, ll c) { 19 ll ret = 1; 20 while (b) { 21 if (b & 1) ret = ret * a % c; 22 b = b / 2; 23 a = a * a % mod; 24 } 25 return ret; 26 } 27 28 void init() { 29 f[0] = 1; 30 for (int i = 1; i < maxn; i++) f[i] = f[i - 1] * i % mod; 31 for (int i = 0; i < maxn; i++) c[i] = quick(f[i], mod - 2, mod); 32 } 33 34 ll C(int n, int k) { 35 if (n < k) return 0ll; 36 return (f[n] * c[k] % mod) * c[n - k] % mod; 37 } 38 39 int main() { 40 // freopen("case.in", "r", stdin); 41 42 init(); 43 int n, k; 44 cin >> n >> k; 45 for (int i = 0; i < n; i++) { 46 int l, r; 47 scanf("%d%d", &l, &r); 48 mp[l]++; 49 mp[r + 1]--; 50 } 51 ll res = 0; 52 int last = mp.begin() -> first, sum = 0; 53 for (map<int,int>::iterator it = mp.begin(); it != mp.end(); it++) { 54 int x = it->first, y = it->second; 55 // cout << sum << endl; 56 // cout << x << ' ' << last << endl; 57 if (sum >= k) { 58 res += C(sum, k) * (x - last) % mod; 59 res %= mod; 60 } 61 last = x; 62 sum += y; 63 } 64 cout << res << endl; 65 66 return 0; 67 } 代码君
转载于:https://www.cnblogs.com/zhenhao1/p/5671965.html
相关资源：数据结构—成绩单生成器