Educational Codeforces Round 42 (Rated for Div. 2)
Educational Codeforces Round 42 (Rated for Div. 2)
attack
发布于 2018-08-01 11:20:35
发布于 2018-08-01 11:20:35
A. Equator(模拟)
找权值的中位数，直接模拟。。
代码写的好丑qwq。。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAXN = 1e6 + 10;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N;
int a[MAXN];
main() {
#ifdef WIN32
// freopen("a.in", "r", stdin);
#endif
int N = read(), sum = 0;
for(int i = 1; i <= N; i++) a[i] = read(), sum += a[i];
int now = 0;
for(int i = 1; i <= N; i++) {
now += a[i];
if(!(sum & 1)) {
if(now >= sum / 2) {
printf("%d", i); return 0;
}
} else {
if(now > sum / 2) {
printf("%d", i); return 0;
}
}
}
}B. Students in Railway Carriage(贪心)
直接贪心放，如果是偶数的话肯定是两种各放一半
如果是奇数的话，应该在都放一半的基础上，把多的放在最后一个
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAXN = 1e6 + 10;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N;
char s[MAXN];
main() {
#ifdef WIN32
// freopen("a.in", "r", stdin);
#endif
int N = read(), A = read(), B = read();
if(A < B) swap(A, B);
scanf("%s", s + 1);
int last = 0;
int ans = 0;
s[N + 1] = '*';
for(int i = 1; i <= N + 1; i++) {
if(s[i] == '*') {
int len = i - last - 1;
ans += min(len / 2, A) + min(len / 2, B);
A -= min(len / 2, A); B -= min(len / 2, B);
if((len & 1) && A > 0) A--, ans++;
if(A < B) swap(A, B);
last = i;
}
}
printf("%d", ans);
}C. Make a Square(数论，暴力)
首先把所有平方数预处理出来
然后对于输出的数的各个位分解出来，
枚举所有的平方数，算出最少需要删几个
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define int long long
using namespace std;
const int MAXN = 1e6 + 10;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int po[MAXN], tot = 0, N, P[MAXN], Pnum = 0;
int check(int val) {
int times = 0;
for(int i = 1; i <= Pnum; i++) {
if(P[i] == val % 10) {
val /= 10, times++;
}
if(val == 0) {
return Pnum - times;
}
}
if(val != 0) return -1;
else return Pnum - times;
}
main() {
#ifdef WIN32
// freopen("a.in", "r", stdin);
#endif
for(int i = 1; ; i++) {
po[++tot] = i * i;
if(po[tot] > 2 * 1e9) break;
}
N = read();
int x = N;
while(x) P[++Pnum] = x % 10, x /= 10;
int ans = 1e9;
for(int i = 1; i <= tot; i++) {
int num = check(po[i]);
if(num != -1) ans = min(ans, num);
}
printf("%I64d", ans == 1e9 ? -1 : ans);
}D. Merge Equals(堆)
用优先队列维护每个数的位置和权值（权值相同的时候位置小的在前面）
然后每次取出前两个，如果相同就合成完再放回去，否则统计答案
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define int long long
using namespace std;
const int MAXN = 1e6 + 10;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N;
struct Node {
int pos, val;
bool operator < (const Node &rhs) const {
return val == rhs.val ? pos > rhs.pos : val > rhs.val;
}
};
priority_queue<Node>q;
int ans[MAXN];
void work() {
while(q.size() >= 2) {
Node x = q.top(); q.pop();
Node y = q.top(); q.pop();
if(x.val != y.val) {q.push(y); ans[x.pos] = x.val; continue;}
q.push((Node){y.pos, x.val * 2});
}
while(q.size() != 0) ans[q.top().pos] = q.top().val, q.pop();
}
main() {
#ifdef WIN32
// freopen("a.in", "r", stdin);
#endif
N = read();
for(int i = 1; i <= N; i++)
q.push((Node){i, read()});
work();
int num = 0;
for(int i = 1; i <= N; i++)
if(ans[i] != 0)
num++;
printf("%I64d\n", num);
for(int i = 1; i <= N; i++)
if(ans[i] != 0)
printf("%I64d ", ans[i]);
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018-06-19 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录