1.结果
赛时做出：AB（D）
赛后做出：CD
评分变化：1535->1500
rank：4521
2.赛后总结
>1 个人评价
这次比赛是我寒假的第一次，昨天坐了一天的动车，虽然平稳，但还是有晕车，导致晚上状态不好，个人因素还是有的。最主要的因素还是后一个小时太晕了，D题有个小问题没发现。
除此之外，近期开始服用的药物让我很晕，这种药还是得继续吃下去，后续还得继续适应这样的情况。
这次的结果并不满足，还得继续。
2> 题目评价
总的来说，这次的题目CD难度不是很大。
C题比赛过程中完全没有思路，一开始想到了gcd，接下来就想到分块处理，不过对于不同因数的分块不能动态做，因此思路终结。同时，对于如何找到m也没有任何思路，于是考试直接放弃。
D题的思路很清楚，而且第一遍写出代码后就通过了样例，不过在后续过程的思考中，对后续过程取模的改动没有让吴想到改进之前取模的过程，因此喜提+2。补题时发现题解思路和我的一模一样，头都大了
补题的时候看了下E，不是很理解，所以停止补题。
3.题目解答
A Satisfying Constraints >link<
题意是求满足条件的个数，有123三种要求，思路是存3，求1的最大值，2的最小值，然后先让ans=Min2 - Max1 + 1，接着判断3中有几个数在范围之内，ans减去这个数字，得出结果。
通过的代码
#include <iostream>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int ma = 0, mi = 1e9;
int n;
int a[101], cnt = 0;
cin >> n;
for (int i = 1; i <= n; i++) {
int x, y;
cin >> x >> y;
if (x == 1)
ma = max(ma, y);
if (x == 2)
mi = min(mi, y);
if (x == 3)
a[++cnt] = y;
}
int ans = mi - ma + 1;
for (int i = 1; i <= cnt; i++)
if (a[i] >= ma && a[i] <= mi)
ans--;
if (ans > 0)
cout << ans << endl;
else
cout << 0 << endl;
}
return 0;
}
B Summation Game >link<
这道题就是求博弈之后的最小值。
先把所有数从大到小排序。
bod的操作及其简单，就是把删除后序列的最大值全部取反
Alice的操作就有点麻烦了，我们就思考删除一个数之后会怎么样。首先，要总和最大，删除的肯定是bob会取反的数。假设删除一个数，bob就会把取反区间的后一个数取反，对结果而言，ans-2*bob选的数+alice删除的数。对Alice而言，删除第一个数是最优解。
所以，我们发现，这个就像滑动区间，假设Bob选取的区间为S，则结果ANS = S后面的总和 - S的总和。加入前缀和优化计算。
点击查看代码
#include <iostream>
#include <algorithm>
using namespace std;
bool cmp(const int a, const int b) {
return a > b;
}
void charge() {
int n, x, k;
cin >> n >> k >> x;
int a[200010] = {0};
long long sum[200010] = {0};
for (int i = 1; i <= n; i++)
cin >> a[i];
sort(a + 1, a + 1 + n, cmp);
for (int i = 1; i <= n; i++)
sum[i] = sum[i - 1] + a[i];
long long ans = -1e18;
for (int i = 0; i <= k; i++) {
if (i + x < n)
ans = max(ans, sum[i] - sum[i + x] * 2 + sum[n]);
else
ans = max(ans, sum[i] - sum[n]);
}
cout << ans << endl;
}
int main() {
int t;
cin >> t;
while (t--) {
charge();
}
return 0;
}
C Partitioning the Array >link< (补)
这个是求不相交子区间是否存在一个模m使得所有子区间取模后的序列一样。
首先，分出子问题：已知A，B，求m，存在 A ≡ B (mod m)。对于这个问题，直接把等式一边移到另一边。可以得出m是|A-B|的因数。
扩大问题，序列相等就说明每一位与其对应的下一段子区间的数取m后相等。因此，想到GCD，求取每一位对应位置的GCD，如果结果相同，ans++。
最后，求n的所有因数。
*注：并不是所有看似ON2的结果都是ON2，思考过程中是否存在舍弃的部分。
点击查看代码
#include <iostream>
using namespace std;
long long gcd(long long x, long long y) {
if (x < y)
return gcd(y, x);
if (y == 0)
return x;
return gcd(y, x % y);
}
void charge() {
int n, a[200010];
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
int ans = 0;
for (int i = 1; i <= n; i++) {
if (n % i == 0) {
int g = 0;
for (int j = 1; j + i <= n; j++) {
g = gcd(g, abs(a[j + i] - a[j]));
}
if (g != 1)
ans++;
}
}
cout << ans << endl;
}
int main() {
int t;
cin >> t;
while (t--) {
charge();
}
return 0;
}
D Array Repetition >http://codeforces.com/contest/1920/problem/D< (补)
给出使用两种方式生成的数组，求第k位的字符。
首先，假设长度为len的数组，求第k位。如果最后一个操作是尾部增加同时k=len，那该问的结果就是末尾增加的字符，若不等，则len--。如果是第二种操作，求取k在未加倍前的位置即可。
该过程可以使用经过堆优化的离线做法，优化结果。
就是这个取模，害的我+2
点击查看代码
#include <iostream>
#include <queue>
#define MAX 1e18
using namespace std;
struct node {
long long num;
int iter;
bool operator>(const node a) const {
return num < a.num;
}
bool operator<(const node a) const {
return num > a.num;
}
};
priority_queue<node, vector<node>, greater<node>> que;
int x[200010];
int y[200010];
void charge() {
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++)
cin >> x[i] >> y[i];
long long k, MAXk = 0;
for (int i = 1; i <= q; i++) {
cin >> k;
MAXk = max(MAXk, k);
node p;
p.iter = i;
p.num = k;
que.push(p);
}
long long len = 0, cnt = n;
for (int i = 1; i <= n; i++) {
if (x[i] == 1) {
if (len == MAXk) {
cnt = i - 1;
break;
}
len++;
} else {
if (MAXk / len < y[i] + 1) {
cnt = i - 1;
break;
}
len *= y[i] + 1;
}
}
while (que.top().num > len) {
node p = que.top();
que.pop();
p.num = (p.num - 1) % len + 1;
que.push(p);
}
int ans[200010];
for (int i = cnt; i >= 1; i--) {
if (x[i] == 1) {
while (!que.empty()) {
if (que.top().num < len)
break;
node p = que.top();
que.pop();
ans[p.iter] = y[i];
}
if(que.empty())
break;
len--;
} else {
len /= y[i] + 1;
while (que.top().num > len) {
node p = que.top();
que.pop();
p.num = (p.num - 1) % len + 1;
que.push(p);
}
}
}
for (int i = 1; i <= q; i++)
cout << ans[i] << " ";
cout << endl;
}
int main() {
int t;
cin >> t;
while (t--) {
charge();
}
return 0;
}