碎碎念昨天下午去打ACM模拟赛了,错过了下午的 Codeforces,于是今天上午补了一次 VP。 隔壁CCPC桂林站已经开打了,祝「基本无害」拿个金牌www
比赛 A.Factorise N+M (0:02)(497/500) 题意 给一个质数 ,找到一个质数 使得 不是质数
分析 当 时, 一定不是质数
1 2 3 4 5 6 void solve () { int n; std::cin >> n; std::cout << n << '\n' ; }
题意 给若干个矩形,将这些矩形拼成一个多边形,要求每个矩形都有一条边在 轴上。 求这个多边形边长的最小值
分析 假定我们现在已经决定好第 个矩形在 轴上的那一条边长度为 ,平行于 轴的那一条边长度为 。 令 当我们把矩形按高度从小到大依次排列,最终的周长为 ,找不到一种更优的排列让周长更小。
接着考虑每一个矩形应该如何放置 令 为假定的最高值,满足 对于任意的矩形,假定它的边长 时,令长度为 的那条边为高,长度为 的那条边为底,对于整体周长的增加值 一定不会有更小的情况。
此时寻找 的具体值应该是多少。不难发现 就是边长中的最大值。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 void solve () { int n; std::cin >> n; std::vector<std::pair<int ,int >> s (n); for (int i = 0 ; i < n; i++) { std::cin >> s[i].first >> s[i].second; if (s[i].first < s[i].second) std::swap (s[i].first,s[i].second); } std::sort (s.begin (),s.end ()); long long sum = 0 ; for (auto x : s) sum = sum + x.second; sum = sum + s[n - 1 ].first; sum = sum * 2 ; std::cout << sum << '\n' ; }
C. Bricks and Bags (0:54)【1141/1500,-2】 题意 有 个数字, 个盒子。 玩家 把数字任意放入每个盒子,使得每个盒子至少有一个数字。 玩家 从每个盒子中取出一个数字 记得分
已知玩家 的策略是最小化 求 的最大值
分析 考虑 号盒子中只有一个数字 的情况 此时玩家 需要把剩余 个数字分成两堆。 无论玩家 如何分这两堆数字,玩家 总能选择一个数字 ,满足对于任意的 有 。 于是玩家 的目标是最大化另一个数字产生的价值。也就是让玩家 在这一个盒子中没有其他选择除了选择这一个产生最大价值的数字,即盒子中只有一个数字。不难发现,这个数字要么是 个数字中的最小值,要么是最大值(此时不考虑边界冲突的问题,即假设最小值和最大值都是可以使用的状态)。
在这种情况下,不难发现被选择的这个数字 本身就是最大值或最小值时 最大。因为有一个完整的 (最大值 - 最小值) + (最大值-次大值 或 次小值-最小值),其余情况都是 (最大值 - 中间值 或 中间值 - 最小值) + |中间值 - 相邻值|
再考虑 号盒子中有 数字的情况,这 个数字要么是最小的 个数字,要么是最大的 个数字。 此时玩家 会选择 最小的数字中最大的那个 或 最大的数字中最小的那个。为了让这个数字与 号盒子还有 号盒子中的数字差值尽可能的小。 按照之前的策略,玩家 会把一个产生最大价值的数字单独放在一个盒子中,把剩余的数字全部放在另一个盒子中。
枚举 ,取最大值。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 void solve () { int n; std::cin >> n; std::vector<int > a (n) ; for (int i = 0 ; i < n; i++) std::cin >> a[i]; std::sort (a.begin (),a.end ()); int ans = 0 ; for (int i = 0 ; i + 2 < n; i++) ans = std::max (ans, a[i + 1 ] - a[i] + a[n - 1 ] - a[i]); for (int i = n - 1 ; i - 2 >= 0 ; i--) ans = std::max (ans, a[i] - a[i - 1 ] + a[i] - a[0 ]); std::cout << ans << '\n' ; }
D. Knowledge Cards (1:18)【1264/1750,-1】 题意 给一个 的地图,在起点 有 个棋子形成一个栈,给定顺序。
将棋子从起点移动到终点 ,形成一个栈,从栈顶到栈底顺序为
一颗棋子可以移动到相邻的格子。除了起点与终点一个格子最多只能有一颗棋子。棋子不能移入起点,不能移出终点。
询问能否通过任意步实现。
分析 棋盘与华容道类似,只要有一个自由点,总能将棋子移动到任意一个位置。
于是题目转换为,对于 ,对于当前的 在栈中出现的位置是前 ,则把元素 从栈中删除。
尝试用一个堆维护信息
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 void solve () { int n,m,k; std::cin >> n >> m >> k; std::queue<int > q; std::priority_queue<int > Q; for (int i = 1 ; i <= k; i++) { int x; std::cin >> x; q.push (x); } while (k) { if (!Q.empty () && Q.top () == k) { Q.pop (); k--; } else if (Q.size () == n * m - 3 ) break ; else { Q.push (q.front ()); q.pop (); } } if (k) std::cout << "TIDAK\n" ; else std::cout << "YA\n" ; }
E. Hanging Hearts (2:05)【1050/2000,-3】 题意 给一棵树,点权为 (点权未知)
每次选择一个叶子节点 ,将点权 加入一个队列 之后对于它的父亲节点 进行操作 删除节点
当整棵树被删掉后, 为队列 中最长不下降子序列的长度
点权是 的一个排列,求 的最大值
分析 考虑一条链的情况 只要将叶子节点的点权赋值为 ,最终的队列 就只包含数字 ,
考虑根节点 有 个子节点 不难发现,无论如何都无法让 ,因为最初我们会选择点权较小的叶子节点 ,刷新根节点的点权 $a{root}’将 小 于 等 于 a_x; 接 着 选 择 另 一 个 叶 子 节 点 y, 有 a_y>a_x, \cdots最 终 选 择 根 节 点 构 成 的 序 列 为 a_x,a_y,\cdots,a {root}’, 其 中 a_{root}’ \le a_x < a_y<\cdots。 score = k$ 即有多个子节点产生贡献的情况下,根节点无法产生贡献。
于是考虑对一棵子树 ,定义 表示这棵子树产生的最大价值是多少, 表示 节点不产生贡献的情况下,这棵子树产生的最大价值是多少。 有 ,
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 std::vector<std::vector<int >> To; std::vector<int > length,f,g; void dfs (int u) { length[u] = 1 ; int sum = 0 ; for (int v : To[u]) { dfs (v); length[u] = std::max (length[u],length[v] + 1 ); g[u] += f[v]; } f[u] = std::max (length[u],g[u]); } void solve () { int n; std::cin >> n; To.resize (n + 1 ); length.resize (n + 1 ); f.resize (n + 1 ); g.resize (n + 1 ); for (int i = 2 ; i <= n; i++) { int u; std::cin >> u; To[u].push_back (i); } dfs (1 ); std::cout << f[1 ] << '\n' ; }
F. Conditional Mix 题意 给 个数字,去构成任意多个集合。 将集合的大小 当做元素放入一个 中,询问有多少种不同的
分析 令 表示在这 个数字中,数字 出现的次数。 因为我们不关心数字本身是几,只关心它出现了几次,于是将 从大到小排序。
不难发现,我们至少要构成 个集合,因为有这么多个数字,而它们不能放入同一个集合中 对于 ,我们可以在前 个集合中放入元素,再新开 个集合。 以此类推,如下图所示。
之后就是考虑如何计算有多少种不同的方案。 猜测是斯特林数,但好像又不是。
总结 表现分:1864
打的并不是很好
题连蒙带猜花了十分钟,直觉认为每个矩形都是大边与 轴平行 写博客时才差不多证明出来正确性
题思考了很久,前面都推的还好,写挂了两次才发现 号盒子可能有多个数字 推广到 个数字时才发现只取一个数字时,那个数字要么是最大值要么是最小值 于是 个数字也应该是最大或最小的 个
题题意一开始理解错了,以为棋盘上的点都可以叠放成栈 然后想到了华容道 写挂了一次,判断边界是写成了 ,这种情况下刚好把棋盘填满,棋子是无法移动的。
题开始没怎么读懂题目,看样例给的图发现就是一棵树,每次选叶子节点。 能感觉到是树形 。 第一次只考虑了根节点分叉的情况,也就是第二层节点中最长链之和。过了五个点,感觉方向是对的 第二次和第三次写的代码有点混乱,现在重新看也没理出什么思路,也是挂在第六个点。 最后定义出 状态方程 推导公式的时候也有点想当然,于是写博客时重新推导了一下,从特例出发到普遍情况汇总
题看到 的范围是 感觉可做,看了下 花了五分钟过了这道题。 应该思考一个小时能想出来,虽然思考四十分钟比赛就结束了,或许是什么数学上的算法我还没学过吧
状态不是很好,下周估计不会打比赛,准备期中考试了。