@Dmaxiya 2018-08-17T02:26:49.000000Z 字数 6355 阅读 1636

Codeforces Round #385 (Div. 2)

Codeforces

Contests 链接：Codeforces Round #385 (Div. 2)
过题数：4
排名：27/8581

A. Hongcow Learns the Cyclic Shift

题意

$Hongcow$ 正在学习英语单词，他想要将一个单词通过循环右移得到新的单词，循环右移的方法是：将这个单词的最后一个字符移动到这个单词的第一个字符之前，现在他想要知道，一个单词经过无限次的循环右移，能够得到多少个不同的单词。

输入

一个字符串 $s$ ，其中 $1\leq|s|\leq50$ ，字符串中只有小写字符 'a'-'z'。

输出

输出一个数字，表示将单词 $s$ 经过任意多次循环右移后得到的不同的单词数量。

样例

输入	输出
abcd	4
bbb	1
yzyz	2

题解

一个字符串只要循环右移 $|s|$ 次就能变成它本身，且 $|s|$ 很小，用 $string$ 暴力枚举即可。

过题代码

#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
string str, tmp;
set<string> st;
int main() {
    #ifdef LOCAL
        freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(cin >> str) {
        st.clear();
        int len = str.length();
        for(int i = 0; i < len; ++i) {
            st.insert(str);
            str = str.substr(1, len - 1) + str[0];
        }
        cout << st.size() << endl;
    }
    return 0;
}

B. Hongcow Solves A Puzzle

题意

$Hongcow$ 很喜欢拼图，现在他有一块长方形的拼图，这块拼图可以用一个 $n\times m$ 的字符串矩阵来描述，'X' 表示这块地方有图片， '.' 表示这块地方是空的，由于这块拼图太重了，所以 $Hongcow$ 不能旋转、翻转这块拼图。现在给定一块拼图，问能否只通过平移，使得这块拼图的复制品能与原拼图不重叠地拼成一个实心矩形。

输入

第一行包含 $n$ 和 $m$ $(1\leq n,m\leq500)$ ，接下来的 $n$ 行每行有 $m$ 个字符，所有字符只包含 '.' 和 'X'，含义如题，数据保证所有的 'X' 在四个方向上是连通的，且至少含有一个 'X'。

输出

如果可以拼成一个矩形，则输出 "YES"，否则输出 "NO"。

样例

输入	输出
2 3 `XXX` `XXX`	YES
2 2 `.X` `XX`	NO
5 5 `.....` `..X..` `.....` `.....` `.....`	YES

题解

多画几组样例就可以发现，在 $X$ 全连通的情况下，只有 $X$ 为一个实心矩形时，才可能将两块拼图不旋转不翻转地拼成一个实心矩形，所以只要找到上下左右最边上的坐标，判断是否实心就可以了。

过题代码

#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 = 600;
int n, m;
int minx, miny, maxx, maxy;
char str[maxn][maxn];
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", &n, &m) != EOF) {
        int cnt = 0;
        minx = miny = INT_MAX;
        maxx = maxy = INT_MIN;
        for(int i = 0; i < n; ++i) {
            scanf("%s", str[i]);
            for(int j = 0; j < m; ++j) {
                if(str[i][j] == 'X') {
                    ++cnt;
                    minx = min(minx, i);
                    miny = min(miny, j);
                    maxx = max(maxx, i);
                    maxy = max(maxy, j);
                }
            }
        }
        if(cnt == 0) {
            printf("NO\n");
            continue;
        }
        bool flag = true;
        for(int i = minx; i <= maxx; ++i) {
            for(int j = miny; j <= maxy; ++j) {
                if(str[i][j] == '.') {
                    flag = false;
                    break;
                }
            }
            if(!flag) {
                break;
            }
        }
        if(flag) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }
    return 0;
}

C. Hongcow Builds A Nation

题意

