@Dmaxiya
2018-08-17T10:22:53.000000Z
字数 5287
阅读 1111
Codeforces
Contests 链接:Educational Codeforces Round 31
过题数:4
排名:93/7946
需要 秒才能看完一本书,接下来的 天时间里,第 天需要花 秒的时间工作,工作的时间不能看书。问她最少需要多少天才能看完书(每一天有 秒)。
第一行有两个整数 ,第二行包含 个数字 。数据保证答案一定不大于 。
输出 看完整本书需要的最少天数。
输入 | 输出 |
---|---|
2 2 86400 86398 |
2 |
2 86400 0 86400 |
1 |
直接按题意模拟。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <ctime>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 100000 + 100;
int n, t, tmp;
int main() {
#ifdef LOCAL
freopen("test.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif
ios::sync_with_stdio(false);
while(scanf("%d%d", &n, &t) != EOF) {
int ans = 0;
for(int i = 1; i <= n; ++i) {
scanf("%d", &tmp);
t -= (86400 - tmp);
if(t <= 0 && ans == 0) {
ans = i;
}
}
printf("%d\n", ans);
}
return 0;
}
对一个长度为 的 串, 为其中连续的 的段数,第 段连续的 的个数为 ,例如 串 ,它的 就是 , 的集合为 。给定 以及 的值,判断是否只存在唯一的满足条件的 串。
第一行为两个整数 ,第二行为 个整数 。
如果只有唯一的 串满足条件,则输出 ,否则输出 。
输入 | 输出 |
---|---|
2 4 1 3 |
NO |
3 10 3 3 2 |
YES |
2 10 1 3 |
NO |
要判断只存在唯一的 串满足条件,只需要判断 这些连续的 的段以及段之间的间隔定为 个 是否正好等于 即可,即判断 是否为真。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <ctime>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 100;
int n, k, tmp;
int main() {
#ifdef LOCAL
freopen("test.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif
ios::sync_with_stdio(false);
while(scanf("%d%d", &n, &k) != EOF) {
int sum = 0;
for(int i = 0; i < n; ++i) {
scanf("%d", &tmp);
sum += tmp + 1;
}
if(sum == k + 1) {
printf("YES\n");
} else {
printf("NO\n");
}
}
return 0;
}
有 个城市,这个城市之间的道路满足以下两个条件:
- 对于第 个城市,都有唯一一条从这个城市出发的道路,这条道路的终点是 ,允许出现 的情况;
- 对于第 个城市,都有唯一一条到达这个城市的道路,这条道路的起点为 且 。
问在最多修改两条道路的情况下,使得有序对 的数量最多,如果图上存在从 到 的道路,则存在一个有序对 。
第一行为一个整数 ,第二行为 个整数 。
输出最多修改两条道路的情况下,图上最多的有序对数量。
输入 | 输出 | 提示 |
---|---|---|
3 2 1 3 |
9 | 可以将 改为 ,将 改为 ,这样就可以有 个有序对 。 |
5 1 5 4 3 2 |
17 | 可以将 改为 而将 改为 。 |
对于按照题给方式生成的 序列,一定是一个 的排列,其中最多修改两条道路,相当于将排列中的两个环合并成一个环,由于有序对的数量等于环上节点数量的平方,所以应该将两个最多节点的环合并,如果只有一个环,则直接输出 。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <ctime>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 100000 + 100;
int n, x, cnt;
int fa[maxn], num[maxn];
LL ans[maxn], Ans;
bool vis[maxn];
void Init() {
Ans = 0;
cnt = 0;
for(int i = 1; i <= n; ++i) {
fa[i] = i;
num[i] = 1;
vis[i] = false;
}
}
int Find(int x) {
return (x == fa[x]? x: fa[x] = Find(fa[x]));
}
void unit(int x, int y) {
int xx = Find(x);
int yy = Find(y);
if(xx != yy) {
num[yy] += num[xx];
fa[xx] = yy;
}
}
int main() {
#ifdef Dmaxiya
freopen("test.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif //Dmaxiya
ios::sync_with_stdio(false);
while(scanf("%d", &n) != EOF) {
Init();
for(int i = 1; i <= n; ++i) {
scanf("%d", &x);
unit(x, i);
}
for(int i = 1; i <= n; ++i) {
int f = Find(i);
if(!vis[f]) {
vis[f] = true;
ans[cnt++] = num[f];
}
}
if(cnt == 1) {
printf("%I64d\n", ans[0] * ans[0]);
continue;
}
sort(ans, ans + cnt);
ans[cnt - 2] += ans[cnt - 1];
for(int i = 0; i < cnt - 1; ++i) {
Ans += ans[i] * ans[i];
}
printf("%I64d\n", Ans);
}
return 0;
}
有 个箱子,最初在第 个箱子里有 种颜色的球,第 种颜色的球的个数为 ,其他的箱子都是空的,可以通过以下的操作将第 种颜色的求放入编号为 的箱子里:
- 选择任意一个非空的箱子,将其中的所有的球从箱子里取出;
- 选择 个空着的箱子(刚刚被取出球的箱子也可以被包括在其中),将刚刚取出的所有球分配到想分配的箱子中, 可以为 或者 。
某次操作的代价是从箱子中取出的球的总个数,而所有操作的代价等于每次操作的代价的和。问要将第 个箱子中的所有的球都放到相应的箱子中,最少需要多少代价。
第一行为一个整数 ,第二行为 个整数 。
输出最少需要的代价。
输入 | 输出 |
---|---|
3 1 2 3 |
6 |
4 2 3 4 5 |
19 |
可以从另一个方向考虑这个问题:将 个球分到 个箱子里使得第 个箱子里的球的个数等于 ,每次只能拆成 个或者 个数字,每次拆的花费为 , 表示被拆的数字,画出这棵树就可以发现这是一棵哈夫曼树,每个节点的子节点数为 ,如果 为偶数,只要再加一个 的节点即可。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <ctime>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
struct Node {
LL num;
Node() {}
Node(LL n) {
num = n;
}
};
bool operator<(const Node &a, const Node &b) {
return a.num > b.num;
}
priority_queue<Node> que;
int n;
LL num;
int main() {
#ifdef LOCAL
freopen("test.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif
ios::sync_with_stdio(false);
while(scanf("%d", &n) != EOF) {
if(n == 1) {
scanf("%I64d", &num);
printf("0\n");
continue;
} else if(n == 2) {
scanf("%I64d", &num);
LL tmp;
scanf("%I64d", &tmp);
printf("%I64d", tmp + num);
continue;
}
LL ans = 0;
while(!que.empty()) {
que.pop();
}
if(n % 2 == 0) {
que.push(Node(0));
}
for(int i = 0; i < n; ++i) {
scanf("%I64d", &num);
que.push(Node(num));
}
while(que.size() != 1) {
Node tmp1 = que.top();
que.pop();
Node tmp2 = que.top();
que.pop();
Node tmp3 = que.top();
que.pop();
Node tmp4(tmp1.num + tmp2.num + tmp3.num);
ans += tmp4.num;
que.push(tmp4);
}
printf("%I64d\n", ans);
}
return 0;
}