个人赛链接: https://www.luogu.com.cn/contest/120684#description
A.围栏木桩
解题思路
第一步求最长不下降子序列套模板即可, 难点在于第二步求最长不下降子序列的数量; 训练赛中我是直接dfs来找的, 后来发现其实第一步和第二步可以放在一个dfs里一起求出来, 显得dp都多余了...但是本着不摸鱼的态度(bushi), 所以还是打算贴一个纯dp的做法
针对第二步我们新开一个数组g[i], 表示以第i个数结尾的最长不下降子序列的方案数, 在众多子序列当中一定存在以第i个数结尾的不下降子序列(该序列也可能就是第i个数自己), 所以这些不下降子序列一定可以比出一个最长的(最长的不一定只有一个); 知晓这个前提后便知道可以将g[i]初始化为1; 在模板中, 当f[j] + 1 == f[i]时说明以第i个数结尾的最长不下降子序列可以由第j个数结尾的最长不下降子序列推导得来, 这也说明g[j]里面的方案都是可以加上q[i]得到g[i]的, 所以g[i]里的方案数应该包含g[j], 即g[i] += g[j]; 当f[j] + 1 > f[i], 说明g[i]里的方案数并不是最长的不下降子序列, 真正的最长不下降子序列是g[j]里面的方案加上q[i]得到的, 所以要推倒从来, 把g[j]赋值给g[i], 即g[i] = g[j]; 最后, 因为整个序列中的最长不下降子序列不一定都是以同一个数结尾, 所以当f[i] == len时应该把当前的方案数也加到num中;
神秘代码1
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10, mod = 1e9 + 7;
int n, m, k;
int q[50], f[50], g[50];
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t--) {
memset(f, 0, sizeof f);
memset(g, 0, sizeof g);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> q[i];
}
int len = 0;
int num = 0;
for (int i = 1; i <= n; i++) {
f[i] = 1;
g[i] = 1;
for (int j = 1; j < i; j++) {
if (q[i] >= q[j]) {
if (f[j] + 1 == f[i]) {
g[i] += g[j];
}
else if (f[j] + 1 > f[i]) {
f[i] = f[j] + 1;
g[i] = g[j];
}
}
}
if (f[i] > len) {
len = f[i];
num = g[i];
}
else if (f[i] == len) {
num += g[i];
}
}
cout << len << ' ' << num << endl;
}
return 0;
}
C.打分
解题思路
还是一个比较明显的二分题, 将分数进行排序后可以直接把最小值丢弃即可, 因为对它的操作成本是最高的, 所以我接下来的操作描述都是忽略最小值的; 然后便分为两种情况, 要不要给最大值加分; 最初的理想情况是把除最大值外的所有值都加成最大值的分数, 我们设需要的总分为cha, 所以当m<=cha时直接把m全用上即可; 然而当m>cha时我们就需要提高最大值之后才能继续给其他的加分, 但是给最大值加分后, 给其他的剩下的分数就少了, 所以此时需要用二分来求具体需要给最大值加多少; 设给最大值加了u, 那么我们就给其他值提高了u * (n-2)的加分上限, 然后我们需要判断剩下的分数是否能够填满这个新加的上限; 注意即使填不满也可能会更新最大值(毕竟也是加了), 所以不管是否填满都需要更新最大值;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10, mod = 1e9 + 7;
int n, m, k, cha, maxn = 0;
int f[N];
bool check(int u) {
int num = (n - 2) * u;
int a = m - u;
if (a >= num) {
maxn = max(maxn, num);
return true;
}
else if (a < num) {
maxn = max(maxn, a);
return false;
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
int sum = 0;
for (int i = 1; i <= n; i++) {
cin >> f[i];
sum += f[i];
}
sort(f + 1, f + 1 + n);
sum = sum - f[1] - f[n];
for (int i = 2; i < n; i++) {
cha = cha + f[n] - f[i];
}
if (m <= cha) {
sum = sum + m;
cout << sum;
return 0;
}
m -= cha;
int l = 0, r = m;
while (l < r) {
int mid = l + r + 1>> 1;
if (check(mid)) {
l = mid;
}
else r = mid - 1;
}
sum = sum + cha + maxn;
cout << sum;
return 0;
}
D.汤姆斯的天堂梦
解题思路
这个题的目的是想让我用dp求解, 但是他的题意实在是太像最短路了, 所以即使他每个点都需要两个值来确定, 但我还是用哈希强行用最短路a了, 就问你过没过吧(bushi); 既然写都写了, 还是把最短路的代码贴上, 可以做个参考, 我这里只讲dp的做法
神秘代码
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10, mod = 1e9 + 7;
int n, m, k, idx = 0, res;
map<PII,int> mp;
int h[N], e[N], ne[N], w[N], d[N];
bool st[N];
int ins(int a,int b) {
idx++;
mp[{a, b}] = idx;
return idx;
}
void add(int a, int b, int c) {
e[res] = b, ne[res] = h[a], w[res] = c, h[a] = res++;
}
int spfa() {
memset(d, 0x3f, sizeof d);
queue<int> q;
q.push(1);
st[1] = true;
d[1] = 0;
while (q.size()) {
int t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (d[j] > d[t] + w[i]) {
d[j] = d[t] + w[i];
if (!st[j]) {
st[j] = true;
q.push(j);
}
}
}
}
}
signed main() {
scanf("%d", &n);
memset(h, -1, sizeof h);
ins(0, 1);
for (int i = 1; i <= n; i++) {
scanf("%d", &m);
for (int j = 1; j <= m; j++) {
int t= ins(i, j);
int a, b;
while (scanf("%d", &a) && a) {
scanf("%d", &b);
int c = mp[{i - 1, a}];
add(c, t, b);
}
}
}
spfa();
int minn = 0x3f3f3f3f;
for (auto t : mp) {
if (t.first.first == n) {
minn = min(minn, d[t.second]);
}
}
printf("%d", minn);
return 0;
}
E.地标访问
解题思路
也是一道较为明显的二分题, 直接二分最多经过的路标数量即可; 在此之前我们先把路标的坐标进行排序并按照正负分成两段, 分别存于mp1和mp2中, 注意, mp1[i]既表示原点右边第i个路标的坐标, 也可以表示从原点往右走一共经过i个路标所需要的时间, 第二层意思就是本题代码的关键; 因为如果要追求最短时间, 那必不能反复横跳, 最多就是来回一次; 所以对于check函数, 我们先遍历往右走所经过的路标数量a, 那往左走所经过的路标数量b就是二分的路标数量减去a, 所以就是O(n)的复杂度; 因为不用回到原点, 所以我们还需要判断一下先往右还是先往左走, 当然也有可能一条路走到黑, 所以a要从0开始遍历; 最后二分出答案结束;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10, mod = 1e9 + 7;
int n, m, k;
int f[N];
bool st[N];
int a, b;
map<int, int> mp1, mp2;
bool check(int u) {
int res;
for (int i = 0; i <= a && i <= u; i++) {
int c = u - i;
if (c <= b) {
res = mp1[i] + mp2[c];
if (i != 0 && c != 0) {
int minn = min(mp1[i], mp2[c]);
res += minn;
}
if (res <= k) return true;
}
}
return false;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> k >> n;
for (int i = 1; i <= n; i++) {
cin >> f[i];
}
sort(f + 1, f + 1 + n);
int pos;
if (f[1] >= 0) pos = 1;
else if (f[n] <= 0) pos = n + 1;
else {
for (int i = 2; i <= n; i++) {
if (f[i] >= 0 && f[i - 1] < 0) {
pos = i;
break;
}
}
for (int i = pos, j = 1; i <= n; i++, j++) mp1[j] = f[i];
for (int i = pos - 1, j = 1; i >= 1; i--, j++) mp2[j] = abs(f[i]);
a = mp1.size(), b = mp2.size();
int l = 0, r = n;
while (l < r) {
int mid = l + r + 1 >> 1;
if (check(mid)) {
l = mid;
}
else r = mid - 1;
}
cout << l << endl;
}
return 0;
}
G.Aggressive cows G
解题思路
签到题, 这也算是二分里比较经典的题了, 二分最短距离, 然后check函数用贪心的来遍历牛棚看是否能够满足最短距离即可;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10, mod = 1e9 + 7;
int n, m, k, cha;
int f[N];
bool check(int u) {
int a = f[1];
int num = 1;
for (int i = 2; i <= n; i++) {
int b = f[i] - a;
if (b >= u) {
a = f[i];
num++;
}
}
if (num >= m) return true;
else return false;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> f[i];
}
sort(f + 1, f + 1 + n);
int len = f[n] - f[1];
int l = 0, r = len;
while (l < r) {
int mid = l + r + 1>> 1;
if (check(mid)) {
l = mid;
}
else r = mid - 1;
}
cout << l;
return 0;
}
I.Chocolate Eating S
解题思路
根据题意可以看出是个二分, Bessie的怪癖也让我省了不少事; 二分最差心情, check函数遍历天数, 并用巧克力将当天的心情提高大于最差心情, 如果办不到就叫乌鸦哥掀桌子(bushi); 找到最大的最差心情后, 再走一遍修改后的check函数得到每块巧克力是在哪天被吃掉即可; 注意本题有个坑点他没有说就是我们处理完最后一天后如果巧克力还有剩余的话也要在最后一天全吃了, 所以这个最后要特判一下;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10, mod = 1e9 + 7;
int n, m, k;
int f[N];
map<int, int> mp;
bool check(int u) {
int a = 0;
int idx = 1;
for (int i = 1; i <= m; i++) {
a = a / 2;
while (a < u &&idx<=n) {
a += f[idx];
idx++;
}
if (a < u) return false;
}
return true;
}
void find(int u) {
int a = 0;
int idx = 1;
for (int i = 1; i <= m; i++) {
a = a / 2;
while (a < u && idx <= n) {
a += f[idx];
mp[idx] = i;
idx++;
}
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
int sum = 0;
for (int i = 1; i <= n; i++) {
cin >> f[i];
sum += f[i];
}
int l = 0, r = sum;
while (l < r) {
int mid = l + r + 1 >> 1;
if (check(mid)) {
l = mid;
}
else r = mid - 1;
}
cout << l << endl;
find(l);
for (int i = 1; i <= n; i++) {
if (!mp[i]) cout << m << endl;
else cout << mp[i] << endl;
}
return 0;
}
K.膜拜
解题思路
虽然题解都说这是个简单dp但是我还是没做出来, 啧. 很烦; 但是本题有个巧妙的地方是利用了前缀和, 把原数据为2的点都改为-1;(前缀和我做题的时候想到了, 所以这里必须夸一嘴); 这样做的好处是我们可以根据一个区间的前缀和判断两类人的差值: 如果s[8]=5, 说明人数差值就是5; 状态表示: d[i]就是前i个人所需要的最少机房数量; 状态计算: d[i] = min(d[i], d[j - 1] + 1); 本题是个线性dp, 和最长上升子序列有些相似; 先1~n遍历i, 再1~i遍历j; 对于第i个人, 我们需要判断他属于哪个机房, 设a = abs(s[i] - s[j - 1])表示区间j~i里人数差值, 如果a = i - j + 1则表示j~i中只有一类人; 所以当a = i - j + 1或者a <= m时我们可以把j~i放到一个机房里, 所以总机房数就是d[j - 1] + 1; 在遍历时取最小值即可;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 2500 + 10, mod = 1e9 + 7;
int n, m, k;
int q[N], d[N], s[N];
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> q[i];
if (q[i] == 2) q[i] = -1;
s[i] = s[i - 1] + q[i];
}
memset(d, 0x3f, sizeof d);
d[0] = 0;
int ini = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
int a = abs(s[i] - s[j - 1]);
if (a == i - j + 1 || a <= m) {
d[i] = min(d[i], d[j - 1] + 1);
}
}
}
cout << d[n];
return 0;
}
L.越越的组队
解题思路
这也是一道较难的dp问题, 我当时状态表示写对, 但不是完全对; 我当时想的状态计算是 (int) d[i][j][k], 表示从前i个人里选出j个人并且分数总和不超过k的最大分数, 但是状态计算却写不出来; 而题解的状态表示是 (bool) d[i][j][k], 表示是否存在从前i个人里选出j个人并且分数恰好为k的情况; 布尔类型的dp我还是第一次见, 知道这个状态表示后状态计算也很容易推导, 先遍历人数i, 再遍历挑选的人数j, 最后遍历总分数k, dp[i][j][k] = dp[i-1][j][k]||dp[i-1][j-1][k-f[i]]; 当k小于f[i]时, 我们只能通过dp[i-1][j][k]来判断dp[i][j][k]是否存在, 因为如果前i-1个人里面能挑出j个人凑到分数k, 那只要不选第i个人, 那么dp[i][j][k]也一定存在; 当k大于等于f[i]时我们还可以通过选第i个人来看看能不能凑出k, 因此问题就变成看能否从前i-1个人里面能挑出j-1个人凑到分数k-f[i], 也就是dp[i-1][j-1][k-f[i]]是否存在; 三维dp我们一般都要优化第一维, 然后j和k要从大到小遍历; 最后我们从sum/2开始从大到小遍历, 直到找到第一个存在的情况, 就是不超过sum/2的最大的分数;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 100 + 10, mod = 1e9 + 7;
int n, m, k, sum, maxn;
int f[N];
bool st[N];
bool dp[N][N * N];
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> f[i];
sum += f[i];
}
sort(f + 1, f + n + 1);
sum = sum / 2;
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = i; j >= 1; j--) {
for (int k = sum; k >= f[i]; k--) {
if (dp[j][k] == 1) continue;
if (dp[j - 1][k - f[i]] == 1) dp[j][k] = 1;
else dp[j][k] = 0;
}
}
}
for (int i = sum; i >= 1; i--) {
if (dp[n / 2][i]) {
cout << i << endl;
break;
}
}
return 0;
}