首页 > 其他分享 >暑假集训CSP提高模拟13

暑假集训CSP提高模拟13

时间:2024-08-01 20:10:33浏览次数:11  
标签:13 dep 3010 ll mid 集训 LCA operatorname CSP

暑假集训CSP提高模拟13

暑假集训CSP提高模拟13

组题人: @joke3579

\(T1\) P185. 小孩召开法 1 \(43pts\)

  • 原题: [ABC278F] Shiritori

  • 部分分

    • 未知 \(pts\) :乱搞。
  • 正解

    • 状压加记忆化搜索。
    • 记录所选字符串的状态及上一个选择的字符串。当存在对方必败时自己必胜。
    点击查看代码
    int f[1<<18][18];
    string s[20];
    bool dfs(int x,int last,int n)
    {
    	if(f[x][last]==-1)
    	{
    		f[x][last]=0;
    		for(int i=0;i<=n-1;i++)
    		{
    			if(((x>>i)&1)==0)
    			{
    				if(last==0||s[last][s[last].size()-1]==s[i+1][0])
    				{
    					if(dfs(x|(1<<i),i+1,n)==0)
    					{
    						f[x][last]=1;
    						break;
    					}
    				}
    			}
    		}
    	}
    	return f[x][last];
    }
    int main()
    {
    	int n,i;
    	cin>>n;
    	for(i=1;i<=n;i++)
    	{
    		cin>>s[i];
    	}
    	memset(f,-1,sizeof(f));
    	if(dfs(0,0,n)==1)	
    	{
    		cout<<"First"<<endl;
    	}
    	else
    	{
    		cout<<"Second"<<endl;
    	}
    	return 0;
    }
    

\(T2\) P188. 小孩召开法 2 \(20pts\)

  • 原题: LibreOJ 6669.Nauuo and Binary Tree

  • 部分分

    • \(20pts\) :乱搞。
  • 正解

    • 由数据范围,猜测询问次数介于 \(O(n) \sim O(n \log n)\) 之间。
    • \(n-1\) 次询问处理出每个点的深度,然后从小到大枚举深度进行处理。
    • 接下来对 \(x,y\) 的询问,由 \(dis_{x,y}=dep_{x}+dep_{y}-2dep_{\operatorname{LCA}(x,y)}\) ,我们就可以得到 \(\operatorname{LCA}(x,y)\) 的深度。
    • 设当前已经建出了深度为 \(0 \sim d-1\) 层的二叉树,未知点为 \(x\) ,已知点为 \(y\) 。询问得到 \(\operatorname{LCA}(x,y)\) 的深度后,我们就可以知道 \(\operatorname{LCA}(x,y)\) 是哪个节点。由于是二叉树, \(x,y\) 一定位于 \(\operatorname{LCA}(x,y)\) 的两棵子树内,那么 \(x\) 的父亲节点一定位于 \(\operatorname{LCA}(x,y)\) 除 \(y\) 所在子树内的另一棵子树。
    • 令 \(y\) 初始为根节点, \(z\) 为 \(y\) 所在的重链的末端点,此时 \(\operatorname{LCA}(x,z)\) 一定在 \(y\) 所在的重链上,从 \(y\) 开始往下跳重儿子直至 \(\operatorname{LCA}(x,z)\) ,然后走到轻子树,接着令 \(y\) 是这棵轻子树的根节点,重复上述过程直至 \(dep_{y}=dep_{x}-1\) 。
    • 连上边后再往上跳更新轻重儿子。
    • 最后的询问次数为 \(O(n \log n)\) ,因为常数很小所以可以通过。
    点击查看代码
    int fa[3010],dep[3010],son[3010],siz[3010],bot[3010];
    vector<int>pos[3010],e[3010];
    void dfs(int x)
    {
    	siz[x]=1;
    	son[x]=0;
    	bot[x]=x;
    	for(int i=0;i<e[x].size();i++)
    	{
    		dfs(e[x][i]);
    		siz[x]+=siz[e[x][i]];
    		son[x]=(siz[e[x][i]]>siz[son[x]])?e[x][i]:son[x];
    		bot[x]=bot[son[x]];
    	}
    }
    void solve(int x)
    {
    	int y=1,d;
    	while(dep[y]!=dep[x]-1)
    	{
    		cout<<"? "<<x<<" "<<bot[y]<<endl;
    		cin>>d;
    		d=(dep[x]+dep[bot[y]]-d)/2;
    		while(dep[y]<d)
    		{
    			y=son[y];//跳重儿子
    		}
    		if(dep[y]!=dep[x]-1)
    		{
    			y=e[y][0]^e[y][1]^son[y];//取轻儿子
    			//因为一定有轻儿子,所以不用担心会 RE
    		}
    	}
    	fa[x]=y;
    	e[y].push_back(x);
    }
    int main()
    {
    	int n,i,j;
    	cin>>n;
    	for(i=2;i<=n;i++)
    	{
    		cout<<"? "<<1<<" "<<i<<endl;
    		cin>>dep[i];
    		pos[dep[i]].push_back(i);
    	}
    	for(i=1;i<=n;i++)
    	{
    		dfs(1);
    		for(j=0;j<pos[i].size();j++)
    		{
    			solve(pos[i][j]);
    		}
    	}
    	cout<<"! ";
    	for(i=2;i<=n;i++)
    	{
    		cout<<fa[i]<<" ";
    	}
    	cout<<endl;
    	return 0;
    }
    

