周一
今天的主要精力在学python
感觉一些事情上还是没有达到自己的期望
但大学还是抱着学习的心态去努力汲取知识
做一块海绵 用这宝贵时光努力学习成长
周二
今天早上跑了步，出了很多汗，整个人都舒服很多
坚持锻炼
最近今天有点摸鱼，回归猛肝的状态
搞起
P3522 [POI2011]TEM-Temperature（单调队列）
这道题首先发现要维护之前的一个区间的最大值
而这个区间又是连续的，左右端点只会增加，就用单调队列
注意单调队列里面存的值是区间的部分值，所以更新的时候要注意不一定是队头的来更新
交上去WA了
因为是最大值，所以我就写了一个单调递减的单调队列，以往我都这么写
但是这道题不行，因为相等的时候元素不能删，这道题更新答案的时候和其位置有关，相等的时候并不是等价的
以前更新答案的时候是f(x)的形式，x同f(x)就同，而这题不一样。
#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], a[N], b[N], q[N], n;int main()
{scanf("%d", &n);_for(i, 1, n) scanf("%d%d", &a[i], &b[i]);int l = 1, r = 1, ans = 1, first = 1;dp[1] = q[1] = 1;_for(i, 2, n){while(l <= r && a[q[l]] > b[i]){l++;if(l <= r) first = q[l];else first = i;}dp[i] = i - first + 1;ans = max(ans, dp[i]);while(l <= r && a[q[r]] < a[i]) r--;q[++r] = i;}printf("%d\n", ans);return 0;
}
P4544 [USACO10NOV]Buying Feed G（单调队列优化dp）
很容易想到dp[i][j]表示前i个坐标j吨饲料的最小花费
一开始想枚举之前所有的坐标，来转移，发现这样很慢
直接前i个，枚举前面一个买或不买，买的话买多少。也就是说存在不买的情况。
可以写出dp[i][j] = min(dp[i-1][j-t] * (x[i] - x[i - 1]) + t * c[i - 1])
0 <= t <= f[i - 1]
这样会超时，考虑单调队列优化
三层循环，i， j， t，显然优化第三层
然后我就卡住了，发现这样很难搞，我就把式子换了一下
dp[i-1][p] + j* j * (x[i] - x[i - 1]) + j * c[i - 1] - p * c[i - 1]
发现j* j * (x[i] - x[i - 1]) + j * c[i - 1]对于当前的dp[i][j]来说是定值
而i定时，dp[i - 1][p] - p * c[i - 1]这个东西是可以用单调队列优化的
因为p有范围，且值只与p本身有关（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 = 500 + 10;
const int M = 1e4 + 10;
struct node { ll x, f, c; };
vector<node> ve;
int q[M], k, e, n;
ll dp[N][M];bool cmp(node a, node b)
{return a.x < b.x;
}ll val(int i, int p)
{return dp[i - 1][p] - p * ve[i - 1].c;
}int main()
{scanf("%d%d%d", &k, &e, &n);_for(i, 1, n){ll x, f, c;scanf("%lld%lld%lld", &x, &f, &c);ve.push_back(node{x, f, c});}ve.push_back(node{e, 0, 0});sort(ve.begin(), ve.end(), cmp);_for(j, 1, k) dp[0][j] = 1e18;rep(i, 1, ve.size()){_for(j, 0, k) dp[i][j] = 1e18;int l = 1, r = 0;_for(j, 0, k){while(l <= r && val(i, q[r]) >= val(i, j)) r--;q[++r] = j;while(l <= r && j - ve[i - 1].f > q[l]) l++;dp[i][j] = min(dp[i][j], j * j * (ve[i].x - ve[i - 1].x) + j * ve[i - 1].c + val(i, q[l]));}}printf("%lld\n", dp[ve.size() - 1][k]);return 0;
}
P3572 [POI2014]PTA-Little Bird（单调队列）
逐渐进入状态
这题依然是单调队列
因为取最小的是dp值，所以按照dp值的大小来构造单调队列
这里的高度要注意
首先dp值小但高度更低也没有关系，这样结果至少不会更差
做单调队列的题目时要考虑是否可以相等的问题
这道题相等的时候要格外考虑，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 = 1e6 + 10;
int h[N], dp[N], q[N], n, m, k;int main()
{scanf("%d", &n);_for(i, 1, n) scanf("%d", &h[i]);scanf("%d", &m);while(m--){scanf("%d", &k);int l = 1, r = 1;q[1] = 1; dp[1] = 0;_for(i, 2, n){while(l <= r && q[l] < i - k) l++;dp[i] = dp[q[l]] + (h[q[l]] <= h[i]);while(l <= r && (dp[q[r]] > dp[i] || dp[q[r]] == dp[i] && h[q[r]] < h[i])) r--;q[++r] = i;}printf("%d\n", dp[n]);}return 0;
}
P3089 [USACO13NOV]Pogo-Cow S（状态设计与枚举顺序）
这题是看题解的
首先这个状态设计我就没想到，dp[j][i]表示从j跳到i的最大值
感觉就挺突然的………………还是太菜了
转移方程很好写 dp[j][i] = max(p[i] + dp[k][j]) = p[i] + max(dp[k][j])
考虑怎么优化，一开始想单调队列优化k，发现不行
因为在j移动的时候，dp[k][j]和j有关。这个值应该和移动j无关才行
然后我就卡住了
看了题解，真的妙，按照常规思维是先枚举i后枚举j
这里改成先枚举j后枚举i，这样子dp[k][j]的时候，就与移动i无关了
可以发现，固定j的时候，i逐渐增大，可以用来转移的dp[k][j]只会增加不会减少
因此就用一个变量来维护就行了
这题还要换个方向，这时其实很容易，把整个数组翻转一下再做一次就行了
#include <bits/stdc++.h>
#define x first
#define p second
#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], ans, n;
pair<int, int> a[N];void solve()
{_for(j, 1, n){dp[j][j] = a[j].p;int mx = dp[j][j], k = j;_for(i, j + 1, n){while(k - 1 >= 1 && abs(a[k - 1].x - a[j].x) <= abs(a[i].x - a[j].x)) mx = max(mx, dp[--k][j]);dp[j][i] = a[i].p + mx;}}_for(j, 1, n)_for(i, j, n)ans = max(ans, dp[j][i]);
}int main()
{scanf("%d", &n);_for(i, 1, n) scanf("%d%d", &a[i].x, &a[i].p);sort(a + 1, a + n + 1);solve();reverse(a + 1, a + n + 1);solve();printf("%d\n", ans);return 0;
}
D - Meaningless Sequence（数位dp）
接下来刷几道数位dp
数位dp无非是问一个区间内有多少个符合题目条件的数
每个数都有个值，如果问个数则值为1，问其他的看题目
这道题可以发现每个数的值就是c^（1的个数）
数位dp套模板就行
模板还是要深刻理解比较好。无非是lead 和 limit 记忆化搜索
这道题前导0，是否为第一位等无所谓
所以不需要lead
#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 = 3000 + 10;
const int mod = 1e9 + 7;
ll dp[N][N], c;
int len;
string a;int add(int a, int b) { return (a + b) % mod; }
int mul(int a, int b) { return 1LL * a * b % mod; }int binpow(int a, int b)
{int res = 1;for(; b; b >>= 1){if(b & 1) res = mul(res, a);a = mul(a, a);}return res;
}int dfs(int pos, int sum, int limit)
{if(pos >= len) return binpow(c, sum);if(!limit && dp[pos][sum] != -1) return dp[pos][sum];ll res = 0, mx = limit ? (a[pos] - '0') : 1;_for(i, 0, mx) res = add(res, dfs(pos + 1, sum + i, i == mx && limit));if(!limit) dp[pos][sum] = res;return res;
}int main()
{cin >> a >> c;len = a.size();memset(dp, -1, sizeof dp);printf("%d\n", dfs(0, 0, 1));return 0;
}
P4999 烦人的数学作业（数位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;
const int mod = 1e9 + 7;
int dp[25][200], a[25], len;int add(int a, int b) { return (a + b) % mod; }
int mul(int a, int b) { return 1LL * a * b % mod; }int dfs(int pos, int sum, int limit)
{if(pos > len) return sum;if(!limit && dp[pos][sum] != -1) return dp[pos][sum];int res = 0, mx = limit ? a[len - pos + 1] : 9;_for(i, 0, mx) res = add(res, dfs(pos + 1, sum + i, i == mx && limit));if(!limit) dp[pos][sum] = res;return res;
}int solve(ll x)
{len = 0;while(x) a[++len] = x % 10, x /= 10;memset(dp, -1, sizeof dp);return dfs(1, 0, 1);
}int main()
{int T; scanf("%d", &T);while(T--){ll l, r;scanf("%lld%lld", &l, &r);printf("%d\n", (solve(r) - solve(l - 1) + mod) % mod);}return 0;
}
P4124 [CQOI2016]手机号码（数位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;
ll dp[25][15][15][2][2][2], a[25], len;ll dfs(int pos, int pre1, int pre2, int have4, int have8, int ans, int lead, int limit)
{if(pos > len) return ans;if(!limit && !lead && dp[pos][pre1][pre2][have4][have8][ans] != -1) return dp[pos][pre1][pre2][have4][have8][ans];ll res = 0, mx = limit ? a[len - pos + 1] : 9;_for(i, 0, mx){if(!i && lead || i == 4 && have8 || i == 8 && have4) continue;res += dfs(pos + 1, i, pre1, have4 | i == 4, have8 | i == 8, ans | (i == pre1 && pre1 == pre2), 0, i == mx && limit);}if(!limit && !lead) dp[pos][pre1][pre2][have4][have8][ans] = res;return res;
}ll solve(ll x)
{len = 0;while(x) a[++len] = x % 10, x /= 10;memset(dp, -1, sizeof dp);return dfs(1, 10, 10, 0, 0, 0, 1, 1);
}int main()
{ll l, r;scanf("%lld%lld", &l, &r);if(l == 1e10) printf("%lld\n", solve(r));else printf("%lld\n", solve(r) - solve(l - 1));return 0;
}
P2606 [ZJOI2010]排列计数（dp统计方案数）
首先把这道题转化到图上
有多少种小根堆的方案
用dp[u]表示以u为根节点的子树有多少种方案
这时我们把最小的数放在u
左子树放一部分，数目是左子树的节点数，剩下的放右子树
这样dp[u] = C(size[u] - 1, size[l]) * dp[l] * dp[r]
用dfs遍历就行 注意边界条件是当这个点为叶子的时候返回1
这里有坑，就是模数可能比较小,可能求组合数的时候n n - m是模数的倍数
这样就不能用费马小定理。解决方法是Lucas 定理
不用考虑具体怎么放，总之就是当前数最小的放在根，然后递归下去
#include <bits/stdc++.h>
#define l(k) (k << 1)
#define r(k) (k << 1 | 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 fac[N], siz[N], n, mod;int add(int a, int b) { return (a + b) % mod; }
int mul(int a, int b) { return 1LL * a * b % mod; }int binpow(int a, int b)
{int res = 1;for(; b; b >>= 1){if(b & 1) res = mul(res, a);a = mul(a, a);}return res;
}int inv(int x) { return binpow(x, mod - 2); }void init(int u)
{siz[u] = 1;if(l(u) <= n) init(l(u)), siz[u] += siz[l(u)];if(r(u) <= n) init(r(u)), siz[u] += siz[r(u)];
}int cal(int n, int m)
{if(m > n) return 0;return mul(fac[n], mul(inv(fac[m]), inv(fac[n - m])));
}int C(int n, int m)
{if(m == 0) return 1;return mul(cal(n % mod, m % mod), C(n / mod, m / mod));
}int dfs(int u)
{if(l(u) > n) return 1;return mul(mul(C(siz[u] - 1, siz[l(u)]), dfs(l(u))), dfs(r(u)));
}int main()
{scanf("%d%d", &n, &mod);fac[0] = 1; _for(i, 1, n) fac[i] = mul(fac[i - 1], i);init(1);printf("%d\n", dfs(1));return 0;
}
周三
昨天效率很高，今天继续肝
开始刷洛谷cf 2100 dp 的题单
CF353D Queue（线性dp）
一个女生前面有男生，就至少交换多少次
如果这个女生前面还有女生，那就是前面这个女生所需要的次数+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()
{string s;cin >> s;int len = s.size(), cnt = 0, ans = 0;rep(i, 0, len){if(s[i] == 'M') cnt++;if(cnt && s[i] == 'F') ans = max(ans + 1, cnt);}printf("%d\n", ans);return 0;
}
CF837D Round Subset（背包拓展）
这题还是蛮有收获的
自己想的时候想到了三维费用背包，5的个数，2的个数，选的数的个数
值为0或1表示是否存在
但是这样时间和空间都会爆炸，就懵逼了
看了题解发现很巧妙
把其中一个维度放到dp值里面
比如把2的个数放到dp值里面，这样时间和空间都少了一维，就可做了
统计的时候扫一遍就行了
注意这题的背包是要刚好放满，所以存在很多不合法的状态，要去掉
是否存在不合法的状态看状态的设计
解决方法是初始化最小，用-0x3f
#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 = 200 + 10;
const int M = 6e3;
int dp[N][M], w[N], v[N], n, m, k;int get(ll x, int p)
{int res = 0;while(x % p == 0){res++;x /= p;}return res;
}int main()
{scanf("%d%d", &n, &k);_for(i, 1, n){ll x; scanf("%lld", &x);w[i] = get(x, 5);v[i] = get(x, 2);m += w[i];}memset(dp, -0x3f, sizeof dp);dp[0][0] = 0;_for(i, 1, n)for(int j = k; j >= 1; j--)for(int r = m; r >= w[i]; r--)dp[j][r] = max(dp[j][r], dp[j - 1][r - w[i]] + v[i]);int ans = 0;for(int i = m; i >= 0; i--)ans = max(ans, min(dp[k][i], i));printf("%d\n", ans);return 0;
}
D. Police Stations（BFS求最短路）
之前比赛中遇到类似的题，也是求每个节点到特定节点的距离的
也是把特定节点扔队列中bfs
这道题一看我就想到这个思路
但是这道题是dp题单里面的，我就往树形dp方面想，结果弄不出来…………
这题蛮巧妙的，其实d根本没有用
把每个点bfs进行染色，被染色到的节点一定是离其最近的，一定是满足题目所说的距离d的条件
这时我们枚举每一条边，如果两个端点颜色不同这条边就可以删掉
注意有坑，可能有两个警察局在同一个点。这时只能算一个警察局
#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 = 3e5 + 10;
struct node { int v, color; };
int color[N], a[N], b[N], n, k, d;
vector<int> g[N];
queue<node> q;int main()
{scanf("%d%d%d", &n, &k, &d);_for(i, 1, k){int x; scanf("%d", &x);if(!color[x]){q.push(node{x, i});color[x] = i;}}_for(i, 1, n - 1){scanf("%d%d", &a[i], &b[i]);g[a[i]].push_back(b[i]);g[b[i]].push_back(a[i]);}while(!q.empty()){node x = q.front(); q.pop();int u = x.v, c = x.color;for(int v: g[u]){if(color[v]) continue;q.push(node{v, color[v] = c});}}int ans = 0;_for(i, 1, n - 1)if(color[a[i]] != color[b[i]])ans++;printf("%d\n", ans);_for(i, 1, n - 1)if(color[a[i]] != color[b[i]])printf("%d ", i);puts("");return 0;
}D. Bad Luck Island（概率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 + 10;
double dp[N][N][N];
int r, s, p;int main()
{scanf("%d%d%d", &r, &s, &p);dp[r][s][p] = 1;for(int i = r; i >= 0; i--)for(int j = s; j >= 0; j--)for(int k = p; k >= 0; k--){double sum = i * j + i * k + j * k;if(fabs(sum) < 1e-8) continue;if(i - 1 >= 0) dp[i - 1][j][k] += dp[i][j][k] * i * k / sum;if(j - 1 >= 0) dp[i][j - 1][k] += dp[i][j][k] * i * j / sum;if(k - 1 >= 0) dp[i][j][k - 1] += dp[i][j][k] * j * k / sum;}double ans1 = 0, ans2 = 0, ans3 = 0;_for(i, 0, r) ans1 += dp[i][0][0];_for(i, 0, s) ans2 += dp[0][i][0];_for(i, 0, p) ans3 += dp[0][0][i];printf("%.12f %.12f %.12f\n", ans1, ans2, ans3);return 0;
}
CodeForces 527D（转化式子 + 线段覆盖）
这个道题我没有去转化那个式子……
其实就把绝对值拆掉，把i放一起，j放一起
发现可以转化为线段覆盖问题，左端点是x - w 右端点是 x + w
问最多选多个个线段使得没有重叠部分
贪心就好，按照右端点排序，注意不是左端点
#include <bits/stdc++.h>
#define r first
#define l second
#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;
vector<pair<int, int>> ve;
int n;int main()
{scanf("%d", &n);_for(i, 1, n){int x, w;scanf("%d%d", &x, &w);ve.push_back(make_pair(x + w, x - w));}sort(ve.begin(), ve.end());int ans = 1, r = ve[0].r;rep(i, 1, ve.size()){if(ve[i].l < r) continue;ans++;r = ve[i].r;}printf("%d\n", ans);return 0;
}
周四
昨天成绩出来绩点专业第二，然后挺开心的就有点干扰训练
过去的已经过去了
今天搞起
CF478D Red-Green Towers（01背包统计方案数）
这题我右往背包的方向想，但是不知道怎么转化成这个模型
我想的时候两种颜色的方块混在一起考虑了，这样很难想
其实只考虑一种方块就好了，另一种方块只是限制了这种方块数量的下界
转化成01背包，物品重量为1，2，……h
总容量为r，问有多少种放置方案
也就是01背包统计方案数
统计的时候从下界到上界求和就行了
#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 mod = 1e9 + 7;
const int N = 2e5 + 10;
int dp[N], r, g, h = 1;int add(int a, int b) { return (a + b) % mod; }int main()
{scanf("%d%d", &r, &g);while((h + 1) * (h + 2) / 2 <= r + g) h++;dp[0] = 1;_for(i, 1, h)for(int j = r; j >= i; j--)dp[j] = add(dp[j], dp[j - i]);int ans = 0;_for(i, max(h * (h + 1) / 2 - g, 0), r)ans = add(ans, dp[i]);printf("%d\n", ans);return 0;
}
CF505C Mr. Kitayuta, the Treasure Hunter(dp状态设计)
我的dp还是比较弱，多练
首先贪心什么的是不行的，考虑dp
很容易想到把位置作为第一维
可以发现这个选择跳c - 1 c c + 1有后效性
那怎么办？那就把这个也变成一维
发现这样空间会炸
解决方法把这一维改成与d相对的值，这样最多就300次
注意很多状态是不合法的，初始化最小
此外，一开始就初始化某些值的时候，ans就为那个值，不要初始化为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 = 3e4 + 10;
int v[N], dp[N][650], d = 320, n, m, last;int main()
{scanf("%d%d", &n, &m);_for(i, 1, n){int x; scanf("%d", &x);v[x]++;last = x;}memset(dp, -0x3f, sizeof dp);dp[m][d] = v[m];int ans = dp[m][d];_for(cur, m + 1, last)_for(k, -300, 300){int mov = m + k;if(cur - mov < m || cur - mov > last) continue;dp[cur][k + d] = v[cur] + max(dp[cur - mov][k + d], max(dp[cur - mov][k + d + 1], dp[cur - mov][k + d - 1]));ans = max(ans, dp[cur][k + d]);}printf("%d\n", ans);return 0;
}
P5788 【模板】单调栈
做题遇到了单调栈，复习一下单调栈
首先清楚单调栈可以用来干嘛
单调栈能O(n)时间处理出每个数离它最近的比他大/小的元素
可以处理出以一个数为最大/小值的最长区间
这道题就是要处理出每个数在右边离它最近的比它大的元素
暴力就n方，每次都往后扫。扫到第一个大于它的数
我们考虑倒着扫，依然是n方的
但是我们能否利用之前的结果呢
可以发现如果x 在 y 的右侧，x还小于等于 y 那么x是永远不可能为答案的
有点像单调队列。
怎么表示这个下标的大小的关系呢？用栈。越靠近栈顶的元素是离当前的数最近的
把上面那个排除条件放到栈里，就是更靠近栈顶又更小的元素要删除
可以发现这样删除之后，就是一个单调的栈，栈顶最小
做的过程中其实依然是暴力，只是说那些不可能为答案的点删掉了，之后的暴力就不会浪费这个时间检查这个点了
因此每次对于当前元素，先维护栈的单调性，比当前元素小于等于的弹出，然后这时栈顶就是大于它的，就是答案。然后再加入当前元素
注意栈里面存的是下标，比较的时候是比较元素，要区分
总结起来就是维护一个单调的栈，加入元素的时候要弹出一些点来维护单调性，弹完后用这时的栈顶来统计答案
#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 = 3e6 + 10;
int a[N], s[N], ans[N], top, n;int main()
{scanf("%d", &n);_for(i, 1, n) scanf("%d", &a[i]);for(int i = n; i >= 1; i--){while(top && a[i] >= a[s[top]]) top--;ans[i] = !top ? 0 : s[top];s[++top] = i;}_for(i, 1, n) printf("%d ", ans[i]); puts("");return 0;
}
CF547B Mike and Feet（贡献 + 单调栈）
这题不要一个区间一个区间去考虑
而要考虑每个数对区间的贡献
也就是考虑每个数什么情况下会影响答案
只有一个数为一个区间的最小值的时候会影响答案
所以就求出以当前这个数为最小值的最大区间，这样这个数会影响从1 到 这个区间长度的答案
也就是要求离这个数最近的小于它的下标的数在哪里
这就是单调栈的模板题了
注意写单调栈弹出元素的时候写while 我开始写成if了
#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;
int a[N], l[N], r[N], s[N], k[N], ans[N], top, n;int main()
{scanf("%d", &n);_for(i, 1, n) scanf("%d", &a[i]);_for(i, 1, n){while(top && a[i] <= a[s[top]]) top--;l[i] = !top ? 1 : s[top] + 1;s[++top] = i;}top = 0;for(int i = n; i >= 1; i--){while(top && a[i] <= a[s[top]]) top--;r[i] = !top ? n : s[top] - 1;s[++top] = i;}int mx = 0;_for(i, 1, n) k[r[i] - l[i] + 1] = max(k[r[i] - l[i] + 1], a[i]);for(int i = n; i >= 1; i--){mx = max(mx, k[i]);ans[i] = mx;}_for(i, 1, n) printf("%d ", ans[i]); puts("");return 0;
}
有点肝不动了……我发现我又连肝了五天
休息休息
周日（牛客第一场补题）
前天休息
昨天整理模板 + 牛客
今天补牛客题
A.Alice and Bob（博弈）
这个博弈论当时我还在想到底是什么策略，因为之前都是想什么策略最好
还是做题太少，方向错了。直接打表
ans[i][j]表示剩下i个石子和j个石子的时候 1表示Alice胜，0表示Bob胜
那么就递推就好了，枚举所有可能取的情况
当前值为0，递推过去则值为1。有点类似素数筛
最开始值为0的为ans[0][0] 然后0 0 去递推
这时第二个值为0，无论Alice怎么取，总会落到值为1的ans值,因为其前面只有0 0值为0，而当前这个状态没有被递推到，说明不能到0 0 然后这个状态又继续去递推
遇到第三个值为0的，同样无论Alice怎么取，总会落到值为1的ans值
#include <bits/stdc++.h>
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
#define rep(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int N = 5000 + 10;
bool ans[N][N]; //用bool更快void read(int& x)
{x = 0; char ch = getchar();while(!isdigit(ch)) ch = getchar();while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
}int main()
{rep(i, 0, N)rep(j, 0, N)if(!ans[i][j]){for(int k = 1; i + k < N; k++)for(int s = 0; j + s * k < N; s++)ans[i + k][j + s * k] = 1;for(int k = 1; j + k < N; k++)for(int s = 0; i + s * k < N; s++)ans[i + s * k][j + k] = 1;}int T; read(T);while(T--){int a, b;read(a); read(b);if(ans[a][b]) puts("Alice");else puts("Bob");}return 0;
}
H.Hash Function（暴力 + 优化）
比赛时没想到优化……
首先可以直到这个答案肯定是大于等于n的，所以直接从n开始枚举答案
直接暴力就是取模然后看是否有重复
优化的话，就是当答案比较大的时候取模相当于没取模
所以可以直接从比答案大的地方才开始取模，至于比答案小的部分，可以直接预处理一个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;const int N = 5e5 + 10;
unordered_map<int, bool> vis;
int a[N], n;bool check(int key)
{for(int i = n; a[i] >= key; i--)if(vis[a[i] % key])return false;return true;
}int main()
{scanf("%d", &n);_for(i, 1, n) scanf("%d", &a[i]), vis[a[i]] = 1;sort(a + 1, a + n + 1);for(int ans = n; ; ans++)if(check(ans)){printf("%d\n", ans);break;}return 0;
}
上面那题正解是FFT
补一下知识点
【模板】多项式乘法（FFT）
两个多项式相乘要O(n^2)
FFT可以优化到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 = 4e6 + 10; //开最高次数的四倍
const double pi = acos(-1.0);struct Complex
{double x, y;
}a[N], b[N], c[N];
int ans[N], r[N], n, m, l, limit = 1;Complex operator + (Complex a, Complex b) { return Complex{a.x + b.x, a.y + b.y}; }
Complex operator - (Complex a, Complex b) { return Complex{a.x - b.x, a.y - b.y}; }
Complex operator * (Complex a, Complex b) { return Complex{a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x}; }void FFT(Complex *A, int type)
{rep(i, 0, limit)if(i < r[i])swap(A[i], A[r[i]]);for(int mid = 1; mid < limit; mid <<= 1){Complex Wn{cos(pi / mid), type * sin(pi / mid)};for(int R = mid << 1, j = 0; j < limit; j += R){Complex w{1, 0};for(int k = 0; k < mid; k++, w = w * Wn) //复数没重载 *= 用*{Complex x = A[j + k], y = w * A[j + mid + k];A[j + k] = x + y;A[j + mid + k] = x - y;}}}
}void read() //读入一个n次多项式和一个m次多项式
{scanf("%d%d", &n, &m);_for(i, 0, n) scanf("%lf", &a[i].x); //a[i].x表示x^i项的系数_for(i, 0, m) scanf("%lf", &b[i].x);
}void solve()
{while(limit <= n + m) limit <<= 1, l++;rep(i, 0, limit) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));FFT(a, 1); FFT(b, 1);_for(i, 0, limit) c[i] = a[i] * b[i];FFT(c, -1);_for(i, 0, n + m) ans[i] = (int)(c[i].x / limit + 0.5);
}int main()
{read();solve();_for(i, 0, n + m) printf("%d ", ans[i]); //答案存在ans数组中return 0;
}
Hash Function（FFT）
这道题需要快速求出任意两个数的差值
这个可以用多项式乘法实现
如果a存在，那么第一个多项式中x ^ a系数为 1 第二个多项式中x ^ (5e5 - a)系数为1
因为次幂不为负，所以加一个5e5
然后这两个多项式卷积，也就是相乘,就可以判断差值是否存在
用FFT来加速这个多项式乘法
这道题还可以用NTT做 明天学一学
#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 = 2e6 + 10;
const int len = 5e5;
const double pi = acos(-1.0);struct Complex
{double x, y;
}a[N], b[N], c[N];
int ans[N], r[N], n, m, l, limit = 1;Complex operator + (Complex a, Complex b) { return Complex{a.x + b.x, a.y + b.y}; }
Complex operator - (Complex a, Complex b) { return Complex{a.x - b.x, a.y - b.y}; }
Complex operator * (Complex a, Complex b) { return Complex{a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x}; }void FFT(Complex *A, int type)
{rep(i, 0, limit)if(i < r[i])swap(A[i], A[r[i]]);for(int mid = 1; mid < limit; mid <<= 1){Complex Wn{cos(pi / mid), type * sin(pi / mid)};for(int R = mid << 1, j = 0; j < limit; j += R){Complex w{1, 0};for(int k = 0; k < mid; k++, w = w * Wn){Complex x = A[j + k], y = w * A[j + mid + k];A[j + k] = x + y;A[j + mid + k] = x - y;}}}
}void read()
{scanf("%d", &n);_for(i, 1, n){int t; scanf("%d", &t);a[t].x = b[len - t].x = 1;}n = m = len;
}void solve()
{while(limit <= n + m) limit <<= 1, l++;rep(i, 0, limit) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));FFT(a, 1); FFT(b, 1);_for(i, 0, limit) c[i] = a[i] * b[i];FFT(c, -1);_for(i, 0, n + m) ans[i] = (int)(c[i].x / limit + 0.5);
}bool check(int key)
{for(int cur = key; cur <= len; cur += key)if(ans[len + cur])return false;return true;
}int main()
{read();solve();for(int ans = 1; ; ans++)if(check(ans)){printf("%d\n", ans);break;}return 0;
}