链接：https://codeforces.com/contest/1015
A - Points in Segments
题意：给定n个范围(l_i,r_i)，问哪些点没有出现过
思路：由于(1leq l_i leq r_i leq m)且m的范围很小，模拟即可
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const int N = 110;
int n, m, vis[N];
vector<int> res;
int main()
{
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
int l, r;
scanf("%d%d", &l, &r);
for (int k = l; k <= r; k++) vis[k] = 1;
}
for (int i = 1; i <= m; i++) {
if (vis[i]) continue;
res.push_back(i);
}
printf("%d
", res.size());
for (int i = 0; i < res.size(); i++) {
printf("%d", res[i]);
printf(i == res.size() - 1 ? "
" : " ");
}
return 0;
}
B - Obtaining the String
题意：给定两个字符串，每次可以交换相邻两个字符，给出任意一组交换次数小于(10^4)的方案使得a串成为b串，输出交换的次数与位置，无解输出-1
思路：从后向前处理b串，每次找到一个位置p使得a[p]=b[i]，然后模拟交换的过程
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const int N = 60;
int n, c[N];
char a[N], b[N];
vector<int> res;
int main()
{
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
scanf("%d%s%s", &n, a + 1, b + 1);
for (int i = 1; i <= n; i++) c[a[i] - 'a' + 1] += 1;
for (int i = 1; i <= n; i++) c[b[i] - 'a' + 1] -= 1;
for (int i = 1; i <= 26; i++) {
if (0 != c[i]) {
printf("-1
");
return 0;
}
}
for (int i = n; i >= 1; i--) {
if (a[i] == b[i]) continue;
int p = 0;
for (int k = 1; k <= i - 1; k++)
if (a[k] == b[i]) p = k;
for (int k = p; k <= i - 1; k++) {
res.push_back(k);
swap(a[k], a[k + 1]);
}
}
printf("%d
", res.size());
for (int i = 0; i < res.size(); i++) {
printf("%d", res[i]);
printf(i == res.size() - 1 ? "
" : " ");
}
return 0;
}
C - Songs Compression
题意：有m大小的空间，有n个物品，第i个物品本来的大小为(a_i)，压缩后的大小为(b_i)，问你最少只需要压缩多少个物品，就能把这个n个物品放进m大小的空间
思路：贪心，对于每个物品，按照(a_i-b_i)从大到小排序，然后找到最前面最少的物品压缩，使得这n个物品放进m大小的空间
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const int N = 100010;
struct node {
ll a, b, d;
};
int n;
ll m;
node nd[N];
bool cmp(node a, node b)
{
return a.d > b.d;
}
int main()
{
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
scanf("%d%lld", &n, &m);
ll sa = 0, sb = 0;
for (int i = 1; i <= n; i++) {
scanf("%lld%lld", &nd[i].a, &nd[i].b);
sa += nd[i].a;
sb += nd[i].b;
nd[i].d = nd[i].a - nd[i].b;
}
if (sb > m) {
printf("-1
");
return 0;
}
sort(nd + 1, nd + n + 1, cmp);
int res = 0;
for (int i = 1; i <= n; i++) {
if (sa <= m) break;
sa -= nd[i].d;
res += 1;
}
printf("%d
", res);
return 0;
}
D - Walking Between Houses
题意：现在有n个房子排成一列，编号为(1~n)，起初你在第1个房子里，现在你要进行k次移动，每次移动一都可以从一个房子i移动到另外一个其他的房子j里(i!=j)，移动的距离为(mid j-imid)。问你进过k次移动后，移动的总和可以刚好是s，若可以则输出YES并依次输出每次到达的房子的编号，否则输出NO
思路：由于每次最多移动(n-1)步，最少移动一步，所以当(s<k)或者(s>k*(n-1))时，无解，直接输出NO即可，有解情况下，考虑以下构造方法
对于每一步，平均每次需要移动(frac{s}{k})步，其中有(s\%k)次需要移动(frac{s}{k}+1)步，所以采用向左走一次、向右走一次的方法即可
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
ll n, k, s;
vector<ll> res;
int main()
{
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
scanf("%lld%lld%lld", &n, &k, &s);
if (s < k || s > k * (n - 1)) {
printf("NO
");
return 0;
}
printf("YES
");
ll b = s / k, bm = s % k, now = 1, t = 1;
for (ll i = 1; i <= bm; i++) {
if (1 == now) res.push_back(now + b + 1);
else res.push_back(now - b - 1);
now = now + (b + 1) * t;
t = -t;
}
for (ll i = bm + 1; i <= k; i++) {
if (now + b <= n) {
res.push_back(now + b);
now += b;
}
else {
res.push_back(now - b);
now -= b;
}
}
for (ll i = 1; i <= k; i++) {
printf("%lld", res[i - 1]);
printf(i == k ? "
" : " ");
}
return 0;
}
E - Stars Drawing (Easy Edition)
见Hard Edition
F - Stars Drawing (Hard Edition)
题意：给你一个(n*m)大小的字符矩阵，仅由"."和"*"组成，提问这个图可否划分为一些由"*"组成的十字形状，这些十字之间可以有重叠，如果可以完全覆盖输出每个十字中心坐标与边长度，不可以输出-1
思路：对于每个"*"，我们预处理出他上下左右能延伸的最大范围，对于每个"*"，我们就能知道他能够形成以他为中心的十字形状最大为多少，然后差分维护一下哪些点被选过了，如果到最后还有点没有被选到，那就是不可能的，输出-1
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const int N = 1010;
struct node {
int a, b, r;
node() { }
node(int _a, int _b, int _r) : a(_a), b(_b), r(_r) { }
};
int n, m, pre[N][N], af[N][N], up[N][N], down[N][N];
int bc[N][N], br[N][N];
char s[N][N];
vector<node> res;
int main()
{
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1);
for (int i = 1; i <= n; i++) {
int now = 0;
for (int k = 1; k <= m; k++) {
if (s[i][k] == '.') pre[i][k] = now = 0;
else {
pre[i][k] = now;
if (0 == now) now = k;
}
}
}
for (int i = 1; i <= n; i++) {
int now = 0;
for (int k = m; k >= 1; k--) {
if (s[i][k] == '.') af[i][k] = now = 0;
else {
af[i][k] = now;
if (0 == now) now = k;
}
}
}
for (int k = 1; k <= m; k++) {
int now = 0;
for (int i = 1; i <= n; i++) {
if (s[i][k] == '.') up[i][k] = now = 0;
else {
up[i][k] = now;
if (0 == now) now = i;
}
}
}
for (int k = 1; k <= m; k++) {
int now = 0;
for (int i = n; i >= 1; i--) {
if (s[i][k] == '.') down[i][k] = now = 0;
else {
down[i][k] = now;
if (0 == now) now = i;
}
}
}
for (int i = 1; i <= n; i++) {
for (int k = 1; k <= m; k++) {
if ('.' == s[i][k]) continue;
int imin = 0;
if (0 != pre[i][k] && 0 != af[i][k] && 0 != up[i][k] && 0 != down[i][k]) {
imin = min(k - pre[i][k], af[i][k] - k);
imin = min(imin, i - up[i][k]);
imin = min(imin, down[i][k] - i);
}
if (0 == imin) continue;
res.push_back(node(i, k, imin));
bc[i][k - imin] += 1;
bc[i][k + imin + 1] -= 1;
br[i - imin][k] += 1;
br[i + imin + 1][k] -= 1;
}
}
for (int i = 1; i <= n; i++) {
for (int k = 1; k <= m; k++) {
bc[i][k] += bc[i][k - 1];
br[i][k] += br[i - 1][k];
}
}
int ok = 1;
for (int i = 1; i <= n; i++) {
for (int k = 1; k <= m; k++) {
if ('.' == s[i][k]) continue;
if (0 == bc[i][k] && 0 == br[i][k]) ok = 0;
}
}
if (0 == ok) {
printf("-1
");
return 0;
}
printf("%d
", res.size());
for (int i = 0; i < res.size(); i++) printf("%d %d %d
", res[i].a, res[i].b, res[i].r);
return 0;
}
G - Bracket Substring
题意：给定一个只由左右括号组成的、长度为m的字符串s，问长度为(2*n)的包含s的合法括号序列方案数，答案对1000000007取模，(1leq nleq 100,1leq |s|leq 200)
思路：字符串下标从1开始，to[i][0/1]表示对于[1,i]这个前缀，在后面加上一个"("或者")"后，这个字符串的后缀与s前缀能够匹配的最大长度为多少，可以暴力处理
假设dp[i][j][k][p]表示前i个字符，有j个"("还没有被匹配掉，同时这个i个字符的后缀能够与s匹配的最大长度为k，并且是否完全包含s，所以枚举前i个字符的状态，对于第i+1个字符
如果第i+1个字符为"("，那么这个i+1个字符能够与s匹配的最大长度就会变成to[k][0](相当于[1,k]这个前缀加上"("，即to[k][0])，注意此时to[k][0]可能等于m，那么dp[i+1][j+1][to[k][0]][p|(to[k][0] == m)]需要加上dp[i][j][k][p]
如果第i+1个字符为")"，同样dp[i+1][j-1][to[k][1]][p|(to[k][1] == m)]需要加上dp[i][j][k][p]
最后的答案就是(sum_{i=0}^{m} dp[2*n][0][i][1])
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 210;
const int mod = 1000000007;
int dp[N][N][N][2], to[N][2], n, m, cnt;
char a[N], b[N];
bool check(int la, int lb, int len)
{
for (int i = 0; i < len; i++)
if (a[la + i] != b[lb + i]) return false;
return true;
}
int calc(char *b, int len)
{
for (int i = len; i >= 1; i--)
if (check(1, len - i + 1, i)) return i;
return 0;
}
int main()
{
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
scanf("%d%s", &n, a + 1);
m = strlen(a + 1);
if (a[1] == '(') to[0][0] = 1;
else to[0][1] = 1;
for (int i = 1; i <= m; i++) {
b[++cnt] = a[i];
b[++cnt] = '(';
to[i][0] = calc(b, cnt);
b[cnt] = ')';
to[i][1] = calc(b, cnt);
cnt -= 1;
}
dp[0][0][0][0] = 1;
for (int i = 0; i <= 2 * n - 1; i++) {
for (int j = 0; j <= n; j++) {
for (int k = 0; k <= m; k++) {
for (int p = 0; p <= 1; p++) {
if (j + 1 <= n) {
int &now = dp[i + 1][j + 1][to[k][0]][p | (to[k][0] == m)];
now = (now + dp[i][j][k][p]) % mod;
}
if (j >= 1) {
int &now = dp[i + 1][j - 1][to[k][1]][p | (to[k][1] == m)];
now = (now + dp[i][j][k][p]) % mod;
}
}
}
}
}
int res = 0;
for (int i = 0; i <= m; i++) res = (res + dp[2 * n][0][i][1]) % mod;
printf("%d
", res);
return 0;
}