$Hongcow$ 是世界的统治者，这个世界上有 $n$ 个城市和 $m$ 条道路，这些道路连接任意两个不相同的城市，且任意两个城市之间最多只有一条道路。在这 $n$ 个城市中有 $k$ 个城市是首都，为了让这个世界稳定，任意一个两个非首都的城市，如果它们能够到达的首都不相同，那么它们之间就不能有能够互相到达的路径。现在 $Hongcow$ 想要在保证世界稳定的前提下，修建尽可能多的路，问他最多能修建多少条道路。

输入

第一行三个整数 $n,m,k~(1\leq n\leq1000,0\leq m\leq10^5,1\leq k\leq n)$ ，第二行有 $k$ 个不同的整数 $c_1,c_2,\cdots,c_k~(1\leq c_i\leq n)$ ，表示 $k$ 个首都，接下去 $m$ 行每行两个整数 $u_i,v_i~(1\leq u_i,v_i\leq n)$ ，表示城市 $u_i$ 与 $v_i$ 之间有一条道路。数据保证世界是稳定的。

输出

输出 $Hongcow$ 在保证世界稳定的前提下，能够修建的最多的道路数。

样例

输入	输出
4 1 2 1 3 1 2	2
3 3 1 2 1 2 1 3 2 3	0

题解

在一个 $x$ 个节点的连通块内，能修建的最多的道路数为 $\frac{x\times(x-1)}{2}$ ，所以可以用并查集判断连通块并统计连通块内的边的数量，对于无法到达首都的那些节点，由于连通块内能连边的道路数是 $n^2$ 增长的，所以应尽量使这些节点往有首都的、节点数多的连通块连通，这样才能让可以修建的道路最多。

过题代码

#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, m, k, ans;
int u[maxn], v[maxn];
int line[maxn];
int sum[maxn];
int cap[maxn];
int fa[maxn];
bool iscap[maxn];
void Init() {
    for(int i = 1; i <= n; ++i) {
        fa[i] = i;
        sum[i] = 1;
        iscap[i] = false;
        line[i] = 0;
    }
}
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);
    if(xx != yy) {
        fa[xx] = yy;
        sum[yy] += sum[xx];
    }
}
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, &m, &k) != EOF) {
        Init();
        for(int i = 0; i < k; ++i) {
            scanf("%d", &cap[i]);
        }
        for(int i = 0; i < m; ++i) {
            scanf("%d%d", &u[i], &v[i]);
            unit(u[i], v[i]);
        }
        int Index = 0;
        for(int i = 0; i < k; ++i) {
            cap[i] = Find(cap[i]);
            iscap[cap[i]] = true;
            if(sum[cap[i]] > sum[cap[Index]]) {
                Index = i;
            }
        }
        Index = cap[Index];
        for(int i = 1; i <= n; ++i) {
            int f = Find(i);
            if(!iscap[f]) {
                unit(f, Index);
            }
        }
        for(int i = 0; i < m; ++i) {
            int uu = Find(u[i]);
            ++line[uu];
        }
        ans = 0;
        for(int i = 0; i < k; ++i) {
            ans += (sum[cap[i]] * (sum[cap[i]] - 1)) / 2 - line[cap[i]];
        }
        printf("%d\n", ans);
    }
    return 0;
}

D. Hongcow's Game

题意

你和 $Hongcow$ 玩一个游戏，首先有一个 $n\times n$ 的矩阵，如果用 $M_{i,j}$ 表示这个矩阵中的第 $i$ 行第 $j$ 列的数字，则这个矩阵满足

$M_{i,j} \begin{cases} =0,&(i=j)\\ \in[0,10^9]&(i\neq j) \end{cases}$
现在你可以问 $Hongcow$ 最多 $20$ 个问题，每个问题包含 $k~(1\leq k\leq n)$ 个整数 $w_1,w_2,\cdots,w_k~(1\leq w_i\leq n)$ ，表示要询问的列数， $Hongcow$ 将会回复你 $n$ 个整数，第 $i$ 个整数表示从第 $i$ 行的所有数字中，选出所有被询问的列的数字中的最小值，即 $\min(M_{i, w_j}),(j\in[1,k])$ ，你要通过 $Hongcow$ 的回答来得到每一行除对角线外的最小值，即 $\min(M_{i,j}),(i\neq j)$ 。

