Codeforces Round 933 (Div. 3) (A~D)-CSDN博客
目录:A B C D E
标签: 暴力枚举(brute force)数学(math)排序算法(sortings)双指针算法(two pointers)
题目大意
给一个长度为n的数组b,和一个长度为m的数组c,还有一个整数k。
从b,c中各选一个数,问有多少种选法使这两个数小于等于k
思路
前缀和快速得出在b数组中小于等于k - c 的数的个数
AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 #include <bits/stdc++.h> using namespace std;const int N = 2020 ;int cnt[N];void solve () { int n, m, k; cin >> n >> m >> k; memset (cnt, 0 , sizeof cnt); for (int i = 0 ; i < n; i++) { int a; cin >> a; cnt[a] ++; } for (int i = 1 ; i <= 2010 ; i ++) cnt[i] += cnt[i-1 ]; int res = 0 ; for (int i = 0 ; i < m; i++) { int b; cin >> b; if (k>=b)res += cnt[k - b]; } cout << res << endl; } int main () { int T; cin >> T; while (T--) solve (); return 0 ; }
标签: 贪心策略(greedy)数学(math)
题目大意
思路
如果要将第一个数变为0,那么只能对第二个数进行操作,变换完后将不会在对第二个数进行操作。
那么同理:将第二个数变为0,只能对第三个进行操作…..
AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include <bits/stdc++.h> using namespace std;const int N = 1000100 ;int cnt[N];void solve () { int n; cin >> n; for (int i = 1 ; i <= n; i++) cin >> cnt[i]; for (int i = 1 ; i <= n - 2 ; i++) { if (cnt[i] > 0 ) { cnt[i+1 ] -= cnt[i] * 2 ; cnt[i+2 ] -= cnt[i]; cnt[i] = 0 ; } } for (int i = 1 ; i <= n; i++) { if (cnt[i] != 0 ) { cout << "NO" << endl; return ; } } cout << "YES" << endl; } int main () { int T; cin >> T; while (T--) solve (); return 0 ; }
标签: 动态规划(dp)字符串处理(strings)
题目大意
给定字符串s,问:最少操作几次使 s 不包含子串”map”和”pie”。
如果字符串 b 中存在一个连续 的字符段等于 a ,则字符串 a是 b 的子串。
思路
如果s中含有 “map” ,删除 ‘a’,含有”pie”,删除 ‘i’ 即可消掉
特判如果含有 “mapie” 这个子串,删除 ‘p’ 即可将map和pie都消掉(只需要删一次)
AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include <bits/stdc++.h> using namespace std;void solve () { int n; string s; cin >> n >> s; int t = s.size (), res = 0 ; for (int i = 0 ; i < t - 2 ; i++) { string subS = s.substr (i, 3 ); if (subS == "map" || subS == "pie" ) res ++; if (i <= t - 5 && s.substr (i, 5 ) == "mapie" ) res--; } cout << res << endl; } int main () { int T; cin >> T; while (T--) solve (); return 0 ; }
标签: 动态规划(dp)实现问题,编程技巧,模拟(implementation)
题目大意
n 个人编号1~n站成一个圈,有一个球在编号为x的人手上,进行m次传球
给定每次投掷的距离和每次投掷的方向(顺时针或逆时针),也有可能不知道方向。
计算出 m 次抛球后可能拿到球的人。
思路
为了方便将编号1~n 进行减一
状态表示:dp[i][j]表示 进行i次传球,球可不可能在编号为j的人手上 (值:1 0)
初始值:没进行传球时球在 x ,即:dp[0][x] = 1;
转态转移:
逆时针传球:dp[i][j] |= dp[i-1][(j + f[i].fr) % n];
顺时针传球:dp[i][j] |= dp[i-1][((j - f[i].fr) % n + n) % n];
AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 #include <bits/stdc++.h> #define fr first #define se second using namespace std;typedef pair<int , char > PII;const int N = 1010 ; PII f[N];int dp[N][N];void solve () { int n, m, x; cin >> n >> m >> x; x--; for (int i = 0 ; i <= m; i++) for (int j = 0 ; j <= n; j++) dp[i][j] = 0 ; for (int i = 1 ; i <= m; i++) cin >> f[i].fr >> f[i].se; dp[0 ][x] = 1 ; int res = 0 ; for (int i = 1 ; i <= m; i++) for (int j = 0 ; j < n; j++) { if (f[i].se == '?' || f[i].se == '1' ) dp[i][j] |= dp[i-1 ][(j + f[i].fr) % n]; if (f[i].se == '?' || f[i].se == '0' ) dp[i][j] |= dp[i-1 ][((j - f[i].fr) % n + n) % n]; if (i==m && dp[i][j]==1 ) res ++; } cout<< res << endl; for (int i = 0 ; i < n; i++) if (dp[m][i] == 1 ) cout << i + 1 << " " ; cout << "\n" ; } int main () { int T; cin >> T; while (T--) solve (); return 0 ; }
标签: 数据结构(data structures)动态规划(dp)
题目大意
n行和 m列组成的网格。第 i行和第 j 列的交点包含数字 a~i,j ~–相应单元格的深度。第一列和最后 列中的所有单元格都与河岸相对应,因此它们的深度为 0。
可以选择每一行安装支架,建造一座桥。
起点和终点必须含有支架
支架间间隔最多为d
问:建造连在一起的k座桥,最少需要多少支架。
思路
直接给出定义,dp[i] 为在 i 处建造支柱最小的花费。dp[i-d-1]~dp[i-1] 里面找最小值转移到dp[i]
下标 i-dis-1 的位置有支柱,最远可以让下标 i 位置造一个支柱,即: dp[i]=min{ dp[i-d-1] ~ dp[i-1] } + d[i] + 1
连续 k 座桥用前缀和或滑动窗口即可
dp这样的时间复杂度为 n * m * d 会T掉
每次存储dp[i-d-1] ~ dp[i-1]最小值转移,即用单调队列优化详情看AC代码,时间复杂度 n * m
基础dp代码 (会T掉)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include <bits/stdc++.h> #define LL long long using namespace std;const int N = 200005 ; LL d[N], ans[111 ];void solve () { int n, m, k, dis; cin >> n >> m >> k >> dis; dis++; for (int j = 1 ;j <= n; j++){ for (int i = 1 ;i <= m; i++){ cin >> d[i]; LL dd = 1e18 ; for (int k = i - 1 ; k >= max (1 , i - dis); k--) dd = min (dd, d[k]); if (i == 1 ) dd = 0 ; d[i] += dd + 1 ; } ans[j] = d[m]; } for (int i = 1 ;i <= n; i++) ans[i] += ans[i-1 ]; LL mi = 1e18 ; for (int i = k;i <= n; i++) mi = min (mi, ans[i] - ans[i-k]); cout << mi << '\n' ; }int main () { int T; cin >> T; while (T--) solve (); return 0 ; }
AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #include <bits/stdc++.h> #define LL long long using namespace std;const int N = 200005 ; LL d[N], ans[111 ], q[N];void solve () { int n, m, k, dis; cin >> n >> m >> k >> dis; dis++; for (int j = 1 ;j <= n; j++){ int hh = 0 , tt = -1 ; q[0 ] = 0 ; for (int i = 1 ;i <= m; i++){ cin >> d[i]; if (q[hh] < i - dis) hh++; d[i] += d[q[hh]] + 1 ; while (tt >= hh && d[i] <= d[q[tt]]) tt--; q[++tt] = i; } ans[j] = d[m]; } for (int i = 1 ;i <= n; i++) ans[i] += ans[i-1 ]; LL mi = 1e18 ; for (int i = k;i <= n; i++) mi = min (mi, ans[i] - ans[i-k]); cout << mi << '\n' ; }int main () { int T; cin >> T; while (T--) solve (); return 0 ; }
logo