太菜了,当时只写出来两题,赛后也只复盘了前三题,第四题看情况吧= =,感觉第三题都挺难了
A. Divan and a Store
题目大意:
规定一个购买物品的最小金额,最大金额,还有你自己的余额。给一排不同价格的物品,问在余额内最多可以买多少个物品。
题解:
排序一下,贪心选就行了。
代码:
int main() { int t; cin >> t; while (t--) { int n, l, r, k; n = read(); l = read(); r = read(); k = read(); int ans = 0; for (int i = 0; i < n; i++) { p[i] = read(); } sort(p, p + n); for (int i = 0; i < n; i++) { if (k - p[i] >= 0 && l <= p[i] && p[i] <= r) { k -= p[i]; ans++; } } printf("%d\n", ans); } }
B. Divan and a New Project
题目大意:
给你n个有不同访问次数的点,问怎样安排可以让累加的访问距离最近。打印最小距离和所有点的具体坐标。
题解:
先给所有点按访问次数的大小排序,然后访问次数越高的点离起点越近就好了。我用了个结构体来关联点序号和次数。总的来说还是贪心。
当时打印点坐标的时候没看清是按照输入顺序点的顺序打印,结果卡了一个钟,后面的题也没来得及看。
英语真的很关键,当时发了个问题得到的回复是:
You claimed answer 78, but your construction gives answer 104.
可能也是太紧张了,没理解'claimed'的意思,结果一直坐牢发呆。
代码:
#include <bits/stdc++.h> #define MAXN 200010 #define INF 0x3f using namespace std; typedef pair<int, int> P; struct build { long long id; long long vis; bool operator < (build b) { return vis < b.vis; } } bu[MAXN]; long long line[MAXN]; int main() { // freopen("06.in", "r", stdin); // freopen("06.out", "w", stdout); int t; cin >> t; while (t--) { long long n; scanf("%lld", &n); for (int i = 1; i <= n; i++) { bu[i].id = i; scanf("%lld", &bu[i].vis); } sort(bu + 1, bu + n + 1); long long js = -1; long long os = 1; long long ans = 0; for (int i = n; i > 0; i--) { if (i % 2 == 0) { line[bu[i].id] = js; ans += (2 * -js) * bu[i].vis; js--; } else { line[bu[i].id] = os; ans += (2 * os) * bu[i].vis; os++; } } printf("%lld\n", ans); for (int i = 0; i <= n; i++) { printf("%lld ", line[i]); } if (t != 0) printf("\n"); } // fclose(stdin); // fclose(stdout); return 0; }
C. Divan and bitwise operations
题目大意:
给出序列的总长度和一些数字片段的或运算和,保证序列的每一个数都至少被一个片段所覆盖,要求所有子序列的异或结果相加等于多少
题解:
对我来说有点难理解,所以比赛完还是花了很久去看其他人的题解。
首先要处理的是序列异或和的问题:
我们按二进制的逐个判断(因为所有位运算的结果不会对其他位数造成任何影响),假设序列中有一个数在该位为 1, 那么则有1/2的子序列在该位的异或结果是1。
解释如下: 1 & 1 = 0 1 & 0 = 1, 如果不包括他的子序列运算结果为1,那么加上他就一定会变成0;如果不包括他的子序列运算结果为0,那么加上他就一定会变成1。
所以我们只需要判断所有数在该位上是否有 1 存在,就可以知道将他们全部异或后的结果是多少。这就是他给出的或运算的作用 -> 将所有数字或运算的结果就可以判断哪些位置上存在 1。
接下来就是解决子序列个数的问题:
这里要用到的是C_{n}^{1} +C_{n}^{2} +C_{n}^{3} +...+C_{n}^{n} = 2^n
那么二分之一的子序列个数,则是2^{n-1}
这样一来答案就出来了,即
[(a1|a2|a3|...|ak) * 2^{n-1}] MOD (1e9 + 7)
因为数可能很大顺便写了一个快速幂取余(复习一下)
代码:
#include<bits/stdc++.h> using namespace std; const int MODS = 1e9 + 7; long long ksm(int a, int n) { if(n == 0) return 1; long long ans = a; int t = 1; while (t < n) { if (2 * t <= n) { ans = (ans * ans) % MODS; t *= 2; } else { ans = (ans * a) % MODS; t++; } } return ans; } int main() { int t; cin >> t; while (t--) { int ans = 0; int n, m; cin >> n >> m; for (int i = 0; i < m; i++) { int x; cin >> x >> x >> x; ans |= x; } printf("%lld\n", ans * ksm(2, n - 1) % MODS); } }
D1. Divan and Kostomuksha (easy version)
感谢wljss大佬教会了我这题(✿✿ヽ(°▽°)ノ✿)
大致题意:
给出一个序列,你可以任意重新排序,使得排序后的结果进行下面计算的值最大
\sum_{i=1}^n \operatorname{gcd}(a_1, \, a_2, \, \dots, \, a_i),
输出计算的结果
题解:
很容易想到,第一个要提取的数是最大的数,因为这样才能得到最大的一个gcd值。
然后也很容易想到相同的数一定是放在一起的,因为a_{i}
的范围并不是很大,所以我们直接开数组计数就行了。
对于每一个数 a_{i}
我们均计算它的倍数的个数,相当于一个前缀和。
然后就是本题的关键——DP。
f[i] = max(f[i], f[j] + (js[i] - js[j]) * i)
i是当前处理的数,j是i小于最大值的所有倍数
代码:
#include<iostream> #include<cstring> #include<string> #include<cstdio> #define LL long long using namespace std; int n, maxx; LL ans; const int N = 100010, M = 5000000; int tong[M + 10]; LL f[M + 10], js[M + 10]; int main() { cin >> n; for (int i = 1, x; i <= n; ++i) { scanf("%d", &x); tong[x]++; maxx = max(maxx, x); } for (int i = maxx; i >= 1; --i) { for (int j = i; j <= maxx; j += i) { js[i] += tong[j]; } } for (int i = maxx; i >= 1; --i) { f[i] = (LL)js[i] * i; for (int j = i * 2; j <= maxx; j += i){ f[i] = max(f[i], f[j] + (LL)(js[i] - js[j]) * i); } } for (int i = 1; i <= maxx; ++i){ ans = max(ans, f[i] + (n - js[i])); } cout << ans; return 0; }
小总结
第二题卡太久了,导致最后分数只有800,第七分钟就AC了第一题,结果一直被卡到了将近比赛结束才过了第二题。感觉没有体现出自己真实水平吧...也是自己英文比赛打太少了,多练点应该会有提升吧。
文章有(2)条网友点评
博客做的好好看呀!!
@ tt 我也觉得
23333...