@Dmaxiya 2018-08-17T10:22:15.000000Z 字数 8006 阅读 1067

Educational Codeforces Round 32

Codeforces

Contests 链接：Educational Codeforces Round 32
过题数：5
排名：266/8563

A. Local Extrema

题意

给定一个长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$ ，定义极值点表示某个数字 $a_i$ 严格大于或小于它左右两边的值，即 $a_i>a_{i-1}~and~a_i>a_{i+1}$ 或者 $a_i<a_{i-1}~and~a_i<a_{i+1}$ ，第一个数字和最后一个数字一定不是极值点，统计序列中极值点的个数。

输入

第一行为一个整数 $n~(1\leq n\leq1000)$ ，第二行为 $n$ 个整数 $a_1,a_2,\cdots,a_n~(1\leq a_i\leq1000)$ 。

输出

输出序列中极值点的个数。

样例

输入	输出
3 1 2 3	0
4 1 5 2 5	2

题解

按题意从 $2$ 到 $n-1$ 跑一遍统计即可。

过题代码

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

B. Buggy Robot

题意

给机器人一个字符串指令，字符串中只包含 $U~D~L$ 和 $R$ 四种字符，分别表示上下左右四个方向，机器人的初始位置为 $(0,0)$ ，而完全正确地执行这些指令可能无法回到原点，问机器人要回到原点最多正确地执行了多少个指令。

输入

第一行为一个整数 $n~(1\leq n\leq100)$ 表示指令的长度，第二行为一个字符串 $s$ ，只包含 $U~D~L~R$ 四种字符，表示机器人接收到的指令。

输出

输出机器人最终要回到原点，最多正确地执行多少个指令。

样例

输入	输出
4 LDUR	4
5 RRRUU	0
6 LLRRRR	4

题解

统计所有字符出现的次数，分别记为 $cnt_U~cnt_D~cnt_L~cnt_R$ ，结果就是 $2\times(\min(cnt_U,cnt_D)+\min(cnt_L,cnt_R))$ 。

过题代码

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

C. K-Dominant Character

题意

如果在给定的字符串中，对于任意一个长度不小于 $k$ 的子串，都包含字符 $c$ ，那么这个字符串就是 $c$ 字符主导的字符串，现在给定一个字符串 $s$ ，要求可能满足条件的最小的 $k$ 值。

输入

输入为一个只包含小写字符的字符串 $s~(1\leq|s|\leq10^5)$ 。

输出

输出可能满足条件的最小的 $k$ 值。

样例

输入	输出
abacaba	2
zzzzz	1
abcde	3

题解

