2023 年山东省大学生程序设计竞赛个人题解

标签：10 read 题解 void long int 2023 程序设计 define

比赛链接

重现赛个人下饭操作太多，后程直接开摆，分数不够理想。这比赛严格来说应该比区域赛简单。不过有几题我挺喜欢的。

先发出来，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;
}

标签：10,read,题解,void,long,int,2023,程序设计,define
From： https://www.cnblogs.com/fsy-juruo/p/17641577.html

2023 年山东省大学生程序设计竞赛个人题解

比赛链接

A. Orders

B. Building Company

E. Math Problem

G. Matching

I. Three Dice

L. Puzzle: Sashigane

M. Computational Geometry

相关文章

赞助商

阅读排行

2023 年山东省大学生程序设计竞赛 个人题解

比赛链接

A. Orders

B. Building Company

E. Math Problem

G. Matching

I. Three Dice

L. Puzzle: Sashigane

M. Computational Geometry

相关文章

赞助商

阅读排行

2023 年山东省大学生程序设计竞赛个人题解