# Educational Codeforces Round 42 (Rated for Div. 2)

## A. Equator(模拟)

```#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAXN = 1e6 + 10;
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;
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
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;
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;
}
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;
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
for(int i = 1; i <= N; i++)
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]);
}```

1811 篇文章121 人订阅

0 条评论

## 相关文章

### POJ 2771 Guardian of Decency

Description Frank N. Stein is a very conservative high-school teacher. He wants...

34940

10030

8110

8820

32320

12050

### Greenrobot-EventBus源码学习（五）

EventBus 深入学习五之注册 订阅者的注册 + 消息推送 1. 注册 先贴出注册代码， 可以可到和 Guava 相比没什么大的区别， 主要的点在内部实...

24060

11820

### Temp权限引起的WCF问题

WCF按照BasicHttpBinding方式发布，部署到服务器上，再在其他项目中引用的时候，就会出现不能正确下载元数据的错误。使用svcutil.exe工具进...

201100

### HDU 4609 3-idiots

http://acm.hdu.edu.cn/showproblem.php?pid=4609 题意：给你一组数，问可以组成多少个三角形 分析：才知道原来有FFT...

29460