输入

初始输入只包含一个数字 $n~(2\leq n\leq1000)$ ，表示矩阵的大小，后面的输入根据你的提问进行回复，每次输入 $n$ 个数字。

输出

如果你要询问 $Hongcow$ ，则先输出一个 $k$ ，第二行为 $k$ 个整数，表示要询问的列数，如果你要回答 $Hongcow$ 的问题，则先输出单独的一行 $-1$ ，第二行输出 $n$ 个整数，第 $i$ 个整数表示 $\min(M_{i, w_j}),(j\in[1,k])$ 。注意在每段输出后清空输出缓冲区。
如果出现下面的情况，你的输出将会返回 $Wrong~Answer$ ：

你的输入格式与题目描述不符；

你的提问超过了 $20$ 个；

你的问题包含了重复的下标；

你的 $k$ 不在区间 $[1,n]$ 之间；

你最后的回答不正确。

样例

输入	输出
3 0 0 0 2 7 0 0 0 4 3 0 8 0 5 4	3 1 2 3 1 3 2 1 2 1 2 1 1 -1 2 5 4
2 0 0 0 0	1 2 1 1 -1 0 0

题解

首先从下标的二进制最低位到最高位枚举（最多只要 $10$ 次），第 $i$ 次枚举第 $i$ 位为 $0/1$ 的所有下标，这样就能得到每一行所有下标组合的最小值，由题意可以知道，如果询问的列下标包含 $x$ ，则关于 $x$ 行的回答总是 $0$ ，这个回答是不正确的，所以只要将这样的回答筛掉，就可以得到正确的答案。

过题代码

#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 = 1000 + 100;
int n, dig;
int Min[maxn], ret[maxn];
int ask[maxn], cnt;
void get_ask(int d, int x) {
    cnt = 0;
    for(int i = 1; i <= n; ++i) {
        if(((i >> d) & 1) == x) {
            ask[cnt++] = i;
        }
    }
}
int main() {
    #ifdef LOCAL
//        freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        Min[i] = INT_MAX;
    }
    int nn = n;
    while(nn != 0) {
        ++dig;
        nn >>= 1;
    }
    for(int i = 0; i < dig; ++i) {
        get_ask(i, 0);
        printf("%d\n", cnt);
        for(int j = 0; j < cnt; ++j) {
            if(j != 0) {
                printf(" ");
            }
            printf("%d", ask[j]);
        }
        printf("\n");
        fflush(stdout);
        for(int j = 1; j <= n; ++j) {
            scanf("%d", &ret[j]);
            if(((j >> i) & 1) != 0) {
                Min[j] = min(Min[j], ret[j]);
            }
        }
        get_ask(i, 1);
        printf("%d\n", cnt);
        for(int j = 0; j < cnt; ++j) {
            if(j != 0) {
                printf(" ");
            }
            printf("%d", ask[j]);
        }
        printf("\n");
        fflush(stdout);
        for(int j = 1; j <= n; ++j) {
            scanf("%d", &ret[j]);
            if(((j >> i) & 1) != 1) {
                Min[j] = min(Min[j], ret[j]);
            }
        }
    }
    printf("-1\n");
    for(int i = 1; i <= n; ++i) {
        if(i != 1) {
            printf(" ");
        }
        printf("%d", Min[i]);
    }
    printf("\n");
    fflush(stdout);
    return 0;
}

Codeforces Round #385 (Div. 2)

A. Hongcow Learns the Cyclic Shift

题意

输入

输出

样例

题解

过题代码

B. Hongcow Solves A Puzzle

题意

输入

输出

样例

题解

过题代码

C. Hongcow Builds A Nation

题意

输入

输出

样例

题解

过题代码

D. Hongcow's Game

题意

输入

输出

样例

题解

过题代码

内容目录

选择主题