竞赛讨论区 > 【题解】牛客OI周赛14-提高组题解

【题解】牛客OI周赛14-提高组题解

头像
恋恋天下第一
编辑于 2020-03-08 11:15:13 APP内打开
赞 3 | 收藏 0 | 回复4 | 浏览1190
感谢各位参加本次比赛

T1

数据范围1(5分):什么都不会的话可以dfs直接搜
数据范围2(15分):由于地图较小,障碍很多,直接dp即可
数据范围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条回帖

回帖
加载中...
话题 回帖

近期热帖

等你来战

查看全部

热门推荐