Codeforces Round #455 (Div. 2)

Codeforces

Contests 链接：Codeforces Round #455 (Div. 2)
过题数：4
排名：225/7758

A. Generate Login

题意

给出一个人的姓和名，分别用小写字符串 $a$ 和 $b$ 表示，一个人的登陆用户名为两个字符串的前缀拼起来，要求这个用户名的字典序最小，求这个用户名。

数据范围

$1\leq\left|a\right|,\left|b\right|\leq10$

题解

按照题意，取两个字符串的前缀拼起来放到 $set$ 里面，然后取 $set$ 的 $begin()$ 指向的元素。

过题代码

#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 str1, str2;
string str;
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 >> str1 >> str2) {
        st.clear();
        int len1 = str1.length();
        int len2 = str2.length();
        for(int i = 1; i <= len1; ++i) {
            for(int j = 1; j <= len2; ++j) {
                str = str1.substr(0, i) + str2.substr(0, j);
                st.insert(str);
            }
        }
        set<string>::iterator it = st.begin();
        cout << *it << endl;
    }
    return 0;
}

B. Segments

题意

给一个长度为 $n$ 的区间，这个区间上左右端点为整数的线段总共有 $\frac{(n+1)\times n}{2}$ 条，现在将这些线段不移动左右端点地平铺在这个区间上，问最少铺多少层。

数据范围

$1\leq n\leq100$

题解

将每一条线段都取一遍，按照线段覆盖问题处理。

过题代码

#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 = 100 + 100;
int n;
int num[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", &n) != EOF) {
        memset(num, 0, sizeof(num));
        for(int i = 0; i < n; ++i) {
            for(int j = i + 1; j <= n; ++j) {
                ++num[i];
                --num[j];
            }
        }
        int ans = 0;
        int tmp = 0;
        for(int i = 0; i <= n; ++i) {
            tmp += num[i];
            ans = max(ans, tmp);
        }
        printf("%d\n", ans);
    }
    return 0;
}

C. Python Indentation

题意

$python$ 语法靠缩进来确定程序的逻辑，现在给出 $N$ 条语句，总共只有两种语法，一种是简单句，单独占一行，另一种是 $for$ 语句，$for$ 语句下可以包含多个语句，$for$ 语句可以嵌套使用，$for$ 语句的下一行必须有一个缩进，$for$ 语句内不能为空，即必须要有循环体。现在给出每一条语句为 $f$（$for$ 语句）或者 $s$（简单句），但没有缩进，问总共有多少种可能的合法的 $python$ 语句。最后将求得的方案数对 $10^9+7$ 取模。

数据范围

$1\leq N\leq5000$

题解

定义 $dp[i][j]$ 表示到第 $i$ 行语句，这条语句在第 $j$ 个缩进的可能性的多少，将第 $i$ 条语句记为 $str_i$，以此可以推导出状态转移方程：

$$dp[i][j]= \begin{cases} dp[i-1][j-1]&str_{i-1}=s\\ \sum_{k=j}^ndp[i-1][k]&str_{i-1}=f \end{cases}$$
从 $dp$ 方程可以看出，每一层只要从后往前循环，就可以将二维拍成一维来写，对于求和操作，就用一个 $sum$ 数组来记录，时间复杂度为 $O(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 MOD = 1000000000 + 7;
const int maxn = 5000 + 100;
int n;
int dp[maxn];
int sum[maxn];
char str[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", &n) != EOF) {
        for(int i = 0; i < n; ++i) {
            scanf("%s", str + i);
        }
        memset(dp, 0, sizeof(dp));
        memset(sum, 0, sizeof(sum));
        dp[1] = sum[1] = 1;
        for(int i = 1; i < n; ++i) {
            for(int j = maxn - 10; j > 0; --j) {
                if(str[i - 1] == 's') {
                    dp[j] = sum[j];
                } else {
                    dp[j] = dp[j - 1];
                }
                sum[j] = dp[j] + sum[j + 1];
                dp[j] %= MOD;
                sum[j] %= MOD;
            }
        }
        int ans = 0;
        for(int i = 0; i < maxn; ++i) {
            ans += dp[i];
            ans %= MOD;
        }
        printf("%d\n", ans);
    }
    return 0;
}

D. Colorful Points

题意

有一个长度为 $n$ 的小写字母序列，对这个序列进行多次操作，每次操作先确定所有旁边有不同字母的位置，然后将这些位置上的字母删掉，问这个序列最多经过多少次操作后，无法进行操作。

数据范围

$1\leq n\leq10^6$

题解

先对整个序列扫一遍，记录下每一段的长度和字母，然后按照题意模拟一遍，时间复杂度为 $O(n)$。

过题代码

#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 = 1000000 + 100;
struct Node {
    int len;
    char ch;
};
char str[maxn];
Node node[maxn];
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%s", str) != EOF) {
        int cnt = 0;
        node[cnt].len = 0;
        node[cnt].ch = str[0];
        for(int i = 1; str[i]; ++i) {
            if(str[i] != str[i - 1]) {
                node[cnt].len = i - node[cnt].len;
                node[++cnt].len = i;
                node[cnt].ch = str[i];
            }
        }
        node[cnt].len = strlen(str) - node[cnt].len;
        ++cnt;
        int ans = 0;
        while(cnt > 1) {
            --node[0].len;
            --node[cnt - 1].len;
            for(int i = 1; i < cnt - 1; ++i) {
                node[i].len -= 2;
            }
            int cnttmp = 0;
            for(int i = 0; i < cnt; ++i) {
                if(node[i].len > 0) {
                    node[cnttmp++] = node[i];
                }
            }
            cnt = cnttmp;
            cnttmp = 0;
            for(int i = 1; i < cnt; ++i) {
                if(node[i].ch == node[cnttmp].ch) {
                    node[cnttmp].len += node[i].len;
                } else {
                    ++cnttmp;
                    node[cnttmp] = node[i];
                }
            }
            cnt = cnttmp + 1;
            ++ans;
        }
        printf("%d\n", ans);
    }
    return 0;
}