Educational Codeforces Round 24

Codeforces

Contests 链接：Educational Codeforces Round 24
过题数：2
排名：902/5771

A. Diplomas and Certificates

题意

总共有 $n$ 个学生，有一部分学生获得了 $diplomas$，有另一部分学生获得了 $certificates$，而其他学生什么都没有获得，其中获得 $diplomas$ 与 $certificates$ 的学生称为 $winner$，问在保证 $winner$ 人数不超过 $\frac{n}{2}$ 且 $\frac{num_{certificates}}{num_{diplomas}}=k$ 的条件下，获得使 $num_{winner}$ 最大的情况。

输入

输入包含两个整数 $n,k~(1\leq n,k\leq10^{12})$。

输出

分别输出获得 $diplomas$、$certificates$ 和什么都没获得的人数。

样例

题解

只要确定获得 $diplomas$ 的人数就可以确定另外两个人数，$num_{diplomas}=\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{k+1}\rfloor$。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <sstream>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL long long
LL n, k, ans;
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%I64d%I64d", &n, &k) != EOF) {
        ans = n / 2 / (k + 1);
        printf("%I64d %I64d %I64d\n", ans, ans * k, n - ans * (k + 1));
    }
    return 0;
}

B. Permutation Game

题意

构造一个 $1-n$ 的排列 $a_1,a_2,\cdots,a_n$，使得对于一个长度为 $m$ 的序列 $l_1,l_2,\cdots,l_m$，当 $1\leq i<m$ 时，总是满足 $l_i+a_{l_i}=l_{i+1}$，当 $l_i+a_{l_i}$ 大于 $n$ 时，将结果减去 $n$。

输入

第一行为两个整数 $n,m~(1\leq n,m\leq100)$，第二行为 $m$ 个整数 $l_1,l_2,\cdots,l_m~(1\leq l_i\leq n)$。

输出

如果无法构造出满足条件的序列，则输出 $-1$，否则输出 $n$ 个整数，如果有多解输出任意一组解。

样例

题解

首先根据 $a_{l_i}=l_{i+1}-l_i$ 先生成一个 $a$ 序列，先计算这个序列中每个数字出现的次数，如果某个数字出现的次数大于 $1$，则这个序列是非法的，接着将这个序列中没有被用到的数据放进去，使得 $a$ 序列成为一个 $n$ 的排列，最后再扫一遍 $l$ 序列，判断是否对于每个 $l_i$ 都满足题给条件。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <sstream>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 100 + 100;
int n, m;
int num[maxn], ans[maxn], cnt[maxn];
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d%d", &n, &m) != EOF) {
        memset(cnt, 0, sizeof(cnt));
        memset(ans, 0, sizeof(ans));
        for(int i = 1; i <= m; ++i) {
            scanf("%d", &num[i]);
        }
        for(int i = 1; i < m; ++i) {
            int tmp = num[i + 1] - num[i];
            tmp = (tmp % n + n) % n;
            if(tmp == 0) {
                tmp = n;
            }
            ans[num[i]] = tmp;
        }
        bool flag = true;
        for(int i = 1; i <= n; ++i) {
            if(ans[i] == 0) {
                continue;
            }
            ++cnt[ans[i]];
            if(cnt[ans[i]] == 2) {
                flag =false;
                break;
            }
        }
        if(!flag) {
            printf("-1\n");
            continue;
        }
        for(int i = 1; i <= n; ++i) {
            if(ans[i] == 0) {
                for(int j = 1; j <= n; ++j) {
                    if(cnt[j] == 0) {
                        ++cnt[j];
                        ans[i] = j;
                        break;
                    }
                }
            }
        }
        for(int i = 1; i < m; ++i) {
            int tmp = num[i] + ans[num[i]];
            tmp = (tmp % n + n) % n;
            if(tmp == 0) {
                tmp = n;
            }
            if(tmp != num[i + 1]) {
                flag = false;
                break;
            }
        }
        if(!flag) {
            printf("-1\n");
            continue;
        }
        for(int i = 1; i <= n; ++i) {
            if(i != 1) {
                printf(" ");
            }
            printf("%d", ans[i]);
        }
        printf("\n");
    }
    return 0;
}

