@Dmaxiya 2018-08-17T02:17:57.000000Z 字数 5976 阅读 1174

Codeforces Round #464 (Div. 2)

Codeforces

Contests 链接：Codeforces Round #464 (Div. 2)
过题数：5
排名：236/10927

A. Love Triangle

题意

有 $n$ 个没有性别区分的人编号为 $1$ 到 $n$ ，每个人都有自己喜欢的人 $f_i$ ，问其中是否存在三角关系？如果 $A$ 喜欢 $B$ ， $B$ 喜欢 $C$ ，而 $C$ 喜欢 $A$ ，则这三个人之间就存在三角关系。

输入

第一行为一个整数 $n~(2\leq n\leq5000)$ ，第二行为 $n$ 个整数 $f_1,f_2\cdots,f_n~(1\leq f_i\leq n,f_i\neq i)$ 。

输出

如果存在三角关系，则输出 $YES$ ，否则输出 $NO$ ，大小写任意。

样例

输入	输出	提示
5 2 4 5 1 3	YES	$2,4,1$ 之间存在三角关系。
5 5 5 5 5 1	NO

题解

对于每一个 $i$ 判断 $f(f(f(i)))$ 是否等于 $i$ 。

过题代码

#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>
using namespace std;
#define LL long long
const int maxn = 5000 + 100;
int n;
int f[maxn];
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        bool flag = false;
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &f[i]);
        }
        for(int i = 1; i <= n; ++i) {
            if(f[f[f[i]]] == i) {
                flag = true;
                break;
            }
        }
        if(flag) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }
    return 0;
}

B. Hamster Farm

题意

有 $n$ 只仓鼠，需要买一些箱子来将这些仓鼠装起来，总共有 $k$ 种箱子，每种箱子能够装下 $a_i$ 只仓鼠，只能选择其中一种箱子，且每个箱子都必须装满仓鼠，无法装满箱子的仓鼠就会被抛弃，要使被抛弃的仓鼠的数量最少，问应该用哪一种箱子，这种箱子需要多少个。

输入

第一行包含两个整数 $n,k~(0\leq n\leq10^{18},1\leq k\leq10^5)$ ，第二行为 $k$ 个整数 $a_1,a_2,\cdots,a_k~(1\leq a_i\leq 10^{18})$ 。

输出

输出应该选择的箱子的编号（箱子按从 $1$ 到 $k$ 编号），以及需要这种箱子的数量。如果有多解输出任意一个。

样例

输入	输出
19 3 5 4 10	2 4
28 3 5 6 30	1 5

题解

对每一种箱子计算能够放下的最多的仓鼠数量 $\lfloor\frac{n}{a_i}\rfloor\times a_i$ ，取最大值。

过题代码

#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>
using namespace std;
#define LL long long
LL n, k, num, ans, Index;
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%I64d%I64d", &n, &k) != EOF) {
        Index = 1;
        ans = (1LL << 63) - 1;
        for(int i = 1; i <= k; ++i) {
            scanf("%I64d", &num);
            if(n / num * num > n / ans * ans) {
                ans = num;
                Index = i;
            }
        }
        printf("%I64d %I64d\n", Index, n / ans);
    }
    return 0;
}

C. Convenient For Everybody

题意

在地球上有 $n$ 个时区，以第 $1$ 个时区的时间为标准时，若第一个时区的时间为 $t$ ，那么第 $i$ 个时区的时间就是 $t+i$ 对 $n$ 取模后的值，由于一天中没有 $0$ 时的表示方法，只有 $n$ 时的表示方法，所以第 $i$ 个时区的时间就是 $(t+i)\%n==0?n:(t+i)\%n$ 。现在要办一场 $Contest$ ，所有时区的人同时开始比赛，每一个时区的人都会在自己当地的时间区间 $[s,f)$ 内开始参加比赛，如果比赛开始的时间超出了这个范围，他们就不会参加这个比赛，已知第 $i$ 个时区有 $a_i$ 个人参加比赛，问应该在第 $1$ 个时区的什么时间举办比赛，才能让全世界参加比赛的人最多。

输入

第一行为一个整数 $n~(2\leq n\leq10^5)$ ，第二行为 $n$ 个整数 $a_1,a_2,\cdots,a_n~(1\leq a_i\leq10^4)$ ，第三行为两个整数 $s,f~(1\leq s<f\leq n)$ 。

输出

输出比赛开始的时间（标准时），如果有多个满足条件的答案，输出最小的一个。

样例

输入	输出	提示
3 1 2 3 1 3	3	如果在第 $1$ 个时区的 $3$ 时开始比赛，此时第 $2$ 个时区的时间为 $1$ 时，第 $3$ 个时区的时间为 $2$ 时，第 $2$ 和第 $3$ 个时区共 $5$ 个人将会参加比赛。
5 1 2 3 4 1 1 3	4	如果在第 $1$ 个时区的 $4$ 时开始比赛，第 $3$ 个时区的时间为 $1$ 时，第 $4$ 个时区的时间为 $2$ 时，两个时区共 $7$ 个人将会参加比赛。

题解

求一个长度为 $f-s$ 的区间和最大值，然后将这个区间的第一个时区的本地开始时间转化为标准时，取标准时中的最小值。

过题代码

