周二 6.1（dp）
这周开始刷kuangbin基础dp专题。昨天写高数作业去了没训练
A - Max Sum Plus Plus（dp空间与时间优化）
这题的dp方程我写出来了，但是感觉空间也炸时间也炸，就懵逼了
要同时对空间和时间优化
表示前j一定选，前j个数分成i段的最大和
那么根据第j个数为新的一段以及和j之前的数为一段两种情况可以写一个dp方程
我当时就懵逼了，m的范围都没给，而且n到1e6，必然超时啊
突破口在 发现这只是需要上一行的j之前所有dp值的最大值
那么我们显然可以开一个数组记录这个最大值，这样就不用枚举k了，大大节省了时间
假设这个数组是pre[j-1]
那么dp方程
发现i这一维度可以直接省掉，也就是
这样也解决了空间的问题 最后答案为
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e6 + 10;
int dp[N], pre[N], a[N], n, m, mx;int main()
{while(~scanf("%d%d", &m, &n)){memset(dp, 0, sizeof(dp));memset(pre, 0, sizeof(pre));_for(i, 1, n) scanf("%d", &a[i]);_for(i, 1, m){mx = -1e9;_for(j, i, n) //枚举从i开始，因为分成i段至少要i个元素{dp[j] = a[j] + max(dp[j - 1], pre[j - 1]);pre[j - 1] = mx; //这里先赋值再更新mx，因为pre[j-1]是不包括j的mx = max(mx, dp[j]);}}printf("%d\n", mx); }return 0;
}
B - Ignatius and the Princess IV(STL)
这题和dp有什么关系吗……
直接unordered_map秒杀
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;unordered_map<int, int> mp;
int n;int main()
{while(~scanf("%d", &n)){mp.clear();_for(i, 1, n){int x; scanf("%d", &x);mp[x]++;}for(auto x: mp)if(x.second >= (n + 1) / 2){printf("%d\n", x.first);break;}}return 0;
}
C - Monkey and Banana
这题就有点类似最大上升子序列，但是做一些处理
虽然每一个积木可以用无数次，但是如果这个积木的高度确定了话，只可能用一次
而且长和宽可以均处理成一个min 一个max，也就是长比宽大
所以可以一个积木化成三个积木，每个积木至多用一次
之后排个序，保证dp的无后效性
然后用最长上升子序列的dp思路就好
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 100;
int dp[N], n;
struct node { int x, y, h; };bool cmp(node a, node b)
{if(a.x == b.x)return a.y < b.y;return a.x < b.x;
}int main()
{int kase = 0;while(scanf("%d", &n) && n){vector<node> ve;_for(i, 1, n){int a, b, c;scanf("%d%d%d", &a, &b, &c);ve.push_back(node{min(a, b), max(a, b), c});ve.push_back(node{min(b, c), max(b, c), a});ve.push_back(node{min(a, c), max(a, c), b});}sort(ve.begin(), ve.end(), cmp);int ans = 0;rep(i, 0, ve.size()){dp[i] = ve[i].h;_for(j, 0, i - 1)if(ve[j].x < ve[i].x && ve[j].y < ve[i].y)dp[i] = max(dp[i], ve[i].h + dp[j]);ans = max(ans, dp[i]);}printf("Case %d: maximum height = %d\n", ++kase, ans);}return 0;
}
周四 6.2
D - Doing Homework（状压dp + 方案记录）
这道题自己独立做没做出来
看题解原来是状压dp
其实看到n <= 15就要意识到了
这么小的范围很可能是状压dp
既然这样，表示状态为S时，1表示选了，0表示没选，的最优结果
那么转移方程就很好写了，枚举当前状态是由哪一个状态转移过来就行了
这道题还要记录方案，所以要记录一下dp转移时的选择以及前驱，用结构体记录一下就好
因为输出的时候是从后往前递归，之后再输出的，所以枚举课程的时候需要逆序枚举，按照题目要求的顺序
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 20;
struct node
{string name;int d, t;
}a[N];
struct node2
{int t, pre, choose;
}record[1 << 15];
int dp[1 << 15], n;void print(int x)
{if(!x) return;print(record[x].pre);cout << a[record[x].choose].name << endl;
}int main()
{int T; scanf("%d", &T);while(T--){memset(record, 0, sizeof(record));memset(dp, 0x3f, sizeof(dp));scanf("%d", &n);_for(i, 1, n) cin >> a[i].name >> a[i].d >> a[i].t;dp[0] = 0;rep(S, 1, 1 << n)for(int j = n; j >= 1; j--)if(S & (1 << (j - 1))){int P = S ^ (1 << (j - 1));int val = max(record[P].t + a[j].t - a[j].d, 0);if(dp[P] + val < dp[S]){dp[S] = dp[P] + val;record[S].t = record[P].t + a[j].t;record[S].choose = j;record[S].pre = P;}}printf("%d\n", dp[(1 << n) - 1]);print((1 << n) - 1);}return 0;
}
E - Super Jumping! Jumping! Jumping!（最长上升子序列）
水题秒了
类似最长上升子序列的思路
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int N = 1e3 + 10;
int a[N], n;
ll dp[N];int main()
{while(scanf("%d", &n) && n){_for(i, 1, n) scanf("%d", &a[i]);ll ans = 0;_for(i, 1, n){dp[i] = a[i];_for(j, 1, i - 1)if(a[j] < a[i])dp[i] = max(dp[i], dp[j] + a[i]);ans = max(ans, dp[i]);}printf("%lld\n", ans);}return 0;
}
F - Piggy-Bank（完全背包）
裸的完全背包，秒了
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int N = 500 + 10;
const int M = 1e4 + 10;
int dp[M], w[N], v[N], n, m;int main()
{int T; scanf("%d", &T);while(T--){int a, b;scanf("%d%d%d", &a, &b, &n);m = b - a;_for(i, 1, n) scanf("%d%d", &v[i], &w[i]);memset(dp, 0x3f, sizeof(dp));dp[0] = 0;_for(i, 1, n)_for(j, w[i], m)dp[j] = min(dp[j], dp[j - w[i]] + v[i]);if(dp[m] > 1e9) puts("This is impossible.");else printf("The minimum amount of money in the piggy-bank is %d.\n", dp[m]);}return 0;
}
G - 免费馅饼（简单dp）
表示前i秒在第j个位置的最多馅饼
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int N = 1e5 + 10;
int dp[N][15], a[N][15], n, T;int main()
{while(scanf("%d", &n) && n){T = 0;memset(a, 0, sizeof a);memset(dp, 0, sizeof dp);_for(i, 1, n){int x, t;scanf("%d%d", &x, &t);T = max(T, t);a[t][x]++;}_for(i, 4, 6) dp[1][i] = a[1][i];_for(i, 2, T)_for(j, 0, 10)dp[i][j] = max(dp[i][j], a[i][j] + max(dp[i - 1][max(j - 1, 0)], max(dp[i - 1][j], dp[i - 1][min(j + 1, 10)])));int ans = 0;_for(j, 0, 10) ans = max(ans, dp[T][j]);printf("%d\n", ans);}return 0;
}
H - Tickets（简单dp）
比较水的dp
这里秒的转化可以模仿高精度进位
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 2e3 + 10;
int dp[N], a[N], b[N], n;int main()
{int T; scanf("%d", &T);while(T--){scanf("%d", &n);_for(i, 1, n) scanf("%d", &a[i]);_for(i, 1, n - 1) scanf("%d", &b[i]);_for(i, 1, n){dp[i] = dp[i - 1] + a[i];if(i - 2 >= 0) dp[i] = min(dp[i], dp[i - 2] + b[i - 1]); //不等式这么写不容易错}int t = dp[n], ans1, ans2, ans3;ans3 = t;ans2 = ans3 / 60; ans3 %= 60;ans1 = ans2 / 60; ans2 %= 60;int op = 1;if(8 + ans1 >= 12) ans1 -= 12, op = 2;printf("%02d:%02d:%02d ", 8 + ans1, ans2, ans3);puts(op == 1 ? "am" : "pm");}return 0;
}
I - 最少拦截系统（最长上升子序列）
做过，知道结论即答案是最长上升子序列
用的是nlogn的做法，之前整理过模板，直接抄模板
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 3e4 + 10;
int dp[N], d[N], a[N], n, len;int main()
{while(~scanf("%d", &n)){_for(i, 1, n) scanf("%d", &a[i]);d[1] = a[1]; len = 1;_for(i, 2, n){if(a[i] > d[len]) d[++len] = a[i];else d[lower_bound(d + 1, d + len + 1, a[i]) - d] = a[i];}printf("%d\n", len);}return 0;
}
J - FatMouse's Speed（最长上升子序列+记录方案）
先排序一下保证dp后效性
然后依然是类似最长上升子序列的思路
记录一下方案就好了
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e3 + 10;
int dp[N], pre[N];
struct node
{int w, s, id;
}a[N];
int n;bool cmp(node x, node y)
{if(x.w != y.w) return x.w < y.w;return x.s > y.s;
}void print(int x)
{if(!x) return;print(pre[x]);printf("%d\n", a[x].id);
}int main()
{int w, s;while(~scanf("%d%d", &w, &s))a[++n] = node{w, s, n};sort(a + 1, a + n + 1, cmp);int ans = 0, pos;_for(i, 1, n){dp[i] = 1;_for(j, 1, i - 1)if(a[j].w < a[i].w && a[j].s > a[i].s && dp[i] < dp[j] + 1){dp[i] = dp[j] + 1;pre[i] = j;}if(ans < dp[i]){ans = dp[i];pos = i;}}printf("%d\n", ans);print(pos);return 0;
}
周五 6.4（dp）
L - Common Subsequence
最长公共子序列
#include <cstdio>
#include <cstring>
#include <algorithm>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e3 + 10;
int dp[N][N];
char a[N], b[N];int main()
{while(~scanf("%s%s", a + 1, b + 1)){int lena = strlen(a + 1), lenb = strlen(b + 1);_for(i, 1, lena)_for(j, 1, lenb){dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);if(a[i] == b[j]) dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - 1]);}printf("%d\n", dp[lena][lenb]);}return 0;
}
N - Longest Ordered Subsequence
最长上升子序列
#include <cstdio>
#include <iostream>
#include <algorithm>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e3 + 10;
int dp[N], a[N], n;int main()
{cin >> n;_for(i, 1, n) cin >> a[i];int ans = 0;_for(i, 1, n){dp[i] = 1;_for(j, 1, i - 1)if(a[i] > a[j])dp[i] = max(dp[i], dp[j] + 1);ans = max(ans, dp[i]);}printf("%d\n", ans);return 0;
}
M - Help Jimmy
首先是dp[i]表示前i个，我发现状态转移还和位置有关，而一个平台上的位置由很多，就卡了一下
借鉴前几天一道cf树形dp的经验，一个区间直接取左右端点
这道题也是一样的，只要用左右端点代替这个区间就好，中间的点不理
表示落到第i个平台到左端点的最少时间，右端点
转移的时候模仿跳的过程，往后面的状态转移
注意这里只能转移一次，也就是转移到最近的平台
如果一直没有符合的平台就是落在地上了，更新一下答案
#include <cstdio>
#include <cstring>
#include <algorithm>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e3 + 10;
int dp[N][2], n, x, y, hmax;
struct node
{int l, r, h;
}a[N];bool cmp(node x, node y)
{return x.h > y.h;
}int main()
{int T; scanf("%d", &T);while(T--){scanf("%d%d%d%d", &n, &x, &y, &hmax);_for(i, 1, n) scanf("%d%d%d", &a[i].l, &a[i].r, &a[i].h);sort(a + 1, a + n + 1, cmp);int st, mi = 1e9;_for(i, 1, n)if(a[i].l <= x && x <= a[i].r && y - a[i].h >= 0 && mi > y - a[i].h){mi = y - a[i].h;st = i;}if(mi == 1e9){printf("%d\n", y);continue;}int ans = 1e9;memset(dp, 0x3f, sizeof dp);dp[st][0] = abs(x - a[st].l);dp[st][1] = abs(x - a[st].r);_for(i, st, n){_for(j, i + 1, n) //左边{if(abs(a[j].h - a[i].h) > hmax) break;if(a[j].l <= a[i].l && a[i].l <= a[j].r){dp[j][0] = min(dp[j][0], dp[i][0] + abs(a[i].l - a[j].l));dp[j][1] = min(dp[j][1], dp[i][0] + abs(a[i].l - a[j].r));break;}if(j == n) ans = min(ans, dp[i][0]);}_for(j, i + 1, n) //右边{if(abs(a[j].h - a[i].h) > hmax) break;if(a[j].l <= a[i].r && a[i].r <= a[j].r){dp[j][0] = min(dp[j][0], dp[i][1] + abs(a[i].r - a[j].l));dp[j][1] = min(dp[j][1], dp[i][1] + abs(a[i].r - a[j].r));break;}if(j == n) ans = min(ans, dp[i][1]);}}printf("%d\n", min(ans, min(dp[n][0], dp[n][1])) + y);}return 0;
}
突然想到可以把起点也看作在一个平台上，这样写起来不用特判，代码更加简洁
#include <cstdio>
#include <cstring>
#include <algorithm>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e3 + 10;
int dp[N][2], n, x, y, hmax;
struct node
{int l, r, h;
}a[N];bool cmp(node x, node y)
{return x.h > y.h;
}int main()
{int T; scanf("%d", &T);while(T--){scanf("%d%d%d%d", &n, &x, &y, &hmax);_for(i, 1, n) scanf("%d%d%d", &a[i].l, &a[i].r, &a[i].h);sort(a + 1, a + n + 1, cmp);a[0].l = a[0].r = x; a[0].h = y;memset(dp, 0x3f, sizeof dp);dp[0][0] = dp[0][1] = 0;int ans = 1e9;_for(i, 0, n){_for(j, i + 1, n) //左边{if(abs(a[j].h - a[i].h) > hmax) break;if(a[j].l <= a[i].l && a[i].l <= a[j].r){dp[j][0] = min(dp[j][0], dp[i][0] + abs(a[i].l - a[j].l));dp[j][1] = min(dp[j][1], dp[i][0] + abs(a[i].l - a[j].r));break;}if(j == n) ans = min(ans, dp[i][0]);}_for(j, i + 1, n) //右边{if(abs(a[j].h - a[i].h) > hmax) break;if(a[j].l <= a[i].r && a[i].r <= a[j].r){dp[j][0] = min(dp[j][0], dp[i][1] + abs(a[i].r - a[j].l));dp[j][1] = min(dp[j][1], dp[i][1] + abs(a[i].r - a[j].r));break;}if(j == n) ans = min(ans, dp[i][1]);}}printf("%d\n", min(ans, min(dp[n][0], dp[n][1])) + y);}return 0;
}
O - Treats for the Cows
表示左端选1~l 右端选r~n时的最大值
#include <cstdio>
#include <algorithm>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 2e3 + 10;
int dp[N][N], a[N], n;int main()
{scanf("%d", &n);_for(i, 1, n) scanf("%d", &a[i]);int ans = 0;_for(l, 0, n)for(int r = n + 1; r > l; r--){int t = l - 0 + n + 1 - r;dp[l][r] = t * a[r] + dp[l][r + 1];if(l - 1 >= 0) dp[l][r] = max(dp[l][r], t * a[l] + dp[l - 1][r]);ans = max(ans, dp[l][r]);}printf("%d\n", ans);return 0;
}
hdu 1058
本来要搜1078的，不知道为啥打错了打成1058……笑死
这道用stl搞一搞就行了。貌似也可以用dp
输出好坑
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
typedef pair<ll, ll> pa;
const int p[] = {2, 3, 5, 7};
map<int, int> id = {
{2, 0}, {3, 1}, {5, 2}, {7, 3}};int main()
{vector<int> ans;priority_queue<pa, vector<pa>, greater<pa>> q;ans.push_back(0); ans.push_back(1);rep(i, 0, 4) q.push(make_pair(p[i], p[i]));_for(i, 1, 5842){pa x = q.top(); q.pop();ans.push_back(x.first);rep(i, id[x.second], 4)q.push(make_pair(x.first * p[i], p[i]));}int n;while(scanf("%d", &n) && n){printf("The %d", n);int t = n % 10;if(t == 1 && n % 100 != 11) printf("st");else if(t == 2 && n % 100 != 12) printf("nd");else if(t == 3 && n % 100 != 13) printf("rd");else printf("th");printf(" humble number is %d.\n", ans[n]);}return 0;
}
周六 6.5（cf + dp）
昨天晚上打了一场cf
第一个小时做了三题。剩下一个小时做第四题，但是比赛时比较紧张，导致能做的题没把一些细节想清楚
赛后静下心想很快就AC了
心理素质还要锻炼
A. Fair Playoff
水题，反过来想方便一点
判断一下什么时候输，而不是判什么时候赢
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;int main()
{int T; scanf("%d", &T);while(T--){int a[5];_for(i, 1, 4) scanf("%d", &a[i]);if(min(a[1], a[2]) > max(a[3], a[4]) || min(a[3], a[4]) > max(a[1], a[2])) puts("NO");else puts("YES");}return 0;
}
B. Array Reodering
发现会gcd后面的数多一个2，利用这个条件，偶数放前面，奇数放后面
用partition实现很方便
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 2e3 + 10;
int a[N], n;int gcd(int a, int b) { return !b ? a : gcd(b, a % b); }int main()
{int T; scanf("%d", &T);while(T--){scanf("%d", &n);_for(i, 1, n) scanf("%d", &a[i]);partition(a + 1, a + n + 1, [](int x) { return x % 2 == 0; });int ans = 0;_for(i, 1, n)_for(j, i + 1, n)ans += gcd(a[i], a[j] * 2) > 1;printf("%d\n", ans);}return 0;
}
C. Unstable String
注意题目说连续的，所以可以维护一个区间
首先求一个最大的满足条件的区间，区间长度为n，答案增加n * (n + 1) / 2
此后如果这个区间的末尾是连续的问号，则左端点就移到末端连续问号的第一个，继续下去
否则就整个区间不要，从新开始
当末端有问号时，注意这部分会重复算，所以要减掉
减的时候要再下一次更新的时候减掉，因为不确定还有没有下一次更新，我因为这里WA了
之后重判断WA了……
要开long long
我的统计答案的ans开了long long
但是我还用了一个变量用于统计ans，这个变量忘记开long long了……
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;ll f(ll n)
{return 1ll * n * (n + 1) / 2;
}int main()
{int T; scanf("%d", &T);while(T--){string s, t;cin >> s;t = s;ll ans = 0;int len = s.size(), l = 0, r = 0;ll last = 0;while(l < len && r < len){while(r + 1 < len && (s[r + 1] != s[r] || s[r] == '?' && s[r + 1] == '?')){if(s[r + 1] == '?'){if(s[r] == '1') s[r + 1] = '0';if(s[r] == '0') s[r + 1] = '1';}r++;}ans += f(r - l + 1) - last;if(t[r] == '?'){int p = r;while(p - 1 >= 0 && t[p - 1] == '?') p--;last = f(r - p + 1);l = p; r++;}else{last = 0;l = r + 1;r = l;}}printf("%lld\n", ans);}return 0;
}D. Playoff Tournament
挺裸的一道树形dp，但是考试时因为点的标号没想清楚最终没A出来
首先要建树，按照题目的的标号建一颗树
然后就树形dp统计
对于每次询问，从当前节点向上更新就好了
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e6 + 10;
int dp[N], l[N], r[N], f[N], fa[N], k, root;
string s;void dfs(int u)
{if(!l[u]){if(s[u] == '?') dp[u] = 2;else dp[u] = 1;return;}dfs(l[u]);dfs(r[u]);if(s[u] == '0') dp[u] = dp[l[u]];if(s[u] == '1') dp[u] = dp[r[u]];if(s[u] == '?') dp[u] = dp[l[u]] + dp[r[u]];
}void query(int u)
{if(!l[u]){if(s[u] == '?') dp[u] = 2;else dp[u] = 1;}else{if(s[u] == '0') dp[u] = dp[l[u]];if(s[u] == '1') dp[u] = dp[r[u]];if(s[u] == '?') dp[u] = dp[l[u]] + dp[r[u]];}if(u != root) query(fa[u]);
}void build()
{int t = k - 1, cnt = 0;while(t){vector<int> ve; ve.push_back(0);_for(i, 1, f[t]) ve.push_back(++cnt);t--;_for(i, 1, f[t]){int now = ++cnt;l[now] = ve[i * 2 - 1];r[now] = ve[i * 2];fa[l[now]] = now;fa[r[now]] = now;}cnt -= f[t];}
}int main()
{f[0] = 1;_for(i, 1, 19) f[i] = f[i - 1] * 2;cin >> k >> s;s = " " + s;build();root = f[k] - 1;dfs(root);int m; cin >> m;while(m--){int x; string op;cin >> x >> op;s[x] = op[0];query(x);printf("%d\n", dp[root]);}return 0;
}
P - FatMouse and Cheese（记忆化搜索）
好久没写记忆化搜索，竟然卡住了
这题倒过来想，dp[x][y]表示以(x, y)为起点的最大值
我一开始想的是为终点的最大值，发现很难搞
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 110;
int a[N][N], dp[N][N], n, k;int dfs(int x, int y)
{if(dp[x][y] != -1) return dp[x][y];int mx = 0;_for(xx, max(x - k, 1), min(x + k, n))if(a[x][y] < a[xx][y])mx = max(mx, dfs(xx, y));_for(yy, max(y - k, 1), min(y + k, n))if(a[x][y] < a[x][yy])mx = max(mx, dfs(x, yy));return dp[x][y] = a[x][y] + mx;
}int main()
{while(~scanf("%d%d", &n, &k)){if(n == -1 && k == -1) break;_for(i, 1, n)_for(j, 1, n)scanf("%d", &a[i][j]);memset(dp, -1, sizeof(dp));printf("%d\n", dfs(1, 1));}return 0;
}
Q - Phalanx
先翻转一下矩阵变成左上到右下
dp[i][j]表示以(i, j)为右下角的最大对称矩阵
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e3 + 10;
int dp[N][N], n;
char a[N][N];int main()
{while(scanf("%d", &n) && n){_for(i, 1, n){scanf("%s", a[i] + 1);reverse(a[i] + 1, a[i] + n + 1);}int ans = 1;_for(i, 1, n)_for(j, 1, n){dp[i][j] = 1;if(i == 1 || j == 1) continue;int x = j - 1, y = i - 1, cnt = 0;while(x >= 1 && y >= 1){if(a[i][x] != a[y][j]) break;x--; y--;cnt++;}dp[i][j] = min(dp[i - 1][j - 1], cnt) + 1;ans = max(ans, dp[i][j]);}printf("%d\n", ans);}return 0;
}
R - Milking Time
类似最长上升子序列的思路
水题
#include <cstdio>
#include <algorithm>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e3 + 10;
int dp[N], n, m, R;
struct segment
{int l, r, v;
}a[N];bool cmp(segment x, segment y)
{return x.l < y.l;
}int main()
{scanf("%d%d%d", &n, &m, &R);_for(i, 1, m) scanf("%d%d%d", &a[i].l, &a[i].r, &a[i].v);sort(a + 1, a + m + 1, cmp);int ans = 0;_for(i, 1, m){dp[i] = a[i].v;_for(j, 1, i - 1)if(a[j].r + R <= a[i].l)dp[i] = max(dp[i], dp[j] + a[i].v);ans = max(ans, dp[i]);}printf("%d\n", ans);return 0;
}
今晚训练赛，打得并不是很好，补它一波题，好好学一波
CodeForces - 1526B
这道题卡了很久……
主要是没意识到不需要考虑那么多1111
其实可以简化为11 和 111
因为11和111和转化出所有的1111 11111……
所以就是看11x + 111y = n
存不存在一组解使得x >=0 y >= 0
考试的时候算一下，可以直接枚举因子暴力
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;int main()
{int T; scanf("%d", &T);while(T--){int x; scanf("%d", &x);bool ok = false;_for(i, 0, 1e6){int t = 111 * i;int now = x - t;if(now < 0) break;if(now % 11 == 0){ok = true;break;}}puts(ok ? "YES" : "NO");}return 0;
}考完后想了想，可以用exgcd解不定方程的思路来弄
这样复杂度是O（1）的
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;int main()
{int T; scanf("%d", &T);while(T--){int n; scanf("%d", &n);int d = 1, x = -10, y = 1;x *= n / d, y *= n / d;int k = (-x + 110) / 111;x += k * 111;y -= k * 11;if(x >= 0 && y >= 0) puts("YES");else puts("NO");}return 0;
}看了官方题解，发现可以推出111的倍数是0到10，太秀了，其实111的倍数是很小的
C2. Potions (Hard Version)
这题也卡了一会儿
用优先队列贪心
每次把人加入队列，如果小于0，就弹出最小的，直到大于等于0
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
priority_queue<int, vector<int>, greater<int>> q;
int n, x;
ll sum;int main()
{scanf("%d", &n);_for(i, 1, n){scanf("%d", &x);sum += x;q.push(x);while(sum < 0) sum -= q.top(), q.pop();}printf("%d\n", q.size());return 0;
}
1528B - Kavi on Pairing Duty
比赛时已经想到了dp[i] = d[i - 1] + dp[i - 2] ……dp[i] + S
S就是全部长度相等有多少种，这部分我想错了导致没做出来
实际上，这部分的个数就是n的因子个数
这部分暴力的话n根号n
有类似筛法的方法可以做到nlogn
因此递推就好了
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e6 + 10;
const int mod = 998244353;
int dp[N], sz[N], n;int add(int a, int b) { return (a + b) % mod; }int main()
{scanf("%d", &n);_for(i, 1, n)for(int j = i; j <= n; j += i)sz[j]++;int sum = 1;dp[1] = 1;_for(i, 2, n){dp[i] = add(sz[i], sum);sum = add(sum, dp[i]);}printf("%d\n", dp[n]);return 0;
}
周日 6.6
B. Monopole Magnets
这道2000的cf题做出来了
但是有时我也会1700 1800的做不出来
所以不一定了，有些题比较符合我的思维，有些不符合，不好说
这道题就是一道思维题
首先一个显然的想法，可以黑格全部放S，这样在一个联通块里面，只要有N，就可以去到所有地方
但是注意，对于一个联通块，不可以走到白色区域
这么处理呢，可以判断每一个行和每一个列，看是否存在一行或一列中有两段以上的连续黑块
而不是dfs当前联通块时判断
还有一种不可行的情况，就是不能每行每列都放S
首先处理出联通块占了所有的行和列
看有多少行和多少列没被。只有其中一个数不为0，另一个数为0的情况才不可行
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e3 + 10;
int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
int vis[N][N], X[N], Y[N], n, m;
char s[N][N];void dfs(int x, int y)
{X[x] = Y[y] = 1;rep(i, 0, 4){int xx = x + dir[i][0], yy = y + dir[i][1];if(s[xx][yy] == '#' && !vis[xx][yy]){vis[xx][yy] = 1;dfs(xx, yy);}}
}int main()
{scanf("%d%d", &n, &m);_for(i, 1, n) scanf("%s", s[i] + 1);_for(i, 1, n){int cnt = 0;_for(j, 1, m)if(s[i][j] == '#' && s[i][j - 1] != s[i][j])cnt++;if(cnt > 1){puts("-1");return 0;}}_for(j, 1, m){int cnt = 0;_for(i, 1, n)if(s[i][j] == '#' && s[i - 1][j] != s[i][j])cnt++;if(cnt > 1){puts("-1");return 0;}}int ans = 0;_for(i, 1, n)_for(j, 1, m)if(s[i][j] == '#' && !vis[i][j]){dfs(i, j);ans++;}int cnt1 = 0, cnt2 = 0;_for(i, 1, n) cnt1 += !X[i];_for(i, 1, m) cnt2 += !Y[i];if(cnt1 && !cnt2 || !cnt1 && cnt2) puts("-1");else printf("%d\n", ans);return 0;
}
B - Array Reodering
之前写的一道题，发现官方题解有个代码写的很秀
把一个数组偶数放前面，奇数放后面
我当时是用partition
还有一种方法，就是用sort
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 2e3 + 10;
int a[N], n;int gcd(int a, int b) { return !b ? a : gcd(b, a % b); }int main()
{int T; scanf("%d", &T);while(T--){scanf("%d", &n);_for(i, 1, n) scanf("%d", &a[i]);sort(a + 1, a + n + 1, [](int x, int y) { return x % 2 == 0 && y % 2 == 1; } );int ans = 0;_for(i, 1, n)_for(j, i + 1, n)ans += gcd(a[i], a[j] * 2) > 1;printf("%d\n", ans);}return 0;
}
D. Playoff Tournament
旧题新写
发现自己写的非常非常麻烦，虽然AC了
其实可以简化很多
（1） 2的k次方直接1 << k
（2）转化一下下标发现类型线段树，只不过左边是+1右边不加1.处理一下就好了
（3）不用dfs，直接循环就好
#include <bits/stdc++.h>
#define l(k) (k << 1 | 1)
#define r(k) (k << 1)
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e6 + 10;
int dp[N], k, n;
string s;void update(int u)
{if(l(u) > n) dp[u] = 1 + (s[u] == '?'); //注意这里要加括号else{if(s[u] == '0') dp[u] = dp[l(u)];if(s[u] == '1') dp[u] = dp[r(u)];if(s[u] == '?') dp[u] = dp[l(u)] + dp[r(u)];}
}int main()
{cin >> k >> s;n = (1 << k) - 1; //直接1 << kreverse(s.begin(), s.end()); //转化下标s = " " + s;for(int i = n; i >= 1; i--) update(i);int m; cin >> m;while(m--){int x; string op;cin >> x >> op;x = n - x + 1; //转化一下s[x] = op[0];for(int i = x; i >= 1; i >>= 1) update(i);cout << dp[1] << endl;}return 0;
}
E. Gold Transfer（树上倍增）
E题没想的那么难，只是开始涉及到一些算法了
这道题就是树上倍增
显然应该找一个深度最浅的点，然后把这个点到根节点全部买了，这样是最优的
那么怎么找这个点呢，可以发现从根节点往给节点v找挺麻烦，要判断v在左子树还是右子树，想了想可以用dfs序。不过这题是动态的不能用dfs序
但是这样是O（q）的，会超时
考虑反过来，从节点v往根节点找，一直往上找，这样方便，也不要判断左右子树啥的
但是一样会超时。这个向下的过程不好优化，但向上的过程可以。
我一开始想到了二分，但是不知道怎么把这个路径给提取出来二分
但还可以联想到树上倍增，一次跳很多格，这样就可以在logq的时间内跳到那个点，然后统计答案
但是更新答案之后要改变a数组的值，这个时候我就懵逼了，不知道怎么一次性把找到的点到根节点的点全部赋值为0
显然不能暴力，暴力超时，然后我就卡住了
之后看了题解，我的思路已经有点接近题解了
题解是把购买分成一个节点一个节点的买，而我想的是一次性买
按照题解的话，就每次倍增找到一个最浅的a数组大于0的点，购买，修改a数组，然后继续倍增找下一个点
显然找到一个点后，下一个点就是它的儿子，这个儿子的子树包含了v
但是用程序不知道怎么实现，干脆就再找一次
这样看起来比较暴力，但实际上是不会超时的
因为一个节点最多被删除一次。总的复杂度是O（qlogq）的
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int N = 3e5 + 10;
int a[N], c[N], up[N][25], q;int main()
{scanf("%d%d%d", &q, &a[0], &c[0]);_for(u, 1, q){int op, v, w;scanf("%d", &op);if(op == 1){scanf("%d%d%d", &up[u][0], &a[u], &c[u]);_for(j, 1, 20) up[u][j] = up[up[u][j - 1]][j - 1];}else{scanf("%d%d", &v, &w);ll ansa = 0, ansc = 0;while(w && a[v]){int p = v;for(int j = 20; j >= 0; j--)if(a[up[p][j]])p = up[p][j];int t = min(w, a[p]);w -= t; a[p] -= t;ansa += t; ansc += 1ll * t * c[p];}printf("%lld %lld\n", ansa, ansc);fflush(stdout);}}return 0;
}
Mean Inequality
挺简单的
直接最高的放后面，然后一高一低一高一低
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 100;
int a[N], b[N], n;int main()
{int T; scanf("%d", &T);while(T--){scanf("%d", &n); n *= 2;_for(i, 1, n) scanf("%d", &a[i]);sort(a + 1, a + n + 1);b[n] = a[n];int l = 1, r = n - 1;for(int i = n - 1; i >= 1; i--){if(i & 1) b[i] = a[l++];else b[i] = a[r--];}_for(i, 1, n) printf("%d ", b[i]); puts("");}return 0;
}
E. Gold Transfer(逆序对)
这道题的翻转其实是迷惑你的
其实就是问一个字符串，每次操作可以交换相邻的两个字符，问最少交换多少次可以转化为另一个字符串
将目标字符串附上编号1 2 3 4 ……n
然后把这个编号赋给第二个字符串，如abc转化为cba
那么第二个字符串就是321
注意这里会有相同的字符串比较麻烦，比如aab为123， 那么原始字符串中有a，到底赋值1还是2呢？
顺序赋值，也就是第一a是1，第二个a是2，这样是最优的。这个可以用队列来实现，因为每次都尾部加入元素，然后取出头部头部出队
然后我们转为为数字后，问题转化为一个排列，最少经过多次交换使其有序，也就是变成123456……
这个答案就是逆序对，因为一次交换可以消灭一个逆序对，而有序时是没有逆序对的，所以就需要交换逆序对的个数
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 2e5 + 10;
queue<int> q[30];
int f[N], a[N], n;
string s, t;int lowbit(int x) { return x & (-x); }void add(int x)
{for(; x <= n; x += lowbit(x))f[x]++;
}int sum(int x)
{int res = 0;for(; x; x -= lowbit(x))res += f[x];return res;
}int main()
{cin >> n >> s;t = s;reverse(t.begin(), t.end());rep(i, 0, n) q[t[i] - 'a'].push(i + 1);rep(i, 0, n){a[i] = q[s[i] - 'a'].front();q[s[i] - 'a'].pop();}long long ans = 0;rep(i, 0, n){ans += sum(n) - sum(a[i]);add(a[i]);}printf("%lld\n", ans);return 0;
}