对于在字符串中出现的每一个字符，都求出它对应的 $k$ 值，取最小的那个 $k$ 就是答案，而对于每一个字符 $c$ ，求 $k$ 值的方法就是将所有距离最近的两个 $c$ ，求出它们距离的最大值，最后再对字符串的首尾做一次处理即可。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <ctime>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 100000 + 100;
char str[maxn];
int num[30], last[maxn];
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif
    ios::sync_with_stdio(false);
    while(scanf("%s", str) != EOF) {
        int len = strlen(str);
        memset(num, 0, sizeof(num));
        memset(last, -1, sizeof(last));
        for(int i = 0; str[i]; ++i) {
            int w = str[i] - 'a';
            num[w] = max(num[w], i - last[w]);
            last[w] = i;
        }
        int ans = maxn;
        for(int i = 0; i < 26; ++i) {
            if(last[i] != -1) {
                num[i] = max(num[i], len - last[i]);
                ans = min(ans, num[i]);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

D. Almost Identity Permutations

题意

如果一个 $1-n$ 的排列为 $almost~identity~permutation$ ，那么它至少有 $n-k$ 个数字满足 $p_i=i$ ，问给定 $n$ 和 $k$ ，有多少个这样的序列满足条件。

输入

输入只包含两个整数 $n~k~(4\leq n\leq1000,1\leq k\leq4)$ 。

输出

输出满足条件的序列的数量。

样例

输入	输出
4 1	1
4 2	7
5 3	31
5 4	76

题解

本题由于 $k$ 非常小，所以可以对每一个 $k$ 分类讨论穷举所有情况

当 $k=1$ 时，有 $n-1$ 个数字在原位，那么最后一个数字一定也在原位，所以只有一种情况;

当 $k=2$ 时，有 $n-2$ 个数字在原位，那么最后剩下的两个数字不在原位的情况只有一种，所有情况就是 $C_n^2$ ，在加上 $k=1$ 的情况的方案数就是答案;

当 $k=3$ 时，除了 $k\leq2$ 的情况，当有 $n-3$ 个数字在原位时，剩下 $3$ 个数字都不在原位的情况只有 $2$ 种，所以总共有 $2\times C_n^3$ 种情况；

当 $k=4$ 时，除了 $k\leq3$ 的情况，当有 $n-4$ 个数字不在原位时，剩下 $4$ 个数字不在原位的情况有 $9$ 种，所以总共有 $9\times C_n^4$ 种情况。

过题代码

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

E. Maximum Subsequence

题意

给定一个长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$ ，从中选出 $k$ 个数字，它们的下标分别为 $b_1,b_2,\cdots,b_k$ ，要使得 $\sum_{i=1}^ka_{b_i}\mod m$ 的值最大，求这个最大值。

输入

第一行为两个整数 $n$ 和 $m~(1\leq n\leq35,1\leq m\leq10^9)$ ，第二行为 $n$ 个整数 $a_1,a_2,\cdots,a_n~(1\leq a_i\leq10^9)$ 。

输出

输出答案。

样例

输入	输出	提示
4 4 5 2 4 1	3	可以选择第 $1$ 和第 $2$ 个数字，这两个数字对 $4$ 取模的值为 $3$ 。
3 20 199 41 299	19	可以选择第 $3$ 个数字。

题解

本题如果 $2^n$ 枚举每个数字选或者不选的话，总的时间复杂度为 $32^{35}\approx34\times10^9$ ，肯定要超时，但是可以将整个数组分成两部分进行 $2^{\frac{n}{2}}$ 次枚举，再对这两部分进行贪心二分求和即可，这样总的时间复杂度可以降到 $2^{\frac{n}{2}}+2^{\frac{n}{2}}+2^{\frac{n}{2}}\times\log_22^{\frac{n}{2}}=2^{\frac{n}{2}}\times(2+\frac{n}{2})\approx5\times10^6$ 。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <ctime>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 100;
int n, m, ans;
int num[maxn];
set<int> st[2];
set<int>::iterator it, itt;
void get_st(int begin, int end, set<int> &st) {
    st.clear();
    st.insert(0);
    for(int i = 0; i < (1 << (end - begin)); ++i) {
        int tmp = 0;
        for(int j = 0; j < end - begin; ++j) {
            if(((i >> j) & 1) == 1) {
                tmp = (tmp + num[j + begin]) % m;
            }
        }
        st.insert(tmp);
    }
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif
    ios::sync_with_stdio(false);
    while(scanf("%d%d", &n, &m) != EOF) {
        ans = 0;
        for(int i = 0; i < n; ++i) {
            scanf("%d", &num[i]);
        }
        get_st(0, (n + 1) / 2, st[0]);
        get_st((n + 1) / 2, n, st[1]);
        for(it = st[0].begin(); it != st[0].end(); ++it) {
            for(int i = 1; i <= 2; ++i) {
                itt = st[1].lower_bound(m * i - *it);
                if(itt != st[1].begin()) {
                    --itt;
                    ans = max(ans, (*it + *itt) % m);
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

G. Xor-MST

题意

给定一个 $n$ 个节点的完全图，每个节点的权值为 $a_i$ ，任意两个节点之间的边权值为 $a_i\bigoplus a_j$ ，求最小生成树的边权和。

输入

第一行为一个正整数 $n~(1\leq n\leq2\times10^5)$ ，第二行为 $n$ 个整数 $a_1,a_2,\cdots,a_n~(0\leq a_i<2^{30})$ 。

输出

输出最小生成树的边权和。

样例

输入	输出
5 1 2 3 4 5	8
4 1 2 3 4	8

题解

由贪心可以知道，高 $x$ 位都相同的所有数字一定先合并到同一个连通块内，再和高 $x-1$ 位相同的数字进行合并，这样得到的异或的和才能最小，因此问题转化为求解在高 $x$ 位都相同，而第 $x+1$ 位不同的情况下，两个子连通块的合并，合并的方式为：对于第 $x+1$ 位为 $0$ 的连通块内的所有数字，查找第 $x+1$ 位为 $1$ 的连通块内的所有数字的异或值最小的那一对数字，暴力是 $n^2$ 的，可以用字典树将查找优化到 $O(n)$ ，解决了两个连通块之间的连边代价计算之后，再加上两个连通块各自的子连通块（第 $x+2$ 位不同的情况）连通的代价，一直递归下去，直到某个连通块不再存在元素或者到达第 $0$ 位停止递归，总的时间复杂度为 $O(30n)$ 。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <ctime>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 200000 + 100;
const int maxcnt = 200000 * 30 + 100;
struct Tree {
    int root, cnt;
    int tree[maxcnt][2];
    int create() {
        ++cnt;
        memset(tree[cnt], 0, sizeof(tree[cnt]));
        return cnt;
    }
    void Init() {
        cnt = 0;
        root = create();
    }
    int id(int x, int Index) {
        return ((x >> Index) & 1);
    }
    void add(int x) {
        int pos = root;
        for(int i = 30; i >= 0; --i) {
            int w = id(x, i);
            if(tree[pos][w] == 0) {
                tree[pos][w] = create();
            }
            pos = tree[pos][w];
        }
    }
    int query(int x) {
        int ret = 0;
        int pos = root;
        for(int i = 30; i >= 0; --i) {
            int w = id(x, i);
            if(tree[pos][w] == 0) {
                w = !w;
                ret |= (1 << i);
            }
            pos = tree[pos][w];
        }
        return ret;
    }
};
int n;
int num[maxn];
Tree t;
LL dfs(int L, int R, int depth) {
    if(L + 1 >= R || depth == -1) {
        return 0;
    }
    LL ret = 0;
    int M = R;
    for(int i = L; i < R; ++i) {
        if(((num[i] >> depth) & 1) == 1) {
            M = i;
            break;
        }
    }
    ret += dfs(L, M, depth - 1) + dfs(M, R, depth - 1);
    if(M != L && R != M) {
        t.Init();
        for(int i = M; i < R; ++i) {
            t.add(num[i]);
        }
        int tmp = INT_MAX;
        for(int i = L; i < M; ++i) {
            tmp = min(tmp, t.query(num[i]));
        }
        ret += tmp;
    }
    return ret;
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif
    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &num[i]);
        }
        sort(num + 1, num + 1 + n);
        printf("%I64d\n", dfs(1, n + 1, 30));
    }
    return 0;
}

Educational Codeforces Round 32

A. Local Extrema

题意

输入

输出

样例

题解

过题代码

B. Buggy Robot

题意

输入

输出

样例

题解

过题代码

C. K-Dominant Character

题意

输入

输出

样例

题解

过题代码

D. Almost Identity Permutations

题意

输入

输出

样例

题解

过题代码

E. Maximum Subsequence

题意

输入

输出

样例

题解

过题代码

G. Xor-MST

题意

输入

输出

样例

题解

过题代码

内容目录