\(T3\) T176. 小孩召开法 3 \(30pts\)

  • 原题: luogu P6240 好吃的题目

  • 部分分

    • \(30pts\) :每组询问跑一遍 \(01\) 背包。
  • 正解

    • 将询问离线下来,然后进行分治。
    • 考虑猫树分治,只单独处理跨过中点的询问,其他询问下放至左右递归中。特判叶子节点的处理。
      • 因过程和猫树很像,所以被称作猫树分治。
    • 对于跨过中点的询问,暴力进行背包合并即可。
    点击查看代码
    struct node
    {
    	ll l,t,id;
    };
    ll h[40010],w[40010],ans[200010],f[40010][210];
    vector<node>q[40010];
    void solve(ll l,ll r)
    {
    	if(l==r)
    	{
    		for(ll i=0;i<q[r].size();i++)
    		{
    			if(q[r][i].l==l)
    			{
    				ans[q[r][i].id]=(q[r][i].t>=h[l])*w[l];
    			}
    		}
    		return;
    	}
    	ll mid=(l+r)/2;
    	memset(f[mid],0,sizeof(f[mid]));//注意清空
    	f[mid][h[mid]]=w[mid];
    	for(ll i=mid-1;i>=l;i--)
    	{
    		for(ll j=1;j<=200;j++)
    		{
    			f[i][j]=f[i+1][j];
    			if(j-h[i]>=0)
    			{
    				f[i][j]=max(f[i][j],f[i+1][j-h[i]]+w[i]);
    			}
    		}
    	}
    	memset(f[mid+1],0,sizeof(f[mid+1]));//注意清空
    	f[mid+1][h[mid+1]]=w[mid+1];
    	for(ll i=mid+2;i<=r;i++)
    	{
    		for(ll j=1;j<=200;j++)
    		{
    			f[i][j]=f[i-1][j];
    			if(j-h[i]>=0)
    			{
    				f[i][j]=max(f[i][j],f[i-1][j-h[i]]+w[i]);
    			}
    		}
    	}
    	for(ll i=l;i<=r;i++)
    	{
    		for(ll j=1;j<=200;j++)
    		{
    			f[i][j]=max(f[i][j],f[i][j-1]);
    		}
    	}
    	for(ll i=mid+1;i<=r;i++)
    	{
    		for(ll j=0;j<q[i].size();j++)
    		{
    			if(l<=q[i][j].l&&q[i][j].l<=mid)
    			{
    				for(ll k=0;k<=q[i][j].t;k++)
    				{
    					ans[q[i][j].id]=max(ans[q[i][j].id],f[i][k]+f[q[i][j].l][q[i][j].t-k]);
    				}
    			}
    		}
    	}
    	solve(l,mid);
    	solve(mid+1,r);
    }
    int main()
    {
    	ll n,m,l,r,t,i;
    	cin>>n>>m;
    	for(i=1;i<=n;i++)
    	{
    		cin>>h[i];
    	}
    	for(i=1;i<=n;i++)
    	{
    		cin>>w[i];
    	}
    	for(i=1;i<=m;i++)
    	{
    		cin>>l>>r>>t;
    		q[r].push_back((node){l,t,i});
    	}
    	solve(1,n);
    	for(i=1;i<=m;i++)
    	{
    		cout<<ans[i]<<endl;
    	}
    	return 0;
    }
    

\(T4\) T177. 小孩召开法 4 \(5pts\)

  • 原题: [AGC056B] Range Argmax
  • 部分分
    • \(5pts\) :输出样例 \(1\) 。
  • 正解
    • 过于抽象,直接贺官方题解了。

    同一个 \(x\) 可能对应多个 \(p\),因此这样计数比较困难。

    考虑反过来计数。

    对于给定的 \(x\),我们将按照以下的方式构造 \(p\):

    • 令 \(p = (-1,-1,\cdots,-1)\) 。
    • 我们从 \(n\) 开始依次递减地考虑每个值 \(v\)。对于每个值,我们找到 \(v\) 能放的最左侧的位置,放进去。

    计数可以通过这种方式生成的 \(p\) 。

    设当前最值为 \(v\)。我们首先确定下标 \(m\),使得 \(p_m = v\)。对于所有包含 \(m\) 的区间 \(i\),有 \(x_i = m\)。删除这些包含 \(m\) 的区间后,我们可以分别考虑位于 \(m\) 左右两侧的区间。由于 \(m\) 为最左侧的可以放 \(v\) 的位置,右侧的数均小于左侧的数,这部分是和原问题等价但规模更小的子问题。

    现在考虑左侧。我们令 \(k\) 为 \(m\) 左侧最大元素对应的下标。有:必定存在一个左侧区间同时包含 \(k\) 和 \(m\)。

    考虑反证。如果左侧没有区间同时包含 \(k\) 和 \(m\),那我们可以令 \(p_k = v\),这必定是更优且满足要求的。这与假设矛盾,因此必定存在同时包含 \(k\) 和 \(m\) 的左侧区间。
    因此,左侧区间所填的数的最大值必定大于等于 \(v\)。

    考虑区间 dp。我们设 \(f(l,r,m)\) 为 \([l,r]\) 区间满足最大值的下标大于等于 \(m\) 的方案数。可以通过枚举中点以及预处理区间最大值的方式转移。转移时加入后缀和即可快速得到最终答案。

    时间复杂度 \(O(n^3)\)。