C. Sofa Thief

题意

在一个 $n\times m$ 的仓库里，有 $d$ 个沙发，每个沙发占两个相邻的位置，用两个坐标 $(x_1,y_1),(x_2,y_2)$ 表示，对于两个沙发 $A$ 和 $B$，如果存在 $x_a<x_b$，则表示 $A$ 沙发在 $B$ 沙发的左边，如果存在 $x_a>x_b$，则表示 $A$ 沙发在 $B$ 沙发的右边，如果存在 $y_a<y_b$，则表示 $A$ 沙发在 $B$ 沙发的上面，如果存在 $y_a>y_b$，则表示 $A$ 沙发在 $B$ 沙发的下面，其中 $x_a,y_a,x_b,y_b$ 分别属于沙发 $A$ 与沙发 $B$ 的其中一个横坐标或纵坐标。注意对于两个沙发，$A$ 可能既在 $B$ 的左边也在 $B$ 的右边。
现在给出某个沙发的左边、右边、上面、下面各有多少个沙发，找出满足条件的沙发。

输入

第一行包含一个整数 $d~(1\leq d\leq10^5)$，第二行为两个整数 $n,m~(1\leq n,m\leq 10^5)$，接下去 $d$ 行，每行四个整数 $x_1,y_1,x_2,y_2~(1\leq x_1,x_2\leq n,1\leq y_1,y_2\leq m)$，表示每个沙发的坐标，数据保证任意两个坐标都不会相同，且对同一个沙发的坐标描述一定是相邻的。最后一行为四个整数 $cnt_l,cnt_r,cnt_t,cnt_b$，表示要找的沙发需要符合的四个方向的沙发数量。数据保证最多只有一个沙发符合条件。

输出

如果不存在满足条件的沙发，就输出 $-1$，否则输出满足条件的沙发编号，沙发编号按照输入顺序从 $1$ 到 $d$ 编号。

样例

题解

