@Dmaxiya 2018-08-17T10:21:46.000000Z 字数 10714 阅读 1021

Codeforces Round #496 (Div. 3)

Codeforces

Contests 链接：Codeforces Round #496 (Div. 3)
过题数：5
排名：237/7632

A. Tanya and Stairways

题意

$Tanya$ 在上楼梯的时候会一阶一阶地数，当她上一个 $5$ 阶的楼梯时，她会数 $1~2~3~4~5$ ，到达第二层时，她会同样地一阶一阶地数上去，现在已经知道她数的 $n$ 个数字，问她走的每一层有多少个台阶。

输入

第一行为一个整数 $n~(1\leq n\leq1000)$ ，第二行为 $n$ 个整数 $a_1,a_2,\cdots,a_n~(1\leq a_i\leq1000)$ ，表示 $Tanya$ 数的每个数字，数据保证合法。

输出

第一行为一个整数 $t$ ，表示 $Tanya$ 上的楼层数，第二行为 $t$ 个整数 $b_1,b_2,\cdots,b_n$ ，表示 $Tanya$ 上的每层的台阶数量。

样例

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

题解

每次数到 $1$ 的时候，输出 $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, cnt;
int num[maxn], ans[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) {
        cnt = 0;
        for(int i = 0; i < n; ++i) {
            scanf("%d", &num[i]);
        }
        num[n] = 1;
        for(int i = 0; i < n; ++i) {
            if(num[i + 1] <= num[i]) {
                ans[cnt++] = num[i];
            }
        }
        printf("%d\n", cnt);
        for(int i = 0; i < cnt; ++i) {
            if(i != 0) {
                printf(" ");
            }
            printf("%d", ans[i]);
        }
        printf("\n");
    }
    return 0;
}

B. Delete from the Left

题意

给定两个字符串 $s$ 和 $t$ ，问至少将这两个字符串从前面往后面删掉多少个字符，才能使得两个字符串相等，空字符串与空字符串也是相等的。

输入

输入为两行字符串 $s$ 和 $t~(1\leq|s|,|t|\leq2\times10^5)$ ，且两个字符串都只包含小写字母。

输出

输出最少需要删除的前缀字符数量。

样例

输入	输出	提示
test west	2	应该将两个字符串都删除到只剩下 $est$ ，这样需要删除 $2$ 个字符。
codeforces yes	9	应该将两个字符串都删除到只剩下 $es$ ，第一个字符串被删了 $8$ 个字符而第二个字符串被删了 $1$ 个字符。
test yes	7	应该将两个字符串都删除到空，总共要删除 $7$ 个字符。
b ab	1	删除掉第二个字符串的 $a$ ，就可以让两个字符串相等。

题解

从后往前找两个字符串的最长公共后缀，如果后缀长度为 $len$ ，最少需要删除的字符数量就是 $|s|+|t|-2\times len$ 。

过题代码

#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;
int len1, len2;
char s[maxn], t[maxn];
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif
    ios::sync_with_stdio(false);
    while(scanf("%s%s", s, t) != EOF) {
        len1 = strlen(s);
        len2 = strlen(t);
        int Min = min(len1, len2);
        int ans = Min;
        for(int i = 1; i <= Min; ++i) {
            if(s[len1 - i] != t[len2 - i]) {
                ans = i - 1;
                break;
            }
        }
        printf("%d\n", len1 + len2 - ans * 2);
    }
    return 0;
}

C. Summarize to the Power of Two

题意

定义一个长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$ 为好的序列，当且仅当对于序列中的每一个整数 $a_i$ ，都可以找到一个对应的数字 $a_j~(i\neq j)$ ，使得 $a_i+a_j$ 是 $2$ 的整数次幂，一个空的序列也是一个好的序列。现在给定一个长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$ ，问最少删除多少个数字，可以使这个序列成为一个好的序列。

输入

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

输出

输出最少要删除的数字个数。

样例

输入	输出	提示
6 4 7 1 5 4 9	1	删除第 $4$ 个数字 $5$ ，剩下的序列 $[4,7,1,4,9]$ 就是一个好的序列。
5 1 2 3 4 5	2
1 16	1
4 1 1 1 1023	0

题解

对于序列中的每个数字，都枚举 $2^x~(0\leq x\leq32)$ ，查找序列中是否存在另一个数字等于 $2^x-a_i$ ，如果存在，则这个数字不需要删除，否则就需要删除这个数字，统计需要删除的数字个数。

过题代码

