本人水平较低,如果有写的不对的或者有疑问的地方,可以在评论区指出,谢谢
方法:可反悔贪心
这个方法我也是第一次学到,当时在赛场上想到的是dp,然后看到数据量直接劝退了。
首先为了理解什么是可反悔贪心,我们先偏离一下题目,看一道另外的一个题目。
种树
我们很容易想到一个dp写法,dp[i][j]
表示前i
个树坑中种了j
棵树的收获,但是数据量直接就劝退,于是我们先尝试着模拟一遍过程。
容易想到一种贪心的方法, 每次都取获利最高的树坑种树,然后做一个标记,表示该坑两边都不种树,最后得到的获利我们就作为最大获利值。用一个优先队列维护即可。但是我们也不难得出,这个方法肯定不是正确解法,因为可能最大值的两边加起来是大于它本身的,比如8,9,8,1这种就是,选9,1肯定不如8,8。于是我们需要对贪心做一个优化。
那么如何优化呢?很明显,就拿8,9,8,1这个举例子,如果需要选2个的话,我们就要给自己选了最大值之后后悔的余地。
我们这样操作,每次取出a[i]
时候,我们同时加入a[i - 1] + a[i + 1] - a[i]这个数字,举个例子
在8,9,8,1这四个数中选择2个数。我们先选择9,然后加入8 + 8 - 9 = 7,然后再选择7(因为8被标记不能选了)于是就得到了9 + 7 = 16的收获。但是我们实际上选的是8 + 8,只不过形式换成了9 + 8 + 8 - 9,相当于我虽然一开始选了9,但是我一看好像另外两个更优,于是就去掉9选择8 + 8
具体我们用一个双向链表维护,选择一个数a[i]
之后,将其左右两边的数删除并加入一个a[i - 1] + a[i + 1] - a[i]
#include <bits/stdc++.h>
#define PLI pair<LL, int>
#define LL long long
using namespace std;
const int N = 5e5 + 10;
LL a[N];
int pre[N], nex[N];
bool v[N];//标记是否已经出队
priority_queue<PLI> q;
inline void del(int u) {
nex[pre[u]] = nex[u];
pre[nex[u]] = pre[u];
}
int main() {
int n, m; cin >> n >> m;
for (int i = 1; i <= n; i ++ ) {
cin >> a[i], q.push({a[i], i});
pre[i] = i - 1, nex[i] = i + 1;
}
LL ans = 0, res = 0;
while (m -- ) {
auto t = q.top();
q.pop();
while (v[t.second]) {
t = q.top();
q.pop();
}
int u = t.second;
v[nex[u]] = v[pre[u]] = true;
ans += a[u];
if (res >= ans) break;
else res = ans;
a[u] = a[nex[u]] + a[pre[u]] - a[u];
del(nex[u]), del(pre[u]);
q.push({a[u], u});
}
cout << res << endl;
return 0;
}
回到原题,我们来看题目。
首先乍一看还是看不出来我们到底如何贪心。于是我们可以构造一个数组从出来
c[i]
表示让s[i]
与s[i + 1]
构成ac的代价,于是题目就变成了在一定代价内,选择不相邻的两个c使得总ac数最多,这就是我们刚刚看到的原题,但是这题有一个难点,就是需要输出方案具体的内容,这里主要讲如何输出方案数
这里的重点就是,我们如何记录到底是选了i还是选择后悔选i,我们这里参考三个顶俩队伍的代码,用一个另外的h来替代我们当前选到的点,于是也需要一个新的L和R数组,具体看代码
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10;//由于我们新造了结点来代替选择到的结点,于是开2倍的空间
int c[N];
char s[N];
int l[N], r[N], R[N], L[N];//这里l[]r[]都表示原始的双向链表,R[]L[]表示新的结点构成的链表
bool v[N];//这里表示是否被标记过
bool tr[N];//这里表示被标记过的多次叠加的结果
int n, k;
priority_queue<PII, vector<PII>, greater<>> q;
inline void del(int u) {
l[r[u]] = l[u];
r[l[u]] = r[u];
}
inline void doit(int u, int h) {
v[l[u]] = v[r[u]] = true;
tr[L[u] - 1] ^= 1;//如果是原始的结点(就是n以内的),就直接取上一个和本身,否则就说明我们之前取过这个,就要往外扩展一层。
tr[R[u]] ^= 1;
//接下来都是更新链表的操作
if (l[u] != 0 && r[u] != n) {//注意两边边界,如果选到边界上说明没有可能会后悔,直接删除结点即可
L[h] = L[l[u]];
R[h] = R[r[u]];
c[h] = c[l[u]] + c[r[u]] - c[u];
del(l[u]), del(r[u]);
r[l[u]] = l[r[u]] = h;
l[h] = l[u], r[h] = r[u];
q.push({c[h], h});
} else if (l[u] == 0 && r[u] != n) {
del(u), del(r[u]);
} else if (l[u] != 0 && r[u] == n) {
del(u), del(l[u]);
}
}
int main() {
cin >> n >> k;
scanf("%s", s + 1);
for (int i = 1; i < n; i ++ ) {
c[i] = (s[i] != 'a') + (s[i + 1] != 'c');//构造c数组
l[i] = i - 1, r[i] = i + 1;
L[i] = i, R[i] = i;
q.push({c[i], i});
}
int ans = 0;
int h = n + 2;//新结点的位置
while (ans < n / 2) {
auto t = q.top();
q.pop();
if (v[t.second]) continue;
int u = t.second;
k -= c[u];
if (k < 0) break;
ans ++ ;
h ++ ;
doit(u, h);
}
cout << ans << endl;
for (int i = n - 1; i; i -- ) {//倒序枚举,计算后缀异或和,当为真时,说明当前已经被改变,否则说明还没改变。这里可以自己画一遍模拟一下,以更好理解。
tr[i] ^= tr[i + 1];
if (tr[i]) s[i + 1] = 'c', s[i] = 'a';
}
printf("%s", s + 1);
return 0;
}
考点:区间dp
比赛的时候竟然没看出来是区间dp,还一直往差分方向想,是我太菜了
其实不难赛后过题的人不配说这句话,状态转移和状态表达还是很(chao)好(ji)想(nan)的,大概就是
状态表达:dp[i][j]
表示合并从i到j的代价最小值
状态转移:
1、当a[i] == a[j]
时dp[i][j] = dp[i + 1][j - 1] + 1
2、当a[k] == a[j]
时$min_{i < k < j}(dp[i][k - 1] + dp[k + 1][j] + 1)$
3、当a[k] == a[i] == a[j]
时$min_{i < k < j}(dp[i][k - 1] + dp[k + 1][j])$
4、一般情况dp[i][j] = min(dp[i + 1][j] + 1, dp[i][j - 1] + 1)
有一点需要注意的dp[i][j]
的最大值应该是j - i,因为最坏情况就是全部点都不同色
我们用记忆化搜索来写
注意,为了枚举k,我们采用一个预处理,即用pre[i]表示颜色为a[i] 的上一个位置出现在哪
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int N = 6060;
int dp[N][N];
int a[N], pre[N];
int dfs(int l, int r) {
if (l == r) return 0;
if (dp[l][r] != INF) return dp[l][r];
int ans = r - l;
ans = min(ans, dfs(l + 1, r) + 1);
ans = min(ans, dfs(l, r - 1) + 1);
if (a[l] == a[r]) ans = min(ans, dfs(l + 1, r - 1) + 1);
for (int k = pre[r]; k > l; k = pre[k]) {
ans = min(ans, dfs(l, k - 1) + dfs(k + 1, r) + 1);
if (a[k] == a[l] && a[k] == a[r])
ans = min(ans, dfs(l, k - 1) + dfs(k + 1, r));
}
return dp[l][r] = ans;
}
inline void solve() {
memset(dp, 0x3f, sizeof dp);
int n; cin >> n;
map<int, int> f;
for (int i = 1; i <= n; i ++ ) {
cin >> a[i];
if (a[i] == a[i - 1]) {
i --, n --;
continue;
}
pre[i] = f[a[i]];
f[a[i]] = i;
}
int ans = dfs(1, n);
cout << ans << endl;
}
int main() {
int t; cin >> t;
while (t -- ) solve();
return 0;
}
打比赛的时候乍一看是个大模拟,后来读完题后就秒看出来是个dp,但是无奈当时被L题卡着了,所以没开这题就很难受
方法:背包dp
感觉就是普通的背包dp,但是需要注意的点比较多,我们先写出状态表达和状态转移
状态表达:dp[i][j][k]
表示在前k天中,只给前i个人做蛋糕,其中前i个人中还有j个人没做的最大获利
状态转移:状态转移:
1、不给i做蛋糕,就是dp[i - 1][j - 1][k]
2、给i做蛋糕,就是dp[i - 1][j][k - c[i]] + v[i]
算出不收到蛋糕的人数,剩下的都用礼物给就行。用f[j]
表示规定钱数内买j件礼物的最大获利
这样就可以写了
#include <bits/stdc++.h>
using namespace std;
const int N = 550, M = 17;
int n, m, w;
int dp[N][M][370];//dp[i][j][k]表示前k天中,只对前i个人考虑是否做蛋糕,并且在前i个人中还有j个人没有做的情况下的最大获利值
int f[M];//f[j]表示在规定钱数内买j件礼物的最大获利值
int a[M], b[M];
int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int s[M];
struct node {
int c, v;
int day;//表示是2021年的第day天
bool operator < (const node &B) const {
return day < B.day;
}
} d[N];
inline void solve() {
cin >> n >> m >> w;
for (int i = 1; i <= n; i ++ ) {
int yy, mm, dd;
scanf("%d-%d-%d", &yy, &mm, &dd);
cin >> d[i].c >> d[i].v;
d[i].day = s[mm - 1] + dd;
if (mm == 2 && dd == 29) i --, n --;
}
for (int i = 1; i <= m; i ++ ) cin >> a[i] >> b[i];
sort(d + 1, d + 1 + n);
memset(f, 0, sizeof f);
for (int i = 0; i < (1 << m); i ++ ) {
int cnt = 0, sum = 0, val = 0;
for (int j = 0; j < m; j ++ ) {
if (i >> j & 1) {
cnt ++ ;
sum += a[j + 1];
val += b[j + 1];
}
}
if (sum <= w) f[cnt] = max(f[cnt], val);
}
for (int i = 0; i <= n; i ++ )
for (int j = 0; j <= m; j ++ )
for (int k = 0; k <= 365; k ++ ) dp[i][j][k] = -1e9;
dp[0][0][0] = 0;
/*
* 状态转移:
* 1、不给i做蛋糕,就是dp[i - 1][j - 1][k];
* 2、给i做蛋糕,就是dp[i - 1][j][k - c[i]] + v[i];
*/
for (int i = 1; i <= n; i ++ ) {
for (int j = 0; j <= min(i, m); j ++ ) {
for (int k = 0; k <= 365; k ++ ) {
dp[i][j][k] = dp[i - 1][max(j - 1, 0)][k];//不给i做蛋糕
if (k >= d[i].c && k <= d[i].day)//只有这样才可以给i做蛋糕
dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k - d[i].c] + d[i].v);
}
}
}
int ans = 0;
for (int j = 0; j <= m; j ++ ) {
for (int k = 0; k <= 365; k ++ ) ans = max(ans, dp[n][j][k] + f[j]);
}
cout << ans << endl;
}
int main() {
for (int i = 1; i <= 12; i ++ ) s[i] = s[i - 1] + mon[i];
int t; cin >> t;
while (t -- ) solve();
return 0;
}
I-Mr. Main and Windmills
这里给出队友写的题解
J-Parallel Sort
这里给出队友写的题解
K-Riichi!!
这里给出队友写的题解
这里先给出队友的线段树做法
接下来给出我们队在比赛时候的写法(比较容易写一些)
方法:二分
具体就是,先暴力,后优化
首先写一个暴力写法
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N];
int col[N];
inline void solve() {
int n; cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
col[1] = 1;
for (int i = 2; i <= n; i ++ ) {
int j = 1;
for (; j < i; j ++ ) {
if (a[i] > a[j]) {
col[i] = col[j];
break;
}
}
if (!col[i]) col[i] = col[i - 1] + 1;
}
int ans = 0;
for (int i = 1; i <= n; i ++ ) ans = max(ans, col[i]);
cout << ans << endl;
for (int i = 1; i <= n; i ++ ) cout << col[i] << ' ';
cout << endl;
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int t; cin >> t;
while (t -- ) solve();
return 0;
}
当然这个肯定是不行的,我们想办法优化,我们发现,每次我们要填色时,都是从前往后找,找到一个比自己小的数字,然后和他填一样的颜色即可,而这个的时间是O(n)的,我们可以从这里下手
我们定义一个数组c,c[i]
表示颜色为i的最大数字为多少,我们注意到,由于数字大的染上颜色要尽量小,所以c数组是具有单调性的,我们二分查找即可
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N], c[N], ans[N];
int main() {
int t;
scanf("%d", &t);
while (t -- ) {
int n; scanf("%d", &n);
for (int i = 0; i <= n + 1; i ++ ) c[i] = 0;
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
int cnt = 0;
for (int i = 1; i <= n; i ++ ) {
int l = 1, r = n;
while (l < r) {
int mid = (l + r) >> 1;
if (c[mid] > a[i]) l = mid + 1;
else r = mid;
}
if (c[l] == 0) cnt ++ ;
c[l] = a[i];
ans[i] = l;
}
printf("%d\n", cnt);
for (int i = 1; i <= n; i ++ ) printf("%d ", ans[i]);
puts("");
}
return 0;
}
队友在补了在补了QAQ
队友补完了,这里是题解
巨巨,G题为什么需要排序啊? 假设不排序,会导致局部不是最优解,但是考虑前n个,值应该最优的吧?
排序是一定要排序的,我们这里考虑的是若只考虑做蛋糕给朋友的收益,当然也有可能我买礼物收益更大,这部分的判断我在代码最后统计答案部分表示出来了的。
忽然发现 赛时G题 很卡时间。 假设把第二重循环和第三重循环互换下, 时间复杂度计算是一样的,但是会TLE。。。
可能是牛客评测机的缘故,他最近好像抖动比较大。
%%%
%%%%
stO_Time_Orz
time聚聚yyds!
%%%
%%%Time聚聚带带我
%%%
%%%
%%%
%%%