【题解】牛客IOI周赛22-提高组
: 1~4 20分
可以观察到数据较小,可以使用 通过(其他乱搞也可)
(为了方便讲解,此处先讲解 )
: 9~12 另20分
可以发现在权值为1的情况下,可以使用贪心(后文将证明),记录下上一次的名次 ,每次都贪心的尽量让名次最大(即 ),若 ,则说明不管怎样都无法满足条件,则将排名设为
由于贪心遗漏的情况是当 时取 通过舍弃这一次的奖品来使下一次获得奖品,而由于权值全部为1,所以本次贪心所选取的补偿了下一个没取到的,所以贪心正确性可证,时间复杂度
: 5~8 20分(可获得40分)
由上文可知,本题需要使用dp来解决,所以考虑直接设计状态 表示第 场考试考第 名时最多的奖品数,则状态转移方程为:
显然当 一定时, 具有单调性,复杂度
: 13~20 40分(可获得100分)
发现 只有,所以连续获奖的次数最多只有次,同时受上文贪心思想的启发,易发现当本次能获得奖品时取 最优,否则取 最优。则可设计状态 表示第 场考试时已经连续获得了 次奖的最多奖品数,则状态转移方程为
其中 为辅助数组,表示连续去 次奖后第 场考试的最大名次,在转移过程中由上述贪心即可求出 数组,而最大值可在上一轮循环的计算中求出,即 可以 求出,由于每取一次奖,能取得名次都会缩小为原来的一半,即 的规模只有,故复杂度为
:可以使用滚动数组优化空间,本题没有卡空间,所以可以不使用
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define int long long using namespace std; int n,m,f[2][65],g[2][65],k; int minn(int x,int y){return x<y?x:y;} int maxx(int x,int y){return x<y?y:x;} signed main() { int i,j,x,y,z; scanf("%lld%lld",&n,&m); for(i=1;i<=n;++i) { scanf("%lld%lld%lld",&x,&y,&z); f[i&1][0]=f[i&1^1][k];if((g[i&1^1][k]>>1)>=y)f[i&1][0]+=z;g[i&1][0]=y;k=0; for(j=1;(g[i&1^1][j-1]>>1)>=x;++j) { f[i&1][j]=f[i&1^1][j-1]+z; if(f[i&1][k]<f[i&1][j])k=j; g[i&1][j]=minn(g[i&1^1][j-1]>>1,y); } } printf("%lld\n",f[i&1^1][k]); return 0; }
: 30分
只需依题目要求操作即可
: 对于另20分(可获得50分)
保证没有2,3操作,数据范围200000,我们需要一个单次操作 的算法来实现,路径加操作易想到差分,通过将路径拆分为两段进行维护
: 对于另30分(可获得80分)
此时没有3操作,由于只需要在最后输出权值,可以想到离线维护,先将所有需要加的点读入进来建树,再做如上操作
另:每次加入一个点时,将它的边建好,其他需要的信息维护好也可以实现动态维护这个操作
: 40分(100分)
根据上面的思路,可以考虑离线处理本题,可以发现对于3操作,删去节点后始终保证树的连通,隐藏含义即为删去的都是当前树的叶子节点,所以后面增加的点提前加上并不影响前面的修改操作,故只需要先将所有操作读进来,将所有的加入,再标记出已删除的点,判断哪些点仍在树上即可。
时间复杂度 ,若使用tarjan求LCA可以优化至
#include<algorithm> #include<iostream> #include<iomanip> #include<cstring> #include<cstdio> #include<cmath> #define LL long long using namespace std; const int INF=0x3f3f3f3f,T=21; int read() { int s=0,bj=0; char ch=getchar(); while(ch<'0'||ch>'9')bj|=(ch=='-'),ch=getchar(); while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar(); return bj?-s:s; } void printnum(LL x) { if(x>9)printnum(x/10); putchar(x%10^48); } void print(LL x,char ch) { if(x<0){putchar('-');x=-x;} printnum(x);putchar(ch); } int f[2000005][22],n,m,d[2000005]; LL v[2000005],num[2000005],ans[2000005]; struct node{int nx,to;}w[4000005];int h[2000005],cnt; void AddEdge(int x,int y) { w[++cnt].to=y;w[cnt].nx=h[x];h[x]=cnt; w[++cnt].to=x;w[cnt].nx=h[y];h[y]=cnt; } struct OPT{int opt,x,y,k;}opt[2000005]; bool vst[2000005]; void DFS(int x,int fa) { f[x][0]=fa;d[x]=d[fa]+1;for(int i=1;i<=T;++i)f[x][i]=f[f[x][i-1]][i-1]; for(int i=h[x];i;i=w[i].nx) { int y=w[i].to; if(y^fa)DFS(y,x); } } int LCA(int x,int y) { if(d[x]>d[y])swap(x,y); for(int i=T;i>=0;--i)if(d[f[y][i]]>=d[x])y=f[y][i]; if(x==y)return x; for(int i=T;i>=0;--i)if(f[x][i]^f[y][i]){x=f[x][i];y=f[y][i];} return f[x][0]; } void Sol(int x,int fa) { ans[x]=v[x]; for(int i=h[x];i;i=w[i].nx) { int y=w[i].to; if((y^fa)&&vst[y]){Sol(y,x);ans[x]+=ans[y];} } } int vss[2000005]; int main() { n=read();m=read();for(int i=1;i<=n;++i){vst[i]=1;num[i]=read();} for(int i=1;i<n;++i)AddEdge(read(),read()); for(int i=1;i<=m;++i) { opt[i].opt=read();opt[i].x=read(); if(opt[i].opt==1){opt[i].y=read();opt[i].k=read();} else if(opt[i].opt==2){int kkk=read();if(vss[kkk])return 1;AddEdge(++n,kkk);num[n]=opt[i].x;vst[n]=1;} else vss[opt[i].x]=1; } DFS(1,0); for(int i=1;i<=m;++i) { int x=opt[i].x,y=opt[i].y,k=opt[i].k; if(opt[i].opt==1){v[x]+=k;v[y]+=k;int lca=LCA(x,y);v[lca]-=k;v[f[lca][0]]-=k;} else if(opt[i].opt==2)continue; else {v[f[x][0]]+=v[x];vst[x]=0;} } Sol(1,0); for(int i=1;i<=n;++i)if(vst[i]){print(i,' ');print(ans[i]+num[i],'\n');} return 0; }
设 表示每一个 的到根求和
因为 ,所以 等价于
同时题目中的每次操作就相当于直接将 加上
于是原问题就等价于每次可以直接单点修改 ,求使得 任意两个节点 和 ,若 为 的祖先,则有 的最小修改次数
做法一:(30分)
设 表示 的子树中最小权值为 的最大子集
转移
做法二:(60分)
在刚刚的基础上优化一下dp的定义
设 表示 的子树中最小权值大于等于 的最大子集
转移
最后在 自己进行更新
做法三:(100分)
可以将上述方法差分后在用线段树合并解决,不过这里着重讲做法四
#include<bits/stdc++.h> #define int long long using namespace std; namespace yspm{ inline int read() { int res=0,f=1; char k; while(!isdigit(k=getchar())) if(k=='-') f=-1; while(isdigit(k)) res=res*10+k-'0',k=getchar(); return res*f; } const int N=2e5+10; struct node{ int ls,rs,sum; #define ls(p) t[p].ls #define rs(p) t[p].rs #define sum(p) t[p].sum }t[N<<6]; int rt[N],tot,p[N],b[N],vv[N],m,n; vector<int> g[N]; inline void update(int &p,int l,int r,int st,int ed,int val) { if(!p) p=++tot; if(l<=st&&ed<=r) return sum(p)++,void(); int mid=(st+ed)>>1; if(l<=mid) update(ls(p),l,r,st,mid,val); if(r>mid) update(rs(p),l,r,mid+1,ed,val); return ; } inline int merge(int x,int y,int l,int r) { if(!x||!y) return x+y; if(l==r) return sum(x)+=sum(y),x; int mid=(l+r)>>1,p=++tot; sum(p)=sum(x)+sum(y); ls(p)=merge(ls(x),ls(y),l,mid); rs(p)=merge(rs(x),rs(y),mid+1,r); return p; } inline int query(int p,int l,int r,int x) { if(!p||x>m) return 0; int mid=(l+r)>>1; if(x<=mid) return sum(p)+query(ls(p),l,mid,x); else return sum(p)+query(rs(p),mid+1,r,x); } inline void dfs(int x,int fa) { int siz=g[x].size(); for(int i=0;i<siz;++i) { int t=g[x][i]; if(t==fa)continue;dfs(t,x); rt[x]=merge(rt[x],rt[t],1,m); } int now=query(rt[x],1,m,p[x]+1)+1; if(now<=query(rt[x],1,m,p[x])) return ; int l=1,r=p[x]; while(l<r) { int mid=(l+r)>>1; if(query(rt[x],1,m,mid)<now) r=mid; else l=mid+1; } return update(rt[x],r,p[x],1,m,1); } inline void dfs1(int x,int fa,int ppp) { vv[x]+=ppp; int siz=g[x].size(); for(int i=0;i<siz;++i) { int t=g[x][i]; if(t==fa)continue; dfs1(t,x,vv[x]); } } signed main() { n=read(); for(int i=1;i<=n;++i)vv[i]=read(); for(int i=2,x,y;i<=n;++i) x=read(),y=read(),g[x].push_back(y),g[y].push_back(x); dfs1(1,0,0); for(int i=1;i<=n+1;++i) p[i]=vv[i],b[++m]=p[i]; sort(b+1,b+m+1); m=unique(b+1,b+m+1)-b-1; g[n+1].push_back(1);g[1].push_back(n+1); for(int i=1;i<=n+1;++i) p[i]=lower_bound(b+1,b+m+1,p[i])-b; dfs(n+1,0); int ans=0; for(int i=1;i<=m;++i) ans=max(ans,query(rt[n+1],1,m,i)); cout<<n+1-ans<<endl; return 0; } } signed main(){ return yspm::main();}
做法四:(100分)
由于每个点只会被修改1次,求最小修改次数就等价于 n-求最多不被修改的点数
考虑一种贪心方案,我们让子树内最小点权尽量大,为新来的点留位置 二分优化 LIS,现在我们依然二分,然后因为多线程合并采用启发式合并套一个有序的结构,使用multiset即可
由于这样并不能保证1号节点所以加入一个虚根0令 且建0到1的边即可
#include<bits/stdc++.h> #define _I inline #define _R register #define ll long long #define ull unsigned long long #define eps 1e-4 #define mod 1000000007 #define INF 0x3f3f3f3f #define y1 yy1 #define memset(x,y) memset(x,y,sizeof(x)) #define memcpy(x,y) memcpy(x,y,sizeof(x)) #define int ll using namespace std; _I int read(){ int x=0;bool f=0;char ch=getchar(); while(ch<'0'||ch>'9')f|=(ch=='-'),ch=getchar(); while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); f&&(x=-x); return x; } const int N=200005; int n,cnt,nx[N<<1],to[N<<1],head[N],val[N]; multiset<int>s[N]; multiset<int>::iterator it; void addedge(int x,int y){ nx[++cnt]=head[x];to[cnt]=y;head[x]=cnt; } void merge(int x,int y){ if(s[x].size()<s[y].size())swap(s[x],s[y]); for(it=s[y].begin();it!=s[y].end();++it)s[x].insert(*it); } void dfs(int x,int fa){ for(_R int i=head[x];~i;i=nx[i])if(to[i]!=fa)dfs(to[i],x),merge(x,to[i]); s[x].insert(val[x]); it=s[x].lower_bound(val[x]); if(it!=s[x].begin())s[x].erase(--it); } void dfs1(int x,int fa,int dep){ val[x]=dep; for(_R int i=head[x];~i;i=nx[i])if(to[i]!=fa)dfs1(to[i],x,dep+val[to[i]]); } signed main(){ n=read();memset(head,-1); for(_R int i=1;i<=n;++i)val[i]=read(); addedge(0,1);val[0]=0; for(_R int i=1,x,y;i<n;++i)x=read(),y=read(),addedge(x,y),addedge(y,x); dfs1(1,0,val[1]); dfs(0,-1); printf("%lld",n+1-s[0].size()); return 0; }