长剖调不出来喜提垫底！
评价：同比赛编号。
牛子老师给出三道原题题号：qoj5418、5146、2303。
染色
简单长剖，为啥没有调出来呢？不懂。
首先按深度考虑，设 \(dp_{x,i}\) 为在 \(x\) 把子树深度 \(i\) 染完的最小代价，转移显然
\[dp_{x,i}=\min(\sum_{v}dp_{v,i-1},a_i) \]这玩意和深度有关，那就长剖一下就行了。取 \(\min\) 是和连续的一段 \(a\) 取 \(\min\)，打个左端点标记就好。
没调出来，好似。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cassert>
#define int long long
using namespace std;
int n,a[100010];
struct ST{
int st[100010][21];
void build(){
for(int i=0;i<n;i++)st[i][0]=a[i];
for(int j=1;j<=__lg(n);j++){
for(int i=0;i+(1<<j)-1<n;i++){
st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]);
}
}
}
int query(int l,int r){
int k=__lg(r-l+1);
return min(st[l][k],st[r-(1<<k)+1][k]);
}
}st;
struct node{
int v,next;
}edge[200010];
int t,head[100010];
void add(int u,int v){
edge[++t].v=v;edge[t].next=head[u];head[u]=t;
}
int dep[100010],son[100010];
void dfs1(int x,int f){
for(int i=head[x];i;i=edge[i].next){
if(edge[i].v!=f){
dfs1(edge[i].v,x);
if(dep[son[x]]<dep[edge[i].v])son[x]=edge[i].v;
}
}
dep[x]=dep[son[x]]+1;
}
int buf1[100010],*dp[100010],*now1=buf1;
int buf2[100010],*lz[100010],*now2=buf2;
void pushtag(int x,int i){
if(lz[x][i]+1<=i)dp[x][i]=min(dp[x][i],st.query(lz[x][i]+1,i));
else dp[x][i]=min(dp[x][i],a[i]);
lz[x][i]=i;
}
void dfs2(int x,int f){
dp[x][0]=a[0];
if(son[x]){
dp[son[x]]=dp[x]+1;lz[son[x]]=lz[x]+1;
dfs2(son[x],x);
}
for(int i=head[x];i;i=edge[i].next){
if(edge[i].v!=f&&edge[i].v!=son[x]){
dp[edge[i].v]=now1;now1+=dep[edge[i].v];
lz[edge[i].v]=now2;now2+=dep[edge[i].v];
dfs2(edge[i].v,x);
for(int j=0;j<dep[edge[i].v];j++){
pushtag(edge[i].v,j);
pushtag(x,j+1);
dp[x][j+1]+=dp[edge[i].v][j];
pushtag(x,j+1);
}
}
}
}
signed main(){
scanf("%lld",&n);
for(int i=0;i<n;i++)scanf("%lld",&a[i]);
st.build();
for(int i=1;i<n;i++){
int u,v;scanf("%lld%lld",&u,&v);
add(u,v);add(v,u);
}
dfs1(1,0);
dp[1]=now1;now1+=dep[1];lz[1]=now2;now2+=dep[1];
dfs2(1,0);
int ans=0;
for(int i=0;i<dep[1];i++){
pushtag(1,i);
ans+=dp[1][i];
}
printf("%lld\n",ans);
return 0;
}
技能
详见 顶级厨师。
重排
简单题。他们说是讲题讲过的，我咋没印象。
首先 \(O(n^2)\) 不难，暴力维护所有位置的概率转移就好。然后这玩意和正解没任何关系。
正解考虑操作落在哪里。以下 \(x\) 为给的 \(i\)。两种情况：
-
所有操作位置 \(<x\)：位置不变，概率 \(\left(\dfrac{x-1}n\right)^k\)。
-
有操作位置 \(\ge x\)：枚举最大位置 \(i\)，概率 \(\left(\dfrac in\right)^k-\left(\dfrac {i-1}n\right)^k\)，期望由于 \(i\) 前边全部乱序就是 \(\dfrac{i+1}2\)。
那全加起来就完事。不取模大概是诈骗。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
const double eps=0;
int n,x,k;
long double p[1000010],sum[1000010];
long double qpow(long double a,int b){
long double ans=1;
while(b){
if(b&1)ans=ans*a;
a=a*a;
b>>=1;
}
return ans;
}
int main(){
scanf("%d%d%d",&n,&x,&k);p[x]=1;
long double ans=1.0*x*qpow(1.0*(x-1)/n,k);
for(int i=x;i<=n;i++){
ans+=1.0*(i+1)/2*(qpow(1.0*i/n,k)-qpow(1.0*(i-1)/n,k));
}
printf("%.6Lf\n",ans);
return 0;
}