比赛链接
重现赛个人下饭操作太多，后程直接开摆，分数不够理想。这比赛严格来说应该比区域赛简单。不过有几题我挺喜欢的。
先发出来，C、D、F、H、J 题这几天会填坑。
A. Orders
点击查看题意简述
某工厂收到 \(n\) 个订单，每个订单形如「在第 \(a_i\) 天前交付 \(b_i\) 件货物」。初始时工厂无货物，且每天其可以生产 \(k\) 件货物，问该工厂是否能完成所有订单？
数据范围：多测，\(1 \leq T \leq 100\)，\(1 \leq n \leq 100\)，余下数在 \(\texttt{int}\) 范围内。
按天数升序订单，依次判断处理该订单时是否有余货即可。
#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define LD long double
#define reg register
#define _rep(i, x, y) for(int i = x; i <= y; i++)
#define _per(i, x, y) for(int i = x; i >= y; i--)
template <typename T>
inline void read(T &x) {
x = 0; T f = (T) 1;
char c = getchar();
for(; !isdigit(c); c = getchar()) {if(c == '-') f = -f;}
for(; isdigit(c); c = getchar()) x = x * 10 + c - 48;
x *= f;
}
template <typename T, typename... Args>
inline void read(T& x, Args&... args) {
read(x); read(args...);
}
template <typename T>
inline void write(T x) {
if(x < 0) {x = -x; putchar('-');}
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
template <typename T>
inline void writesp(T x, char sp = ' ') {write(x); putchar(sp);}
int T, n, k;
struct M {
int a, b;
} m[105];
bool operator < (const M &A, const M &B) {return A.a < B.a || (A.a == B.a && A.b > B.b);}
int main() {
read(T);
while(T--) {
read(n, k);
_rep(i, 1, n) read(m[i].a, m[i].b);
std::sort(m + 1, m + n + 1);
LL tot = 0, lasday = 0, flg = 1;
_rep(i, 1, n) {
tot += 1ll * (m[i].a - lasday) * k, lasday = m[i].a;
if(m[i].b > tot) {flg = 0; break;}
tot -= m[i].b;
}
puts((flg ? "Yes" : "No"));
}
return 0;
}
B. Building Company
点击查看题意简述
某公司初始时有 \(g\) 类员工，编号分别为 \(t_1, t_2, \cdots, t_g\)，其中 \(t_i\) 类员工初始时有 \(u_i\) 人。现有 \(n\) 项可以承接的工程，第 \(i\) 项工程有 \(m_i\) 条诸如「拥有多于 \(b_{i,j}\) 个 \(a_{i,j}\) 类员工」\((1 \leq j \leq m_i)\) 的要求。如果要求均满足，那么该公司可以获得 \(k_i\) 中员工，其中第 \(c_{i, j}\) 类员工可获得 \(d_{i, j}\) 人 \((1 \leq j \leq k_i)\)。如果每个工程只能承接一次，且承接一项工程后，员工的数量不会消耗。问：最多能承接的工程数？
数据范围：\(1 \leq n, g \leq 10^5\)，余下正整数在 \(\texttt{int}\) 范围内。
当前员工数，每项工程剩余的要求数都是可以容易维护的。使用类似拓扑排序的方法，先将可以承接的工程加入队列，随后分别领取奖励，同时判断领取后是否可以满足其他要求即可。时间复杂度 \(\mathcal{O}(n \log n)\)。
赛时用的离散化 + 一堆 std::vector 维护后拓扑结果 TLE 了...
#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define LD long double
#define reg register
#define _rep(i, x, y) for(int i = x; i <= y; i++)
#define _per(i, x, y) for(int i = x; i >= y; i--)
template <typename T>
inline void read(T &x) {
x = 0; T f = (T) 1;
char c = getchar();
for(; !isdigit(c); c = getchar()) {if(c == '-') f = -f;}
for(; isdigit(c); c = getchar()) x = x * 10 + c - 48;
x *= f;
}
template <typename T, typename... Args>
inline void read(T& x, Args&... args) {
read(x); read(args...);
}
template <typename T>
inline void write(T x) {
if(x < 0) {x = -x; putchar('-');}
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
template <typename T>
inline void writesp(T x, char sp = ' ') {write(x); putchar(sp);}
const int maxN = 1e5 + 10;
using pii = std::pair<int, int>;
int g, n, a[maxN], b[maxN], m[maxN], k[maxN], remain[maxN];
std::vector<pii> awa[maxN];
std::unordered_map<int, LL> tot;
std::unordered_map<int, std::priority_queue<pii, std::vector<pii>, std::greater<pii> > > ne;
int L = 1, R = 0, que[maxN];
void _reduce(int _t, int _num) {
LL u = tot[_t]; u += _num; tot[_t] = u;
while(!ne[_t].empty() && ne[_t].top().first <= u) {
pii uu = ne[_t].top();
remain[uu.second]--;
if(remain[uu.second] == 0) que[++R] = uu.second;
ne[_t].pop();
}
}
int main() {
read(g);
_rep(i, 1, g) read(a[i], b[i]);
read(n);
_rep(i, 1, n) {
int x, y;
read(m[i]); _rep(j, 1, m[i]) read(x, y), ne[x].push(std::make_pair(y, i));
read(k[i]); _rep(j, 1, k[i]) read(x, y), awa[i].push_back(std::make_pair(x, y));
remain[i] = m[i];
}
_rep(i, 1, n) if(m[i] == 0) que[++R] = i;
_rep(i, 1, g) _reduce(a[i], b[i]);
while(L <= R) {
int u = que[L]; ++L;
for(auto t : awa[u]) _reduce(t.first, t.second);
}
writesp(R, '\n');
return 0;
}
E. Math Problem
点击查看题意简述
给定正整数 \(n\)、\(k\)，随后你可以进行如下两种操作任意次：
- 操作一：任选 \([0, k)\) 中的正整数 \(x\)，并置 \(n := k \cdot n + x\)。耗费 \(a\) 元/次。
- 操作二：置 \(n := \lfloor \frac{n}{k} \rfloor\)。耗费 \(b\) 元/次。
问：能否通过若干次操作使得最终的数为 \(m\) 的倍数（0 视为任意正整数的倍数）？如可以，最小花费是？\(1 \leq n \leq 10^{18}\)，余下的正整数 \(\in [1, 10^9]\)。
首先观察到，进行一次操作一后再进行操作二与不操作无区别，所以唯一可能的操作方法是：先进行若干次操作二后执行若干次操作一。
枚举操作二的执行次数 \(r \leq \log_k n\)，记剩下的数为 \(res\)。执行 \(t\) 次操作一后，最终的数应形如 \(k^t \cdot res + R\)，其中 \(R \in [0, k^t - 1] \cap \mathbb{N}\)。我们希望选取合适的 \(R\) 使得 \(k^t \cdot res \equiv -R \pmod m\)。
不断进行操作一直至符合要求即可。可以发现 \(t > \log_k m\) 时必然存在 \(R\) 符合要求。
最终对所有答案取最小值，时间复杂度 \(\mathcal{O}(\log_k n \cdot \log_k m)\)。注意特判边界。
#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define LD long double
#define reg register
#define int long long
#define _rep(i, x, y) for(int i = x; i <= y; i++)
#define _per(i, x, y) for(int i = x; i >= y; i--)
template <typename T>
inline void read(T &x) {
x = 0; T f = (T) 1;
char c = getchar();
for(; !isdigit(c); c = getchar()) {if(c == '-') f = -f;}
for(; isdigit(c); c = getchar()) x = x * 10 + c - 48;
x *= f;
}
template <typename T, typename... Args>
inline void read(T& x, Args&... args) {
read(x); read(args...);
}
template <typename T>
inline void write(T x) {
if(x < 0) {x = -x; putchar('-');}
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
template <typename T>
inline void writesp(T x, char sp = ' ') {write(x); putchar(sp);}
int T, k, m, a, b;
LL n;
signed main() {
read(T);
while(T--) {
read(n, k, m, a, b);
LL ans = LONG_LONG_MAX;
if(n % m == 0) ans = 0;
else if(k == 1) ans = LONG_LONG_MAX;
else {
int cnt = 0; LL res = n;
while(res) {
LL Bcnt = 0, cum = 1ll * res % m, tot = 1;
while(true) {
if(tot >= m) break;
if((cum % m >= 1 - tot + m) || cum % m == 0) break;
++Bcnt, cum = 1ll * cum * k % m, tot = 1ll * tot * k;
}
ans = std::min(ans, 1ll * cnt * b + 1ll * Bcnt * a);
res /= k; ++cnt;
}
ans = std::min(ans, 1ll * cnt * b);
}
writesp((ans == LONG_LONG_MAX ? -1 : ans), '\n');
}
return 0;
}
G. Matching
点击查看题意简述
我们利用某数列 \(\{a_n\}\) 构造一无向图 \(G\)：对所有 \(1 \leq i \lt j \leq n\)，如果 \(i - j = a_i - a_j\)，则在 \(G\) 中连接一条从 \(i\) 号节点到 \(j\) 号节点，权值为 \((a_i + a_j)\) 的无向边。给定 \(\{a_n\}\)，求图 \(G\) 的匹配中的边权之和最大者。
数据范围：多测，\(1 \leq n \leq 10^5\)，\(\sum n \leq 5 \times 10^5\)，\(a_i \in [-10^9, 10^9]\)。
\(i - j = a_i - a_j\) 等价于 \(i - a_i = j - a_j\)。所以所有满足 \(i - a_i\) 相等的 \(i\) 之间都会两两连边，最终的 \(G\) 一定是若干个子完全图组成的。
显然我们可以对每一个子完全图考虑贡献。而由题意，某子完全图的匹配相当于选择偶数个 \(a_i\) 答案的最大值。所以只要不断选择两个 \(a_i\) 最大的点，直至二者之和小于 0 即可。
时间复杂度 \(\mathcal{O}(n \log n)\)。
#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define LD long double
#define reg register
#define _rep(i, x, y) for(int i = x; i <= y; i++)
#define _per(i, x, y) for(int i = x; i >= y; i--)
template <typename T>
inline void read(T &x) {
x = 0; T f = (T) 1;
char c = getchar();
for(; !isdigit(c); c = getchar()) {if(c == '-') f = -f;}
for(; isdigit(c); c = getchar()) x = x * 10 + c - 48;
x *= f;
}
template <typename T, typename... Args>
inline void read(T& x, Args&... args) {
read(x); read(args...);
}
template <typename T>
inline void write(T x) {
if(x < 0) {x = -x; putchar('-');}
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
template <typename T>
inline void writesp(T x, char sp = ' ') {write(x); putchar(sp);}
const int maxN = 1e5 + 10;
LL T, n, tot = 0;
struct Node {
LL a, pot, pos;
} nn[maxN];
bool operator < (const Node &a, const Node &b) {
return a.pot < b.pot || (a.pot == b.pot && a.a > b.a);
}
std::vector<LL> Has[maxN];
int main() {
read(T);
while(T--) {
read(n);
_rep(i, 1, n) read(nn[i].a), nn[i].pot = i - nn[i].a, nn[i].pos = i;
std::sort(nn + 1, nn + n + 1);
tot = 0; LL lastans = INT_MAX;
_rep(i, 1, n) {
if(lastans != nn[i].pot) ++tot, lastans = nn[i].pot;
Has[tot].push_back(nn[i].a);
}
LL ans = 0;
_rep(i, 1, tot) {
LL l = Has[i].size();
_rep(j, 0, l / 2 - 1) {
LL delta = Has[i][2 * j] + Has[i][2 * j + 1];
ans += (delta <= 0 ? 0 : delta);
}
}
writesp(ans, '\n');
_rep(i, 1, n) Has[i].clear();
}
return 0;
}
I. Three Dice
点击查看题意简述
抛掷三颗骰子，是否存在朝上的红色点数和为 \(A\)、朝上的蓝色点数和为 \(B\) 的情况？一颗标准骰子的 1、4 两面是红色点数，其他的是蓝色点数。
好像怎么做都可以... 暴力枚举三颗骰子的状态判断是否符合。时间复杂度 \(\mathcal{O}(1)\)。
#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define LD long double
#define reg register
#define _rep(i, x, y) for(int i = x; i <= y; i++)
#define _per(i, x, y) for(int i = x; i >= y; i--)
template <typename T>
inline void read(T &x) {
x = 0; T f = (T) 1;
char c = getchar();
for(; !isdigit(c); c = getchar()) {if(c == '-') f = -f;}
for(; isdigit(c); c = getchar()) x = x * 10 + c - 48;
x *= f;
}
template <typename T, typename... Args>
inline void read(T& x, Args&... args) {
read(x); read(args...);
}
template <typename T>
inline void write(T x) {
if(x < 0) {x = -x; putchar('-');}
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
template <typename T>
inline void writesp(T x, char sp = ' ') {write(x); putchar(sp);}
bool Valid[101][101];
int main() {
memset(Valid, 0, sizeof(Valid));
_rep(a, 1, 6) {
_rep(b, 1, 6) {
_rep(c, 1, 6) {
int A = 0, B = 0;
if(a == 1 || a == 4) A += a;
else B += a;
if(b == 1 || b == 4) A += b;
else B += b;
if(c == 1 || c == 4) A += c;
else B += c;
Valid[A][B] = true;
}
}
}
int AA, BB; read(AA, BB);
puts(Valid[AA][BB] ? "Yes" : "No");
return 0;
}
L. Puzzle: Sashigane
点击查看题意简述
给出一种用 \(\leq \frac{n^2 - 1}{3}\) 个 L 形拼图覆盖一个 \(n \times n\) 的、其上有一个黑格的游戏板的方案。要求除了黑格之外剩下所有格子恰好被一个 L 形拼图所覆盖。如不存在合法方案则报告无解。
数据范围：\(1 \leq n \leq 1000\)。
首先，黑格在四个角时，构造是容易的（见下左图）。如果黑格在某条边界上，取右下角的某个子正方形，将其中的 L 形拼图对应旋转即可（见下右图）。
随后考虑一般情况。从左上角为起点框出恰好能“包围”黑格的最小子正方形（见左图灰色填充部分）。子正方形内使用上述右图的方法，外侧直接包围即可（见下右图）。
时间复杂度 \(\mathcal{O}(n)\)。
#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define LD long double
#define reg register
#define _rep(i, x, y) for(int i = x; i <= y; i++)
#define _per(i, x, y) for(int i = x; i >= y; i--)
template <typename T>
inline void read(T &x) {
x = 0; T f = (T) 1;
char c = getchar();
for(; !isdigit(c); c = getchar()) {if(c == '-') f = -f;}
for(; isdigit(c); c = getchar()) x = x * 10 + c - 48;
x *= f;
}
template <typename T, typename... Args>
inline void read(T& x, Args&... args) {
read(x); read(args...);
}
template <typename T>
inline void write(T x) {
if(x < 0) {x = -x; putchar('-');}
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
template <typename T>
inline void writesp(T x, char sp = ' ') {write(x); putchar(sp);}
int n, x, y, tot = 0, r[6666], c[6666], h[6666], w[6666];
void constr(int _r, int _c, int _h, int _w) {++tot; r[tot] = _r, c[tot] = _c, h[tot] = _h, w[tot] = _w;}
int main() {
read(n, x, y);
puts("Yes");
int m = std::max(x, y);
_rep(i, m + 1, n) constr(i, i, 1 - i, 1 - i);
if(x == y) {
_rep(i, 1, m - 1) constr(i, i, x - i, x - i);
} else if(x > y) {
_rep(i, 1, y - 1) constr(x - y + i, i, y - i, y - i);
_rep(i, 1, x - y) constr(i, x - i + 1, x - i, i - x);
} else if(x < y) {
_rep(i, 1, x - 1) constr(i, y - x + i, x - i, x - i);
_rep(i, x + 1, y) constr(i, y + 1 - i, 1 - i, i - 1);
}
writesp(tot, '\n');
_rep(i, 1, tot) printf("%d %d %d %d\n", r[i], c[i], h[i], w[i]);
return 0;
}
M. Computational Geometry
点击查看题意简述
给出某凸 \(n\) 边形 \(G\)，要求逆时针选择 \(G\) 的三个顶点 B、C、A，使得 B、C 间夹着 \(k\) 条边，且由 AB、AC 与 B、C 间夹着的 \(k\) 条边组成的 \(k + 2\) 边形面积最大。
数据范围：多测，\(3 \leq n \leq 10^5\)，\(\sum n \leq 10^5\)，\(1 \leq k \leq n-2\)。
B、C 的选择只有 \(n\) 种，考虑枚举 B、C。而且循环枚举 B、C 时，每跳向相邻的一个点，其面积变化只需考虑 2 个三角形的面积。所以可以算出初始时 B、C 间夹着的 \(k\) 条边与 BC 组成的 \(k + 1\) 边形的面积，随后只需加（或减）两个三角形的面积即可。
固定 B、C 后考虑求 A，只需最大化 \(\triangle ABC\) 的面积。而随 A 跳向下一个相邻点，\(\triangle ABC\) 的面积是几乎单峰的，可以使用三分法求解。
综上本题解决，时间复杂度 \(\mathcal{O}(n \log n)\)。
本题还有实际效率更快的算法，在计算 \(\triangle ABC\) 的面积时使用类似旋转卡壳的方法即可做到 \(\mathcal{O}(n)\)。
#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define LD long double
#define reg register
#define _rep(i, x, y) for(int i = x; i <= y; i++)
#define _per(i, x, y) for(int i = x; i >= y; i--)
template <typename T>
inline void read(T &x) {
x = 0; T f = (T) 1;
char c = getchar();
for(; !isdigit(c); c = getchar()) {if(c == '-') f = -f;}
for(; isdigit(c); c = getchar()) x = x * 10 + c - 48;
x *= f;
}
template <typename T, typename... Args>
inline void read(T& x, Args&... args) {
read(x); read(args...);
}
template <typename T>
inline void write(T x) {
if(x < 0) {x = -x; putchar('-');}
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
template <typename T>
inline void writesp(T x, char sp = ' ') {write(x); putchar(sp);}
const int maxN = 2e5 + 10;
int T, n, k;
struct Point2 {
LL x, y;
Point2(LL _x = 0, LL _y = 0) : x(_x), y(_y) {}
} P[maxN];
typedef Point2 Vector2;
Vector2 operator - (Point2 A, Point2 B) {return Vector2(A.x - B.x, A.y - B.y);}
LL Cross(Vector2 A, Vector2 B) {return A.x * B.y - A.y * B.x;}
LL solve(LL a, LL b) {
LL Ans1 = 0; int l = a, r = b;
while(r - l >= 3) {
int m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
if(Cross(P[m1] - P[a], P[b] - P[a]) < Cross(P[m2] - P[a], P[b] - P[a])) l = m1; else r = m2;
}
_rep(i, l, r) Ans1 = std::max(Ans1, Cross(P[i] - P[a], P[b] - P[a]));
return Ans1;
}
int main() {
read(T);
while(T--) {
read(n, k);
_rep(i, 1, n) read(P[i].x, P[i].y);
_rep(i, 1, n) P[n + i] = P[i];
LL maxAns = 0, Ans = 0;
_rep(i, 2, k) Ans = Ans + Cross(P[i] - P[1], P[i + 1] - P[1]);
maxAns = std::max(maxAns, Ans + solve(k + 1, n + 1));
_rep(i, 2, n) {
Ans = Ans - Cross(P[i] - P[i - 1], P[k + i] - P[i - 1]);
Ans = Ans + Cross(P[k + i - 1] - P[i - 1], P[k + i] - P[i - 1]);
maxAns = std::max(maxAns, Ans + solve(k + i, n + i));
}
printf("%.15lf\n", maxAns * 1.0 / 2);
}
return 0;
}