假设第 $i$ 个沙发的 $x_{i1}\leq x_{i2},y_{i1}\leq y_{i2}$，由于上下左右四个方向的判定是类似的，因此这里只讨论左边的情况，可以推广到另外三个方向的情况：
由左边的判定方法可知：第 $i$ 个沙发左边的沙发个数等于满足 $x_{j1}<x_{i2}$ 的沙发个数（一个沙发只要有一个点满足条件，就能计入答案），我们可以通过对每个沙发的贡献做前缀和来 $O(1)$ 求出 $cnt_{il}$。对于第 $j$ 个沙发，它对所有满足 $x_{j1}<x_{i2}~(i\neq j)$ 的沙发都有贡献，因此可以在 $x=x_{j1}+1$ 处标记一个 $1$，最后做一个前缀和即可查询到任意一个沙发左边的沙发个数。
对其他三个方向也做同样的判断。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <sstream>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 100000 + 100;
int d, n, m, ans;
int node[maxn][4], cnt[4];
int Sum[4][maxn], Ends[4][2], dx[4];
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d", &d) != EOF) {
        ans = -1;
        memset(Sum, 0, sizeof(Sum));
        scanf("%d%d", &n, &m);
        dx[0] = dx[2] = 1;
        dx[1] = dx[3] = -1;
        Ends[0][1] = n + 1;
        Ends[1][0] = n - 1;
        Ends[2][1] = m + 1;
        Ends[3][0] = m - 1;
        Ends[1][1] = Ends[3][1] = 0;
        Ends[0][0] = Ends[2][0] = 2;
        for(int i = 1; i <= d; ++i) {
            for(int j = 0; j < 4; ++j) {
                scanf("%d", &node[i][j]);
            }
            swap(node[i][1], node[i][2]);
            if(node[i][0] < node[i][1]) {
                swap(node[i][0], node[i][1]);
            }
            if(node[i][2] < node[i][3]) {
                swap(node[i][2], node[i][3]);
            }
            ++Sum[0][node[i][1] + 1];
            ++Sum[1][node[i][0] - 1];
            ++Sum[2][node[i][3] + 1];
            ++Sum[3][node[i][2] - 1];
        }
        for(int i = 0; i < 4; ++i) {
            for(int j = Ends[i][0]; j != Ends[i][1]; j += dx[i]) {
                Sum[i][j] += Sum[i][j - dx[i]];
            }
        }
        for(int i = 0; i < 4; ++i) {
            scanf("%d", &cnt[i]);
        }
        for(int i = 1; i <= d; ++i) {
            bool flag = true;
            for(int j = 0; j < 4; ++j) {
                int tmp = Sum[j][node[i][j]];
                if(node[i][j] != node[i][j ^ 1]) {
                    --tmp;
                }
                if(tmp != cnt[j]) {
                    flag = false;
                    break;
                }
            }
            if(flag) {
                ans = i;
                break;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

D. Multicolored Cars

题意

$Alice$ 和 $Bob$ 两个人在车里可以看到窗外一辆辆行驶过的车，每辆车都有一个颜色 $c$，$Alice$ 和 $Bob$ 最开始分别选一种颜色 $A$ 和 $B~(A\neq B)$，每经过一辆车，就统计到目前为止颜色为 $A$ 的车的数量 $cnt_A(i)$ 和颜色为 $B$ 的车的数量 $cnt_B(i)$，对于经过的每一辆车：

• 如果 $cnt_A(i)>cnt_B(i)$，则 $Alice$ 获胜；
• 如果 $cnt_B(i)\geq cnt_A(i)$，则 $Bob$ 获胜；
• 否则两人平局。

$Bob$ 知道将要经过的每一辆车的颜色，现在 $Alice$ 已经选择了一种颜色 $A$，问 $Bob$ 应该选择什么颜色才能获胜？

输入

第一行包含两个整数 $n,A~(1\leq n\leq10^5,1\leq A\leq10^6)$，第二行包含 $n$ 个整数 $c_1,c_2,\cdots,c_n~(1\leq c_i\leq10^6)$。

输出

如果 $Bob$ 可以获胜，则输出他应该选择的颜色 $B~(1\leq B\leq10^6)$，否则输出 $-1$。数据保证如果 $Bob$ 可以获胜，那么在 $[1,10^6]$ 内一定存在一种颜色可以使 $Bob$ 获胜，如果有多解输出任意一组。

样例

题解

首先将所有颜色都作为可能的答案，每出现一种颜色，就将这种颜色的出现次数 $+1$，接着将所有出现次数小于 $cnt_A(i)$ 的数字删除，最后剩下来的的颜色就是答案，如果最后没有数字留下，则输出 $-1$。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <sstream>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 1000000 + 100;
struct Node {
    int cnt, num;
    Node() {}
    Node(int c, int n) {
        cnt = c;
        num = n;
    }
};
bool operator<(const Node &a, const Node &b) {
    return (a.cnt == b.cnt? a.num < b.num: a.cnt > b.cnt);
}
int n, A, c;
bool vis[maxn];
int cnt[maxn];
set<Node> st;
set<Node>::iterator it;
vector<set<Node>::iterator> vct;
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d%d", &n, &A) != EOF) {
        st.clear();
        memset(cnt, 0, sizeof(cnt));
        memset(vis, 0, sizeof(vis));
        for(int i = 1; i <= 1000000; ++i) {
            st.insert(Node(0, i));
        }
        for(int i = 0; i < n; ++i) {
            scanf("%d", &c);
            if(vis[c]) {
                continue;
            }
            it = st.find(Node(cnt[c], c));
            st.erase(it);
            ++cnt[c];
            st.insert(Node(cnt[c], c));
            it = st.upper_bound(Node(cnt[A] - 1, 0));
            vct.clear();
            for(; it != st.end(); ++it) {
                vct.push_back(it);
            }
            int len = vct.size();
            for(int i = 0; i < len; ++i) {
                vis[vct[i]->num] = true;
                st.erase(vct[i]);
            }
        }
        st.erase(Node(cnt[A], A));
        if(st.empty()) {
            printf("-1\n");
            continue;
        }
        it = st.begin();
        printf("%d\n", it->num);
    }
    return 0;
}