@Dmaxiya
2018-08-17T10:17:57.000000Z
字数 5976
阅读 993
Codeforces
Contests 链接:Codeforces Round #464 (Div. 2)
过题数:5
排名:236/10927
有 个没有性别区分的人编号为 到 ,每个人都有自己喜欢的人 ,问其中是否存在三角关系?如果 喜欢 , 喜欢 ,而 喜欢 ,则这三个人之间就存在三角关系。
第一行为一个整数 ,第二行为 个整数 。
如果存在三角关系,则输出 ,否则输出 ,大小写任意。
输入 | 输出 | 提示 |
---|---|---|
5 2 4 5 1 3 |
YES | 之间存在三角关系。 |
5 5 5 5 5 1 |
NO |
对于每一个 判断 是否等于 。
#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;
}
有 只仓鼠,需要买一些箱子来将这些仓鼠装起来,总共有 种箱子,每种箱子能够装下 只仓鼠,只能选择其中一种箱子,且每个箱子都必须装满仓鼠,无法装满箱子的仓鼠就会被抛弃,要使被抛弃的仓鼠的数量最少,问应该用哪一种箱子,这种箱子需要多少个。
第一行包含两个整数 ,第二行为 个整数 。
输出应该选择的箱子的编号(箱子按从 到 编号),以及需要这种箱子的数量。如果有多解输出任意一个。
输入 | 输出 |
---|---|
19 3 5 4 10 |
2 4 |
28 3 5 6 30 |
1 5 |
对每一种箱子计算能够放下的最多的仓鼠数量 ,取最大值。
#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;
}
在地球上有 个时区,以第 个时区的时间为标准时,若第一个时区的时间为 ,那么第 个时区的时间就是 对 取模后的值,由于一天中没有 时的表示方法,只有 时的表示方法,所以第 个时区的时间就是 。现在要办一场 ,所有时区的人同时开始比赛,每一个时区的人都会在自己当地的时间区间 内开始参加比赛,如果比赛开始的时间超出了这个范围,他们就不会参加这个比赛,已知第 个时区有 个人参加比赛,问应该在第 个时区的什么时间举办比赛,才能让全世界参加比赛的人最多。
第一行为一个整数 ,第二行为 个整数 ,第三行为两个整数 。
输出比赛开始的时间(标准时),如果有多个满足条件的答案,输出最小的一个。
输入 | 输出 | 提示 |
---|---|---|
3 1 2 3 1 3 |
3 | 如果在第 个时区的 时开始比赛,此时第 个时区的时间为 时,第 个时区的时间为 时,第 和第 个时区共 个人将会参加比赛。 |
5 1 2 3 4 1 1 3 |
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 <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;
}
给定两个长度为 的字符串 和 ,要将字符串 中的一些字符进行替换,使 ,如果有字符对 ,就可以将 中的 字符用 字符进行替换,反之亦然,问至少需要多少个字符对,可以将 变为 。
第一行为一个整数 ,第二行和第三行分别为字符串 和 ,两个字符串都只包含小写字母。
第一行为一个整数 ,表示最少需要的字符对数,接下去 行每行两个字符 ,表示字符 之间可以相互替换,如果有多解可以输出任意一组。
输入 | 输出 |
---|---|
3abb dad |
2 a d b a |
8drpepper cocacola |
7 l e e d d c c p p o o r r a |
将字符串 和 中所有相同位置上的字符做并查集,在同一个连通块内内字符只需要和根节点进行交换,就可以在连通块内任意地改变某个字符为另一个字符。
#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;
}
有一个集合 ,这个集合初始为空,有 次操作,每次操作可以是:
- 加入一个新的整数到集合中,这个整数一定大于当前集合中所有其他数字;
- 从当前集合中寻找一个子集 ,使得这个子集中的 的值最大。
第一行为一个整数 ,接下来 行,每行要么是 ,要么是 ,如果是 ,则将 加入到集合中,否则为一次询问。 保证满足题意,且在第一个 之前至少存在一个 操作。
对于每一次询问,输出询问的答案,误差在 以内即认为程序正确。
输入 | 输出 |
---|---|
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 |
每次询问,贪心地选择最后加入的数字作为最大值,其他数字从前往后,只要加入某个数字 能够使得所有被选中的平均值下降,就可以选择这个值,因为序列是递增的,所以越往后选择的最大值,能选择的其他的数字一定越多,所以之前选过的数字在下一次询问中一定也会被选中,因此总的复杂度可以为 。
#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;
}