#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 = 120000 + 100;
int n;
LL num[maxn], two[50];
set<LL> st;
map<LL, int> mp;
map<LL, int>::iterator it, itt;
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif
    ios::sync_with_stdio(false);
    for(int i = 0; i <= 31; ++i) {
        two[i] = (1LL << i);
    }
    while(scanf("%d", &n) != EOF) {
        mp.clear();
        st.clear();
        for(int i = 0; i < n; ++i) {
            scanf("%I64d", &num[i]);
            ++mp[num[i]];
        }
        for(it = mp.begin(); it != mp.end(); ++it) {
            for(int j = 0; j <= 31; ++j) {
                itt = mp.find(two[j] - it->first);
                if(itt != mp.end()) {
                    if(itt->first != it->first) {
                        st.insert(it->first);
                        break;
                    } else {
                        if(itt->second != 1) {
                            st.insert(it->first);
                            break;
                        }
                    }
                }
            }
        }
        int ans = 0;
        for(it = mp.begin(); it != mp.end(); ++it) {
            if(st.find(it->first) == st.end()) {
                ans += it->second;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

D. Polycarp and Div 3

题意

给定一个大整数，将这个大整数进行分割，使得被分割的每一部分除了 $0$ 以外都不含前导零，且都能被 $3$ 整除，问最多能分割成多少部分。

输入

输入为一个正整数 $s$ ， $s$ 的长度在 $1$ 到 $2\times10^5$ 之间，最左边的数字保证不为 $0$ 。

输出

输出能够切割的合法的最大段数。

样例

输入	输出	提示
3121	2	一种合法的切割方式为 $3\|12\|1$
6	1	一位数字无法切割，且这个数字能被 $3$ 整除，所以答案为 $1$ 。
1000000000000000000000000000000000	33	应该在每位数字之间进行分割，这样将会得到一个 $1$ 以及 $33$ 个 $0$ 。
201920181	4	一种合法的分割为 $2\|0\|1\|9\|201\|81$ ，其中有 $4$ 段数字能够被 $3$ 整除。

题解

先将每位数字对 $3$ 取模后得到一个新的数字串，然后从前往后进行贪心，只要碰到 $0~12~21~111~222$ ，就直接进行分割，就能得到最优解。

过题代码

#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;
int len, ans;
int num[maxn];
char str[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) {
        len = strlen(str);
        for(int i = 0; i < len; ++i) {
            num[i] = (str[i] - '0') % 3;
        }
        ans = 0;
        for(int i = 0; i < len; ++i) {
            if(num[i] == 0) {
                ++ans;
                continue;
            }
            if(i + 1 < len && num[i] == 2 && num[i + 1] == 1) {
                ++ans;
                ++i;
                continue;
            }
            if(i + 1 < len && num[i] == 1 && num[i + 1] == 2) {
                ++ans;
                ++i;
                continue;
            }
            if(i + 2 < len && num[i] == 1 && num[i + 1] == 1 && num[i + 2] == 1) {
                ++ans;
                i += 2;
            }
            if(i + 2 < len && num[i] == 2 && num[i + 1] == 2 && num[i + 2] == 2) {
                ++ans;
                i += 2;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

E1. Median on Segments (Permutations Edition)

题意

给定一个 $1-n$ 的排列 $p_1,p_2.\cdots,p_n$ ，问这个序列有多少个区间满足中位数等于 $m$ 的条件。
其中中位数的定义为：对于长度为奇数的序列，将这个序列按从小到大排序后中间的数字就是中位数，对于长度为偶数的序列，将这个序列按从小到大排序后，取中间两个数中小的那个数就是中位数。

输入

第一行为两个整数 $n,m~(1\leq n\leq2\times10^5,1\leq m\leq n)$ ，第二行为 $1-n$ 的排列 $p_1,p_2,\cdots,p_n$ 。

输出

输出满足条件的区间的个数。

样例

输入	输出	提示
5 4 2 4 5 3 1	4	满足条件的区间为： $[1,3],[2,2],[2,3]$ 和 $[2,4]$ .
5 5 1 2 3 4 5	1
15 8 1 15 2 14 3 13 4 8 12 5 11 6 10 7 9	48

题解

所有满足条件的区间一定都包含数字 $m$ ，所以这些区间的左端点一定在 $m$ 左边，右端点一定在 $m$ 的右边，先统计 $m$ 的右边 $cnt_{cnt_{a_i<m}-cnt_{a_i>m},r}$ 的值，再对于 $m$ 的左边的每个端点，计算有多少个右端点满足 $cnt_{cnt_{a_i>m}-cnt_{a_i<m},l}=cnt_{cnt_{a_i<m}-cnt_{a_i>m},r}$ （区间长度为奇数的情况）以及 $cnt_{cnt_{a_i>m}-cnt_{a_i<m}-1,l}=cnt_{cnt_{a_i<m}-cnt_{a_i>m},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 = 200000 + 100;
int n, m, Index;
int num[maxn], cnt[2];
map<int, 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%d", &n, &m) != EOF) {
        mp.clear();
        memset(cnt, 0, sizeof(cnt));
        ++mp[0];
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &num[i]);
            if(num[i] == m) {
                Index = i;
            }
            if(num[i] > m) {
                num[i] = 1;
            } else {
                num[i] = 0;
            }
        }
        for(int i = Index + 1; i <= n; ++i) {
            ++cnt[num[i]];
            ++mp[cnt[0] - cnt[1]];
        }
        memset(cnt, 0, sizeof(cnt));
        LL ans = mp[0] + mp[-1];
        for(int i = Index - 1; i > 0; --i) {
            ++cnt[num[i]];
            if(mp.find(cnt[1] - cnt[0]) != mp.end()) {
                ans += mp[cnt[1] - cnt[0]];
            }
            if(mp.find(cnt[1] - cnt[0] - 1) != mp.end()) {
                ans += mp[cnt[1] - cnt[0] - 1];
            }
        }
        printf("%I64d\n", ans);
    }
    return 0;
}

E2. Median on Segments (General Case Edition)

题意

给定一个长度为 $n$ 的序列 $a_1,a_2.\cdots,a_n$ ，问这个序列有多少个区间满足中位数等于 $m$ 的条件。中位数的定义同 E1 题。

输入

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

输出

输出满足条件的区间的个数。

样例

输入	输出	提示
5 4 1 4 5 60 4	8	满足条件的区间为： $[1,3],[1,4],[1,5],[2,2],[2,3],[2,5],[4,5],[5,5]$ 。
3 1 1 1 1	6
15 2 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3	97

题解

如果将所有大于等于 $m$ 的数字标记为 $1$ ，所有小于 $m$ 的数字标记为 $-1$ ，那么对于任意一个区间，这个区间的中位数大于等于 $m$ 当且仅当区间和大于 $0$ ，对 $m+1$ 做相同的操作，则答案为 $cnt_{mid\geq m}-cnt_{mid\geq m+1}$ 。
求解 $cnt_{mid\geq m}$ 的方法为：对这个只包含 $1$ 和 $-1$ 的数组，从前往后扫描，扫描到第 $i$ 个数字的前缀和 $sum_i$ 时，统计有多少个 $j$ 满足条件 $sum_i-sum_j>0$ ，即有多少个区间和大于 $0$ ，统计满足条件的前缀和个数可以用树状数组维护。

过题代码

#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;
LL n, m, nn, Sum;
LL num[maxn], numtmp[maxn];
LL sum[maxn << 1];
int id(int x) {
    return x + maxn;
}
int lowbit(int x) {
    return x & (-x);
}
void update(int Index, int x) {
    while(Index <= nn) {
        sum[Index] += x;
        Index += lowbit(Index);
    }
}
int query(int Index) {
    int ret = 0;
    while(Index != 0) {
        ret += sum[Index];
        Index -= lowbit(Index);
    }
    return ret;
}
LL solve(LL m) {
    memset(sum, 0, sizeof(sum));
    LL ret = 0;
    Sum = 0;
    update(id(0), 1);
    for(int i = 1; i <= n; ++i) {
        int tmp = 1;
        if(num[i] < m) {
            tmp = -1;
        }
        Sum += tmp;
        ret += query(id(Sum) - 1);
        update(id(Sum), 1);
    }
    return ret;
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif
    ios::sync_with_stdio(false);
    nn = maxn * 2 - 1;
    while(scanf("%I64d%I64d", &n, &m) != EOF) {
        for(int i = 1; i <= n; ++i) {
            scanf("%I64d", &num[i]);
        }
        printf("%I64d\n", solve(m) - solve(m + 1));
    }
    return 0;
}

F. Berland and the Shortest Paths

题意

在一个 $n$ 个节点 $m$ 条边的无向图中，选出 $n-1$ 条边，使得这些边能构成一个节点为 $n$ 的树，假设树上每个节点到节点 $1$ 的最短路为 $d_i$ ，则要使构造出来的树满足 $\sum_{i=2}^nd_i$ 最小，输出 $k$ 中选边的方案，如果总的合法方案数少于 $k$ 种，则直接输出所有方案。

输入

第一行为三个整数 $n,m,k~(2\leq n\leq2\times10^5,n−1\leq m\leq2\times10^5,1\leq k\leq2\times10^5)$ ，接下去 $m$ 行每行两个整数 $u,v~(1\leq u,v\leq n,u\neq v)$ ，表示图上的 $m$ 条边，图保证连通。

输出

第一行为将要输出的方案数 $t$ ，如果总的方案数大于 $k$ ，则只要输出任意 $k$ 个方案，否则输出所有方案，接下去 $t$ 行每行为一个 $01$ 字符串，第 $i$ 位为 $0$ 表示不选第 $i$ 条边，为 $1$ 表示选择这条边，数据保证 $m\times k\leq10^6$ 。

样例

输入	输出
4 4 3 1 2 2 3 1 4 4 3	2 1110 1011
4 6 3 1 2 2 3 1 4 4 3 2 4 1 3	1 101001
5 6 2 1 2 1 3 2 4 2 5 3 4 3 5	2 111100 110110

题解

首先对这张图从 $1$ 开始进行一次 $bfs$ ，计算每个点到达 $1$ 的最短距离 $dis_i$ ，对于第 $i$ 个节点，查找与其相连的所有节点中， $dis_j=dis_i-1$ 的节点，这些节点一定可以作为节点 $i$ 的父节点（在生成的树中），每个节点的前缀节点个数为 $cnt_i$ ，则所有的方案数为 $\prod_{i=2}^ncnt_i$ ，注意所有方案数可能会爆 $long~long$ 。

过题代码

#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 maxm = 1000000 + 100;
struct Node {
    int pos, Index;
    Node() {}
    Node(int p, int I) {
        pos = p;
        Index = I;
    }
};
int INF;
LL ans;
int n, m, k, u, v;
int dis[maxn];
char str[maxm];
vector<Node> G[maxn], pre[maxn];
queue<int> que;
void bfs() {
    dis[1] = 0;
    que.push(1);
    while(!que.empty()) {
        int tmp = que.front();
        que.pop();
        int len = G[tmp].size();
        for(int i = 0; i < len; ++i) {
            int pos = G[tmp][i].pos;
            if(dis[pos] == INF) {
                dis[pos] = dis[tmp] + 1;
                que.push(pos);
            }
        }
    }
}
void dfs(int depth) {
    if(depth == n + 1) {
        printf("%s\n", str + 1);
        --ans;
        return ;
    }
    int len = pre[depth].size();
    for(int i = 0; i < len; ++i) {
        str[pre[depth][i].Index] = '1';
        dfs(depth + 1);
        str[pre[depth][i].Index] = '0';
        if(ans <= 0) {
            return ;
        }
    }
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif
    ios::sync_with_stdio(false);
    memset(&INF, 0x3f, sizeof(INF));
    while(scanf("%d%d%d", &n, &m, &k) != EOF) {
        ans = 1;
        memset(str, '0', sizeof(str));
        str[m + 1] = '\0';
        for(int i = 1; i <= n; ++i) {
            dis[i] = INF;
            G[i].clear();
            pre[i].clear();
        }
        for(int i = 1; i <= m; ++i) {
            scanf("%d%d", &u, &v);
            G[u].push_back(Node(v, i));
            G[v].push_back(Node(u, i));
        }
        bfs();
        for(int i = 2; i <= n; ++i) {
            int len = G[i].size();
            for(int j = 0; j < len; ++j) {
                int pos = G[i][j].pos;
                if(dis[pos] == dis[i] - 1) {
                    pre[i].push_back(Node(pos, G[i][j].Index));
                }
            }
        }
        for(int i = 2; i <= n; ++i) {
            ans *= (LL)pre[i].size();
            if(ans > k) {
                ans = k;
                break;
            }
        }
        ans = min(ans, (LL)k);
        printf("%I64d\n", ans);
        dfs(2);
    }
    return 0;
}

Codeforces Round #496 (Div. 3)

A. Tanya and Stairways

题意

输入

输出

样例

题解

过题代码

B. Delete from the Left

题意

输入

输出

样例

题解

过题代码

C. Summarize to the Power of Two

题意

输入

输出

样例

题解

过题代码

D. Polycarp and Div 3

题意

输入

输出

样例

题解

过题代码

E1. Median on Segments (Permutations Edition)

题意

输入

输出

样例

题解

过题代码

E2. Median on Segments (General Case Edition)

题意

输入

输出

样例

题解

过题代码

F. Berland and the Shortest Paths

题意

输入

输出

样例

题解

过题代码

内容目录