周一 5.17
昨晚很晚睡，搞得今天状态很差
坚持早睡早起，锻炼身体
「一本通 5.5 练习 1」烽火传递
秒切
表示第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 = 2e5 + 10;
int a[N], dp[N], q[N], n, m;int main()
{scanf("%d%d", &n, &m);_for(i, 1, n) scanf("%d", &a[i]);int l = 1, r = 1;_for(i, 1, n){if(l <= r && q[l] < i - m) l++;dp[i] = a[i] + dp[q[l]];while(l <= r && dp[q[r]] >= dp[i]) r--;q[++r] = i;}int ans = 1e9;_for(i, n - m + 1, n)ans = min(ans, dp[i]);printf("%d\n", ans);return 0;
}
「一本通 5.5 练习 2」绿色通道
又很快切掉了
首先看答案的询问方式，最大的最小，这不就二分答案吗
那么确定空题段了之后，实际上就是确定了最长区间的大小了
表示第i题必抄切1~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 = 5e4 + 10;
int a[N], dp[N], q[N], n, t;bool check(int m)
{int l = 1, r = 1;_for(i, 1, n){if(l <= r && i - q[l] - 1 > m) l++;dp[i] = a[i] + dp[q[l]];while(l <= r && dp[q[r]] >= dp[i]) r--;q[++r] = i;}int res = 1e9;_for(i, n - m, n)res = min(res, dp[i]);return res <= t;
}int main()
{scanf("%d%d", &n, &t);_for(i, 1, n) scanf("%d", &a[i]);int l = -1, r = n;while(l + 1 < r){int m = l + r >> 1;if(check(m)) r = m;else l = m;}printf("%d\n", r);return 0;
}
「一本通 5.5 练习 3」理想的正方形
又很顺利的切掉了
这道题一维就很简单，直接裸的滑动窗口
二维就跑两次单调队列就行了
第一次跑每一行，像一维那样的单调队列
第二次就固定一个列跑单调队列，每次的元素时第一次跑单调队列的最值
#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 a[N][N], b[N][N], ans1[N][N], ans2[N][N], q[N], n, m, k;int main()
{scanf("%d%d%d", &n, &m, &k);_for(i, 1, n)_for(j, 1, m)scanf("%d", &a[i][j]);_for(i, 1, n){int l = 1, r = 0;_for(j, 1, m){if(l <= r && q[l] <= j - k) l++;while(l <= r && a[i][q[r]] >= a[i][j]) r--; q[++r] = j;b[i][j] = a[i][q[l]];}}_for(j, k, m){int l = 1, r = 0;_for(i, 1, n){if(l <= r && q[l] <= i - k) l++;while(l <= r && b[q[r]][j] >= b[i][j]) r--;q[++r] = i;ans1[i][j] = b[q[l]][j];}}_for(i, 1, n){int l = 1, r = 0;_for(j, 1, m){if(l <= r && q[l] <= j - k) l++;while(l <= r && a[i][q[r]] <= a[i][j]) r--; q[++r] = j;b[i][j] = a[i][q[l]];}}_for(j, k, m){int l = 1, r = 0;_for(i, 1, n){if(l <= r && q[l] <= i - k) l++;while(l <= r && b[q[r]][j] <= b[i][j]) r--;q[++r] = i;ans2[i][j] = b[q[l]][j];}}int ans = 2e9;_for(i, 1, n)_for(j, 1, m)if(i >= k && j >= k)ans = min(ans, ans2[i][j] - ans1[i][j]);printf("%d\n", ans);return 0;
}
周二 5.18（单调队列优化dp）
P2569 [SCOI2010]股票交易
这道题是看题解的，学到了很多很多
主要是两个点，一个是dp方程，一个是单调队列的写法
(1)很容易想到表示前i天，手上有j股赚最多的钱
这时i有三种设计方法，一种是第i天一定交易，一种是第i天一定不交易，一种是第i天交易或不交易
这个挺关键的，我一开始想的是第i天一定交易，导致推出的dp方程时间复杂度有n的四次方，这题看数据范围就是n的平方
要优化两个n，我就懵逼了，最多就单调队列优化掉一个，还有一个咋整
所以肯定是我弄错了
结果果然是，应该设第i天交易或不交易，类似背包里面的f[i][j]
然后就是分类讨论了
(1)第i天不交易
(2)第i天交易，的j是交易过后的
对于买股票
这里有个非常关键的一点就是
我开始想的那个再优化一个n就是从这里来
第i天交易，离第i天最近的能交易的就是第天
那为什么不选择, 呢
我开始想的时候就是都要选，所以多了一个n
实际上不用，因为状态设计的缘故,已经包含了的结果了
注意前面有
或者说已经包括了的最优结果了
这种情况下，时间复杂度是n^3的
我们看到这里有一个区间长度，所以提示我们用单调队列优化
要枚举i,j,k,显然要优化k，区间范围是k
那么我们就把dp方程中有关k的部分提出来，i，j看作常值
于是就可以用单调队列优化了
可以把那一坨式子写一个函数，会方便点，表示单调队列中元素的值
卖钱也是一样，注意这时k > j，因此要逆序
(2)然后讲一下单调队列写法的问题，我因为这个卡了很久
我看了蛮多单调队列的题解，发现l和r的写法每道题各不相同，也很少有人解释一下为什么这么写……
一般是这么写
l = 1 r = 0
因为这样加入第一个元素q[++r] = i
就刚好是l = 1, r = 1, q[1] = i
刚刚好
问题在于有时候在循环中，还没执行q[++r] = i时，一上来就取出队头，但是这个时候队列为空，这个时候该这么处理？
常用的做法是开始令l = 1, r = 1
即默认一开始队列中有一个0，代表为空，一般来说这样第一个dp值转移的时候是不会错的，可以自己验证一下
有些题中这个0还非常重要 比如P4954 [USACO09OPEN]Tower of Hay G中，0代表空地，一定要加入
但是这道题不一样，这道题转移第一个dp值用0就会错，因为这个时侯根据dp方程0不再代表空了
那么就看第一个dp值要怎么处理，发现一开始队列为空时，就不转移就行了，所以一开始就直接判队列是否为空就好了
还有一点，初始化的时候初始化l和r就行了，q数组里面的值不用清空，有值没有影响。
#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 ap[N], bp[N], as[N], bs[N];
int dp[N][N], q[N], n, m, w;int val1(int t, int k, int i)
{return dp[t][k] + k * ap[i];
}int val2(int t, int k, int i)
{return dp[t][k] + k * bp[i];
}int main()
{scanf("%d%d%d", &n, &m, &w);_for(i, 1, n) scanf("%d%d%d%d", &ap[i], &bp[i], &as[i], &bs[i]);memset(dp, 128, sizeof(dp)); //因为能买的股有限制，所以有些状态压根不存在，所以全部初始化最小_for(i, 1, n){_for(j, 0, as[i]) dp[i][j] = -j * ap[i];_for(j, 0, m) dp[i][j] = max(dp[i][j], dp[i - 1][j]);int t = i - w - 1;if(t <= 0) continue;int l = 1, r = 0;_for(j, 0, m){if(l <= r && j - q[l] > as[i]) l++;if(l <= r) dp[i][j] = max(dp[i][j], val1(t, q[l], i) - j * ap[i]);while(l <= r && val1(t, q[r], i) <= val1(t, j, i)) r--;q[++r] = j;}l = 1, r = 0;for(int j = m; j >= 0; j--){if(l <= r && q[l] - j > bs[i]) l++;if(l <= r) dp[i][j] = max(dp[i][j], val2(t, q[l], i) - j * bp[i]);while(l <= r && val2(t, q[r], i) <= val2(t, j, i)) r--;q[++r] = j;}}printf("%d\n", dp[n][0]);return 0;
}「一本通 5.6 例 1」任务安排 1
按照题意，第j批任务完成的时间是j * s + T[i]
这个第几批任务就挺麻烦，复杂度要到n^3
怎么优化呢
第一个循环前i个以及枚举以i为结尾的一批不好优化
考虑优化j
之所以要j，是因为不知道是第几批，这个第几批影响到费用的计算
所以用一个很骚的思想，叫费用提前计算
对于当前这一批会多一个s，对总答案的贡献就是
s * (c[n] - c[j]) j表示第j + 1到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 = 5e3 + 10;
int T[N], C[N], dp[N], n, s;int main()
{scanf("%d%d", &n, &s);_for(i, 1, n){int t, c;scanf("%d%d", &t, &c);T[i] = T[i - 1] + t;C[i] = C[i - 1] + c;}memset(dp, 0x3f, sizeof(dp));dp[0] = 0;_for(i, 1, n)_for(j, 0, i - 1)dp[i] = min(dp[i], dp[j] + T[i] * (C[i] - C[j]) + s * (C[n] - C[j]));printf("%d\n", dp[n]);return 0;
}
周六 5.22
前几天各种作业考试什么的很多，就没训练
周末搞一搞训练赛的题目
D. Remove One Element
水题
我当时写了一个线性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 = 2e5 + 10;
int a[N], dp[N][2], n;int main()
{scanf("%d", &n);_for(i, 1, n) scanf("%d", &a[i]);int ans = 0;_for(i, 1, n){if(a[i] > a[i - 1]){dp[i][0] = dp[i - 1][0] + 1;dp[i][1] = dp[i - 1][1] + 1;}else dp[i][0] = dp[i][1] = 1;if(i >= 2 && a[i] > a[i - 2])dp[i][1] = max(dp[i][1], dp[i - 2][0] + 1);ans = max(ans, max(dp[i][0], dp[i][1]));}printf("%d\n", ans);return 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 = 2e5 + 10;
int a[N], l[N], r[N], n;int main()
{scanf("%d", &n);_for(i, 1, n) scanf("%d", &a[i]);_for(i, 1, n){if(a[i] > a[i - 1]) l[i] = l[i - 1] + 1;else l[i] = 1;}for(int i = n; i >= 1; i--){if(a[i] < a[i + 1]) r[i] = r[i + 1] + 1;else r[i] = 1;}int ans = 0;_for(i, 1, n) ans = max(ans, l[i]);_for(k, 1, n)if(a[k - 1] < a[k + 1])ans = max(ans, l[k - 1] + r[k + 1]);printf("%d\n", ans);return 0;
}周日 5.23（训练赛补题）
poj 1375（高中数学）
跟之前训练赛的题非常像
就是要求直线的斜率
比赛的时候感觉计算非常的复杂，就没算了
补题的时候发现我弄复杂了，因为只需要解出k，所以有k的放一边，没有k的放一边
最后解一元二次方程就好了
这次是死在数学上
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
#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;double x1, y1;
int n;pair<double, double> get(double x, double y, double r)
{double a = (x - x1) * (x - x1) - r * r;double b = 2 * (x - x1) * (y1 - y);double c = (y - y1) * (y - y1) - r * r;double k1, k2, x3, x4;if(fabs(a) > 1e-8){double t = sqrt(b * b - 4 * a * c);k1 = (-b + t) / (2 * a), k2 = (-b - t) / (2 * a);x3 = x1 - y1 / k1, x4 = x1 - y1 / k2;}else{x3 = x1;k2 = -c / b;x4 = x1 - y1 / k2;}if(x3 > x4) swap(x3, x4);return make_pair(x3, x4);
}int main()
{while(scanf("%d", &n) && n){vector<pair<double, double> > ve, ans;scanf("%lf%lf", &x1, &y1);_for(i, 1, n){double x, y, r;scanf("%lf%lf%lf", &x, &y, &r);ve.push_back(get(x, y, r));}sort(ve.begin(), ve.end());double l = ve[0].first, r = ve[0].second;REP(i, 1, ve.size()){double ll = ve[i].first, rr = ve[i].second;if(ll < r) r = max(r, rr);else{ans.push_back(make_pair(l, r));l = ll, r = rr;}}ans.push_back(make_pair(l, r));REP(i, 0, ans.size()) printf("%.2f %.2f\n", ans[i].first, ans[i].second);puts("");}return 0;
}
CodeForces - 1519D（观察）
这道题一开始是想用dp的，用dp[i][j]表示i到j的值
但是发现不知道怎么写转移方程，就懵逼了
关键是观察到dp[i][j] 可以转移到dp[i - 1][j + 1]
因为对称轴是一样的。翻转问题中对称轴很重要
于是枚举对称轴就行了，O（n^2）
发现dp数组都可以省掉
自己想的时候就是暴力区间加暴力计算n^3
这里优化的关键在于利用了之前计算的结果，现在的结果可以由之前的结果推出来
#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 = 5000 + 10;
ll a[N], b[N], s1[N], s2[N];
int n;int main()
{scanf("%d", &n);_for(i, 1, n) scanf("%lld", &a[i]);_for(i, 1, n) scanf("%lld", &b[i]);_for(i, 1, n) s1[i] = s1[i - 1] + a[i] * b[i];for(int i = n; i >= 1; i--) s2[i] = s2[i + 1] + a[i] * b[i];ll ans = s1[n];_for(k, 1, n){ll sum = a[k] * b[k];int l = k, r = k;while(1 <= l && r <= n){ans = max(ans, sum + s1[l - 1] + s2[r + 1]);sum += a[l - 1] * b[r + 1] + a[r + 1] * b[l - 1];l--; r++;}if(k + 1 > n) continue;l = k, r = k + 1;sum = a[l] * b[r] + a[r] * b[l];while(1 <= l && r <= n){ans = max(ans, sum + s1[l - 1] + s2[r + 1]);sum += a[l - 1] * b[r + 1] + a[r + 1] * b[l - 1];l--; r++;}}printf("%lld\n", ans);return 0;
}
Gym - 102823G（数学）
就是一道思维数学题
考试的时候想到做差gcd，只能说想到了一半，还有另一半没想清楚
首先既然每个数加一个x都是一个g的倍数（g > 1）
那么可以每个数都减去第一个数把x都减掉
这个时候就都是g的倍数了，就把这些数求gcd得到g
这个时候注意，g的所有因子的符合条件，而不仅仅是g
每一个因子都对应不同的x，所以我们应该选择一个最优的因子使得x最小
对于一个因子k，如果a[1] % k == 0那就x = 0， 否则x = k - a[1] % k
#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 = 1e5 + 10;
int a[N], b[N], n;void update(int& ans, int g)
{if(a[1] % g == 0) ans = min(ans, 0);else ans = min(ans, g - a[1] % g);
}int gcd(int a, int b)
{if(!a) return b;return !b ? a : gcd(b, a % b);
}int main()
{int T, kase = 0;scanf("%d", &T);while(T--){scanf("%d", &n);_for(i, 1, n) scanf("%d", &a[i]);_for(i, 1, n) b[i] = abs(a[i] - a[1]);int g = b[1];_for(i, 2, n) g = gcd(g, b[i]);if(g == 0){if(a[1] > 1) printf("Case %d: 0\n", ++kase);else printf("Case %d: 1\n", ++kase);continue;}if(g == 1){printf("Case %d: -1\n", ++kase);continue;}int ans = 1e9;update(ans, g);for(int i = 2; i * i <= g; i++)if(g % i == 0){update(ans, i);update(ans, g / i);}printf("Case %d: %d\n", ++kase, ans);}return 0;
}
还更紧队训把，把最近落下的队训内容全都补一补。有多余时间再自己学
补完训练赛的题把三个kuangbin专题刷一刷。我有点好高骛远了
所以最近就是训练赛加三个kuangbin专题，先赶上队训的节奏