@Dmaxiya 2018-08-17T10:17:23.000000Z 字数 7267 阅读 996

Codeforces Round #468 (Div. 2)

Codeforces

Contests 链接：Codeforces Round #468 (Div. 2)
过题数：4
排名：287/7914

A. Friends Meeting

题意

有两个人分别站在 $x=a$ 和 $x=b$ 的位置，两个人走第 $i$ 步需要消耗 $i$ 点体力，求要使两人相遇两人的最小总体力消耗值。

输入

输入第一行为一个整数 $a~(1\leq a\leq1000)$ ，第二行为一个整数 $b~(1\leq b\leq1000)$ ，其中 $a\neq b$ 。

输出

输出最小总体力消耗。

样例

输入	输出	提示
3 4	1	第一个人往右移动一步，或者第二个人往左移动一步，两种走法需要消耗的体力总和都为 $1$ 。
101 99	2	两个人各往中间走一步，他们将会在 $x=100$ 处相遇，并且总体力消耗为 $2$ 。
5 10	9	其中一种最优的方案是：第一个人向右移动 $3$ 步，第二个人向左移动 $2$ 步，他们将在 $x=8$ 处相遇，且总消耗为 $1+2+3+1+2=9$ 。

题解

暴力从 $\min(a,b)$ 到 $\max(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
LL ans;
int a, b;
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", &a, &b) != EOF) {
        ans = INT_MAX;
        if(a > b) {
            swap(a, b);
        }
        for(int i = a; i <= b; ++i) {
            LL tmp1 = (i - a);
            tmp1 = (1 + tmp1) * tmp1 / 2;
            LL tmp2 = (b - i);
            tmp2 = (1 + tmp2) * tmp2 / 2;
            ans = min(ans, tmp1 + tmp2);
        }
        printf("%I64d\n", ans);
    }
    return 0;
}

B. World Cup

题意

世界杯的比赛按两队之间进行比赛的淘汰制，最初 $1$ 队和 $2$ 队进行比赛， $3$ 队和 $4$ 队进行比赛……获胜的队伍进入下一轮比赛， $1$ 队和 $2$ 队中的胜利队伍和 $3$ 队与 $4$ 队的获胜队伍进行比赛……不断淘汰队伍，直到剩下最后一支队伍。问第 $a$ 支队伍和第 $b$ 支队伍可能会在第几场比赛相遇。

输入

输入包含三个整数 $n,a,b~(2\leq n\leq256,1\leq a,b\leq n)$ ，数据保证在任意轮次的比赛中都会有偶数支队伍进行比赛且 $a\neq b$ 。

输出

如果 $a$ 队和 $b$ 队在总决赛之前相遇，输出他们相遇的比赛轮数，否则输出 "Final!"。

样例

输入	输出	提示
4 1 2	1
8 2 6	Final!	如果 $2$ 队和 $6$ 队在相遇之前的所有比赛都获胜，那么他们将会在第 $3$ 轮比赛中相遇，这一轮比赛是总决赛，因此应该输出 "Final"。
8 7 5	2

题解

根据比赛的队伍编号和比赛淘汰规则可以发现，每轮比赛相当于在高位相同低位不同的二进制数中选出其中一个数字，因此可以用二进制模拟，最后判断总决赛的轮数是否等于 $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;
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 round;
        for(int i = 1; i <= 20; ++i) {
            a = (a + 1) / 2;
            b = (b + 1) / 2;
            if(a == b) {
                round = i;
                break;
            }
        }
        int dig = 0;
        int nn = n;
        while(nn != 0) {
            nn >>= 1;
            ++dig;
        }
        if(round == dig - 1) {
            printf("Final!\n");
        } else {
            printf("%d\n", round);
        }
    }
    return 0;
}

C. Laboratory Work

题意

给定一个长度为 $n$ 的整数序列 $x_1,x_2,\cdots,x_n$ ，要求构造一个长度为 $n$ 的整数序列使得新序列的平均值等于原序列的平均值，新序列的最大值和最小值不能超过原序列的最大值与最小值的范围，且新序列和原序列相同数字的个数最少。

输入

输入第一行包含一个整数 $n~(1\leq n\leq10^5)$ ，第二行包含 $n$ 个整数 $x_1,x_2,\cdots,x_n~(-10^5\leq a_i\leq10^5)$ ，数据保证 $\max(a_i)-\min(a_i)\leq2,~i\in[1,n]$ 。

输出

第一行输出一个整数，表示新构造的序列和原序列相同的数字个数，第二行为 $n$ 个整数，表示新序列的每个数字，如果有多解输出任意一个。

样例

