A. 染色
发现一条链的话等同于对一个区间取 \(min\)
长剖，记录取 \(min\) 的次数和推到的位置，使用 \(st\) 表辅助处理
每次合并将取 \(min\) 推到较短长度
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
int read(){
int x = 0; char c = getchar();
while(!isdigit(c))c = getchar();
do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
return x;
}
const int maxn = 1e5 + 55;
int n, a[maxn];
vector<int>g[maxn], h[maxn];
vector<ll>f[maxn];
int mi[maxn][18];
int query(int l, int r){
int k = __lg(r - l + 1);
return min(mi[l][k], mi[r - (1 << k) + 1][k]);
}
void push_down(int x, int len){
int cnt = 0;
for(int i = 1; i <= len; ++i){
cnt += h[x][h[x].size() - i]; h[x][h[x].size() - i] = 0;
if(cnt)f[x][f[x].size() - i] = min(f[x][f[x].size() - i], (ll)query(max(1, i - cnt + 1), i));
}
if(h[x].size() > len)h[x][h[x].size() - len - 1] += cnt;
}
void merge(int x, int y){
if(f[x].size() < f[y].size())swap(f[x], f[y]), swap(h[x], h[y]);
push_down(x, f[y].size()); push_down(y, f[y].size());
for(int i = 1; i <= f[y].size(); ++i)f[x][f[x].size() - i] += f[y][f[y].size() - i];
f[y].clear(); h[y].clear();
}
void dfs(int x, int fa){
for(int v : g[x])if(v != fa){dfs(v, x); merge(x, v);}
f[x].push_back(a[1]); h[x].push_back(1);
}
int main(){
freopen("color.in","r",stdin);
freopen("color.out","w",stdout);
n = read();
for(int i = 1; i <= n; ++i)a[i] = mi[i][0] = read();
for(int j = 1; (1 << j) <= n; ++j)
for(int i = 1; i + (1 << j) - 1 <= n; ++i)
mi[i][j] = min(mi[i][j - 1], mi[i + (1 << (j - 1))][j - 1]);
for(int i = 1; i < n; ++i){
int u = read(), v = read();
g[u].push_back(v); g[v].push_back(u);
}
dfs(1, 0); push_down(1, h[1].size());
ll ans = 0; for(ll v : f[1])ans += v;
printf("%lld\n",ans);
return 0;
}
B. 技能
原题2023冲刺清北营10顶级厨师
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
int read(){
int x = 0; char c = getchar();
while(!isdigit(c))c = getchar();
do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
return x;
}
const int maxn = 1005, B = 200, inf = 0x3f3f3f3f;
int n, a[maxn][3], ans, f[maxn][B + 5][B + 5][3];
void ckmx(int &x, int y){if(x < y)x = y;}
int main(){
freopen("skill.in","r",stdin);
freopen("skill.out","w",stdout);
n = read();
for(int i = 1; i <= n; ++i){
a[i][0] = read();
a[i][1] = read();
a[i][2] = read();
}
ans = 0;
for(int i = 0; i <= n; ++i)
for(int j = 0; j <= B; ++j)
for(int k = 0; k <= B; ++k)
for(int s = 0; s < 3; ++s)
f[i][j][k][s] = -inf;
f[0][0][0][0] = f[0][0][0][1] = f[0][0][0][2] = 0;
for(int i = 0; i <= n; ++i){
for(int p = 0; p <= min(i, B); ++p)
for(int q = 0; q <= min(i, B); ++q)
for(int las = 0; las < 3; ++las){
if(i == n)ans = max(ans, f[i][p][q][las]);
else{
ckmx(f[i + 1][p + (p != 0)][q + (q != 0)][las], f[i][p][q][las] + a[i + 1][las] - p - q);
if(las == 0){
ckmx(f[i + 1][2][q + (q != 0)][1], f[i][p][q][las] + a[i + 1][1] - 1 - q);
ckmx(f[i + 1][2][p + (p != 0)][2], f[i][p][q][las] + a[i + 1][2] - 1 - p);
}else if(las == 1){
ckmx(f[i + 1][2][q + (q != 0)][0], f[i][p][q][las] + a[i + 1][0] - 1 - q);
ckmx(f[i + 1][p + (p != 0)][2][2], f[i][p][q][las] + a[i + 1][2] - 1 - p);
}else if(las == 2){
ckmx(f[i + 1][q + (q != 0)][2][0], f[i][p][q][las] + a[i + 1][0] - 1 - q);
ckmx(f[i + 1][p + (p != 0)][2][1], f[i][p][q][las] + a[i + 1][1] - 1 - p);
}
}
}
}
printf("%d\n",ans);
return 0;
}
C. 重排
考虑一次操作之后，原数在每个位置的概率相同
那么只需要关心操作的最长长度，和原数的位置
如果最长操作为 \(m\) 那么，期望位置是 \((m + 1) / 2\)
于是
\[ ans = (\frac{i - 1}{n})^k i + \sum_{m = i}^{n}\frac{m + 1}{2}((\frac{m}{n})^k - (\frac{m - 1}{n})^k) \]code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
int read(){
int x = 0; char c = getchar();
while(!isdigit(c))c = getchar();
do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
return x;
}
const int maxn = 1e6 + 55;
int n, pos, k;
double f[maxn], g[maxn];
double qpow(double x, int y){
double ans = 1;
for(; y; y >>= 1, x = x * x)if(y & 1)ans = ans * x;
return ans;
}
int main(){
freopen("arrange.in","r",stdin);
freopen("arrange.out","w",stdout);
n = read(); pos = read(); k = read();
for(int i = 1; i <= n; ++i)f[i] = qpow(1.0 * i / n, k);
double ans = pos * f[pos - 1];
for(int i = pos; i <= n; ++i)ans = (ans + (i + 1.0) / 2.0 * (f[i] - f[i - 1]));
printf("%.20lf\n",ans);
return 0;
}