4/4
有空切了一场BC，因为题目比较水，所以就写个题解放上来了，仅是纪念一下。。。。
题A
题意：给你一个矩形，然后一个人在左下角，一个人在右上角，他们按照各自的坐标系走，然后他们都知道在哪个地方汇合，也就是向x走多少，向y走多少，然后给你矩阵的大小，问你能不能够走出迷宫。
题解：理解题意就很水了，发现只有中间的点才可以，所以满足的条件是n和m均为偶数，然后中间的点汇合才行。
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 #define lson l, m, rt << 1 6 #define rson m + 1, r, rt << 1 1 7 #define ll long long 8 9 int main() { 10 // freopen("case.in", "r", stdin); 11 int n, m, x, y; 12 while (scanf("%d%d%d%d", &n, &m, &x, &y) == 4) { 13 if (n % 2 == 0 && m % 2 == 0 && x == n / 2 && y == m / 2) puts("YES"); 14 else puts("NO"); 15 } 16 } 代码君
题B
题意：略
题解：模拟水题
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 const int maxn = 110; 6 int v[maxn]; 7 8 bool cmp(int a, int b) { 9 return a > b; 10 } 11 12 int main() { 13 // freopen("case.in", "r", stdin); 14 int n; 15 while (scanf("%d", &n) == 1) { 16 bool ok = false; 17 int x = 100000000, pos; 18 for (int i = 0; i < n; i++) { 19 scanf("%d", v + i); 20 if (v[i] % 2) { 21 ok = true; 22 if (x > v[i]) x = v[i], pos = i; 23 } 24 } 25 if (!ok) { puts("-1"); continue; } 26 swap(v[pos], v[n - 1]); 27 sort(v, v + n - 1, cmp); 28 if (v[0] == 0) { puts("-1"); continue; } 29 for (int i = 0; i < n - 1; i++) printf("%d", v[i]); 30 printf("%d", v[n - 1]); 31 puts(""); 32 } 33 } 代码君
题C
题意：让你找子串满足其中的每种字符个数不超过k；
题解：依次记录以i为结尾的子串有多少个满足，用l代表能够到达的左边界，这样扫描依次就可以了。
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 #define lson l, m, rt << 1 6 #define rson m + 1, r, rt << 1 1 7 #define ll long long 8 9 const int maxn = 1e5 + 10; 10 int k, cnt[30]; 11 char s[maxn]; 12 13 int main() { 14 // freopen("case.in", "r", stdin); 15 int T; 16 cin >> T; 17 while (T--) { 18 scanf("%s", s); 19 scanf("%d", &k); 20 int n = strlen(s); 21 22 memset(cnt, 0, sizeof cnt); 23 24 ll ans = 0; 25 int l = 0; 26 for (int i = 0; i < n; i++) { 27 int id = s[i] - 'a'; 28 cnt[id]++; 29 while (cnt[id] > k) { 30 cnt[s[l] - 'a']--; 31 l++; 32 } 33 ans += i - l + 1; 34 } 35 36 cout << ans << endl; 37 } 38 } 代码君
题D
题意：给你一串序列，有两种操作：
S x y 表示把v[x] = y
Q l r d p表示d位（从左边开始数）数字为p的个数是多少？
题解：类似华工校赛的题目，用分块的做法，即是把序列分成sqrt(n)块，然后用cnt[i][j][k]表示这个块的信息，表示第i块，j位，为k的个数，然后S操作就O（1）更新，Q操作就块内查询，块两边暴力查询即可。
1 /*zhen hao*/ 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 #define lson l, m, rt << 1 6 #define rson m + 1, r, rt << 1 1 7 #define xx first 8 #define yy second 9 10 const int maxn = 1e5 + 10; 11 int cnt[511][11][11], v[maxn]; 12 13 void depart(int x, int r, int oper) { 14 for (int i = 1; i <= 10; i++) { 15 cnt[r][i][x % 10] += oper; 16 x /= 10; 17 } 18 } 19 20 int main() { 21 // freopen("case.in", "r", stdin); 22 int T; 23 scanf("%d", &T); 24 while (T--) { 25 int n, q; 26 scanf("%d%d", &n, &q); 27 for (int i = 0; i < n; i++) scanf("%d", &v[i]); 28 29 int size = (int)ceil(sqrt(double(n))); 30 memset(cnt, 0, sizeof cnt); 31 for (int i = 0; i < n; i++) { 32 depart(v[i], i / size, 1); 33 } 34 35 char op[5]; 36 for (int i = 0; i < q; i++) { 37 scanf("%s", op); 38 if (op[0] == 'S') { 39 int x, y; 40 scanf("%d%d", &x, &y); --x; 41 depart(v[x], x / size, -1); 42 depart(y, x / size, 1); 43 v[x] = y; 44 } 45 else if (op[0] == 'Q') { 46 int l, r, d, p, res = 0; 47 scanf("%d%d%d%d", &l, &r, &d, &p); 48 --l; --r; 49 int ll = l / size, rr = r / size; 50 for (int j = l; j <= min((ll + 1) * size - 1, r); j++) { 51 int x = v[j]; 52 for (int k = 1; k < d; k++) x /= 10; 53 res += (x % 10 == p); 54 } 55 for (int j = ll + 1; j <= rr - 1; j++) { 56 res += cnt[j][d][p]; 57 } 58 if (ll != rr) { 59 for (int j = rr * size; j <= r; j++) { 60 int x = v[j]; 61 for (int k = 1; k < d; k++) x /= 10; 62 res += (x % 10 == p); 63 } 64 } 65 printf("%d\n", res); 66 } 67 } 68 } 69 } 代码君
转载于:https://www.cnblogs.com/zhenhao1/p/5450173.html
