补题补题......
C 题写挂了好几个次, 最后一题看了好久题解才懂...... 我太迟钝了......
然后因为 longlong 调了半个小时......
A.Equation
题目大意: 有一个数字 n, 让你给出任意两个合数 a,b 满足 a - b = n.
我们知道大于 2 的偶数都是合数, 那么如果 n 为奇数, 只要 n 加上一个奇数合数一定也为合数, 如果 n 为偶数, 那么 n 加上一个偶数合数也一定为合数.
因为只求任意一组, 就直接选择 4,9, 若为奇数输出 9+n 和 9, 偶数输出 4+n 和 4.
代码如下:
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <cstring>
- #include <vector>
- #define rep(x, l, r) for(int x = l; x <= r; x++)
- #define repd(x, r, l) for(int x = r; x>= l; x--)
- #define clr(x, y) memset(x, y, sizeof(x))
- #define all(x) x.begin(), x.end()
- #define pb push_back
- #define mp make_pair
- #define MAXN
- #define fi first
- #define se second
- #define SZ(x) ((int)x.size())
- using namespace std;
- typedef long long ll;
- typedef vector<int> vi;
- typedef pair<int, int> pii;
- const int INF = 1 <<30;
- const int p = 1000000009;
- int lowbit(int x){ return x & (-x);}
- int fast_power(int a, int b){ int x; for(x = 1; b; b>>= 1){ if(b & 1) x = 1ll * x * a % p; a = 1ll * a * a % p;} return x % p;}
- int main(){
- int n;
- scanf("%d", &n);
- if(n % 2) printf("%d %d\n", n + 9, 9);
- else printf("%d %d\n", n + 4, 4);
- return 0;
- }
- View Code
- B.Modulo Equality
题目大意: 有两个长为 n 的数列 a 和 b, 现在让你给 a 中每个数加上一个数 x 并对 m 取模, 并重新排列, 使得两数列相同. 求最小的 x.
很明显 x 一定是在 (a1 - bi + m) mod m 中的一个数, 我们只要枚举这个数, 判断和数列 b 是否相同即可.
n 最大只有 2000, 为了方便(我比较懒), 判断相同时可以直接将 a 重新排序后判断, 不会超时.
代码如下:
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <cstring>
- #include <vector>
- #define rep(x, l, r) for(int x = l; x <= r; x++)
- #define repd(x, r, l) for(int x = r; x>= l; x--)
- #define clr(x, y) memset(x, y, sizeof(x))
- #define all(x) x.begin(), x.end()
- #define pb push_back
- #define mp make_pair
- #define MAXN 2005
- #define fi first
- #define se second
- #define SZ(x) ((int)x.size())
- using namespace std;
- typedef long long ll;
- typedef vector<int> vi;
- typedef pair<int, int> pii;
- const int INF = 1 <<30;
- const int p = 1000000009;
- int lowbit(int x){ return x & (-x);}
- int fast_power(int a, int b){ int x; for(x = 1; b; b>>= 1){ if(b & 1) x = 1ll * x * a % p; a = 1ll * a * a % p;} return x % p;}
- int a[MAXN], b[MAXN], c[MAXN];
- int main(){
- int n, m;
- scanf("%d%d", &n, &m);
- rep(i, 1, n) scanf("%d", &a[i]);
- rep(i, 1, n) scanf("%d", &b[i]);
- sort(a + 1, a + n + 1);
- sort(b + 1, b + n + 1);
- int ans = INF;
- rep(i, 1, n){
- int res = (b[1] - a[i] + m) % m;
- rep(j, 1, n) c[j] = (a[j] + res) % m;
- sort(c + 1, c + n + 1);
- bool flag = 1;
- rep(j, 1, n)
- if(c[j] != b[j]){
- flag = 0;
- break;
- }
- if(flag) ans = min(ans, res);
- }
- printf("%d\n", ans);
- return 0;
- }
- View Code
- C.Long Beautiful Integer
题目大意: 给你一个数字 x, 以及正整数 k, 求一个大于等于 x 的最小数字 y 并满足 yi = yi + k (1 <= i <= n - k) .n 为 x 的长度, n 小于等于 500.
这一题 hack 数据还真多, 197 组......
首先可以发现, 数字 y 的长度一定是等于 x 的长度的, 因为全为 9 的数字一定满足条件.
对于 yi = yi + k 这个式子, 我们发现, 对于所有位置 i 对 k 取模结果相同的, 该位上的数字也一定是相同的.
那我们只要枚举最后前 k 位数字即可, 为了让数字尽量小, 我们让 y 的每一位和 x 一样大, 然后判断此时 y 和 x 的大小.
若 y 大于等于 x, 那么 y 就是答案. 若 y 小于 x, 只需要在第 k 位加上 1 即可.
注意: 需要进位!!!
代码如下:
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <cstring>
- #include <vector>
- #define rep(x, l, r) for(int x = l; x <= r; x++)
- #define repd(x, r, l) for(int x = r; x>= l; x--)
- #define clr(x, y) memset(x, y, sizeof(x))
- #define all(x) x.begin(), x.end()
- #define pb push_back
- #define mp make_pair
- #define MAXN 200005
- #define fi first
- #define se second
- #define SZ(x) ((int)x.size())
- using namespace std;
- typedef long long ll;
- typedef vector<int> vi;
- typedef pair<int, int> pii;
- const int INF = 1 <<30;
- const int p = 1000000009;
- int lowbit(int x){ return x & (-x);}
- int fast_power(int a, int b){ int x; for(x = 1; b; b>>= 1){ if(b & 1) x = 1ll * x * a % p; a = 1ll * a * a % p;} return x % p;}
- int num[MAXN], ans[MAXN];
- char st[MAXN];
- int main(){
- int n, m;
- scanf("%d%d", &n, &m);
- scanf("%s", st);
- int maxx = 0;
- rep(i, 1, n){
- num[i] = st[i - 1] - '0';
- maxx = max(maxx, num[i]);
- }
- int minx = INF, miny = INF;
- rep(i, 1, m){
- ans[i] = num[i];
- for(int j = i ; j <= n; j += m){
- if(ans[i] <num[j]) minx = min(minx, j);
- if(ans[i]> num[j]) miny = min(miny, j);
- }
- }
- if(miny> minx){
- ans[m] = num[m] + 1;
- for(int x = m; x> 0 && ans[x] == 10; x--){
- ans[x] = 0;
- ans[x - 1]++;
- }
- }
- printf("%d\n", n);
- rep(i, 1, n) printf("%d", ans[(i - 1) % m + 1]);
- puts("");
- return 0;
- }
- View Code
- D.Domino for Young
题目大意: 有一个不规则的网格长为 n, 第 i 列有 ai , 现在用 1*2 的骨牌覆盖它, 求最多能放多少个骨牌.
这题是我人生第一道秒掉的 D 题!!!
一看题目, 这不是《组合数学》第一章的例题嘛, 虽然有点差别, 但是思路基本一模一样.
先讲一下组合那道题, 就是说有一个 n*m 的网格(n 和 m 为偶数), 将它的左上角和右下角两个格子去掉, 证明用 1*2 的骨牌覆盖它, 没有一种方法能将它完美覆盖.
这道题目就是 0,1 染色, 对相邻的节点染上不同的颜色, 如图所示.
每一个骨牌只能覆盖一个 0 和一个 1, 而这张图中一共有 12 个 1 和 10 个 0, 不合.
那么回到这一题, 我们也可以将这个网格进行黑白染色, 每一个骨牌也是只能覆盖一个 0 和一个 1, 那么在最优的覆盖方案中, 覆盖完了 0 和 1 中较少的. 答案就是 0 的个数和 1 的个数的最小值.
另外 0,1 个数的详见代码.
代码如下:
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <cstring>
- #include <vector>
- #define rep(x, l, r) for(int x = l; x <= r; x++)
- #define repd(x, r, l) for(int x = r; x>= l; x--)
- #define clr(x, y) memset(x, y, sizeof(x))
- #define all(x) x.begin(), x.end()
- #define pb push_back
- #define mp make_pair
- #define MAXN 200005
- #define fi first
- #define se second
- #define SZ(x) ((int)x.size())
- using namespace std;
- typedef long long ll;
- typedef vector<int> vi;
- typedef pair<int, int> pii;
- const int INF = 1 <<30;
- const int p = 1000000009;
- int lowbit(int x){ return x & (-x);}
- int fast_power(int a, int b){ int x; for(x = 1; b; b>>= 1){ if(b & 1) x = 1ll * x * a % p; a = 1ll * a * a % p;} return x % p;}
- int num[MAXN], ans[MAXN];
- char st[MAXN];
- int main(){
- int n, m;
- scanf("%d%d", &n, &m);
- scanf("%s", st);
- int maxx = 0;
- rep(i, 1, n){
- num[i] = st[i - 1] - '0';
- maxx = max(maxx, num[i]);
- }
- int minx = INF, miny = INF;
- rep(i, 1, m){
- ans[i] = num[i];
- for(int j = i ; j <= n; j += m){
- if(ans[i] <num[j]) minx = min(minx, j);
- if(ans[i]> num[j]) miny = min(miny, j);
- }
- }
- if(miny> minx){
- ans[m] = num[m] + 1;
- for(int x = m; x> 0 && ans[x] == 10; x--){
- ans[x] = 0;
- ans[x - 1]++;
- }
- }
- printf("%d\n", n);
- rep(i, 1, n) printf("%d", ans[(i - 1) % m + 1]);
- puts("");
- return 0;
- }
- View Code
- E.K Integers
题目大意: 有一数列 p, 长度为 n. 求最少的交换两个相邻数字的操作, 使得数列 p 中存在连续子序列 1,2,..., i . 其中 i 为 1,2,..., n .
这题大概一看就和逆序对有关, 因为这个交换相邻操作和冒泡排序一模一样, 而冒泡需要的操作就是逆序对的个数.
不难得出, 当 i = n 时, 答案就是逆序对个数.
对于其它的 i 来说, 我们也可以得到这样一个贪心思想, 先将 1..i 放到一起, 然后再将它们变成有序的.
变成有序的需要的操作很显然也可以按照 i = n 来做, 但是将 1..i 要放到哪里去呢?
根据初中学习的零点分段法, 不知道的可以去看百度百科 (传送门) 了解一下.
最后将它们移到 1..n 在原数列中的中间一个位置(为了方便, 后文用 mid 表示), 一定是最优的, 这可以用二分查找来实现.
至于它们需要移动多少呢? 这要分成左右两段来算.
首先 mid 左边的全部移到中点, 我们假设它们一共有 x 个, 那么它们分别会被移到 mid - x , mid - x + 1 ,..., mid - 1 . 需要移动的操作个数分别要减去它们在数列中的位置, 总答案就是要减去它们的总和 sum , 这可以用线段树或树状数组维护. 得出以下的式子.
ans = mid - x + mid - x + 1 + ... + mid - 1 - sum = mid • x - sum - x • (x + 1) / 2;
注意, 在代码中为了方便 x 包含了在 mid 点上的点, 所以变成了 mid • x - sum - x • (x - 1) / 2 .
另外在右边也是差不多, 得出式子为 ans = sum - mid • x - x • (x + 1) / 2 .
代码中还有以下几个注意点:
1. 其实当 i = n 的时候也是可以用上一个式子算的, 后面两个值都为 0, 你可以手算一下.
2. 需要两个树状数组, 一个维护前缀和(当然也可以用归并排序并加一些记录, 但是比较长), 一个维护上述的 sum .
3. 要开 longlong! 要开 longlong!! 要开 longlong!!! 重要的事情说三遍.
代码如下:
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <cstring>
- #include <vector>
- #define rep(x, l, r) for(int x = l; x <= r; x++)
- #define repd(x, r, l) for(int x = r; x>= l; x--)
- #define clr(x, y) memset(x, y, sizeof(x))
- #define all(x) x.begin(), x.end()
- #define pb push_back
- #define mp make_pair
- #define MAXN 200005
- #define fi first
- #define se second
- #define SZ(x) ((int)x.size())
- using namespace std;
- typedef long long ll;
- typedef vector<int> vi;
- typedef pair<int, int> pii;
- const int INF = 1 <<30;
- const int p = 1000000009;
- int lowbit(int x){ return x & (-x);}
- int fast_power(int a, int b){ int x; for(x = 1; b; b>>= 1){ if(b & 1) x = 1ll * x * a % p; a = 1ll * a * a % p;} return x % p;}
- int n;
- int a[MAXN], pos[MAXN];
- ll tree0[MAXN], tree1[MAXN];
- void update0(int x, int y){
- for(int i = x; i <= n; i += lowbit(i)) tree0[i] += y;
- }
- void update1(int x, int y){
- for(int i = x; i <= n; i += lowbit(i)) tree1[i] += y;
- }
- ll query0(int x){
- ll res = 0;
- for(int i = x; i> 0; i -= lowbit(i)) res += tree0[i];
- return res;
- }
- ll query1(int x){
- ll res = 0;
- for(int i = x; i> 0; i -= lowbit(i)) res += tree1[i];
- return res;
- }
- int main(){
- scanf("%d", &n);
- rep(i, 1, n){
- scanf("%d", &a[i]);
- pos[a[i]] = i;
- }
- ll res0 = 0;
- rep(i, 1, n){
- res0 += i - 1 - query0(pos[i]);
- update0(pos[i], 1);
- update1(pos[i], pos[i]);
- int l = 1, r = n, s;
- while(l <= r){
- int mid = (l + r)>> 1;
- if(query0(mid - 1) * 2 <= i){
- s = mid;
- l = mid + 1;
- }
- else r = mid - 1;
- }
- ll left_sum0 = query0(s), left_sum1 = query1(s);
- ll res1 = left_sum0 * s - left_sum1 - left_sum0 * (left_sum0 - 1) / 2;
- ll right_sum0 = i - left_sum0, right_sum1 = query1(n) - left_sum1;
- res1 += right_sum1 - right_sum0 * s - right_sum0 * (right_sum0 + 1) / 2;
- printf("%lld", res0 + res1);
- }
- puts("");
- return 0;
- }
- View Code
来源: https://www.cnblogs.com/nblyz2003/p/12177652.html