#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 <sstream>
using namespace std;
#define LL long long
const int maxn = 200000 + 100;
int n, s, t, ans, tmp, Max;
int sum[maxn];
int change(int x) {
    x = ((s - x) % n + n) % n;
    if(x == 0) {
        x = n;
    }
    return x;
}
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        tmp = 0;
        ans = 1;
        Max = 0;
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &sum[i]);
            sum[i + n] = sum[i];
        }
        scanf("%d%d", &s, &t);
        for(int i = 1; i <= 2 * n; ++i) {
            sum[i] += sum[i - 1];
        }
        int d = t - s;
        for(int i = 0; i < n; ++i) {
            if(sum[i + d] - sum[i] > Max) {
                tmp = i;
                Max = sum[i + d] - sum[i];
                ans = change(tmp);
            } else if(sum[i + d] - sum[i] == Max) {
                if(change(i) < ans) {
                    tmp = i;
                    ans = change(tmp);
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

D. Love Rescue

题意

给定两个长度为 $n$ 的字符串 $s$ 和 $t$ ，要将字符串 $s$ 中的一些字符进行替换，使 $s=t$ ，如果有字符对 $(c_1,c_2)$ ，就可以将 $s$ 中的 $c_1$ 字符用 $c_2$ 字符进行替换，反之亦然，问至少需要多少个字符对，可以将 $s$ 变为 $t$ 。

输入

第一行为一个整数 $n~(1\leq n\leq10^5)$ ，第二行和第三行分别为字符串 $s$ 和 $t$ ，两个字符串都只包含小写字母。

输出

第一行为一个整数 $t$ ，表示最少需要的字符对数，接下去 $t$ 行每行两个字符 $c_1,c_2$ ，表示字符 $c_1,c_2$ 之间可以相互替换，如果有多解可以输出任意一组。

样例

输入	输出
3 `abb` `dad`	2 a d b a
8 `drpepper` `cocacola`	7 l e e d d c c p p o o r r a

题解

将字符串 $s$ 和 $t$ 中所有相同位置上的字符做并查集，在同一个连通块内内字符只需要和根节点进行交换，就可以在连通块内任意地改变某个字符为另一个字符。

过题代码

#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 <sstream>
using namespace std;
#define LL long long
const int maxn = 100000 + 100;
int n, cnt;
char str1[maxn], str2[maxn];
int fa[30];
vector<int> G[30];
void Init()  {
    for(int i = 0; i < 26; ++i) {
        fa[i] = i;
        G[i].clear();
    }
}
int Find(int x) {
    return (x == fa[x]? x: fa[x] = Find(fa[x]));
}
void unit(int x, int y) {
    int xx = Find(x);
    int yy = Find(y);
    fa[xx] = yy;
}
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d%s%s", &n, str1, str2) != EOF) {
        cnt = 0;
        Init();
        for(int i = 0; i < n; ++i) {
            unit(str1[i] - 'a', str2[i] - 'a');
        }
        for(int i = 0; i < 26; ++i) {
            if(Find(i) != i) {
                G[Find(i)].push_back(i);
                ++cnt;
            }
        }
        printf("%d\n", cnt);
        for(int i = 0; i < 26; ++i) {
            int len = G[i].size();
            if(len == 0) {
                continue;
            }
            for(int j = 0; j < len; ++j) {
                printf("%c %c\n", 'a' + i, 'a' + G[i][j]);
            }
        }
    }
    return 0;
}

E. Maximize!

题意

有一个集合 $S$ ，这个集合初始为空，有 $Q$ 次操作，每次操作可以是：

加入一个新的整数到集合中，这个整数一定大于当前集合中所有其他数字；

从当前集合中寻找一个子集 $s$ ，使得这个子集中的 $Max(s)-Mean(s)$ 的值最大。

输入

第一行为一个整数 $Q~(1\leq Q\leq5\times10^5)$ ，接下来 $Q$ 行，每行要么是 $1~x~(1\leq x\leq10^9)$ ，要么是 $2$ ，如果是 $1~x$ ，则将 $x$ 加入到集合中，否则为一次询问。 $x$ 保证满足题意，且在第一个 $2$ 之前至少存在一个 $1$ 操作。

输出

对于每一次询问，输出询问的答案，误差在 $10^{-6}$ 以内即认为程序正确。

样例

输入	输出
6 1 3 2 1 4 2 1 8 2	0.0000000000 0.5000000000 3.0000000000
4 1 1 1 4 1 5 2	2.0000000000

题解

每次询问，贪心地选择最后加入的数字作为最大值，其他数字从前往后，只要加入某个数字 $x$ 能够使得所有被选中的平均值下降，就可以选择这个值，因为序列是递增的，所以越往后选择的最大值，能选择的其他的数字一定越多，所以之前选过的数字在下一次询问中一定也会被选中，因此总的复杂度可以为 $O(n)$ 。

过题代码

#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 <sstream>
using namespace std;
#define LL long long
const int maxn = 500000 + 100;
int n, command, cnt, Index;
double sum;
double num[maxn];
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        Index= 0;
        cnt = 0;
        double sum = 0;
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &command);
            if(command == 1) {
                ++cnt;
                scanf("%lf", &num[cnt]);
            } else {
                while((sum + num[cnt]) / (Index + 1) > num[Index + 1]) {
                    ++Index;
                    sum += num[Index];
                }
                printf("%.10f\n", num[cnt] - (sum + num[cnt]) / (Index + 1));
            }
        }
    }
    return 0;
}

Codeforces Round #464 (Div. 2)

A. Love Triangle

题意

输入

输出

样例

题解

过题代码

B. Hamster Farm

题意

输入

输出

样例

题解

过题代码

C. Convenient For Everybody

题意

输入

输出

样例

题解

过题代码

D. Love Rescue

题意

输入

输出

样例

题解

过题代码

E. Maximize!

题意

输入

输出

样例

题解

过题代码

内容目录