总结

  • \(T4\) 赛时没读懂题。

后记

标签:13,dep,3010,ll,mid,集训,LCA,operatorname,CSP
From: https://www.cnblogs.com/The-Shadow-Dragon/p/18336722

相关文章

  • 暑假集训csp提高模拟13
    赛时rank28,T144,T20,T330,T45啊哈哈哈哈哈,我要挂没啦,啊哈哈哈哈哈哈哈哈哈最后10min的心路历程感觉应该又要挂分了(11:20)感觉一分没有(11:23)要被薄纱了(11:25)感觉人均AK,就我不会(11:25)啊哈哈哈哈哈,我太菜了,我要AF0了(11:27)啊哈哈哈,看了一眼自己代码,我咋只......
  • Luogu P1613 跑路 题解 [ 蓝 ] [ 倍增 ] [ Floyd 最短路 ] [ 状压 dp ]
    跑路:绝佳倍增好题,思路是化\(2^k\)为\(1\),倍增起预处理作用。最近不知道是撞了什么运,前一脚看的是绿题,写完之后交一发,发现直接被lxl升蓝了,血赚。思路:Floyd首先观察到每次走\(2^k\)的代价为\(1\),我们可以预处理出每次走\(2^i\)能到哪些点。但为了让这题的代码更好实......
  • CodeForces 1132B Discounts
    题目链接:CodeForces1132B【Discounts】思路    因为使用coupons购买q[i]块巧克力,不需要付最便宜的那块巧克力的钱,所以为了使得优惠最大化,所以可以在使用优惠券的时候购买最贵的p[i]块巧克力,所以计算所有巧克力价格高之和和排序后很快能得到答案。代码#include<cst......
  • [赛记] 暑假集训CSP提高模拟 #N/A 总结
    没写的有些多,所以一块写EVA原题:忘了;贪心;赛时将每条鱼放在了右端点,导致分的情况太多,最后没打完;贪心的想一下,将每条鱼放在网的左或右端点肯定不会更劣;将每条鱼作为网的左端点,然后利用相对运动的知识统计出剩下$n-1$条鱼的进入和出去网的范围的时间(可以将出去的时间稍......
  • 代码随想录day16 || 513 树左下角值,112 路径之和,116 中序后序遍历构造二叉树
    切片传递问题question:什么情况下传递切片,什么情况下传递切片指针,为什么有时候会修改原始副本,有时候又不会呢?typesli[]intfuncmain(){ slice:=[]int{1} fmt.Printf("slice:%p\n",slice) change1(slice) fmt.Println("=================================") s2:=......
  • CSP-J2019公交换乘
    马上CSP2024了,做题ing...(题目描述戳它思路1.用结构体双端队列存票,用双端队列的原因是后面要遍历2.结构体元素:price+time+used3.过期的票要及时pop4.不要一边遍历一边pop,用used标记代码#include<bits/stdc++.h>usingnamespacestd;structTicket{intprice......
  • SSCI新质生产力测算数据集(2013-2022年)
    数据来源:参考发表于InternationalReviewofEconomicsandFinance上的文章,基于He和Liu(2024)的做法,构建了一个衡量新质生产力的指标体系,通过熵值法对各个指标进行计算得到各省份新质生产力水平数据。时间跨度:2013-2022年数据范围:省级层面包含指标:样例数据:测算代码:包......
  • CVE-2023-1313
    开启靶场url访问/install来运行安装http://eci-2ze0wqx38em0qticuhug.cloudeci1.ichunqiu.com/install/得知其用户和密码为admin登录查找文件上传位置上传一句话木马文件<?phpechophpinfo();@eval($_POST['flw']);?>下载查看上传木马路径复制路径/storag......
  • 中山集训 day 1 day 3 模拟赛补题
    Round1A模拟即可。赛场上的写法我自认为写的挺好的。把所有的in替换成outans可以得到的所有串预处理出来,然后和其他原来的串判一下相等即可。Round1B很容易写错的题目。需要意识到\(dp_{\{\}}=x\),如果\(x\)的值更小的话,可以考虑将本来设为dp状态的四元组中的某......
  • 2024暑假集训测试16
    前言比赛链接。真是一次比一次唐了。被莫反害惨了属于是(其实完全是自己唐吧),T1狂推莫反不止,一直想着怎么处理\(999\)的限制,最后推出来了复杂度是\(999\sqrtn\)的,过不去,继续唐我的高级分块套分块做法,比赛快结束了才发现正因为那个限制所以我直接枚举就行了,丫的最后少了......