牛客小白月赛88 出题人题解
牛客小白月赛88 出题人题解
出题人:WIDA 。
协调员:tokitsukaze 。
第一轮内测同学:Hamine,_rsy,464zzyx,想打一辈子算法竞赛怎么办,silverbullet23,honey__ 。
第二轮内测同学:xxiu_,djwcb,cstdios,xfy_,yangjl,lz214,wy/,薛定谔的上帝,爱音乐的博博,_锦木千束,you_xiao,这题你已经AC了,Sakura_t,枫系,HQPYH,octal,蔡光,tarjen,-.--.--.-,liangqianxing,jackle 。
希望大家今晚玩的开心~
题目总览与预期
A | 超级闪光牛可乐 | *800 | 构造 | ||
B | 人列计算机 | *900 | 模拟, 字符串 | ||
C | 时间管理大师 | *1100 | 模拟, 数据结构 | ||
D | 我不是大富翁 | *1400 | 动态规划, 数学 | ||
E | 多重映射 | *1600 | 贪心, 数据结构, 图论 | ||
F | 现在是消消乐时间 | *1700 | 构造, 数论, 搜索, 模拟, 暴力 | ||
G | 三点不共线 | *1700 | 几何, 数论, 构造 |
小结:
就 G 题的题面缺陷道歉,在书写时出现了纰漏,非常抱歉!
本场比赛的 idea 来自于我 2023 年初为实验室大一学弟学妹们出的训练赛,在2023年ICPC南京站前夕就已经投稿了,由于种种原因放出的较迟,但是很高兴最终能在六个月后与大家见面!比赛借鉴了 sua 命题组的题面风格以及 Polygon 对于题面 Markdown 语法的要求,尽可能的做到了规范。题目先后一共进行了八轮修改、三次验题,非常不容易,希望大家能喜欢最终呈现的这一版本题目。
本场总体情况符合预期,唯一的小问题在 F 的通过人数,标程不难实现,但是可能 G 更加易上手导致排行榜歪了。
关于这一题还有一个小插曲,在于原先 F 是在 E 的位置上,范围更宽松、允许 的做法通过,另有一个 hard ver 要求
计算出有多少合法发射位置,由于题数原因合并为一题且与 E 互换了位置(使得这场少了一道经典的数数题)。大家可以思考一下原先的这个 hard ver 该如何实现。
除此之外,本次比赛的 E 非常不幸的与前日进行的 HUAWEI Programming Contest 2024(AtCoder Beginner Contest 342) 中的 C 题撞了 idea ,但是由于解法差异较大,在验题组讨论过后决定不做修改,大家可以看作是那一题的 ProMax 版本。
以上,再次感谢大家参加。
Update1: 彩蛋。
Problem A: 超级闪光牛可乐
*800, 100% (构造)题解
打卡题,直接输出任意一个食物 次即可。
参考代码
int main() {
int p;
char op;
cin >> p >> p >> op;
cout << string(1000, op) << "\n";
}
出题思路
构造打卡题,主推一个好玩 狠狠偷吃清楚姐姐的零食 。
另,今天是妇女节,让我们祝清楚洁洁节日快乐!
Problem B: 人列计算机
*900, 85% (模拟, 字符串)题解
打卡题,寻找适当的函数读入后进行模拟判断。
提供一个码量较小的做法。注意到不同的门电路之间的差别很小,从这些不同之处入手——首先检查第 行第
列的这个字符,知道逻辑门的种类,随后检查第
列的输入数据即可,其余的部分都是没有用的,读入后直接丢弃。
参考代码
int main() {
vector<string> s(5);
for (int i = 0; i < 5; i++) {
getline(cin, s[i]);
}
char op = s[2][5];
if (op == '&') {
cout << (s[1][0] & s[3][0]) - '0' << "\n";
} else if (op == '=') {
cout << (s[1][0] | s[3][0]) - '0' << "\n";
} else {
cout << !(s[2][0] - '0') << "\n";
}
}
出题思路
难点是读入函数的选择。本题不同写法的码量差异极大,出题人也想借此拉开各层次选手的过题速度。
如果你耗费了较多时间,建议尝试更短的写法。
Problem C: 时间管理大师
*1100, 60% (数据结构)题解
打卡题。我们可以将给定的时间从“小时-分钟”的形式转化为“纯分钟”的形式。
具体来说, 即为第
项日程事件的“纯分钟”形式。这样做的好处在于我们可以使用一维数组来储存事件,直接进行时间计算与去重。而要重新转换回“小时-分钟”形式也非常简单,不妨使用
表示第
个闹钟响起的时间,那么小时数即为
整除
、分钟数即为
。这一思想也是哈希思想的体现。
当然,暴力模拟也能通过本题,这里不再赘述。
参考代码
const int P = 24 * 60;
int main() {
int n;
cin >> n;
vector<bool> vis(P);
for (int i = 0; i < n; i++) {
int h, m;
cin >> h >> m;
int bell = h * 60 + m;
vis[bell - 1] = vis[bell - 3] = vis[bell - 5] = true;
}
cout << accumulate(vis.begin(), vis.end(), 0) << "\n";
for (int i = 0; i < P; i++) {
if (vis[i]) {
cout << i / 60 << " " << i % 60 << "\n";
}
}
}
出题思路
本题题干细节较多,主要考察读题能力;此外还需要对于数组的熟练运用。
同样的,本题不同写法的码量差异极大,如果你耗费了较多时间,建议尝试更短的写法。
Problem D: 我不是大富翁
*1400, 35% (动态规划, 数学)题解
简单动态规划。使用 表示在第
回合
是否有可能站在
号地块,初始状态为
,最终只需要判定
是否为
。下方描述转移:对于
可以从上一轮的
地块向左移动
个地块得到、也可以从上一轮的
地块向右移动
个地块得到——即由
和
转移。需要注意的细节是,由于是环形地图,在转移时需要针对
进行取模。时间复杂度
,空间复杂度
。
另外值得一提的是,本题的空间限制不允许二维 long long
数组通过(希望大家都能摆脱 #define int long long
的坏习惯),你可以选择滚动数组或是使用 bool
、 int
类型数组。
参考代码
int main() {
int n, m;
cin >> n >> m;
vector dp(m + 1, vector(n, false));
dp[0][0] = true;
for (int i = 1; i <= m; i++) {
int x;
cin >> x;
x %= n;
for (int j = 0; j < n; j++) {
dp[i][j] = dp[i - 1][(j + x) % n] | dp[i - 1][(j - x + n) % n];
}
}
cout << (dp[m][0] ? "YES" : "NO") << "\n";
}
出题思路
比较无聊但是具有教育意义的题目,非常浅的考察了动态规划,希望没学过动态规划和运用不熟练的同学都能够解出来。
Problem E: 多重映射
*1600, 15% (贪心, 数据结构, 图论)题解
解法一:逆向处理
正难则反!注意到在前面进行的操作会被后面进行的操作所覆盖,不如逆序处理每一个操作。如果学习过并查集或者链表,那么会比较方便的理解本题的处理过程。
我们使用一个数组 father
记录每一个数字最终会变成什么。在初始状态下,由于没有进行过替换操作,所以所有数字的 father
均为它自己。那么,将数字 替换成数字
这一操作就可以用
father[a] = father[b]
这行代码来表示。由于逆序处理,最后 father[a]
数组中储存的就是 这个数字的最终答案。注意到本题有多组数据,每一次都初始化整个数组必然会导致超时,所以我们可以仅对使用到的数字进行初始化,同时借助哈希表
来动态处理。这一思想也是离散化思想的体现。时间复杂度
,空间复杂度
。
注意到这与并查集非常相似,但是使用经典的并查集却无法通过本题!原因在于本题的操作需要严格按照时间先后顺序执行(有向),在此附上一组 hack 数据,简单的运用并查集大概率会得到 2 2 2
。
1
3 2
1 3 2
1 2
3 1
解法二:启发式合并
注意到每一次操作都会将更多的数字变得相同(逐渐有序),所以只需要在原先暴力修改的基础上加入一定启发式合并的思想。具体来说,在每次修改的时候,优先修改数量较少的那个数字,再通过 swap
操作复原。这一步最坏时间复杂度 约为
,空间复杂度
,可以通过本题。
参考代码
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int Task = 1;
for (cin >> Task; Task; Task--) {
int n, m;
cin >> n >> m;
vector<int> in(n), l(m), r(m);
map<int, int> fa;
for (int i = 0; i < n; i++) {
cin >> in[i];
}
for (int i = 0; i < m; i++) {
cin >> l[i] >> r[i];
}
for (int i = m - 1; i >= 0; i--) {
if (fa.count(r[i])) {
fa[l[i]] = fa[r[i]];
} else {
fa[l[i]] = r[i];
}
}
for (int i = 0; i < n; i++) {
cout << (fa[in[i]] ? fa[in[i]] : in[i]) << " \n"[i == n - 1];
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
vector<vector<int>> dic(1E6 + 1);
int Task = 1;
for (cin >> Task; Task; Task--) {
int n, m;
cin >> n >> m;
vector<int> in(n), ans;
for (int i = 0; i < n; i++) {
cin >> in[i];
ans.push_back(in[i]);
dic[in[i]].push_back(i);
}
for (int i = 0; i < m; i++) {
int l, r;
cin >> l >> r;
if (l == r) continue;
if (dic[l].size() < dic[r].size()) {
dic[r].insert(dic[r].end(), dic[l].begin(), dic[l].end());
dic[l].clear();
} else {
dic[l].insert(dic[l].end(), dic[r].begin(), dic[r].end());
dic[r].clear();
swap(dic[l], dic[r]);
}
ans.push_back(r);
}
for (auto i : ans) {
for (auto j : dic[i]) {
in[j] = i;
}
dic[i].clear();
}
for (int i = 0; i < n; i++) {
cout << in[i] << " \n"[i == n - 1];
}
}
}
出题思路
带点毒瘤的题目,题目形象易懂、粗看上手难度较低,但是具体书写的时候较易出错(特别是学习过并查集但是不熟悉原理的同学,很容易就会误入歧途)。内测没有人能够只靠一发就 AC 这道题。
Problem F: 现在是消消乐时间
*1700, 5% (构造, 数论, 搜索, 模拟, 暴力)题解
很容易发现的结论是,从这样的位置发射的小球必定会经过全部方格,从此入手。
解法一:过程优化的暴力搜索
如果从某个点射出的小球无法消除全部方块,那么其经过的所有点也一定不是答案,使用数组记录剪枝。由于每一个点至多被检查四次(四个方向),时间复杂度 ,空间复杂度
,足以通过本题。需要注意的是,该方法需要开辟较大的空间,使用
vector
有超时风险。
解法二:起点优化的暴力搜索
显然,结束情况只分两种,一种是回到发射点,另一种是射向矩形的四个角。分类讨论,对于第一种情况,我们将结束情况看作是初始情况,那么发射地点可以从四个角中任选;对于第二种情况,路径上的任何一个点都可以作为起点,由于这样的路径一定不经过四个角,所以可以选择相邻四个角的点。
所以,如果存在答案,那么第 行编号为
的竖线处、第
行编号为
的竖线处一定存在一个合法发射地点。故只需要暴力测试这两个位置即可,时间复杂度
,空间复杂度
,可以通过本题。
解法三:数论
这一解法其实是对解法二的总结,由三部分构成:
时间复杂度 ,空间复杂度
。证明较难,此处不给出,留待读者自证。
参考代码
const int N = 2E3 + 1;
bool vis[N][N][5];
int main() {
int n, m, d;
cin >> n >> m >> d;
vector<int> mx = {1, 1, -1, -1};
vector<int> my = {1, -1, 1, -1};
vector<string> str = {"UR", "UL", "DR", "DL"};
auto clac = [&](int x, int y, int k) -> bool {
int sum = 0;
while (!vis[x][y][k]) {
vis[x][y][k] = true;
int dx = x + mx[k], dy = y + my[k];
if ((dx < 0) + (n < dx) + (dy < 0) + (m < dy) == 2) break;
if (dx < 0) {
k -= 2;
} else if (n < dx) {
k += 2;
} else if (dy < 0) {
k -= 1;
} else if (m < dy) {
k += 1;
}
sum += max(x, x + mx[k]) > d;
x += mx[k], y += my[k];
}
return sum == (n - d) * m;
};
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
for (int k = 0; k <= 3; k++) {
if (!clac(i, j, k)) continue;
cout << "YES\n";
cout << i << " " << j << "\n";
cout << str[k] << "\n";
return 0;
}
}
}
cout << "NO\n";
}
int main() {
int n, m, d;
cin >> n >> m >> d;
auto clac = [&](int sx, int sy) -> bool {
vector vis(n + 1, vector(m + 1, false));
int x = sx, y = sy;
int dx = 1, dy = 1, cnt = 0;
while (cnt++ <= n * m) {
vis[x][y] = true;
int bounce = 0;
if (x + dx < 0 || n < x + dx) {
dx *= -1;
bounce++;
}
if (y + dy < 0 || m < y + dy) {
dy *= -1;
bounce++;
}
if (bounce == 2) break;
x += dx, y += dy;
}
bool flag = true;
for (int i = d; i < n; i++) {
for (int j = 0; j < m; j++) {
if (vis[i][j] + vis[i + 1][j] + vis[i][j + 1] +
vis[i + 1][j + 1] < 2) {
flag = false;
}
}
}
return flag;
};
if (clac(0, 0)) {
cout << "YES\n0 0\nUR\n";
} else if (clac(0, 1)) {
cout << "YES\n0 1\nUL\n";
} else {
cout << "NO\n";
}
}
int main() {
int n, m, d;
cin >> n >> m >> d;
if (d == n || gcd(n, m) == 1) {
cout << "YES\n";
cout << 0 << " " << 0 << "\n";
cout << "UR\n";
} else if (gcd(n, m) == 2) {
cout << "YES\n";
cout << 0 << " " << 1 << "\n";
cout << "UR\n";
} else {
cout << "NO\n";
}
}
Problem G: 三点不共线
*1700, 5% (几何, 数论, 构造)题解
解法一:中垂线+三角函数
作线段 的中垂线,垂足为
,易知这条中垂线上一定存在两个合法的点
(对称分布)。在
中,通过三角函数可以得到
的长度:
。
过 点作
点所在横线的垂线,垂足为
。在
中,通过反三角函数可以得到直线
与
轴的夹角(即为下图中的
):
。这样做的目的在于求解出
,不妨记为
。
过 点作
点所在横线的垂线,垂足为
。在
中,通过三角函数可以得到
点相对于
点的坐标差
,
:
。
最终,一个合法的 点的坐标即为
。时间复杂度
,空间复杂度
。
解法二:中垂线+向量
这一解法其实是对解法一的优化。作线段 的中垂线,垂足为
。在
中,通过正弦函数可以得到
的长度:
。
此时,可以通过 旋转求得
。最终,一个合法的
点的坐标即为
。时间复杂度
,空间复杂度
。
参考代码
const double PI = acos(-1);
double toArc(double x) { // 角度转弧度
return PI / 180 * x;
}
double dis(double x1, double y1, double x2, double y2) { // 距离公式
double val = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
return sqrt(val);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(12);
int Task = 1;
for (cin >> Task; Task; Task--) {
double x1, y1, x2, y2, alpha;
cin >> x1 >> y1 >> x2 >> y2 >> alpha;
alpha = toArc(alpha / 2);
double k = 0;
if (x1 != x2) {
k = (y1 - y2) / (x1 - x2);
}
double xM = (x1 + x2) / 2;
double yM = (y1 + y2) / 2;
double angle = atan(abs(yM - y1) / abs(xM - x1));
double line = dis(x1, y1, xM, yM);
line /= tan(alpha);
if (k < 0) {
cout << xM - line * sin(angle) << " " << yM - line * cos(angle) << "\n";
} else {
cout << xM + line * sin(angle) << " " << yM - line * cos(angle) << "\n";
}
}
}
const double PI = acos(-1);
const double EPS = 1E-7;
template<class T> struct Point {
T x, y;
Point(T x_ = 0, T y_ = 0) : x(x_), y(y_) {} // 初始化
Point &operator+=(Point p) & { return x += p.x, y += p.y, *this; }
Point &operator-=(Point p) & { return x -= p.x, y -= p.y, *this; }
Point &operator*=(T t) & { return x *= t, y *= t, *this; }
Point &operator/=(T t) & { return x /= t, y /= t, *this; }
friend Point operator+(Point a, Point b) { return a += b; }
friend Point operator-(Point a, Point b) { return a -= b; }
friend Point operator*(Point a, T b) { return a *= b; }
friend Point operator*(T a, Point b) { return b *= a; }
friend Point operator/(Point a, T b) { return a /= b; }
friend auto &operator>>(istream &is, Point &p) {
return is >> p.x >> p.y;
}
};
double toArc(double x) { // 角度转弧度
return PI / 180 * x;
}
template<class T> Point<T> rotate(Point<T> p1, Point<T> p2) { // 旋转
Point<T> vec = p1 - p2;
return {-vec.y, vec.x};
}
Point<double> standardize(Point<double> vec) { // 转换为单位向量
return vec / sqrt(vec.x * vec.x + vec.y * vec.y);
}
template<class T> double dis(T x1, T y1, T x2, T y2) { // 距离公式
double val = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
return sqrt(val);
}
template<class T> double dis(Point<T> a, Point<T> b) {
return dis(a.x, a.y, b.x, b.y);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(12);
int Task = 1;
for (cin >> Task; Task; Task--) {
Point<double> A, B;
double alpha;
cin >> A >> B >> alpha;
double deg1 = toArc(alpha / 2);
double deg2 = PI / 2 - deg1;
double MC = dis(A, B) / 2 * sin(deg2) / sin(deg1);
auto vec = standardize(rotate(A, B));
auto ans = (A + B) / 2 + vec * MC;
cout << ans.x << " " << ans.y << "\n";
}
}
出题思路
磨时间题,有多种做法,不熟悉公式的话难度会比较高。