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 + ;

inline int read() {

    char c = getchar(); int x = , f = ;

    while(c < '' || c > '') {if(c == '-') f = -; c = getchar();}

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * f;

}

int N;

int a[MAXN];

main() {

#ifdef WIN32

//    freopen("a.in", "r", stdin);

#endif

    int N = read(), sum = ;

    for(int i = ; i <= N; i++) a[i] = read(), sum += a[i];

    int now = ;

    for(int i = ; i <= N; i++) {

        now += a[i];

        if(!(sum & )) {

            if(now >= sum / ) {

                printf("%d", i); return ;

            }

        } else {

            if(now > sum / ) {

                printf("%d", i); return ;

            }

        }

    }

}

B. Students in Railway Carriage(贪心)

直接贪心放，如果是偶数的话肯定是两种各放一半

如果是奇数的话，应该在都放一半的基础上，把多的放在最后一个

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

const int MAXN = 1e6 + ;

inline int read() {

    char c = getchar(); int x = , f = ;

    while(c < '' || c > '') {if(c == '-') f = -; c = getchar();}

    while(c >= '' && c <= '') x = x *  + c - '', 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 + );

    int last = ;

    int ans = ;

    s[N + ] = '*';

    for(int i = ; i <= N + ; i++) {

        if(s[i] == '*') {

            int len = i - last - ;

            ans += min(len / , A) + min(len / , B);

            A -= min(len / , A); B -= min(len / , B);

            if((len & ) && A > ) 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 + ;

inline int read() {

    char c = getchar(); int x = , f = ;

    while(c < '' || c > '') {if(c == '-') f = -; c = getchar();}

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * f;

}

int po[MAXN], tot = , N, P[MAXN], Pnum = ;

int check(int val) {

    int times = ;

    for(int i = ; i <= Pnum; i++) {

        if(P[i] == val % ) {

            val /= , times++;

        }

        if(val == ) {

            return Pnum - times;

        }

    }

    if(val != ) return -;

    else return Pnum - times;

}

main() {

#ifdef WIN32

//    freopen("a.in", "r", stdin);

#endif

    for(int i = ; ; i++) {

        po[++tot] = i * i;

        if(po[tot] >  * 1e9) break;

    }

    N = read();

    int x = N;

    while(x) P[++Pnum] = x % , x /= ;

    int ans = 1e9;

    for(int i = ; i <= tot; i++) {

        int num = check(po[i]);

        if(num != -) ans = min(ans, num);

    }

    printf("%I64d", ans == 1e9 ? - : 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 + ;

inline int read() {

    char c = getchar(); int x = , f = ;

    while(c < '' || c > '') {if(c == '-') f = -; c = getchar();}

    while(c >= '' && c <= '') x = x *  + c - '', 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() >= ) {

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

    }

    while(q.size() != ) ans[q.top().pos] = q.top().val, q.pop();

}

main() {

#ifdef WIN32

//    freopen("a.in", "r", stdin);

#endif

    N = read();

    for(int i = ; i <= N; i++)

        q.push((Node){i, read()});

    work();

    int num = ;

    for(int i = ; i <= N; i++)

        if(ans[i] != )

            num++;

    printf("%I64d\n", num);

    for(int i = ; i <= N; i++)

        if(ans[i] != )

            printf("%I64d ", ans[i]);

}

巴特西

Educational Codeforces Round 42 (Rated for Div. 2)

A. Equator(模拟)

B. Students in Railway Carriage(贪心)

C. Make a Square(数论，暴力)

D. Merge Equals(堆)

最新文章

热门文章