【解题报告】Codeforces Round #302 (Div. 2)

本文主要是介绍【解题报告】Codeforces Round #302 (Div. 2)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

A.Set of Strings（Codeforces 544A）

思路

显然，若字符串中有不少于 $k$ 个不同的字符，则一定能找到满足条件的分割方式。（因为允许只含有一个字符的子串）

代码

#include <bits/stdc++.h>
using namespace std;int k, vis[30];
string s, sub;
vector <int> v;int main() {cin >> k >> s;for(int i = 0; i < s.size(); i++) {if(vis[s[i]-'a'] == 0) {vis[s[i]-'a'] = 1;v.push_back(i);}}if(v.size() < k) puts("NO");else {puts("YES");for(int i = 0; i < k; i++) {if(i != k - 1) sub = s.substr(v[i], v[i+1] - v[i]);else sub = s.substr(v[i], s.size() - v[i]);cout << sub << endl;}}return 0;
}

B.Sea and Islands（Codeforces 544B）

思路

这是一道构造的题目。由于是构造，所以只需要找到构造的特例就行。首先，由国际象棋的棋盘可以联想到， $ceil( \frac{1}{2} n^2)$ 为岛的数量的上界。既然想到了国际象棋的棋盘，那么岛的摆放也可以按照国际象棋中的黑格子的分布来摆。这样既适用于所有情况，又能以非常简洁的代码来实现。

代码

#include <cstdio>int n, k;int main() {scanf("%d%d", &n, &k);if(2 * k - 1 > n * n) {puts("NO");}else {puts("YES");for(int i = 0; i < n; i++) {for(int j = 0; j < n; j++) {if(k > 0 && ((i ^ j) & 1) == 0) {putchar('L');k--;}else {putchar('S');}}puts("");}}return 0;
}

C.Writing Code（Codeforces 544C）

思路

这种有一定资源限制求最优解或解的数量，或者说在每种状态下有超过一种的决策方案，但是不同的决策向量的子结构能转移到同一个状态的问题，通常能用动态规划解决。更具体地，通常能用背包思想解决。因为显然程序员i写的单行代码就是背包问题中的物品 $i$ 。由于一个程序员写的代码行数没有数量限制，因此这是个完全背包问题。回忆一下，只有一种限制条件（二维）的完全背包的状态转移方程为 d[i][j]=d[i−1][j]+d[i