Educational Codeforces Round 42

Codeforces

Contests 链接：Educational Codeforces Round 42
过题数：5
排名：103/11738

A. Equator

题意

$Polycarp$ 总共要刷 $n$ 天的题，第 $i$ 天他刷了 $a_i$ 道题，他想要在刷题量达到总量的一半的那天晚上庆祝一下，问他将在第几天庆祝。

输入

第一行为一个整数 $n~(1\leq n\leq2\times10^5)$，第二行包含 $n$ 个整数 $a_1,a_2,\cdots,a_n~(1\leq a_i\leq10^4)$。

输出

输出他将在第几天庆祝，天数从 $1$ 开始计算。

样例

题解

按题意扫两遍数组。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 200000 + 100;
int n, ans;
LL half, sum;
LL num[maxn];
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//        freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        half = sum = 0;
        for(int i = 1; i <= n; ++i) {
            scanf("%I64d", &num[i]);
            sum += num[i];
        }
        for(int i = 1; i <= n; ++i) {
            half += num[i];
            if(half * 2 >= sum) {
                ans = i;
                break;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

B. Students in Railway Carriage

题意

在地铁上有 $n$ 个座位，某些位置上已经被乘客占据，现在有 $a$ 个写代码的学生和 $b$ 个运动员学生，问在满足下面条件下，地铁上最多能坐下多少个学生：

1. 没有任何一个写代码的学生坐在写代码的学生旁边；
2. 没有任何一个运动员学生坐在运动员学生旁边。

输入

第一行为三个整数 $n,a,b~(1\leq n\leq2\times10^5,0\leq a,b\leq2\times10^5,a+b>0)$，第二行为一个长度为 $n$ 的字符串，字符串只包含 . 和 *，点表示这个位置为空位，星号表示这个位置有乘客占据。

输出

输出最多能够坐得下的学生的数量。

样例

题解

每跑到一个空位，判断前一个是否是 $A$ 或者 $B$，如果是，则该空位只能填入另一种学生，否则将剩余学生人数多的填入。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 200000 + 100;
int n, a, b;
char str[maxn];
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//        freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%d%d%d", &n, &a, &b) != EOF) {
        int sum = a + b;
        int flag = 0;
        scanf("%s", str);
        for(int i = 0; str[i]; ++i) {
            if(str[i] == '.') {
                if(flag == 0) {
                    if(a > b) {
                        flag = 1;
                        --a;
                    } else if(b > a) {
                        flag = 2;
                        --b;
                    } else if(a == b && b != 0) {
                        --b;
                        flag = 2;
                    }
                } else if(flag == 1) {
                    if(b > 0) {
                        --b;
                        flag = 2;
                    } else {
                        flag = 0;
                    }
                } else if(flag == 2) {
                    if(a > 0) {
                        --a;
                        flag = 1;
                    } else {
                        flag = 0;
                    }
                }
            } else {
                flag = 0;
            }
        }
        printf("%d\n", sum - a - b);
    }
    return 0;
}

C. Make a Square

题意

给定一个不包含前导零的正整数 $n$，要求删除最少的数字位，使得最终剩下的数字不包含前导零且它是一个完全平方数，或者判断这是无法实现的。

输入

输入只包含一个整数 $n~(1\leq n\leq2\times10^9)$。

输出

如果无法实现，则输出 $-1$，否则输出需要的最少的次数。

样例

题解

$bfs$ 所有删除状态，判断数字是否含有前导零且为完全平方数。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 44721 + 11;
int num;
string str;
int Pow[maxn];
int *it;
set<string> st;
queue<string> que;
bool judge(const string &str) {
    if(str[0] == '0') {
        return false;
    }
    int tmp = 0;
    int len = str.length();
    for(int i = 0; i < len; ++i) {
        tmp = tmp * 10 + str[i] - '0';
    }
    it = lower_bound(Pow + 1, Pow + maxn, tmp);
    if(it - Pow != maxn && *it == tmp) {
        return true;
    }
    return false;
}
int bfs() {
    string s, tmp;
    int len = str.length();
    que.push(str);
    st.insert(str);
    while(!que.empty()) {
        tmp = que.front();
        que.pop();
        if(judge(tmp)) {
            return len - tmp.length();
        }
        int l = tmp.length();
        for(int i = 0; i < l; ++i) {
            s = tmp.substr(0, i) + tmp.substr(i + 1, l);
            if(s != "" && st.find(s) == st.end()) {
                st.insert(s);
                que.push(s);
            }
        }
    }
    return -1;
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//        freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    for(int i = 1; i < maxn; ++i) {
        Pow[i] = i * i;
    }
    while(cin >> str) {
        st.clear();
        while(!que.empty()) {
            que.pop();
        }
        printf("%d\n", bfs());
    }
    return 0;
}

D. Merge Equals

题意

给定一个长度为 $n$ 的序列，多次扫描这个序列，每次扫描如果找到出现至少两次的数字中值最小的数字，将最左边的数字合并到右边的那个数字中，并将右边的数字用这个数字的两倍代替，如对于序列 $[3,4,1,2,2,1,1]$，操作步骤如下：

$$[3,4,1,2,2,1,1]\rightarrow[3,4,2,2,2,1]\rightarrow[3,4,4,2,1]→[3,8,2,1]$$ 对于序列 $[1,1,3,1,1]$ 的操作如下：
$$[1,1,3,1,1]\rightarrow[2,3,1,1]\rightarrow[2,3,2]\rightarrow[3,4]$$ 对于给定的序列，输出最终的结果。

输入

第一行为一个整数 $n~(1\leq n\leq1.5\times10^5)$，第二行为 $n$ 个整数 $a_1,a_2,\cdots,a_n~(1\leq a_i\leq10^9)$。

输出

输出最终的序列。

样例

题解

以数字大小为主关键字，数字的下标为次关键字，用大顶堆进行维护，如果两次弹出堆顶的元素相同，则把这个两个数字合并并放回到堆中，否则将小的数字放到答案数组中，另一个数字继续与下一个弹出的元素进行比较。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 150000 + 100;
struct Node {
    int Index;
    LL num;
    Node() {}
    Node(int I, LL n) {
        Index = I;
        num = n;
    }
};
bool operator<(const Node &a, const Node &b) {
    if(a.num == b.num) {
        return a.Index > b.Index;
    }
    return a.num > b.num;
}
int n;
bool vis[maxn];
LL num[maxn];
priority_queue<Node> que;
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//        freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        int cnt = n;
        for(int i = 1; i <= n; ++i) {
            scanf("%I64d", &num[i]);
            que.push(Node(i, num[i]));
            vis[i] = true;
        }
        Node last = que.top();
        que.pop();
        while(!que.empty()) {
            Node tmp = que.top();
            que.pop();
            if(tmp.num != last.num) {
                last = tmp;
                continue;
            }
            --cnt;
            vis[last.Index] = false;
            num[tmp.Index] = last.num * 2;
            que.push(Node(tmp.Index, last.num * 2));
            last = que.top();
            que.pop();
        }
        bool flag = false;
        printf("%d\n", cnt);
        for(int i = 1; i <= n; ++i) {
            if(vis[i]) {
                if(flag) {
                    printf(" ");
                }
                flag = true;
                printf("%I64d", num[i]);
            }
        }
        printf("\n");
    }
    return 0;
}