Educational Codeforces Round 33

Codeforces

Contests 链接：Educational Codeforces Round 33
过题数：3
排名：813/9628

A. Chess For Three

题意

$Alex$、$Bob$ 和 $Carl$ 三个人轮流玩一个游戏，这个游戏没有平局，三个人玩游戏的规则如下：

1. 由 $Alex$ 和 $Bob$ 先进行游戏，$Carl$ 在旁边旁观；
2. 上一局游戏失败的人退出游戏，旁观下一局的比赛，上一局旁观的人继续与获胜的人进行游戏。
   现在他们进行了 $n$ 轮游戏，并记录下了每一局获胜的人，现在要求检查这个记录是否是可能出现的情况（例如上一局失败的人不可能在下一局继续进行游戏）。

输入

第一行为一个正整数 $n~(1\leq n\leq100)$，接下来 $n$ 行每行为一个整数 $a_i~(a_i\in[1,3])$，分别对应 $Alex$、$Bob$ 和 $Carl$，表示第 $i$ 局获胜的人。

输出

如果这种结果是可能出现的，输出 $YES$，否则输出 $NO$。

样例

题解

按照题意模拟，如果出现旁观者获胜的情形，就是非法的情况，否则总是合法的。

过题代码

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

B. Beautiful Divisors

题意

如果一个数字的二进制表示是由 $k$ 位连续的 $1$ 与 $k-1$ 位连续的 $0$ 组成，那么这个数字就是一个漂亮的数，换一句话说，如果一个数字能够表示成某个整数 $k$ 的 $2^k(2^k-1)$，那么它就是漂亮的数。现在给定一个整数 $n$，询问最大的能整除 $n$ 的漂亮的数。

输入

输入只包含一个整数 $n~(1\leq n\leq10^5)$。

输出

输出最大的能整数 $n$ 的漂亮的数。

样例

题解

从 $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 <algorithm>
using namespace std;
#define LL long long
int n;
int lowbit(int x) {
    return x & (-x);
}
bool judge(LL x) {
    for(int i = 1; i < 30; ++i) {
        if(x == ((1LL << i) - 1) * (1LL << (i - 1))) {
            return true;
        }
    }
    return false;
}
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        int ans;
        for(int i = n; i > 0; --i) {
            if(judge(i) && n % i == 0) {
                ans = i;
                break;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

C. Rumor

题意

$Vova$ 在玩一款游戏，这款游戏的目标是将谣言散播到所有的游戏人物，总共有 $n$ 个游戏人物，$Vova$ 每将谣言告诉给一个人物并要他把谣言告诉他的朋友，就需要 $c_i$ 的代价，$n$ 个人物中有 $m$ 对朋友，如果 $a$ 和 $b$ 是朋友，那么 $a$ 就会把谣言告诉 $b$ 并且在告诉的过程中是免费的。问 $Vova$ 要完成游戏任务所需要的最小的代价。

输入

第一行为两个整数 $n,m~(1\leq n\leq10^5,0\leq m\leq10^5)$，第二行为 $n$ 个整数 $c_1,c_2,\cdots,c_n~(0\leq c_i\leq10^9)$，接下去 $m$ 行每行两个整数 $a,b~(1\leq a,b\leq n)$，表示第 $a$ 个人和第 $b$ 个人是朋友。

输出

输出最小代价。

样例

题解

能够互相散播谣言的组成了一个连通块，只要选择每个连通块中代价最小的一个，就可以以这个代价将谣言散播到这个连通块，连通块的最小值用并查集进行维护。

过题代码

#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 <algorithm>
using namespace std;
#define LL long long
const int maxn = 100000 + 100;
int n, m, u, v;
LL ans;
int fa[maxn];
LL Min[maxn];
bool vis[maxn];
void Init() {
    for(int i = 1; i <= n; ++i) {
        fa[i] = i;
        vis[i] = false;
    }
}
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;
    Min[yy] = min(Min[xx], Min[yy]);
}
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d%d", &n, &m) != EOF) {
        ans = 0;
        Init();
        for(int i = 1; i <= n; ++i) {
            scanf("%I64d", &Min[i]);
        }
        for(int i = 0; i < m; ++i) {
            scanf("%d%d", &u, &v);
            unit(u, v);
        }
        for(int i = 1; i <= n; ++i) {
            int f = Find(i);
            if(!vis[f]) {
                vis[f] = true;
                ans += Min[f];
            }
        }
        printf("%I64d\n", ans);
    }
    return 0;
}