Codeforces Round #501 (Div. 3)
2024-08-27 03:16:38
A - Points in Segments
题意：implement
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool vis[105];
int ans[105], atop;
void test_case() {
int n, m;
scanf("%d%d", &n, &m);
while(n--) {
int u, v;
scanf("%d%d", &u, &v);
for(int i = u; i <= v; ++i)
vis[i] = 1;
}
for(int i = 1; i <= m; ++i)
if(!vis[i])
ans[++atop] = i;
printf("%d\n", atop);
for(int i = 1; i <= atop; ++i)
printf("%d%c", ans[i], " \n"[i == atop]);
if(atop == 0)
puts("");
}
int main() {
#ifdef KisekiPurin
freopen("KisekiPurin.in", "r", stdin);
#endif // KisekiPurin
int t = 1;
for(int ti = 1; ti <= t; ++ti) {
//printf("Case #%d: ", ti);
test_case();
}
}
B - Obtaining the String
题意：给两个字符串s,t，使用冒泡排序从s到达t，求方法。
题解：implement
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
char s[105], ss[105], t[105], tt[105];
int ans[10005], atop;
void test_case() {
int n;
scanf("%d%s%s", &n, s + 1, t + 1);
strcpy(ss + 1, s + 1);
strcpy(tt + 1, t + 1);
sort(ss + 1, ss + 1 + n);
sort(tt + 1, tt + 1 + n);
if(strcmp(ss + 1, tt + 1) != 0) {
puts("-1");
return;
}
for(int i = 1; i <= n; ++i) {
while(t[i] != s[i]) {
for(int j = i + 1; j <= n; ++j) {
if(s[j] == t[i]) {
int k = j - 1;
while(t[i] != s[i]) {
ans[++atop] = k;
swap(s[k], s[k + 1]);
--k;
}
break;
}
}
}
}
printf("%d\n", atop);
for(int i = 1; i <= atop; ++i)
printf("%d%c", ans[i], " \n"[i == atop]);
}
int main() {
#ifdef KisekiPurin
freopen("KisekiPurin.in", "r", stdin);
#endif // KisekiPurin
int t = 1;
for(int ti = 1; ti <= t; ++ti) {
//printf("Case #%d: ", ti);
test_case();
}
}
C - Songs Compression
题意：有n个数字ai和n个数字bi，花费代价1可以把ai缩小到bi，求缩减总容量小于等于m的最小代价。
题解：implement
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
priority_queue<int> pq;
void test_case() {
int n, m;
scanf("%d%d", &n, &m);
ll sum = 0;
for(int i = 1, a, b; i <= n; ++i) {
scanf("%d%d", &a, &b);
pq.push(a - b);
sum += a;
}
int cnt = 0;
while(pq.size()) {
if(sum <= m)
break;
sum -= pq.top();
++cnt;
pq.pop();
}
if(sum > m)
cnt = -1;
printf("%d\n", cnt);
}
int main() {
#ifdef KisekiPurin
freopen("KisekiPurin.in", "r", stdin);
#endif // KisekiPurin
int t = 1;
for(int ti = 1; ti <= t; ++ti) {
//printf("Case #%d: ", ti);
test_case();
}
}
D - Walking Between Houses
题意：有[1,n]号房子，相邻房子距离1，要移动恰好k次，总共恰好s距离，求方法。注意不能原地踏步。
题解：很显然只要是s>=k且s<=k*(n-1)都可以构造，但是因为不能原地踏步就很恶心。先尽可能走最远，直到某次走最远之后会使得s<k，这样就走一步不那么远的直到走完之后s=k，然后反复横跳。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int ans[200005], atop;
void test_case() {
int n, k;
ll s;
scanf("%d%d%lld", &n, &k, &s);
if(s < k || s > (1ll * k * (n - 1))) {
puts("NO");
return;
}
if(s == k) {
puts("YES");
for(int i = 1; i <= k; ++i)
printf("%d%c", 1 + ((i & 1) == 1), " \n"[i == k]);
return;
}
int cur = 1;
while(s - (n - 1) >= (k - 1)) {
s -= n - 1;
k -= 1;
if(cur == 1) {
ans[++atop] = n;
cur = n;
} else {
ans[++atop] = 1;
cur = 1;
}
}
if(k) {
int p = s - (k - 1);
assert(p <= (n - 1));
if(cur == 1) {
ans[++atop] = 1 + p;
cur = 1 + p;
s -= p;
k -= 1;
} else {
ans[++atop] = n - p;
cur = n - p;
s -= p;
k -= 1;
}
}
if(cur == 1) {
for(int i = 1; i <= k; ++i)
ans[++atop] = 1 + ((i & 1) == 1);
} else {
for(int i = 1; i <= k; ++i)
ans[++atop] = cur - ((i & 1) == 1);
}
puts("YES");
ll sum = 0;
ans[0] = 1;
for(int i = 1; i <= atop; ++i) {
printf("%d%c", ans[i], " \n"[i == atop]);
sum += abs(ans[i] - ans[i - 1]);
}
//printf("sum=%lld\n", sum);
}
int main() {
#ifdef KisekiPurin
freopen("KisekiPurin.in", "r", stdin);
#endif // KisekiPurin
int t = 1;
for(int ti = 1; ti <= t; ++ti) {
//printf("Case #%d: ", ti);
test_case();
}
}
E1 - Stars Drawing (Easy Edition)
题意：给一个图，用一些十字星把这个图覆盖出来。图<=100*100。
题解：枚举每个中心，然后枚举上下左右拓展的极限，把这个极限覆盖上去，最后得出的图假如和原图不同就-1。
E2 - Stars Drawing (Hard Edition)
题意：图<=1000*1000。把枚举上下左右换成一个很复杂的check，输入一个中心、一个方向和一个长度，返回这段是否完全被覆盖。这个可以用前缀和来实现，所以枚举中心然后二分长度就可以。但是最后答案不能够暴力更新，这个就直接在lr打上差分标记，然后最后扫过来填上去就可以了。
有没有更好的办法？
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
char g[1005][1005];
int prefixl[1005][1005];
int prefixu[1005][1005];
int cntl[1005][1005], cntu[1005][1005];
char ans[1005][1005];
bool checku(int i, int j, int l) {
if(i - l - 1 < 0)
return false;
return (prefixu[i - 1][j] - prefixu[i - l - 1][j]) == l;
}
bool checkl(int i, int j, int l) {
if(j - l - 1 < 0)
return false;
return (prefixl[i][j - 1] - prefixl[i][j - l - 1]) == l;
}
bool checkr(int i, int j, int l) {
if(i + l > n)
return false;
return (prefixu[i + l][j] - prefixu[i][j]) == l;
}
bool checkd(int i, int j, int l) {
if(j + l > m)
return false;
return (prefixl[i][j + l] - prefixl[i][j]) == l;
}
bool check(int i, int j, int l) {
return checku(i, j, l) && checkl(i, j, l) && checkr(i, j, l) && checkd(i, j, l);
}
struct Answer {
int i, j, l;
Answer(int ii, int jj, int ll) {
i = ii, j = jj, l = ll;
}
};
vector<Answer>ans2;
void solve(int i, int j) {
if(i == 1 || j == 1 || i == n || j == m)
return;
if(g[i][j] == '*' && g[i - 1][j] == '*' && g[i + 1][j] == '*' && g[i][j - 1] == '*' && g[i][j + 1] == '*') {
int L = 1, R = min(min(i - 1, n - i), min(j - 1, m - j));
int ans = 0;
while(1) {
int M = L + R >> 1;
if(L == M) {
if(check(i, j, R)) {
ans = R;
break;
}
ans = L;
break;
}
if(check(i, j, M))
L = M;
else
R = M - 1;
}
++cntu[i - ans][j];
--cntu[i + ans + 1][j];
++cntl[i][j - ans];
--cntl[i][j + ans + 1];
ans2.push_back(Answer(i, j, ans));
}
return;
}
void test_case() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i) {
scanf("%s", g[i] + 1);
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j)
prefixl[i][j] = prefixl[i][j - 1] + (g[i][j] == '*');
}
for(int j = 1; j <= m; ++j) {
for(int i = 1; i <= n; ++i)
prefixu[i][j] = prefixu[i - 1][j] + (g[i][j] == '*');
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j)
solve(i, j);
}
memset(ans, '.', sizeof(ans));
for(int i = 1; i <= n; ++i) {
int cur = 0;
for(int j = 1; j <= m; ++j) {
cur += cntl[i][j];
if(cur)
ans[i][j] = '*';
}
}
for(int j = 1; j <= m; ++j) {
int cur = 0;
for(int i = 1; i <= n; ++i) {
cur += cntu[i][j];
if(cur)
ans[i][j] = '*';
if(ans[i][j] != g[i][j]) {
puts("-1");
return;
}
}
}
printf("%d\n", (int)ans2.size());
for(auto i : ans2)
printf("%d %d %d\n", i.i, i.j, i.l);
}
int main() {
#ifdef KisekiPurin
freopen("KisekiPurin.in", "r", stdin);
#endif // KisekiPurin
int t = 1;
for(int ti = 1; ti <= t; ++ti) {
//printf("Case #%d: ", ti);
test_case();
}
}
事实上并不需要二分，可以dp转移出四个方向上的最远值。然后直接取min。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
char g[1005][1005];
short u[1005][1005];
short d[1005][1005];
short l[1005][1005];
short r[1005][1005];
short cntu[1005][1005];
short cntl[1005][1005];
char ans[1005][1005];
struct Answer {
int i, j, l;
Answer(int ii, int jj, int ll) {
i = ii, j = jj, l = ll;
}
};
vector<Answer>ans2;
void solve(int i, int j) {
int len = min(min(u[i][j], d[i][j]), min(l[i][j], r[i][j]));
if(len <= 1)
return;
len -= 1;
++cntu[i - len][j];
--cntu[i + len + 1][j];
++cntl[i][j - len];
--cntl[i][j + len + 1];
ans2.push_back(Answer(i, j, len));
}
void test_case() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i)
scanf("%s", g[i] + 1);
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
u[i][j] = (g[i][j] == '*') ? u[i - 1][j] + 1 : 0;
l[i][j] = (g[i][j] == '*') ? l[i][j - 1] + 1 : 0;
}
}
for(int i = n; i >= 1; --i) {
for(int j = m; j >= 1; --j) {
d[i][j] = (g[i][j] == '*') ? d[i + 1][j] + 1 : 0;
r[i][j] = (g[i][j] == '*') ? r[i][j + 1] + 1 : 0;
}
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j)
solve(i, j);
}
memset(ans, '.', sizeof(ans));
for(int i = 1; i <= n; ++i) {
int cur = 0;
for(int j = 1; j <= m; ++j) {
cur += cntl[i][j];
if(cur)
ans[i][j] = '*';
}
}
for(int j = 1; j <= m; ++j) {
int cur = 0;
for(int i = 1; i <= n; ++i) {
cur += cntu[i][j];
if(cur)
ans[i][j] = '*';
if(ans[i][j] != g[i][j]) {
puts("-1");
return;
}
}
}
printf("%d\n", (int)ans2.size());
for(auto i : ans2)
printf("%d %d %d\n", i.i, i.j, i.l);
}
int main() {
#ifdef KisekiPurin
freopen("KisekiPurin.in", "r", stdin);
#endif // KisekiPurin
int t = 1;
for(int ti = 1; ti <= t; ++ti) {
//printf("Case #%d: ", ti);
test_case();
}
}
F - Bracket Substring
题意：有个不一定合法的括号串s，求长度为2n的串中有多少种是包含n为子串且合法的。
题解：换句话说就是在左右加一个n个使得它合法，问有多少种。看起来像是dp。设dp[i][j][k]为已经有总共i长度的串，其中现在以s的第j位结尾，左括号比右括号多k个的合法方案数，则答案为dp[2n][l][0]。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
char s[205];
ll dp[205][205][205];
void test_case() {
int n;
scanf("%d%s", &n, s + 1);
int l = strlen(s + 1);
dp[0][0][0] = 1;
for(int i = 1; i <= 2 * n; ++i) {
//没有进入s串，直接转移
for(int k = 0; k <= i; ++k)
dp[i][0][k] = (k >= 1 ? dp[i - 1][0][k - 1] : 0) + dp[i - 1][0][k + 1];
//开始进入s串/已经进入s串
for(int j = 1; j <= min(i, l); ++j) {
if(s[j] == '(') {
for(int k = 0; k <= i; ++k)
dp[i][j][k] = (k >= 1 ? dp[i - 1][j - 1][k - 1] : 0);
} else {
for(int k = 0; k <= i; ++k)
dp[i][j][k] = dp[i - 1][j - 1][k + 1];
}
}
//结束进入s串
if(i > l && l) {
for(int k = 0; k <= i; ++k)
dp[i][l][k] += (k >= 1 ? dp[i - 1][l][k - 1] : 0) + dp[i - 1][l][k + 1];
}
for(int j = 0; j <= min(i, l); ++j) {
for(int k = 0; k <= i; ++k) {
dp[i][j][k] %= MOD;
printf("dp[%d][%d][%d]=%lld\n", i, j, k, dp[i][j][k]);
}
}
printf("\n");
}
printf("%lld\n", dp[2 * n][l][0] % MOD);
}
int main() {
#ifdef KisekiPurin
freopen("KisekiPurin.in", "r", stdin);
#endif // KisekiPurin
int t = 1;
for(int ti = 1; ti <= t; ++ti) {
//printf("Case #%d: ", ti);
test_case();
}
}
这样会重复，比如
2
()
答案应该是2，但是上面这样会输出3。
解决的办法要利用字符串里面的KMP算法的next数组，得先放一下。
最新文章
- 4年，如何从草根成长成为CTO-（第一篇）
- 【思维导图】Fiddler学习笔记
- 虚方法的调用是怎么实现的(单继承VS多继承)
- wpa_supplicant移植
- OpenGL画图旋转
- crontab 配置
- linux内核交互,设备驱动控制管理接口
- 探索Android该Parcel机制上
- SpringMvc笔记-对RESTFUL风格的配置
- Centos7 上安装配置 RabbitMQ
- ios开发常识（1）开发语言和参考资料
- event工具集
- HTTP与HTTPS的理解
- Spring 中事务控制的API介绍
- 新建项目虚拟环境及pycharm配置
- Hadoop---日志服务器
- valgrind 工具介绍和简单的使用
- $digest already in progress 解决办法
- Java之集合(九)LinkedHashMap
- bzoj5153 [Wc2018]州区划分