# | Name |
---|---|
https://codeforces.com/contest/1283/problem/A | Minutes Before the New Year https://codeforces.com/contest/1283/problem/A standard input/output1 s, 256 MB |
https://codeforces.com/contest/1283/problem/B | Candies Division https://codeforces.com/contest/1283/problem/B standard input/output2 s, 256 MB |
https://codeforces.com/contest/1283/problem/C | Friends and Gifts https://codeforces.com/contest/1283/problem/C standard input/output2 s, 256 MB |
https://codeforces.com/contest/1283/problem/D | Christmas Trees https://codeforces.com/contest/1283/problem/D standard input/output2 s, 256 MB |
https://codeforces.com/contest/1283/problem/E | New Year Parties https://codeforces.com/contest/1283/problem/E standard input/output2 s, 256 MB |
https://codeforces.com/contest/1283/problem/F | DIY Garland https://codeforces.com/contest/1283/problem/F standard input/output2 s, 256 MB |
总结
6/6 unofficial rank 42
题目很简单而且有些锅 (描述以及 spj), 虽然赛后才修好 C 的 judge, 但是还是 rated 了.
A
给 h:m, 求到 0:0 还有多少分钟
- \[ res=(24-h)\cdot60-m \]
- B
n 个物品分给 k 个人, 要求每个人的差不超过 1 且大一点的人数不超过总人数一半.
大部分人可以取到 \(n/k\) 个物品, 小部分是 \(n/k+1\)
答案为 \(\min((k - k / 2) * (n / k) + (k / 2) * (n / k + 1), n)\)
C
给 n 个点连 n 条有向边使得他们成环, 已经给出一些边.
简单来说是一些链和一些点, 使得他们成环即可, 链的终点特性的入度为 1 没有出度. 成环的方法是首尾相接.
D
有 n+m 个不同一维坐标整点, 给出其中 n 个记做 a 集合, 求构造 m 个使得这 m 个在 a 集合中最近的点距离和最小.
输出距离和构造的点坐标.
显然类似 bfs 即可, 用 map 做 vis 标记.
E
有 n 个整数, 表示坐标轴上 n 个点, 定义一个序列的值为他们占用的不同位置的数量. 对其中每个数 x 可以选择 x-1,x,x+1 三种, 求序列最小值和最大值.
对最小值可以 dp 求解, 只需要判断每个点前两个的关系即可, 最大值直接贪心优先放在 - 1 位置, 如果已经放过了放在本身, 再放过了放在 + 1 就可以了.
F
构造一棵有根树, 有点权,\(i\) 点的点权为 \(2^{i}\), 定义一个边的权为割掉这条边会丢失的点权, 其中丢失的部分是原理根节点的部分, 给出 n-1 条边中靠近根节点的点下标, 保证给出的边是按边权大到小排序的, 求原树的形状.
首先对没有出度的点进行排序, 已知没有出度的点必是叶子节点且他们构造的点权必是最小的一批, 按边权从小到大倒塞回去, 构成逆拓扑序, 如果一个节点被塞到度为 0 了则把它也加入队列, 此时产生了一个权值排序的问题, 由于一个点如果没有出度, 它的权值以及它对父亲节点的贡献是固定的, 所以可以对这个用优先队列维护拓扑, 权值为子树的最大点. 因为点权为 \(2^i\), 无论如何选择, 对一个集合 \(a:\{x_1, x_2 \dots, x_n\}\) 和另一个集合 \(b:\{y_1,y_2,\dots, y_m\}\), 如果 \(\max(x_i)>max(y_i)\),a 集合贡献总是比 b 大, 所以可以对每一个点维护一个子树最大值. 然后就可以解出所有的边了.
代码:
- /*================================================================
- * Copyright (C) 2019 Sangfor Ltd. All rights reserved.
- *
- * 创 建 者: badcw
- * 创建日期: 2019/12/29
- *
- ================================================================*/
- #include <bits/stdc++.h>
- #define ll long long
- using namespace std;
- const int maxn = 2e5+50;
- const int mod = 1e9+7;
- ll qp(ll a, ll n) {
- ll res = 1;
- while (n> 0) {
- if (n & 1) res = res * a % mod;
- a = a * a % mod;
- n>>= 1;
- }
- return res;
- }
- template <class T>
- inline bool scan(T& ret) {
- char c;
- int sgn;
- if (c = getchar(), c == EOF) return 0; // EOF
- while (c != '-' && (c <'0' || c> '9')) c = getchar();
- sgn = (c == '-') ? -1 : 1;
- ret = (c == '-') ? 0 : (c - '0');
- while (c = getchar(), c>= '0' && c <= '9') ret = ret * 10 + (c - '0');
- ret *= sgn;
- return 1;
- }
- //template <class T>
- //inline void out(T x) {
- // if (x> 9) out(x / 10);
- // putchar(x % 10 + '0');
- //}
- int n;
- int deg[maxn];
- int pos[maxn];
- int a[maxn];
- struct node {
- int x;
- bool operator <(const node& oth) const {
- return pos[x]> pos[oth.x];
- }
- };
- int main(int argc, char* argv[]) {
- scanf("%d", &n);
- for (int i = 1; i <n; ++i) {
- int x;
- scanf("%d", &x);
- a[i] = x;
- deg[x] ++;
- }
- for (int i = 1; i <= n; ++i) pos[i] = i;
- priority_queue<node> qu;
- for (int i = 1; i <= n; ++i) {
- if (!deg[i]) {
- qu.push({i});
- }
- }
- printf("%d\n", a[1]);
- for (int i = n - 1; i>= 1; --i) {
- printf("%d %d\n", a[i], qu.top().x);
- pos[a[i]] = max(pos[a[i]], qu.top().x);
- qu.pop();
- deg[a[i]] --;
- if (deg[a[i]] == 0) {
- qu.push({a[i]});
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3357088.html