10.1
闲话
做题纪要
10.2
闲话
做题纪要
10.3
闲话
做题纪要
luogu P3241 [HNOI2015] 开店
-
多倍经验： luogu P4211 [LNOI2014] LCA
-
不难发现两个点在点分树上的 \(\operatorname{LCA}\) 是一个求距离的好的分割点，考虑点分树。
-
暂且不考虑 \([l,r]\) 的限制，因为只是一个限制范围的查找。
-
设 \(siz_{x}\) 表示点分树上以 \(x\) 为根的子树大小， \(sum_{0/1,x}\) 表示点分数上以 \(x\) 为根的子树内的所有节点到 \(x\) / \(x\) 在点分树上的父亲节点的距离和。
-
设当前开店节点为 \(x\) ，在点分树上跳到了 \(rt\) 。
-
仍考虑枚举 \(\operatorname{LCA}\) ，除去 \(rt\) 方向上的贡献，此时对答案产生的贡献为 \(sum_{0,fa_{rt}}-sum_{1,rt}+(siz_{fa_{rt}}-siz_{rt}) \times dis_{x,fa_{rt}}\) 。
-
对于年龄 \(\in [l,r]\) 的限制，套一个支持单点插入、区间查询的数据结构即可。
-
离散化后使用动态开点线段树貌似空间还是会爆炸，又因为没有修改操作，所以使用
vector代替即可。具体地，原区间查询距离和转化为二分端点后的两个前缀和相减，原查询大小和转化为二分端点后两个端点相减。点击查看代码
struct node {ll nxt,to,w; }e[300010]; ll head[300010],a[300010],b[300010],ask,cnt=0; void add(ll u,ll v,ll w) {cnt++;e[cnt].nxt=head[u];e[cnt].to=v;e[cnt].w=w;head[u]=cnt; } struct LCA {ll siz[300010],fa[300010],dep[300010],son[300010],top[300010],dis[300010];void init(){dfs1(1,0);dfs2(1,1);}void dfs1(ll x,ll father){siz[x]=1;fa[x]=father;dep[x]=dep[father]+1;for(ll i=head[x];i!=0;i=e[i].nxt){if(e[i].to!=father){dis[e[i].to]=dis[x]+e[i].w;dfs1(e[i].to,x);siz[x]+=siz[e[i].to];son[x]=(siz[e[i].to]>siz[son[x]])?e[i].to:son[x];}}}void dfs2(ll x,ll id){top[x]=id;if(son[x]!=0){dfs2(son[x],id);for(ll i=head[x];i!=0;i=e[i].nxt){if(e[i].to!=fa[x]&&e[i].to!=son[x]){dfs2(e[i].to,e[i].to);}}}}ll lca(ll u,ll v){while(top[u]!=top[v]){if(dep[top[u]]>dep[top[v]]){u=fa[top[u]];}else{v=fa[top[v]];}}return (dep[u]<dep[v])?u:v;}ll get_dis(ll x,ll y){return dis[x]+dis[y]-2*dis[lca(x,y)];} }L; struct SMT {struct quality{ll val,sum;bool operator < (const quality &another) const{return val<another.val;}};vector<quality>e[300010];void update(ll x,ll val,ll sum){e[x].push_back((quality){val,sum});}void init(ll n){for(ll i=1;i<=n;i++){sort(e[i].begin(),e[i].end());for(ll j=1;j<e[i].size();j++){e[i][j].sum+=e[i][j-1].sum;}}}ll query_sum(ll x,ll l,ll r){l=lower_bound(e[x].begin(),e[x].end(),(quality){l,0})-e[x].begin();r=upper_bound(e[x].begin(),e[x].end(),(quality){r,0})-e[x].begin()-1;ll ans=0;if(0<=r&&r<e[x].size()){ans+=e[x][r].sum;}if(0<=l-1&&l-1<e[x].size()){ans-=e[x][l-1].sum;}return ans;}ll query_siz(ll x,ll l,ll r){l=lower_bound(e[x].begin(),e[x].end(),(quality){l,0})-e[x].begin();r=upper_bound(e[x].begin(),e[x].end(),(quality){r,0})-e[x].begin()-1;return r-(l-1);} }T[2]; struct Divide_On_Tree {ll siz[300010],weight[300010],vis[300010],fa[300010],center=0;void init(ll n){center=0;get_center(1,0,n);get_siz(center,0);build(center);} void get_center(ll x,ll fa,ll n){siz[x]=1;weight[x]=0;for(ll i=head[x];i!=0;i=e[i].nxt){if(e[i].to!=fa&&vis[e[i].to]==0){get_center(e[i].to,x,n);siz[x]+=siz[e[i].to];weight[x]=max(weight[x],siz[e[i].to]);}}weight[x]=max(weight[x],n-siz[x]);if(weight[x]<=n/2){center=x;}}void get_siz(ll x,ll fa){siz[x]=1;for(ll i=head[x];i!=0;i=e[i].nxt){if(e[i].to!=fa&&vis[e[i].to]==0){get_siz(e[i].to,x);siz[x]+=siz[e[i].to];}}}void build(ll x){vis[x]=1;for(ll i=head[x];i!=0;i=e[i].nxt){if(vis[e[i].to]==0){center=0;get_center(e[i].to,x,siz[e[i].to]);get_siz(center,0);fa[center]=x;build(center);}}}void update(ll x,ll mod){T[0].update(x,a[x],0);for(ll rt=x;fa[rt]!=0;rt=fa[rt]){T[0].update(fa[rt],a[x],L.get_dis(fa[rt],x));T[1].update(rt,a[x],L.get_dis(fa[rt],x));}}ll query(ll x,ll l,ll r,ll mod){ll ans=T[0].query_sum(x,l,r);for(ll rt=x;fa[rt]!=0;rt=fa[rt]){ans+=T[0].query_sum(fa[rt],l,r)-T[1].query_sum(rt,l,r);ans+=(T[0].query_siz(fa[rt],l,r)-T[0].query_siz(rt,l,r))*L.get_dis(fa[rt],x);}return ans;} }D; int main() {ll n,m,mod,u,v,w,x,l,r,ans=0,i;cin>>n>>m>>mod;for(i=1;i<=n;i++){cin>>a[i];}for(i=1;i<=n-1;i++){cin>>u>>v>>w;add(u,v,w);add(v,u,w);}L.init();D.init(n);for(i=1;i<=n;i++){D.update(i,mod);}T[0].init(n);T[1].init(n);for(i=1;i<=m;i++){cin>>x>>l>>r;l=(l+ans)%mod;r=(r+ans)%mod;if(l>r){swap(l,r);}ans=D.query(x,l,r,mod);cout<<ans<<endl;}return 0; }
10.4
闲话
做题纪要
luogu P3345 [ZJOI2015] 幻想乡战略游戏
luogu P5311 [Ynoi2011] 成都七中
[ABC373F] Knapsack with Diminishing Values
- 暴力
-
分组背包写个常数小点的加手动开 \(O3\) 就过了（赛时直接把火车头粘上了），算下来 \(AT\) 神机能跑 \(1e10\) 。
点击查看代码
#include<bits/stdc++.h> #pragma GCC optimize(3) #pragma GCC target("avx") #pragma GCC optimize("Ofast") #pragma GCC optimize("inline") #pragma GCC optimize("-fgcse") #pragma GCC optimize("-fgcse-lm") #pragma GCC optimize("-fipa-sra") #pragma GCC optimize("-ftree-pre") #pragma GCC optimize("-ftree-vrp") #pragma GCC optimize("-fpeephole2") #pragma GCC optimize("-ffast-math") #pragma GCC optimize("-fsched-spec") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("-falign-jumps") #pragma GCC optimize("-falign-loops") #pragma GCC optimize("-falign-labels") #pragma GCC optimize("-fdevirtualize") #pragma GCC optimize("-fcaller-saves") #pragma GCC optimize("-fcrossjumping") #pragma GCC optimize("-fthread-jumps") #pragma GCC optimize("-funroll-loops") #pragma GCC optimize("-fwhole-program") #pragma GCC optimize("-freorder-blocks") #pragma GCC optimize("-fschedule-insns") #pragma GCC optimize("inline-functions") #pragma GCC optimize("-ftree-tail-merge") #pragma GCC optimize("-fschedule-insns2") #pragma GCC optimize("-fstrict-aliasing") #pragma GCC optimize("-fstrict-overflow") #pragma GCC optimize("-falign-functions") #pragma GCC optimize("-fcse-skip-blocks") #pragma GCC optimize("-fcse-follow-jumps") #pragma GCC optimize("-fsched-interblock") #pragma GCC optimize("-fpartial-inlining") #pragma GCC optimize("no-stack-protector") #pragma GCC optimize("-freorder-functions") #pragma GCC optimize("-findirect-inlining") #pragma GCC optimize("-fhoist-adjacent-loads") #pragma GCC optimize("-frerun-cse-after-loop") #pragma GCC optimize("inline-small-functions") #pragma GCC optimize("-finline-small-functions") #pragma GCC optimize("-ftree-switch-conversion") #pragma GCC optimize("-foptimize-sibling-calls") #pragma GCC optimize("-fexpensive-optimizations") #pragma GCC optimize("-funsafe-loop-optimizations") #pragma GCC optimize("inline-functions-called-once") #pragma GCC optimize("-fdelete-null-pointer-checks") using namespace std; #define ll long long #define ull unsigned long long #define sort stable_sort #define endl '\n' ll w[3010],v[3010],f[2][3010]; int main() {ll n,m,ans=0,i,j,k;cin>>n>>m;for(i=1;i<=n;i++){cin>>w[i]>>v[i];}for(i=1;i<=n;i++){for(j=1;j<=m;j++){f[i&1][j]=f[(i-1)&1][j];}for(k=1;k*w[i]<=m;k++){for(j=k*w[i];j<=m;j++){f[i&1][j]=max(f[i&1][j],f[(i-1)&1][j-k*w[i]]+k*v[i]-k*k);}}}for(i=1;i<=m;i++){ans=max(ans,f[n&1][i]);}cout<<ans<<endl;return 0; }
-