输入	输出	提示
6 -1 1 1 0 0 -1	2 0 0 0 0 0 0	原序列的平均值为 $0$ ，新序列的平均值也为 $0$ ，且两个序列只有 $2$ 个数字相同。
3 100 100 101	3 101 100 100	原序列和新序列只能完全相同，这样就有 $3$ 个数字和原序列相同。
7 -10 -9 -10 -8 -10 -9 -9	5 -10 -10 -9 -9 -9 -9 -9

题解

如果原序列的 $\max(a_i)-\min(a_i)\leq1,~i\in[1,n]$ ，则只能输出原序列，否则在以下两种方案中选择一种相同数字个数最少的：
1. 把 $\min(cnt_{Min},cnt_{Max})$ （ $cnt_{Min}$ 表示与最小值相等的数字个数， $cnt_{Max}$ 则为与最大值相等的数字个数）个最小值与最大值都转化为 $\frac{Min+Max}{2}$ ；
2. 把 $\lfloor\frac{cnt_{Mid}}{2}\rfloor$ 个中间值（ $Mid=\frac{Min+Max}{2}$ ）转化为 $Max$ 值， $\lfloor\frac{cnt_{Mid}}{2}\rfloor$ 个中间值转化为 $Min$ 值。

过题代码

#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, Min, Max;
int cnt[10];
int num[maxn], ans;
set<int> st;
set<int>::iterator it;
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) {
        st.clear();
        ans = 0;
        memset(cnt, 0, sizeof(cnt));
        for(int i = 0; i < n; ++i) {
            scanf("%d", &num[i]);
            st.insert(num[i]);
        }
        it = st.begin();
        Min = *it;
        it = st.end();
        --it;
        Max = *it;
        if(Min == Max || Max - 1 == Min) {
            printf("%d\n", n);
            for(int i = 0; i < n; ++i) {
                if(i != 0) {
                    printf(" ");
                }
                printf("%d", num[i]);
            }
            printf("\n");
            continue;
        }
        int Mid = Max - 1;
        int dx = 0;
        for(int i = 0; i < n; ++i) {
            dx += num[i] - Mid;
            ++cnt[num[i] - Min];
        }
        if(2 * min(cnt[0], cnt[2]) > cnt[1] / 2 * 2) {
            ans = min(cnt[0], cnt[2]) * 2;
            cnt[0] -= ans / 2;
            cnt[2] -= ans / 2;
            cnt[1] += ans;
        } else {
            ans = cnt[1] / 2 * 2;
            cnt[0] += ans / 2;
            cnt[2] += ans / 2;
            cnt[1] -= ans;
        }
        printf("%d\n", n - ans);
        int ccnt = 0;
        for(int i = 0; i < cnt[0]; ++i, ++ccnt) {
            if(ccnt != 0) {
                printf(" ");
            }
            printf("%d", Min);
        }
        for(int i = 0; i < cnt[1]; ++i, ++ccnt) {
            if(ccnt != 0) {
                printf(" ");
            }
            printf("%d", Mid);
        }
        for(int i = 0; i < cnt[2]; ++i, ++ccnt) {
            if(ccnt != 0) {
                printf(" ");
            }
            printf("%d", Max);
        }
        printf("\n");
    }
    return 0;
}

D. Peculiar apple-tree

题意

有一棵 $n$ 个节点 $n-1$ 条边的树，树根为 $1$ ，且在底下，树叶在顶端（也就是一棵倒过来的树），每个节点上都有一个苹果，每一秒第 $i$ 层（从下往上数）的苹果就会滚落到第 $i-1$ 层，每两个苹果滚落到同一个节点上，它们就会相互抵消，问最后能够收获到多少个苹果。

输入

第一行为一个整数 $n~(2\leq n\leq10^5)$ ，第二行为 $n-1$ 个整数 $p_2,p_3,\cdots,p_n~(1\leq p_i<i)$ ，表示第 $i$ 个几点的父节点是 $p_i$ 。

输出

输出最终能在树根收获的苹果数。

样例

输入	输出	提示
3 1 1	1
5 1 2 2 2	3
18 1 1 1 4 4 3 2 2 2 10 8 9 9 9 10 10 4	4

题解

统计每一层树上的节点数量，如果是奇数，这一层就能收获一个苹果，否则就无法收获苹果，最后求和就是答案。

过题代码

