Educational Codeforces Round 42 (Rated for Div. 2)

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]);
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

POJ 2771 Guardian of Decency

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

34940
来自专栏数据结构与算法

11.6NOIP模拟赛解题报告

很显然的一个贪心是从左往右扫,如果遇到一个不合法的点\(i\),那么升级\(i + R\)处的炮台。。

10030
来自专栏数据结构与算法

BZOJ1576: [Usaco2009 Jan]安全路经Travel(最短路 并查集)

给你一张无向图,保证从1号点到每个点的最短路唯一。对于每个点求出删掉号点到它的最短路上的最后一条边(就是这条路径上与他自己相连的那条边)后1号点到它的最短路的长...

8110
来自专栏懒人开发

Eventbus3代码分析(七):整体结构

自己没有怎么花时间画图,怕可能有遗漏的地方 所以,先参考一下别人的代码分析 (之前的内容,应该没有雷同的地方,参考别人的分析,也是自我提高的过程) 我们先...

8820
来自专栏曾大稳的博客

队列(Queue)

看看队列在Android里面的使用 Handle消息队列 使用Handle的时候都要使用Looper.loop()

32320
来自专栏数据结构与算法

BZOJ2818: Gcd(莫比乌斯反演)

求$gcd(i, j)$为素数的对数,$ i \leqslant N ,j \leqslant N$

12050
来自专栏小灰灰

Greenrobot-EventBus源码学习(五)

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

24060
来自专栏数据结构与算法

BZOJ4010: [HNOI2015]菜肴制作(拓扑排序 贪心)

11820
来自专栏张善友的专栏

Temp权限引起的WCF问题

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

201100
来自专栏calmound

HDU 4609 3-idiots

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

29460

扫码关注云+社区

领取腾讯云代金券