暑假集训CSP提高模拟14
\(T1\) P209.BA \(30pts\)
-
部分分
- \(30pts\) ：输出 \(\left\lceil \dfrac{\sum\limits_{i=1}^{m}a_{i}}{n} \right\rceil\) 。
-
数形结合，将 \(\{ a \}\) 抽象成矩形，烙饼抽象成海报覆盖，最终有 \(\max(\max\limits_{i=1}^{m} \{ a_{i} \},\left\lceil \dfrac{\sum\limits_{i=1}^{m}a_{i}}{n} \right\rceil)\) 即为所求，注意精度（？）。
点击查看代码
int main() { ll n,m,x,sum=0,maxx=0,i; cin>>m>>n; for(i=1;i<=m;i++) { cin>>x; sum+=x; maxx=max(maxx,x); } cout<<max(maxx,(sum+n-1)/n)<<endl; return 0; }
\(T2\) P210. BB \(25pts\)
-
部分分
-
\(25pts\) ：枚举所有合法状态，由买方是 \(A\) 还是 \(B\) 决定取最大值还是最小值转移，因为只能应付 \(n\) 很小的数据，所以暴力跳父亲比树剖维护路径信息会快点（？）。
点击查看代码
struct node { ll nxt,to; }e[400010]; ll head[400010],w[400010],fa[400010],dfn[400010],out[400010],a[400010],vis[400010],tot=0,cnt=0; struct BIT { ll c[400010]; void init() { memset(c,0,sizeof(c)); } ll lowbit(ll x) { return (x&(-x)); } void add(ll n,ll x,ll val) { for(ll i=x;i<=n;i+=lowbit(i)) { c[i]+=val; } } ll getsum(ll x) { ll ans=0; for(ll i=x;i>=1;i-=lowbit(i)) { ans+=c[i]; } return ans; } ll ask(ll l,ll r) { return getsum(r)-getsum(l-1); } }A,B; void add(ll u,ll v) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; head[u]=cnt; } void dfs(ll x) { tot++; dfn[x]=tot; for(ll i=head[x];i!=0;i=e[i].nxt) { dfs(e[i].to); } out[x]=tot; } ll dp(ll pos,ll n,ll sum) { if(pos==n+1) { return sum; } else { ll minn=0x7f7f7f7f,maxx=-0x7f7f7f7f,n1,n2,x; if(pos%2==1) { for(ll i=1;i<=n;i++) { if(vis[i]==0) { n1=n2=0; x=i; while(x!=1) { x=fa[x]; n2+=(vis[x]==-1); } n1=B.ask(dfn[i],out[i]); vis[i]=1; A.add(n,dfn[i],1); maxx=max(maxx,dp(pos+1,n,sum+n1-n2-w[i])); A.add(n,dfn[i],-1); vis[i]=0; } } return maxx; } else { for(ll i=1;i<=n;i++) { if(vis[i]==0) { n1=n2=0; x=i; while(x!=1) { x=fa[x]; n2+=(vis[x]==1); } n1=A.ask(dfn[i],out[i]); vis[i]=-1; B.add(n,dfn[i],1); minn=min(minn,dp(pos+1,n,sum-(n1-n2))); B.add(n,dfn[i],-1); vis[i]=0; } } return minn; } } } int main() { ll n,i; cin>>n; for(i=1;i<=n;i++) { cin>>w[i]; } for(i=2;i<=n;i++) { cin>>fa[i]; add(fa[i],i); } dfs(1); cout<<dp(1,n,0)<<endl; return 0; }
-
-
正解
- 买方每次购买一个点都会得到 \(n_{1}-n_{2}-w_{x}\) 个游戏币，相应的对方减少 \(n_{1}-n_{2}\) 个游戏币即得到 \(n_{2}-n_{1}\) 个游戏币。
- 当购买一个点后，给祖先每个点的所属对象（不管是现在还是未来）交一个游戏币，这样的话仍满足题意。那么一个点对答案产生的贡献就是 \(siz_{x}-1-(dep_{x}-1)-w_{x}=siz_{x}-dep_{x}-w_{x}\) 。
- 排序后跳着选即可。
点击查看代码
struct node { ll nxt,to; }e[400010]; ll head[400010],w[400010],siz[400010],dep[400010],fa[400010],cnt=0; void add(ll u,ll v) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; head[u]=cnt; } void dfs(ll x) { siz[x]=1; dep[x]=dep[fa[x]]+1; for(ll i=head[x];i!=0;i=e[i].nxt) { dfs(e[i].to); siz[x]+=siz[e[i].to]; } } int main() { ll n,ans=0,i; cin>>n; for(i=1;i<=n;i++) { cin>>w[i]; } for(i=2;i<=n;i++) { cin>>fa[i]; add(fa[i],i); } dfs(1); for(i=1;i<=n;i++) { w[i]=siz[i]-dep[i]-w[i]; } sort(w+1,w+1+n); for(i=n;i>=1;i-=2) { ans+=w[i]; } cout<<ans<<endl; return 0; }