題目：https://www.luogu.org/problemnew/show/P4364

原來(lái)想了一個(gè)錯(cuò)誤的思路，就是這樣：

　　solve( cr , l , r ) 表示 cr 為根的子樹(shù)填 [ l , r ] 的數(shù)；然后把 l 給 cr ，剩下的 [ l+1 , r ] 分成一段一段，大的段給標(biāo)號(hào)小的孩子。

然后只能得 60 分。

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<cmath> #define db double #define pb push_back using namespace std; int rdn() {int ret=0;bool fx=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();}while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();return fx?ret:-ret; } const int N=5e5+5; int n,d[N],p[N],siz[N]; db k; vector<int> vt[N]; void dfs(int cr) {siz[cr]=1;for(int i=0,lm=vt[cr].size();i<lm;i++)dfs(vt[cr][i]), siz[cr]+=siz[vt[cr][i]]; } void solve(int cr,int l,int r) {p[cr]=d[l]; int p0=l;for(int i=vt[cr].size()-1;i>=0;i--){solve(vt[cr][i],p0+1,p0+siz[vt[cr][i]]);p0+=siz[vt[cr][i]];} } int main() {n=rdn();scanf("%lf",&k);for(int i=1;i<=n;i++)d[i]=rdn();sort(d+1,d+n+1);for(int i=1;i<=n;i++)vt[(int)floor(i/k)].pb(i);dfs(0); solve(0,0,n);for(int i=1;i<=n;i++)printf("%d ",p[i]);puts(""); return 0; } View Code

看了看題解。https://files-cdn.cnblogs.com/files/NaVi-Awson/IIIDX.pdf

關(guān)于 “去掉父親預(yù)留的影響” ，是這樣考慮：

　　按順序枚舉節(jié)點(diǎn)，在樹(shù)上就是像 bfs 一樣遍歷；

　　一個(gè)點(diǎn) cr 要預(yù)留，是為了讓 “和它深度相同的點(diǎn)” 不要搶了它的位置。

　　當(dāng)開(kāi)始遍歷 cr 的子樹(shù)的時(shí)候，直接去掉 cr 的影響并再也不加入了；這樣不會(huì)有錯(cuò)，因?yàn)榇藭r(shí)不會(huì)再遍歷和 cr 深度相同的點(diǎn)了；

　　下一層的點(diǎn)已經(jīng)由它們的父親留好了位置，所以去掉 cr 的影響也不會(huì)讓之后的點(diǎn)出錯(cuò)。

還有一種不太能理解的做法：https://www.cnblogs.com/HocRiser/p/8742680.html

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<cmath> #define ls Ls[cr] #define rs Rs[cr] using namespace std; int rdn() {int ret=0;bool fx=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();}while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();return fx?ret:-ret; } int Mn(int a,int b){return a<b?a:b;} int Mx(int a,int b){return a>b?a:b;} const int N=5e5+5,M=N<<1; int n,a[N],fa[N],ans[N],siz[N],tp[N],tx[N]; int tot,Ls[M],Rs[M],mn[M],tg[M]; void pshp(int cr){mn[cr]=Mn(mn[ls],mn[rs]);} void build(int l,int r,int cr) {if(l==r){mn[cr]=n-l;return;}int mid=l+r>>1;ls=++tot; build(l,mid,ls);rs=++tot; build(mid+1,r,rs);pshp(cr); } void pshd(int cr) {if(!tg[cr])return; int w=tg[cr]; tg[cr]=0;tg[ls]+=w; tg[rs]+=w; mn[ls]+=w; mn[rs]+=w; } void mdfy(int l,int r,int cr,int L,int R,int k) {if(l>=L&&r<=R){tg[cr]+=k;mn[cr]+=k;return;}int mid=l+r>>1; pshd(cr);if(L<=mid)mdfy(l,mid,ls,L,R,k);if(mid<R)mdfy(mid+1,r,rs,L,R,k);pshp(cr); } int qry(int l,int r,int cr,int k) {if(l==r)return mn[cr]>=k?l:-1;int mid=l+r>>1,ret=-1; pshd(cr);if(mn[ls]>=k)ret=qry(mid+1,r,rs,k);if(ret>=0)return ret;return qry(l,mid,ls,k); } int main() {n=rdn(); double sl; scanf("%lf",&sl);for(int i=1;i<=n;i++)a[i]=rdn();sort(a+1,a+n+1);for(int i=1;i<=n;i++)tp[i]=a[i];int m=unique(tp+1,tp+n+1)-tp-1;for(int i=1;i<=n;i++){a[i]=lower_bound(tp+1,tp+m+1,a[i])-tp;tx[a[i]]++;}for(int i=2;i<=m;i++)tx[i]+=tx[i-1];for(int i=1;i<=n;i++) fa[i]=floor(i/sl);for(int i=n;i;i--) siz[i]++,siz[fa[i]]+=siz[i];tot=1; build(0,n,1);for(int i=1;i<=n;i++){if(i>1&&fa[i]!=fa[i-1])mdfy(0,n,1,0,ans[fa[i]]-1,siz[fa[i]]-1);//-1 for already useint p=qry(0,n,1,siz[i])+1;p=++tx[a[p]-1];// ans[i]=p;mdfy(0,n,1,0,p-1,-siz[i]);}for(int i=1;i<=n;i++)printf("%d ",tp[a[ans[i]]]);puts(""); return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Narh/p/10537426.html

總結(jié)

以上是生活随笔為你收集整理的洛谷 4364 [九省联考2018]IIIDX——“预留”的思路的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。