太菜了,当时只写出来两题,赛后也只复盘了前三题,第四题看情况吧= =,感觉第三题都挺难了
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了第一题,结果一直被卡到了将近比赛结束才过了第二题。感觉没有体现出自己真实水平吧...也是自己英文比赛打太少了,多练点应该会有提升吧。
叨叨几句... NOTHING