Codeforces Round #699 (Div. 2)

E.

题意:n本书,每本书有颜色a[i],一次操作可以将其中一本书放在末尾,求满足:相同颜色的书都是相邻的 的最小操作次数.

显然最多只需要n次,考虑能节省多少次.倒着考虑,记f[i]为i~n最多能节约的次数.先预处理出每种颜色的出现的位置范围l[i],r[i].

1.不节约这本书f[i] = f[i + 1]

2.if i == l[a[i]], f[i] = cnt[a[i]] + f[r[a[i]]+1]

3.if i != l[a[i]], f[i] = cnt[a[i]](位置i后的a[i]个数),为什么不加上f[r[a[i]]+1]呢?首先这个转移必然不可能是最优的,肯定会被前面i = l[a[i]]时替换掉,所以我们只考虑这部分被继承时的情况.如果被继承只有可能前面出现i' == l[a[i']],并且r[a[i']]>i,那么f[i'] = cnt[a[i']] + f[r[a[i']+1]],此时我们保留a[i']和i以及i后面的a[i]不动,先将i前面i'后面的a[i]移到末尾,再把其他与a[i],a[i']不同的数移到末尾即可.

#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0) 
#define ll long long 
// #define double long double
#define ull unsigned long long 
#define PII pair<int, int> 
#define PDI pair<double, int> 
#define PDD pair<double, double> 
#define debug(a) cout << #a << " = " << a << endl 
#define point(n) cout << fixed << setprecision(n)
#define all(x) (x).begin(), (x).end() 
#define mem(x, y) memset((x), (y), sizeof(x))
#define lbt(x) (x & (-x)) 
#define SZ(x) ((x).size()) 
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
// namespace nqio { const unsigned R = 4e5, W = 4e5; char* a, * b, i[R], o[W], * c = o, * d = o + W, h[40], * p = h, y; bool s; struct q { void r(char& x) { x = a == b && (b = (a = i) + fread(i, 1, R, stdin), a == b) ? -1 : *a++; } void f() { fwrite(o, 1, c - o, stdout); c = o; } ~q() { f(); }void w(char x) { *c = x; if (++c == d) f(); } q& operator >>(char& x) { do r(x); while (x <= 32); return *this; } q& operator >>(char* x) { do r(*x); while (*x <= 32); while (*x > 32) r(*++x); *x = 0; return *this; } template<typename t> q& operator>>(t& x) { for (r(y), s = 0; !isdigit(y); r(y)) s |= y == 45; if (s) for (x = 0; isdigit(y); r(y)) x = x * 10 - (y ^ 48); else for (x = 0; isdigit(y); r(y)) x = x * 10 + (y ^ 48); return *this; } q& operator <<(char x) { w(x); return *this; }q& operator<< (char* x) { while (*x) w(*x++); return *this; }q& operator <<(const char* x) { while (*x) w(*x++); return *this; }template<typename t> q& operator<< (t x) { if (!x) w(48); else if (x < 0) for (w(45); x; x /= 10) *p++ = 48 | -(x % 10); else for (; x; x /= 10) *p++ = 48 | x % 10; while (p != h) w(*--p); return *this; } }qio; }using nqio::qio;
using namespace std;
mt19937 rnd(random_device{}());
const int N = 2e6 + 10;
int n, a[N], f[N], l[N], r[N];
map<int, int> cnt;
signed main() {IOS;cin >> n;for (int i = 1; i <= n; ++i) {cin >> a[i];}for (int i = 1; i <= n; ++i) {r[a[i]] = i;}for (int i = n; i >= 1; --i) {l[a[i]] = i;}for (int i = n; i >= 1; --i) {++cnt[a[i]];f[i] = f[i + 1];if (i == l[a[i]]) f[i] = max(f[i], f[r[a[i]] + 1] + cnt[a[i]]);else f[i] = max(f[i], cnt[a[i]]);}cout << n - f[1] << "\n";
}

F.

题意:对n个节点1为根的树ab染色,有x个a,n-x个b.定义i节点上的字符串为1到i路径上的字符.求字符串种类数最少多少种,输出染色方案.

首先每一层尽可能染成一种颜色,如果恰好平分,那么答案为树的最大深度.这毫无疑问是答案下界,我们再去找答案上界,猜测是最大深度+1.假设我们在染色某一层时,剩下m个点未染色,有t个非叶节点,那么我们肯定能将这t个非叶节点染成同一种颜色,因为至少还有t个叶子节点,我们只需要拿数量多的颜色来染即可,然后染叶子节点,显然能调整成与刚才非叶节点同一种颜色.

问题转化成了将每一层都染成a或者b,能否刚好染好每一层.这是一个典型的多重背包,我们将每层点的个数看成是物品,x或者n - x看成容积,然后求出选出若干层能否得到容积即可.由于要回溯,我们不压缩状态.设f[i][j]为考虑前i个物品,选的点数为j的可行性,可行性多重背包可以用贪心优化成O(nm).修改状态为f[i][j]为前i个物品凑出j的前提下,前i - 1个物品最多凑的价值.

这里详细说一下多重背包的优化方法:

由于我们只关注可行性,所以我们只需要关注会传递可行性的转移即可.

1.如果前i - 1个物品能凑出j,那么显然前i个也肯定能凑出来.if (f[i - 1][j] != -1) f[i][j] = j

2.如果前i - 1个物品凑不出来j,需要用第i个物品配合前i - 1个物品来凑,我们让体积从小到大枚举,先得到小于j能凑出来的体积,如果能凑出j - v[i],(v[i]为第i个物品的体积),那么如果还有至少一个i号物品,肯定能凑出j - v[i],换而言之,如果f[j - v[i]] != -1 && (j - f[i][j - v[i]) / v[i] <= cnt[i],那么f[i][j] = f[i][j - v[i]].

回溯的时候,我们需要求出拼成容积m每个价值的物品用了多少个.可以倒着来used[i] = (cur - f[i][cur]) / v[i]; cur = f[i][cur].

#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0) 
#define ll long long 
// #define double long double
#define ull unsigned long long 
#define PII pair<int, int> 
#define PDI pair<double, int> 
#define PDD pair<double, double> 
#define debug(a) cout << #a << " = " << a << endl 
#define point(n) cout << fixed << setprecision(n)
#define all(x) (x).begin(), (x).end() 
#define mem(x, y) memset((x), (y), sizeof(x))
#define lbt(x) (x & (-x)) 
#define SZ(x) ((x).size()) 
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
// namespace nqio { const unsigned R = 4e5, W = 4e5; char* a, * b, i[R], o[W], * c = o, * d = o + W, h[40], * p = h, y; bool s; struct q { void r(char& x) { x = a == b && (b = (a = i) + fread(i, 1, R, stdin), a == b) ? -1 : *a++; } void f() { fwrite(o, 1, c - o, stdout); c = o; } ~q() { f(); }void w(char x) { *c = x; if (++c == d) f(); } q& operator >>(char& x) { do r(x); while (x <= 32); return *this; } q& operator >>(char* x) { do r(*x); while (*x <= 32); while (*x > 32) r(*++x); *x = 0; return *this; } template<typename t> q& operator>>(t& x) { for (r(y), s = 0; !isdigit(y); r(y)) s |= y == 45; if (s) for (x = 0; isdigit(y); r(y)) x = x * 10 - (y ^ 48); else for (x = 0; isdigit(y); r(y)) x = x * 10 + (y ^ 48); return *this; } q& operator <<(char x) { w(x); return *this; }q& operator<< (char* x) { while (*x) w(*x++); return *this; }q& operator <<(const char* x) { while (*x) w(*x++); return *this; }template<typename t> q& operator<< (t x) { if (!x) w(48); else if (x < 0) for (w(45); x; x /= 10) *p++ = 48 | -(x % 10); else for (; x; x /= 10) *p++ = 48 | x % 10; while (p != h) w(*--p); return *this; } }qio; }using nqio::qio;
using namespace std;
mt19937 rnd(random_device{}());
const int N = 2e6 + 10;
int n, a[N], f[N], l[N], r[N];
map<int, int> cnt;
signed main() {IOS;cin >> n;for (int i = 1; i <= n; ++i) {cin >> a[i];}for (int i = 1; i <= n; ++i) {r[a[i]] = i;}for (int i = n; i >= 1; --i) {l[a[i]] = i;}for (int i = n; i >= 1; --i) {++cnt[a[i]];f[i] = f[i + 1];if (i == l[a[i]]) f[i] = max(f[i], f[r[a[i]] + 1] + cnt[a[i]]);else f[i] = max(f[i], cnt[a[i]]);}cout << n - f[1] << "\n";
}