A - A + B = C
首先去除 a,b,c 的后导零并记录个数，最后在答案中算上即可，所以下面讨论的均为 a,b,c 个位不为0的情况。显然 x,y,z 均不为0的解一定可以转化为其中至少有一个为0的解，所以我们只讨论 x,y,z 中至少有一个为0的情况。当 x=y=z=0 时，只需判断 a+b=c 是否成立即可；当只有 x=y=0 时，只需解方程 a+b=c\cdot 10^z，求出 a+b 并去除其后导零并判断是否与 c 相等即可，对于 x=z=0,y=z=0 的情况同理可得；当只有 x=0 时，显然 a+b\cdot 10^y=c\cdot 10^z 无解，对于 y=0,z=0 的情况同样无解，至此讨论完毕，用大整数实现即可。
B - Bracket Sequences on Tree
咕
C - Cuber Occurrence
咕
D - Data Structure Problem
有结论：点积为最值的点对一定在凸包上，通过移动两端点的方法即可证明。由于数据随机，凸包的期望大小为 \log n。当加入点时，如果落在了凸包上则加入并重新计算凸包，则期望总重构次数为 \log n，该操作期望总复杂度 O(n\log n+\log^2 n\cdot \log\log n)。当删除点时，由于要删除的是当前剩下的第 r 个点，用pbds中的平衡树维护即可，如果删除的点是凸包上的点，则暴力重构凸包，该操作总复杂度 O(n\log n+\log^2 n)。查找点积最小值点对时，在凸包上暴力枚举即可，该操作总复杂度 O(n\log^2 n)。
E - Equation
咕
F - Halt Hater
由于向右转代价为0，所以如果当前处在某一条边上，则相当于你已经占据了不断向右转所围成的这个格子。所以将每一个格子视为一个点，从一个格子到一个边相连的格子，代价为一次直走的代价 b；从一个格子到一个点相连的格子，代价为一次左转的代价 a。若要从格子 (x_0,y_0) 到格子 (x_t,y_t)，则有三种情况：两次直走、先直着走再斜着走、斜着走两次；分类讨论即可。答案即为从初始格子走到终点相邻的四个格子中答案的最小值。
G - Intersection of Prisms
咕
H - Just Repeat
对于颜色为 c 的牌，若Cuber QQ有 x_c 张，Quber CC有 y_c 张。如果 y_c=0，则这 x_c 张牌一定是Cuber QQ留在最后出的，对于 x_c=0 的情况同理。对于每一方来说，都想让自己得分与对手得分的差值最大化，当 x_c\neq 0,y_c\neq 0 时，如果一方出了这张颜色为 c 的牌，相当于让差值增加了 x_c+y_c。所以将这些颜色按照 x_c+y_c 降序排序，然后双方轮流出 x_c+y_c 最大的颜色即可。
I - Kejin Player
设 f[i] 表示从第 i 级升到第 i+1 级的期望花费，则有等式 f[i]=a_i+(1-p_i)\sum_{k=x_i}^{i}f[k]，移项可得 f[i]=\frac{a_i+(1-p_i)\sum_{k=x_i}^{i-1}f[k]}{p_i}，递推求解即可。对于询问 l,r，答案即为 \sum_{k=l}^{r-1}f[k]。
J - Final Exam
对于最坏的情况，如果出题老师想要卡掉他，一定是挑他复习时间最少的 n-k+1 道题，将其全部卡掉。所以只需要在最小的 n-k+1 道题中过其中一道题，即可满足在最坏情况下也能答对至少 k 题。对于最小的 n-k+1 道题，如果它们的复习总时长 t\le m，则老师总有办法能卡掉所有题；而当 t=m+1 时，一定至少能过其中一道题。此外要让所有题的复习总时长最小，即要在 t=m+1 的情况下让第 n-k+1 小的题目复习时长最小，即为 \left\lceil\frac{m+1}{n-k+1}\right\rceil，所以最终答案为 \left\lceil\frac{m+1}{n-k+1}\right\rceil\cdot(k-1)+m-1。
Code
A - A + B = C
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define MAX_L 100005
using namespace std;
struct Bign {
int len, sgn, w[MAX_L];
void clear() {
len = sgn = 1;
memset(w, 0, sizeof(w));
}
Bign operator=(int x) {
clear();
if (x != 0) {
if (x < 0) {
sgn = -1, x = -x;
}
len = 0;
while (x) {
w[len++] = x % 10;
x /= 10;
}
}
return *this;
}
Bign operator=(string s) {
clear();
reverse(s.begin(), s.end());
if (s.back() == '-') {
sgn = -1, s.pop_back();
}
for (int i = 0; i < s.size(); i++) {
w[i] = s[i] - '0';
}
len = s.size();
return *this;
}
Bign() {
clear();
}
Bign(int x) {
*this = x;
}
friend istream& operator>>(istream& in, Bign& a) {
string s;
in >> s;
a = s;
return in;
}
friend ostream& operator<<(ostream& out, const Bign& a) {
if (a.sgn < 0) {
out << "-";
}
for (int i = a.len - 1; i >= 0; i--) {
out << a.w[i];
}
return out;
}
friend int cmp(const Bign& a, const Bign& b) {
if (a.sgn != b.sgn) {
return a.sgn > b.sgn ? 1 : -1;
}
int res = a.sgn;
if (a.len != b.len) {
return a.len > b.len ? res : -res;
}
for (int i = a.len - 1; i >= 0; i--) {
if (a.w[i] != b.w[i]) {
return a.w[i] > b.w[i] ? res : -res;
}
}
return 0;
}
friend bool eq(const Bign& a, const Bign& b) {
return cmp(a, b) == 0;
}
friend Bign add(const Bign& a, const Bign& b) {
Bign c;
c.len = max(a.len, b.len);
for (int i = 0; i < c.len; i++) {
if (i < a.len) {
c.w[i] += a.w[i];
}
if (i < b.len) {
c.w[i] += b.w[i];
}
c.w[i + 1] += c.w[i] / 10;
c.w[i] %= 10;
}
if (c.w[c.len] > 0) {
c.len++;
}
return c;
}
friend Bign sub(Bign a, Bign b) {
Bign c;
if (a < b) {
swap(a, b), c.sgn = -1;
}
c.len = a.len;
for (int i = 0; i < c.len; i++) {
c.w[i] += a.w[i];
if (i < b.len) {
c.w[i] -= b.w[i];
}
if (c.w[i] < 0) {
c.w[i] += 10, c.w[i + 1]--;
}
}
while (c.w[c.len - 1] == 0) {
c.len--;
}
return c;
}
friend Bign operator+(const Bign& a, const Bign& b) {
return add(a, b);
}
friend Bign operator-(const Bign& a, const Bign& b) {
return sub(a, b);
}
friend bool operator<(const Bign& a, const Bign& b) {
return cmp(a, b) < 0;
}
friend bool operator>(const Bign& a, const Bign& b) {
return cmp(a, b) > 0;
}
friend bool operator==(const Bign& a, const Bign& b) {
return eq(a, b);
}
int remove() {
int cnt = 0;
while (cnt < len && w[cnt] == 0) {
cnt++;
}
for (int i = cnt, j = 0; i < len; i++, j++) {
w[j] = w[i];
}
for (int i = 0, j = len - 1; i < cnt; i++, j--) {
w[j] = 0;
}
len -= cnt;
return cnt;
}
};
int T;
Bign a, b, c;
void print(int x, int y, int z) {
int mn = min(x, min(y, z));
int d = max(0, -mn);
cout << x + d << " " << y + d << " " << z + d << endl;
}
int main() {
ios::sync_with_stdio(false);
cin >> T;
while (T--) {
cin >> a >> b >> c;
int ta = a.remove();
int tb = b.remove();
int tc = c.remove();
if (a + b == c) {
print(-ta, -tb, -tc);
continue;
}
Bign t = c - b;
if (t > 0) {
int cnt = t.remove();
if (t == a) {
print(cnt - ta, -tb, -tc);
continue;
}
}
t = c - a;
if (t > 0) {
int cnt = t.remove();
if (t == b) {
print(-ta, cnt - tb, -tc);
continue;
}
}
t = a + b;
if (t > 0) {
int cnt = t.remove();
if (t == c) {
print(-ta, -tb, cnt - tc);
continue;
}
}
cout << -1 << endl;
}
}
B - Bracket Sequences on Tree
C - Cuber Occurrence
D - Data Structure Problem
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <set>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define MAX_N 100005
#define EPS 1e-8
#define eq(x, y) (fabs((x) - (y)) < EPS)
using namespace std;
const unsigned mul = 20190812;
class Magic {
public:
Magic(unsigned state) : state(state), ans(0) {}
unsigned long long retrieve() {
unsigned modulo = 0x7fffffff;
state = ((unsigned long long)state * mul + ans) % modulo;
unsigned high = state;
state = ((unsigned long long)state * mul + ans) % modulo;
return high * modulo + state;
}
int retrieve(int a, int b) {
assert(a <= b);
return (int)(retrieve() % (b - a + 1)) + a;
}
void submit(unsigned k) {
ans = ans * mul + k;
}
unsigned retrieveAns() {
return ans;
}
private:
unsigned state, ans;
};
#define int long long
struct Point {
int x, y;
Point() {}
Point(int _x, int _y) : x(_x), y(_y) {}
friend Point operator+(const Point &a, const Point &b) {
return Point(a.x + b.x, a.y + b.y);
}
friend Point operator-(const Point &a, const Point &b) {
return Point(a.x - b.x, a.y - b.y);
}
friend bool operator<(const Point &a, const Point &b) {
return a.x != b.x ? a.x < b.x : a.y < b.y;
}
friend int sqr(const Point &p) {
return p.x * p.x + p.y * p.y;
}
friend int dot(const Point &a, const Point &b) {
return a.x * b.x + a.y * b.y;
}
friend int cross(const Point &a, const Point &b) {
return a.x * b.y - b.x * a.y;
}
};
using namespace __gnu_pbds;
#define pii pair<int, int>
#define pip pair<int, Point>
#define ti tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define tp tree<Point, null_type, less<Point>, rb_tree_tag, tree_order_statistics_node_update>
#define tpip tree<pip, null_type, less<pip>, rb_tree_tag, tree_order_statistics_node_update>
namespace Graham {
pip p[MAX_N];
pip con[MAX_N];
bool cmp(const pip &a, const pip &b) {
int c = cross(a.second - p[1].second, b.second - p[1].second);
return c ? c > 0 : sqr(a.second - p[1].second) < sqr(b.second - p[1].second);
}
void graham(vector<pip> &vc) {
if (vc.size() <= 2) {
return;
}
int n = 0;
for (int i = 0; i < vc.size(); i++) {
p[++n] = vc[i];
}
for (int i = 2; i <= n; i++) {
if (p[i].second < p[1].second) {
swap(p[i], p[1]);
}
}
sort(p + 2, p + 1 + n, cmp);
int tot = 0;
con[++tot] = p[1], con[++tot] = p[2];
for (int i = 3; i <= n; i++) {
while (tot >= 2 && cross(con[tot].second - con[tot - 1].second, p[i].second - con[tot].second) <= 0) {
tot--;
}
con[++tot] = p[i];
}
vc.clear();
for (int i = 1; i <= tot; i++) {
vc.push_back(con[i]);
}
}
} // namespace Graham
class DataStructure {
public:
int sz, cnt;
tpip tr;
vector<pip> vc;
DataStructure() {
sz = cnt = 0;
}
void add(int x, int y) {
sz++, cnt++;
tr.insert(pip(cnt, Point(x, y)));
vc.push_back(pip(cnt, Point(x, y)));
Graham::graham(vc);
}
void erase(int r) {
sz--;
pip res = *tr.find_by_order(r - 1);
tr.erase(res);
for (int i = 0; i < vc.size(); i++) {
if (vc[i].first == res.first) {
vc.clear();
for (auto tt = tr.begin(); tt != tr.end(); tt++) {
vc.push_back(*tt);
}
Graham::graham(vc);
return;
}
}
}
int size() {
return sz;
}
pii query() {
if (sz == 0) {
return pii(0, 0);
}
int dt = dot(vc[0].second, vc[0].second);
pii res(vc[0].first, vc[0].first);
for (int i = 0; i < vc.size(); i++) {
for (int j = 0; j < vc.size(); j++) {
if (vc[i].first <= vc[j].first) {
int ndt = dot(vc[i].second, vc[j].second);
if (ndt < dt) {
dt = ndt, res = pii(vc[i].first, vc[j].first);
} else if (ndt == dt) {
res = min(res, pii(vc[i].first, vc[j].first));
}
}
}
}
return res;
}
};
signed main() {
ios::sync_with_stdio(false);
const int lim = 1e9;
int q;
cin >> q;
for (int k = 0; k < q; k++) {
unsigned state;
cin >> state;
string s;
cin >> s;
DataStructure ds;
Magic magic(state);
for (char c : s) {
if (c == 'a') {
int x = magic.retrieve(-lim, lim);
int y = magic.retrieve(-lim, lim);
ds.add(x, y);
} else if (c == 'e') {
unsigned pos = magic.retrieve(1, ds.size());
ds.erase(pos);
} else if (c == 'q') {
auto best = ds.query();
magic.submit(best.first);
magic.submit(best.second);
}
}
cout << magic.retrieveAns() << endl;
}
}
E - Equation
F - Halt Hater
#include <iostream>
#include <stdio.h>
#include <string.h>
#define int long long
using namespace std;
int T, a, b, x, y;
int solve(int x, int y) {
x = abs(x), y = abs(y);
int ans = (x + y) * b;
int mn = min(x, y), mx = max(x, y);
ans = min(ans, (mx - mn) * b + mn * a);
if ((x + y) & 1) {
ans = min(ans, (mx - 1) * a + b);
} else {
ans = min(ans, mx * a);
}
return ans;
}
signed main() {
ios::sync_with_stdio(false);
cin >> T;
while (T--) {
cin >> a >> b >> x >> y;
int ans = solve(x, y);
ans = min(ans, solve(x - 1, y));
ans = min(ans, solve(x, y + 1));
ans = min(ans, solve(x - 1, y + 1));
cout << ans << endl;
}
}
G - Intersection of Prisms
H - Just Repeat
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <map>
#define MAX_N 100005
#define pii pair<int, int>
#define int long long
using namespace std;
int T, n, m, p;
int a[MAX_N];
int b[MAX_N];
namespace Gen {
unsigned long long k1, k2, mod;
unsigned long long rng() {
unsigned long long k3 = k1, k4 = k2;
k1 = k4;
k3 ^= k3 << 23;
k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
return k2 + k4;
}
void gen() {
cin >> k1 >> k2 >> mod;
for (int i = 1; i <= n; i++) {
a[i] = rng() % mod;
}
cin >> k1 >> k2 >> mod;
for (int i = 1; i <= m; i++) {
b[i] = rng() % mod;
}
}
} // namespace Gen
struct cmp {
bool operator()(const pii &a, const pii &b) {
return a.first + a.second < b.first + b.second;
}
};
signed main() {
ios::sync_with_stdio(false);
cin >> T;
while (T--) {
cin >> n >> m >> p;
if (p == 1) {
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= m; i++) {
cin >> b[i];
}
} else {
Gen::gen();
}
map<int, pii> mp;
for (int i = 1; i <= n; i++) {
mp[a[i]].first++;
}
for (int i = 1; i <= m; i++) {
mp[b[i]].second++;
}
int ra = 0, rb = 0;
priority_queue<pii, vector<pii>, cmp> q;
for (auto it = mp.begin(); it != mp.end(); it++) {
pii tp = it->second;
if (!tp.first || !tp.second) {
ra += tp.first, rb += tp.second;
} else {
q.push(tp);
}
}
int sd = 0, sa = 0, sb = 0;
while (!q.empty()) {
pii tp = q.top();
q.pop();
if (sd == 0) {
sa += tp.first;
} else {
sb += tp.second;
}
sd = 1 - sd;
}
int ta = ra + sa, tb = rb + sb;
if (ta > tb) {
cout << "Cuber QQ" << endl;
} else {
cout << "Quber CC" << endl;
}
}
}
I - Kejin Player
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 500005
#define MOD 1000000007
#define inv(x) (fpow((x), MOD - 2))
#define int long long
using namespace std;
int T, n, q;
int p[MAX_N];
int x[MAX_N];
int a[MAX_N];
int f[MAX_N];
int s[MAX_N];
int fpow(int x, int k) {
int ans = 1;
while (k) {
if (k & 1) {
ans = ans * x % MOD;
}
x = x * x % MOD, k >>= 1;
}
return ans;
}
signed main() {
ios::sync_with_stdio(false);
cin >> T;
while (T--) {
cin >> n >> q;
int u, d;
for (int i = 1; i <= n; i++) {
cin >> u >> d >> x[i] >> a[i];
p[i] = u * inv(d) % MOD;
}
for (int i = 1; i <= n; i++) {
f[i] = (a[i] + (1 - p[i] + MOD) * (s[i - 1] - s[x[i] - 1] + MOD)) % MOD * inv(p[i]) % MOD;
s[i] = (s[i - 1] + f[i]) % MOD;
}
int l, r;
while (q--) {
cin >> l >> r;
cout << (s[r - 1] - s[l - 1] + MOD) % MOD << endl;
}
}
}
J - Final Exam
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#define int long long
using namespace std;
int T, n, m, K;
signed main() {
ios::sync_with_stdio(false);
cin >> T;
while (T--) {
cin >> n >> m >> K;
cout << (int)ceil((m + 1.0) / (n - K + 1.0)) * (K - 1) + m + 1 << endl;
}
}