企业网站建设方案,免费网站制作平台推荐,专业手机网站制作公司,wordpress自定义文章E. 题意:n本书,每本书有颜色a[i],一次操作可以将其中一本书放在末尾,求满足:相同颜色的书都是相邻的 的最小操作次数.
显然最多只需要n次,考虑能节省多少次.倒着考虑,记f[i]为i~n最多能节约的次数.先预处理出每种颜色的出现的位置范围l[i],r[i].
1.不节约这本书f[i] f[i 1]…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 pairint, int
#define PDI pairdouble, int
#define PDD pairdouble, 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; } templatetypename 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; }templatetypename 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];
mapint, 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 pairint, int
#define PDI pairdouble, int
#define PDD pairdouble, 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; } templatetypename 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; }templatetypename 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];
mapint, 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;
}
