Educational Codeforces Round 35

Codeforces

Contests 链接：Educational Codeforces Round 35
过题数：5
排名：116/9081

A. Nearest Minimums

题意

给定一个长度为 $n$ 的序列，找到所有数字 $a_i$ 中的最小值，找到所有等于最小值的两个值中，距离最近的两个数字，输出这个距离。数据保证至少有两个最小值。

数据范围

$2\leq n\leq10^5\\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 = 100000 + 100;
int n;
int Min;
int 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) {
        Min = INT_MAX;
        for(int i = 0; i < n; ++i) {
            scanf("%d", &num[i]);
            Min = min(Min, num[i]);
        }
        int dis = INT_MAX;
        int last = -200000;
        for(int i = 0; i < n; ++i) {
            if(num[i] == Min) {
                dis = min(dis, i - last);
                last = i;
            }
        }
        printf("%d\n", dis);
    }
    return 0;
}

B. Two Cakes

题意

有两块蛋糕，分别被切成 $a$ 片与 $b$ 片，要放到 $n$ 个盘子里，使得每个盘子里只能有一种蛋糕，每片蛋糕至少被放在一个盘子里，要让所有盘子中的蛋糕片数的最小值最大，输出这个最大值 $x$。

数据范围

$1\leq a,b\leq100,2\leq n\leq a+b$

题解

因为要保证每片蛋糕都被放在一个盘子里，所以让 $a$ 作为片数小的那个，从 $a$ 到 $0$ 遍历最小值，每次判断该最小值是否成立，都先放 $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
int n, a, b;
bool judge(int least, int aa, int bb) {
    int i;
    for(i = 0; i < n; ++i) {
        if(aa >= least) {
            aa -= least;
        } else if(bb >= least) {
            bb -= least;
        } else {
            break;
        }
    }
    return i == n;
}
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 ans = 0;
        if(a > b) {
            swap(a, b);
        }
        for(int i = a; i >= 0; --i) {
            if(judge(i, a, b)) {
                ans = i;
                break;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

C. Three Garlands

题意

有三种霓虹灯，第 $i$ 种霓虹灯每 $k_i$ 秒亮一次，问，如果给定 $k_i$，能否找到三个打开这三种灯的时间点，使得最后一盏灯被打开后，每一秒都至少有一盏灯在发亮。

数据范围

$1\leq k_i\leq1500$

题解

因为有三盏灯要轮流发亮，所以如果三盏灯的间隔时间 $k_i$ 都大于 $3$，则必然找不到任何的方式使得每一秒都至少有一盏灯在发亮，对于不大于 $3$ 的情况，暴力枚举判断即可。

过题代码

#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 = 50;
int k1, k2, k3;
bool flag;
bool lit[maxn];
bool judge(int a, int b, int c) {
    int aa = a;
    int bb = b;
    int cc = c;
    memset(lit, 0, sizeof(lit));
    while(aa < maxn) {
        lit[aa] = true;
        aa += k1;
    }
    while(bb < maxn) {
        lit[bb] = true;
        bb += k2;
    }
    while(cc < maxn) {
        lit[cc] = true;
        cc += k3;
    }
    for(int i = max(a, max(b, c)); i < maxn; ++i) {
        if(!lit[i]) {
            return false;
        }
    }
    return true;
}
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", &k1, &k2, &k3) != EOF) {
        if(k1 >= 4 && k2 >= 4 && k3 >= 4) {
            printf("NO\n");
            continue;
        }
        flag = false;
        for(int i = 1; i <= 5; ++i) {
            for(int j = 1; j <= 5; ++j) {
                for(int k = 1; k <= 5; ++k) {
                    if(judge(i, j, k)) {
                        flag = true;
                        break;
                    }
                }
                if(flag) {
                    break;
                }
            }
            if(flag) {
                break;
            }
        }
        if(flag) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }
    return 0;
}

D. Inversion Counting

题意

给定一个长度为 $n$ 的全排列 $a_i$，有 $m$ 次操作，每次操作给定区间 $[l,r]$，将序列从 $l$ 到 $r$ 反转，求每次操作后，序列逆序对的奇偶性。

数据范围

$1\leq n\leq1500,1\leq m\leq2\times10^5\\1\leq a_i\leq n,1\leq l_i\leq r_i\leq n$

题解

改变任意两个数字的的位置，只看这两个数字的话，整体的逆序对奇偶性改变，将 $[l,r]$ 区间上的所有数字反转，则逆序对改变的次数为 $\frac{(len-1)\times len}{2}$，其中 $len$ 为反转长度，即 $r-l+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 = 2000;
int n, flag, m, l, r;
int 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) {
        flag = 0;
        for(int i = 0; i < n; ++i) {
            scanf("%d", &num[i]);
            for(int j = 0; j < i; ++j) {
                if(num[j] > num[i]) {
                    ++flag;
                }
            }
        }
        flag %= 2;
        scanf("%d", &m);
        for(int i = 0; i < m; ++i) {
            scanf("%d%d", &l, &r);
            LL tmp = r - l + 1;
            if((tmp - 1) * tmp / 2 % 2 == 1) {
                flag = 1 - flag;
            }
            if(!flag) {
                printf("even\n");
            } else {
                printf("odd\n");
            }
        }
    }
    return 0;
}

E. Stack Sorting

题意

如果一个序列，可以通过进栈出栈操作达到非递减的状态，那么这个序列就是“可栈排序”的序列。现在有一个长度为 $n$ 的排列，给出前 $k$ 个数字 $p_i$，如果能够在这 $k$ 个数字后将这个排列补全，使这个排列成为一个“可栈排序”序列，则该问题有解，输出字典序最大的那个解，否则输出 $-1$。

数据范围

$2\leq n\leq200000,1\leq k\leq n,1\leq p_i\leq n$

题解

先对前 $k$ 个数字用“栈排序”跑一遍，在栈内则存了一个不可“栈排序”的序列，这个序列一定由多个连续的递减序列拼成，从后往前扫一遍这个栈，每当碰到一个数字，就将小于这个数字的，没有出现过的数字添加按从大到小添加到原序列尾部。

过题代码

#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, k, cnt, Index;
bool vis[maxn];
int num[maxn];
int sta[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", &n, &k) != EOF) {
        cnt = 0;
        Index = 1;
        memset(vis, 0, sizeof(vis));
        for(int i = 0; i < k; ++i) {
            scanf("%d", &num[i]);
            vis[num[i]] = true;
            sta[cnt++] = num[i];
            while(cnt != 0 && sta[cnt - 1] == Index) {
                ++Index;
                --cnt;
            }
        }
        for(int i = cnt - 1; i >= 0; --i) {
            int tmp = sta[i] - 1;
            while(tmp > 0 && !vis[tmp]) {
                num[k++] = tmp;
                --tmp;
            }
        }
        int tmp = n;
        while(tmp > 0 && !vis[tmp]) {
            num[k++] = tmp;
            --tmp;
        }
        cnt = 0;
        Index = 1;
        for(int i = 0; i < n; ++i) {
            sta[cnt++] = num[i];
            while(cnt != 0 && sta[cnt - 1] == Index) {
                ++Index;
                --cnt;
            }
        }
        if(cnt == 0) {
            for(int i = 0; i < n; ++i) {
                if(i != 0) {
                    printf(" ");
                }
                printf("%d", num[i]);
            }
            printf("\n");
        } else {
            printf("-1\n");
        }
    }
    return 0;
}