Codeforces Round #445 (Div. 2)

Codeforces

Contests 链接：Codeforces Round #445 (Div. 2)
过题数：3
排名：315/5849

A. ACM ICPC

题意

给定 $6$ 个数字，问是否存在一种平分的方式，使得其中 $3$ 个数的和等于另外 $3$ 个数的和。

输入

输入包含 $6$ 个整数 $a_1,a_2\cdots,a_6~(0\leq a_i\leq1000)$。

输出

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

样例

题解

生成 $6$ 个数字的全排列，对于每一种排列，判断前 $3$ 个数字的和的 $2$ 倍是否等于 $6$ 个数字的和。

过题代码

#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 = 100;
int num[maxn];
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif
    ios::sync_with_stdio(false);
    while(scanf("%d", &num[0]) != EOF) {
        bool flag = false;
        int sum = num[0];
        for(int i = 1; i < 6; ++i) {
            scanf("%d", &num[i]);
            sum += num[i];
        }
        sort(num, num + 6);
        do {
            int tmp = 0;
            for(int i = 0; i < 3; ++i) {
                tmp += num[i];
            }
            if(tmp * 2 == sum) {
                flag = true;
                break;
            }
        } while(next_permutation(num, num + 6));
        if(flag) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }
    return 0;
}

B. Vlad and Cafes

题意

给定一个长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$，在序列中查找一个数字，要求每个其他数字最后一次出现的位置都在这个数字最后一次出现的位置之后。

输入

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

输出

输出满足条件的数字。

样例

题解

先将所有数字都放入一个 $set$ 当中，再从后往前从 $set$ 中删除数字，当 $set$ 为空时，说明所有数字的最后一次出现的位置都已经扫到，最后一个被删除的数字就是答案。

过题代码

#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, ans;
int num[maxn];
set<int> st;
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) {
        st.clear();
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &num[i]);
            st.insert(num[i]);
        }
        for(int i = n; i > 0; --i) {
            st.erase(num[i]);
            if(st.empty()) {
                ans = num[i];
                break;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

C. Petya and Catacombs

题意

$Petya$ 在一个有 $n$ 个节点的地下墓穴中探险，节点与节点之间存在通道，有些通道可能是连接到同一个节点上的，$Petya$ 经过每条通道的时间都是一分钟，在探险的过程中，$Petya$ 会在自己的笔记本上按下面的规则做笔记：

1. 如果 $Petya$ 在第 $i$ 分钟到达某个节点，而他之前已经到达过这个节点，就会在笔记本上的第 $i$ 个位置记下上次到达这个节点的时间 $t_i$，而将到达这个节点的时间更新为 $i$；
2. 如果 $Petya$ 到达了一个之前从未到达过的节点，他就会记下任何一个小于当前时间 $i$ 的正整数为 $t_i$。

最开始（第 $0$ 分钟） $Petya$ 在任意一个节点上，且他不会记录下 $t_0$，$Petya$ 探险结束后就扔下了他的笔记本，而 $Vasya$ 捡到了他的笔记本，$Vasya$ 想知道在按照上面的规则记录数字的情况下，$Petya$ 最少走到了多少个节点。

输入

第一行为一个整数 $n~(1\leq n\leq2\times10^5)$，表示 $Petya$ 在笔记本上记录下的数字个数，第二行为 $n$ 个整数 $t_1,t_2,\cdots,t_n~(0\leq t_i<i)$。

输出

输出一个整数，表示 $Petya$ 最少可能经过的节点数。

样例

题解

对于每次记录，贪心地能够回到已经到达过的节点就让 $Petya$ 回去，而判断已经到达过的节点的方式，就是判断在经过的洞穴中，存在上一次到达时间等于 $t_i$ 的数字，并将这个数字更新为 $i$，用 $set$ 来实现会方便很多，最终的答案就是 $set$ 的大小。

过题代码

#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
int n, num;
set<int> st;
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) {
        st.clear();
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &num);
            st.erase(num);
            st.insert(i);
        }
        printf("%d\n", (int)st.size());
    }
    return 0;
}

D. Restoration of string

题意

如果一个字符串在另一个字符串中出现的次数是最多的，那么这个字符串就是最频繁子串，现在给定 $n$ 个字符串，$s_1,s_2,\cdots,s_n$，要求构造一个字符串，使得每一个 $s_i$ 都是构造出来的字符串的最频繁字串。

输入

第一行为一个整数 $n~(1\leq n\leq10^5)$，接下去 $n$ 行每行为一个字符串 $s_1,s_2,\cdots,s_n~(\sum_{i=1}^n|s_i|\leq10^5)$。

输出

输出满足条件的字符串，如果有多个答案则输出长度最小的字符串，如果仍然有多个，则输出字典序最小的字符串。

样例

题解

对于每个给出的字符串，在任意两个相邻字符之间连一条有向边，这样所有的字符串就可以连接成一张有向图，而这张有向图必须为一条链：

1. 如果有向图存在环则无论多长的字符串都无法满足条件，例如 "ab" 和 "ba"，构造出的字符串无论有多长，其中一个子串出现的次数总是比另一个大 $1$；
2. 如果有向图存在岔路，则无法构造出该字符串或者有一个字符重复出现的情况，如 "ab" 和 "ac"，无论是 "abc" 或是 "acb" 都无法满足条件，而 "abac" 将使得 "ab" 和 "ac" 都不是最频繁子串，"a" 才是最频繁子串。
   在满足构造出的有向图是一条链的情况下，按照字典序输出答案即可。

过题代码

#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 = 100000 + 100;
const int maxm = 30;
int n;
int degin[maxm], degout[maxm];
bool head[maxm];
char str[maxn];
bool G[maxm][maxm];
queue<int> que;
int id(char ch) {
    return ch - 'a';
}
bool topsort() {
    for(int i = 0; i < 26; ++i) {
        if(degin[i] == 0) {
            que.push(i);
        }
    }
    while(!que.empty()) {
        int tmp = que.front();
        que.pop();
        for(int i = 0; i < 26; ++i) {
            if(G[tmp][i]) {
                --degin[i];
                if(degin[i] == 0) {
                    que.push(i);
                }
            }
        }
    }
    for(int i = 0; i < 26; ++i) {
        if(degin[i] != 0) {
            return false;
        }
    }
    return true;
}
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) {
        memset(head, 0, sizeof(head));
        memset(degin, 0, sizeof(degin));
        memset(degout, 0, sizeof(degout));
        memset(G, 0, sizeof(G));
        for(int i = 0; i < n; ++i) {
            scanf("%s", str);
            head[id(str[0])] = true;
            for(int j = 1; str[j]; ++j) {
                int u = id(str[j - 1]);
                int v = id(str[j]);
                if(!G[u][v]) {
                    G[u][v] = true;
                    ++degin[v];
                    ++degout[u];
                }
            }
        }
        bool flag = true;
        for(int i = 0; i < 26; ++i) {
            if(degin[i] > 1 || degout[i] > 1) {
                flag = false;
                break;
            }
        }
        memcpy(degout, degin, sizeof(degin));
        if(!topsort()) {
            flag = false;
        }
        if(!flag) {
            printf("NO\n");
            continue;
        }
        for(int i = 0; i < 26; ++i) {
            if(degout[i] == 0 && head[i]) {
                flag = true;
                int pos = i;
                while(flag) {
                    flag = false;
                    printf("%c", pos + 'a');
                    for(int j = 0; j < 26; ++j) {
                        if(G[pos][j]) {
                            pos = j;
                            flag = true;
                            break;
                        }
                    }
                }
            }
        }
        printf("\n");
    }
    return 0;
}