@Dmaxiya 2020-12-12T15:28:10.000000Z 字数 5229 阅读 1087

Codeforces Round #423 (Div. 2)

Codeforces

Contests 链接：Codeforces Round #423 (Div. 2)
过题数：2
排名：1611/9405

A. Restaurant Tables

题意

一个餐馆里有 $a$ 个单人座和 $b$ 个双人座，如果来了一位顾客，如果还有单人座就让他坐单人座，否则如果有空着的双人座，就让他坐双人座，否则如果有已经坐了一位顾客的双人座，就让他坐那个双人座，否则餐馆就无法接待这位顾客；如果来了两位顾客，如果有空着的双人座，就让他们坐双人座，否则餐馆就无法接待他们。问这个餐馆最后拒绝了多少位顾客。

输入

第一行包含三个整数 $n,a,b~(1\leq n,a,b\leq2\times10^5)$ ，分别表示来的顾客的组数、单人座的数量和双人座的数量，第二行包含 $n$ 个整数 $t_1,t_2,\cdots,t_n~(1\leq t_i\leq2)$ ，表示 $n$ 组按顺序来的顾客里每一组的人数。

输出

输出这个餐馆最后拒绝的顾客数量。

样例

输入	输出	提示
4 1 2 1 2 1 1	0	第一组顾客坐在一个单人座上，第二组顾客坐在第一个双人座上，第三组顾客只能坐在剩下的第二个双人座上，第四组顾客只能和第三组顾客一起坐在第二个双人座上，这个餐馆可以接待所有顾客。
4 1 1 1 1 2 1	2	第一组顾客坐在单人座上，第二组顾客坐在剩下的双人座上，第三组顾客由于没有空着的双人座，所以餐馆无法接待他们，第四组顾客要和第二组顾客一起坐在双人座上，最终餐馆拒绝了两位顾客。

题解

用一个变量 $c$ 记录被占用了一个位置的双人座的数量，按题意模拟就能得到答案。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <sstream>
#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, a, b, c, t, ans;
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d%d%d", &n, &a, &b) != EOF) {
        ans = 0;
        c = 0;
        for(int i = 0; i < n; ++i) {
            scanf("%d", &t);
            if(t == 1) {
                if(a > 0) {
                    --a;
                } else if(b > 0) {
                    --b;
                    ++c;
                } else if(c > 0) {
                    --c;
                } else {
                    ++ans;
                }
            } else {
                if(b > 0) {
                    --b;
                } else {
                    ans += 2;
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

B. Black Square

题意

在一个 $n\times m$ 的方格上，只有黑和白两种颜色，现在要在这个方格纸上涂出一块正方形的黑色区域，在涂的过程中只能将白色涂成黑色，不能将黑色涂成白色，且在正方形之外的所有颜色都是白色，问最少需要把多少块白色方格涂成黑色？如果无法办到则输出 $-1$ 。

输入

第一行包含两个整数 $n,m~(1\leq n,m\leq100)$ ，接下去 $n$ 行每行一个长度为 $m$ 的字符串，字符串内只有 'B' 和 'W' 两种字符，分别表示黑色和白色。

输出

输出要涂出一个边长为正整数的正方形黑色方块，且正方形之外的所有颜色都是白色，最少需要涂的白色方块数，如果无法办到则输出 $-1$ 。

样例

输入	输出	提示
5 4 `WWWW` `WWWB` `WWWB` `WWBB` `WWWW`	5	需要填充的五个白色方格的坐标为 $(2,2),(2,3),(3,2),(3,3),(4,2)$ ，该正方形的边长为 $3$ 。
1 2 `BB`	-1	所有的方格都是黑色，且形状是一个矩形，所以无法涂成一个正方形。
3 3 `WWW` `WWW` `WWW`	1	所有的方格都是白色的，所以最少只要涂一个方格就能得到一个边长为 $1$ 的正方形。

题解

找到最左上和最右下的黑色方格，在水平和竖直方向的距离最大的，就是最终的正方形的边长 $a$ ，边长应该满足 $a\leq\min(n,m)$ ，否则无法形成黑色正方形，然后计算需要涂色的白色方格数即可。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <sstream>
#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 = 100 + 100;
int n, m, maxx, maxy, minx, miny, a, cnt;
char str[maxn];
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d%d", &n, &m) != EOF) {
        cnt = 0;
        maxx = maxy = -1;
        minx = miny = INT_MAX;
        for(int i = 0; i < n; ++i) {
            scanf("%s", str);
            for(int j = 0; j < m; ++j) {
                if(str[j] == 'B') {
                    minx = min(minx, i);
                    miny = min(miny, j);
                    maxx = max(maxx, i);
                    maxy = max(maxy, j);
                    ++cnt;
                }
            }
        }
        if(maxx == -1) {
            printf("1\n");
            continue;
        }
        a = max(maxx - minx, maxy - miny) + 1;
        if(a > min(n, m)) {
            printf("-1\n");
            continue;
        }
        printf("%d\n", a * a - cnt);
    }
    return 0;
}

C. String Reconstruction

题意

$Ivan$ 本来有一个只包含小写字母的字符串 $s$ ，但是他忘了这个字符串是什么，只记得这个字符串的一部分特征，他记得字符串 $s$ 的 $n$ 个子串 $t_1,t_2,\cdots,t_n$ 以及第 $i$ 个子串出现的 $k_i$ 个位置 $x_{i,1},x_{i,2},\cdots,x_{i,k_i}$ ，他现在想要根据这些信息构造出一个新的字符串，要使这个新字符串的字典序最小，求满足条件的新字符串。

输入

第一行为一个整数 $n~(1\leq n\leq10^5)$ ，接下去 $n$ 行，每行的开头为一个只包含小写字母的非空字符串 $t_i~(\sum_{i=1}^n|t_i|\leq10^6)$ ，接下去为一个整数 $k_i~(1\leq k_i\leq10^6,\sum_{i=1}^nk_i\leq10^6)$ ，表示子串 $t_i$ 出现在 $s$ 中的 $k_i$ 个位置，后面跟着 $k_i$ 个整数 $x_{i,1},x_{i,2},\cdots,x_{i,k_i}~(1\leq x_{i,j}\leq10^6)$ 。被描述的每个子串 $t_i$ 出现的位置可能是重合的，数据保证不自相矛盾，一定能构造出一个合法的字符串 $s$ 。

输出

输出满足条件的字典序最小的字符串 $s$ 。

样例

输入	输出
3 a 4 1 3 5 7 ab 2 1 5 ca 1 4	abacaba
1 a 1 3	aaa
3 ab 1 1 aba 1 3 ab 2 3 5	ababab

题解

由数据范围可知，可能的最长的字符串的长度为 $2\times10^6$ ，可以先将 $1-2\times10^6$ 都放入集合 $set$ ，表示还未确定字符的下标，根据每个子串以及出现的位置，每次都从 $set$ 中二分查找出起始位置和终止位置，跑遍所有没有确定字符的下标，将这些字符按照题给规则确定，并从 $set$ 中删除这些下标，时间复杂度为 $O(n\log n)$ 。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <sstream>
#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 = 2000000 + 100;
int n, k, x, len, Size;
char ans[maxn], str[maxn];
set<int> st;
set<int>::iterator Begin, End, it;
vector<set<int>::iterator> vct;
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        st.clear();
        memset(ans, 0, sizeof(ans));
        for(int i = 1; i < maxn; ++i) {
            st.insert(i);
        }
        while(n--) {
            scanf("%s%d", str, &k);
            len = strlen(str);
            while(k--) {
                scanf("%d", &x);
                vct.clear();
                Begin = st.lower_bound(x);
                End = st.upper_bound(x + len - 1);
                for(it = Begin; it != End; ++it) {
                    vct.push_back(it);
                    ans[*it] = str[*it - x];
                }
                Size = vct.size();
                for(int i = 0; i < Size; ++i) {
                    st.erase(vct[i]);
                }
            }
        }
        for(int i = maxn - 1; i >= 0; --i) {
            if(ans[i] != '\0') {
                len = i + 1;
                break;
            }
        }
        for(int i = 1; i < len; ++i) {
            if(ans[i] == '\0') {
                ans[i] = 'a';
            }
        }
        printf("%s\n", ans + 1);
    }
    return 0;
}