#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, p, ans;
vector<int> G[maxn];
int num[maxn];
void dfs(int x, int depth) {
    num[depth] ^= 1;
    int len = G[x].size();
    for(int i = 0; i < len; ++i) {
        int pos = G[x][i];
        dfs(pos, depth + 1);
    }
}
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) {
        ans = 0;
        for(int i = 1; i <= n; ++i) {
            G[i].clear();
            num[i] = 0;
        }
        for(int i = 2; i <= n; ++i) {
            scanf("%d", &p);
            G[p].push_back(i);
        }
        dfs(1, 1);
        for(int i = 1; i <= n; ++i) {
            ans += num[i];
        }
        printf("%d\n", ans);
    }
    return 0;
}

E. Game with String

题意

对于一个给定的字符串 $s$ ， $Kolya$ 和 $Vasya$ 在这个字符串的基础上进行一个游戏，两个人都知道最初的字符串是什么，现在 $Kolya$ 将选择一个整数 $k$ ，将字符串循环左移 $k$ 位生成一个新的字符串 $t$ ，即：将字符串 $s=s_1s_2s_3\cdots s_n$ 变为 $t=s_{k+1}s_{k+2}\cdots s_ns_1s_2\cdots s_k$ ， $Vasya$ 不知道 $k$ 的值，也不知道新的字符串 $t$ 是什么样的，但是 $Kolya$ 可以告诉 $Vasya$ 字符串 $t$ 的第一个字符， $Vasya$ 也有一次询问的机会，询问新字符串的第 $i$ 位是什么字符，问如果 $Vasya$ 采取最优的询问策略，她能通过这两个信息唯一确定 $k$ 值的概率。

输入

输入为一个只包含小写字母的字符串 $s~(3\leq|s|\leq5000)$ 。

输出

输出 $Vasya$ 能唯一确定 $k$ 值的概率，误差在 $10^{-6}$ 就认为程序正确。

样例

输入	输出	提示
technocup	1.000000000000000	不论 $k$ 为何值， $Vasya$ 只要通过询问新字符串的第二个字符，就能唯一地确定 $k$ 的值，因此概率为 $1$ 。
tictictactac	0.333333333333333	如果新字符串的第一个字符为 `t` 或者 `c`，那么 $Vasya$ 无法通过一次询问唯一地确定 $k$ 的值，如果新字符串的第一个字符为 `i` 或者 `a`， $Vasya$ 就可以通过询问新字符串的第 $4$ 个字符来唯一地确定 $k$ 的值。
bbaabaabbb	0.100000000000000

题解

定义 $num_{i,j,l}$ （这里 $l$ 仅仅是为了区别于 $k$ ）为在原字符串中，从字符 $i$ 往右 $j$ 个位置的字符为 $l$ （如果下标超过 $|s|$ 则从 $1$ 开始继续往右），只有当 $num_{i,j,l}$ 的值为 $1$ 时， $Vasya$ 才能在看到新字符串的第一个字符为 $i$ 、询问得到第 $j-1$ 个位置的字符为 $l$ 时，唯一地确定 $k$ 的值。但是由于字符 $i$ 往右移动 $j$ 位能够到达的字符 $l$ 有许多个，为了让唯一确定 $k$ 值的概率尽可能地大， $Vasya$ 应该询问向右移动 $j$ 位后，得到的唯一不同的字符 $l$ 的数量尽可能多的位置，询问这些 $j$ 的值，才可能唯一确定尽可能多的 $k$ ，最后将这些能唯一确定的字符位置个数相加，除以字符串的长度，就是能唯一确定 $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 = 5000 + 100;
char str[maxn];
int ccnt[26];
int num[30][maxn][30];
int main() {
    #ifdef LOCAL
        freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    memset(ccnt, 0, sizeof(ccnt));
    scanf("%s", str);
    int len = strlen(str);
    for(int i = 0; i < len; ++i) {
        for(int j = 1; j < len; ++j) {
            int Index = (i + j) % len;
            ++num[str[i] - 'a'][j][str[Index] - 'a'];
        }
    }
    for(int i = 0; i < 26; ++i) {
        for(int j = 1; j < len; ++j) {
            int cnt = 0;
            for(int k = 0; k < 26; ++k) {
                if(num[i][j][k] == 1) {
                    ++cnt;
                }
            }
            ccnt[i] = max(ccnt[i], cnt);
        }
    }
    int ans = 0;
    for(int i = 0; i < 26; ++i) {
        ans += ccnt[i];
    }
    printf("%.10f\n", (double)ans / len);
    return 0;
}

Codeforces Round #468 (Div. 2)

A. Friends Meeting

题意

输入

输出

样例

题解

过题代码

B. World Cup

题意

输入

输出

样例

题解

过题代码

C. Laboratory Work

题意

输入

输出

样例

题解

过题代码

D. Peculiar apple-tree

题意

输入

输出

样例

题解

过题代码

E. Game with String

题意

输入

输出

样例

题解

过题代码

内容目录