感谢各位参加本次比赛
T1
数据范围1(5分):什么都不会的话可以dfs直接搜
数据范围2(15分):由于地图较小,障碍很多,直接dp即可
数据范围3(15分):因为需要走最短路径,所以最短路径一定是向右走m步,向上走n步,只需要确定哪些步向右,哪些步向上。组合数公式即可,Ans=
数据范围4(15分):一个障碍,思路同上一个数据范围,只需要去除不合法的情况,即路径中经过了障碍点的情况数。这个不符合的情况数可以用乘法原理,从起点到障碍点*从障碍点到终点的路径条数算出来。是规模更小的子问题。
数据范围5(15分):多了一个点,还是同样的思路。不过需要考虑两个点的位置关系,如果不能同时经过,就直接减,否则需要加上同时经过两个障碍点的情况数,也就是容斥原理。
数据范围6(20分):一样的思路,容斥的时候多加几种情况即可。
(所以输出frog是骗不了分的)
前30分的暴力可以随便乱搞得到,重点讲正解。
很显然是状压题目,预处理出change[i][j]表示在刺激第i个点,经过j秒后对整个神经树的影响。1代表这个点被反转,0代表没有反转。所以算贡献时将 sta |= change 即可
那么就可以枚举时间,每个情况,每个点的影响,得到转移方程:
dp[i+1][j^change[k][i]] = dp[i][j]?true:false
std:
数据范围3(15分):因为需要走最短路径,所以最短路径一定是向右走m步,向上走n步,只需要确定哪些步向右,哪些步向上。组合数公式即可,Ans=
数据范围4(15分):一个障碍,思路同上一个数据范围,只需要去除不合法的情况,即路径中经过了障碍点的情况数。这个不符合的情况数可以用乘法原理,从起点到障碍点*从障碍点到终点的路径条数算出来。是规模更小的子问题。
数据范围5(15分):多了一个点,还是同样的思路。不过需要考虑两个点的位置关系,如果不能同时经过,就直接减,否则需要加上同时经过两个障碍点的情况数,也就是容斥原理。
数据范围6(20分):一样的思路,容斥的时候多加几种情况即可。
T2
先考虑答案是否一定存在,由于刺激一个点以后,下一秒刺激其父亲节点,等价于单点改变这个点的状态。所以我们可以用2s的时间单点修改状态,答案一定<=2n且>=n,一定不会输出“frog”(所以输出frog是骗不了分的)
前30分的暴力可以随便乱搞得到,重点讲正解。
很显然是状压题目,预处理出change[i][j]表示在刺激第i个点,经过j秒后对整个神经树的影响。1代表这个点被反转,0代表没有反转。所以算贡献时将 sta |= change 即可
那么就可以枚举时间,每个情况,每个点的影响,得到转移方程:
dp[i+1][j^change[k][i]] = dp[i][j]?true:false
std:
#include<bits/stdc++.h> #define ll long long using namespace std; int n,fa[25],maxn; int need;//最后需要的状态 int s[25][50];//第i个点和它的前j个祖先有哪些点 bool dp[50][1<<17]; template<class T>inline void read(T &res) { char c;T flag=1; while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0'; while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag; } void print(int x) { while(x) { cout<<(x&1); x>>=1; } puts(""); } void init() { //把需要的状态压成二进制 for(register int i=1;i<=n;++i) { read(fa[0]); if(fa[0]) need|=1<<(i-1); } // print(need); //处理出每个时刻点i的反转情况 for(register int i=1;i<=n;++i) { s[i][1]=1<<(i-1); int x=fa[i]; for(register int j=2;j<=(n<<1);++j) { s[i][j]=s[i][j-1]; if(x) s[i][j]|=(1<<(x-1)); x=fa[x]; } } } void work() { dp[0][need]=true; for(register int i=1;i<=(n<<1);++i)//枚举每个时刻 { for(register int j=0;j<=maxn;++j)//枚举每个初始情况 { if(!dp[i-1][j]) continue; for(register int k=0;k<=n;++k)//枚举每个点 { int now=j^s[k][i];//now是反转后的情况 // print(now); dp[i][now]=true; if(!now) { printf("%d\n",i); exit(0); } } } } } int main() { // freopen("20.in","r",stdin); // freopen("20.out","w",stdout); read(n);maxn=(1<<n)-1; for(register int i=2;i<=n;++i) read(fa[i]); init(); work(); return 0; }
T3
给定一颗或几颗树,询问到x到第k远点的距离,树随机生成,期望树高为logn以下对于各数据范围给出做法
1.n,q≤1,000,暴力求出每个点到x的距离排序即可,注意可能每次dis数组要清空
2.k=1,即求到x最远的点的距离,树形dp,随意选一个根,第一遍dp求出根到各个点的距离dis,再一次dp分别求出各个点先向上走再向下走到叶子的最大距离f,对每个点x取max( dis[rt] - dis[x] , f[x] )即可
3.m=n-1,这个没什么说的,有没有都一样,只是没有的时候要注意初始化
4.注意树高期望为log,那么可以考虑乱搞,将所有询问离线,仍随意选择一个根,先求出dis数组,如果向下递归到v,则会将v所在子树的dis都减去w,其他点加上w(这一步可以变成v所在子树的dis减去2*w,其他点不变,询问时需要加回来一个w),而一个子树的dfs序是连续的,转成序列后就变成了区间修改,求第k大的问题,所以用值域线段树加二分或者平衡树维护,由于期望树高是log,那么每个点期望被修改log次,直接暴力单点修改会修改nlogn次,修改一次的复杂度为logn,那么整个算法的时间复杂度为O(nlog2n+qlogn)
P.S.暴力修改的前提是期望树高为logn,如果不是随机生成的树,那么就要用点分树转成平衡状态了qwq,时间复杂度是O(nlog3n)
std:
#include<bits/stdc++.h> #define N 100005 using namespace std; typedef long long ll; int n,m,T; int ndsum,root,l,r,p; ll dis[N],ans[N]; bool vis[N]; struct Node {int k,opt;}; struct Tree { int ch[2],size,key; ll val; }t[N]; struct Edge { int next,to; ll dis; }edge[N<<1];int head[N],cnt=1; vector <Node> q[N]; void add_edge(int from,int to,ll dis) { edge[++cnt].next=head[from]; edge[cnt].to=to; edge[cnt].dis=dis; head[from]=cnt; } template<class T> void read(T &x) { char c;int sign=1; while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48; while((c=getchar())>='0'&&c<='9') x=(x<<1)+(x<<3)+c-48; x*=sign; } inline int add_node(ll val,int nd=-1) { if(nd==-1) nd=++ndsum;//带回收的加点 t[nd].size=1; t[nd].key=rand(); t[nd].val=val; t[nd].ch[0]=t[nd].ch[1]=0; return nd; } inline void update(int rt) {t[rt].size=t[t[rt].ch[0]].size+t[t[rt].ch[1]].size+1;} void split(int rt,ll x,int &l,int &r) { if(!rt) {l=0;r=0;return;} if(t[rt].val<=x) {l=rt; split(t[rt].ch[1],x,t[rt].ch[1],r);} else {r=rt; split(t[rt].ch[0],x,l,t[rt].ch[0]);} update(rt); } int merge(int l,int r) { if(!l||!r) return l+r; if(t[l].key<t[r].key) { t[l].ch[1]=merge(t[l].ch[1],r); update(l); return l; } else { t[r].ch[0]=merge(l,t[r].ch[0]); update(r); return r; } } int query(int rt,int k) { if(k<=t[t[rt].ch[0]].size) return query(t[rt].ch[0],k); if(k==t[t[rt].ch[0]].size+1) return rt; return query(t[rt].ch[1],k-t[t[rt].ch[0]].size-1); } inline void Add(ll x,int nd=-1)//添加一个元素 { split(root,x,l,r); root=merge(merge(l,add_node(x,nd)),r); } inline int Erase(ll x)//删除一个元素,并返回其序号 { split(root,x,p,r); split(p,x-1,l,p); int ret=p; p=merge(t[p].ch[0],t[p].ch[1]); root=merge(l,merge(p,r)); return ret; } void init(int rt,int fa,ll len)//初始化子树得到dis { Add(len); dis[rt]=len; for(int i=head[rt];i;i=edge[i].next) { int v=edge[i].to; if(v==fa) continue; init(v,rt,len+edge[i].dis); } } void T_dfs(int rt,int fa,ll val)//给rt这个子树加上val { int nd=Erase(dis[rt]); dis[rt]+=val; Add(dis[rt],nd); for(int i=head[rt];i;i=edge[i].next) { int v=edge[i].to; if(v==fa) continue; T_dfs(v,rt,val); } } void dfs(int rt,int fa,ll len)//递归处理每一个点 { vis[rt]=1; if(!q[rt].empty())//计算rt上的问题 { for(vector<Node>::iterator it=q[rt].begin();it!=q[rt].end();++it) { if((it->k)<ndsum) ans[it->opt]=t[query(root,ndsum-(it->k)+1)].val+len; else ans[it->opt]=-1; } } for(int i=head[rt];i;i=edge[i].next) { int v=edge[i].to; if(v==fa) continue; T_dfs(v,rt,-edge[i].dis*2);//减掉两倍 dfs(v,rt,len+edge[i].dis); T_dfs(v,rt,edge[i].dis*2);//回溯 } } int main() { srand((unsigned)time(NULL)); read(n);read(m);read(T); for(int i=1;i<=m;++i) { int x,y; ll z; read(x);read(y);read(z); add_edge(x,y,z); add_edge(y,x,z); } for(int i=1;i<=T;++i) { int x,k; read(x);read(k); q[x].push_back((Node){k,i}); } for(int i=1;i<=n;++i) if(!vis[i]) { ndsum=root=0; init(i,0,0LL); dfs(i,0,0LL); } for(int i=1;i<=T;++i) printf("%lld\n",ans[i]); return 0; }
全部评论
(4) 回帖