D. High Load

题意

有 $n$ 个节点，在其中添加 $n-1$ 条边，每条边连接两个不同的节点，使所有节点连通，且在树上总共有 $k$ 个节点的度为 $1$ ，找到一种最优的连接方案，使得树的直径最小。

输入

输入只有两个整数 $n,k~(3\leq n\leq2\times10^5,2\leq k\leq n-1)$ 。

输出

第一行输出最小的树的直径，接下去 $n-1$ 行为树上的所有边，边的顺序和节点的顺序任意，且每条边不能重复出现。

样例

输入	输出	提示
3 2	2 1 2 2 3	输出所表示的树如图：其中黄色为度为 $1$ 的节点。
5 3	3 1 2 2 3 3 4 3 5	输出所表示的树如图：其中黄色为度为 $1$ 的节点。

题解

构造一个叶子节点数量为 $k$ 的菊花树。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <sstream>
#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 = 200000 + 100;
int n, k, cnt;
int depth[maxn], fa[maxn];
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d%d", &n, &k) != EOF) {
        depth[1] = 0;
        for(int i = 2; i <= n; ++i) {
            int f = i - k;
            if(f < 1) {
                f = 1;
            }
            depth[i] = depth[f] + 1;
            fa[i] = f;
        }
        sort(depth + 1, depth + 1 + n);
        printf("%d\n", depth[n] + depth[n - 1]);
        for(int i = 2; i <= n; ++i) {
            printf("%d %d\n", fa[i], i);
        }
    }
    return 0;
}

Codeforces Round #423 (Div. 2)

A. Restaurant Tables

题意

输入

输出

样例

题解

过题代码

B. Black Square

题意

输入

输出

样例

题解

过题代码

C. String Reconstruction

题意

输入

输出

样例

题解

过题代码

D. High Load

题意

输入

输出

样例

题解

过题代码

内容目录