首页 > 其他分享 >2024.9.24 模拟赛 CSP4

2024.9.24 模拟赛 CSP4

时间:2024-10-02 11:34:11浏览次数:9  
标签:24 rs int 2024.9 CSP4 tr ls LL dis

模拟赛

暴力场。出题人学政治的?

T1 商品

值域线段树

直接看值域上,每两个相邻的点的差提供的贡献,相当于值域上某一区间每一个位置都有 \(1\) 的贡献再减一。

所以直接值域线段树,查询区间和。贪心发现左右端点一定挂在某个点上时最优。注意左右端点挂住的情况分别跑一遍。

边界处理比较细节。

code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define LL long long
const int N = 2e5+5,MAX = 1e9+5;
int n,d;
int a[N],rt;
namespace DSEG
{
	struct T
	{
		int l,r; LL lz,sum;
	} tr[N<<6];
	int tot;
	inline void pushup(int k) {tr[k].sum=tr[tr[k].l].sum+tr[tr[k].r].sum;}
	inline void pushdown(int k,int l,int r)
	{
		if(tr[k].lz)
		{
			int lz=tr[k].lz; tr[k].lz=0;
			if(!tr[k].l) tr[k].l=++tot;
			if(!tr[k].r) tr[k].r=++tot;
			int mid=(r-l>>1)+l;
			tr[tr[k].l].lz+=lz; tr[tr[k].l].sum+=lz*(mid-l+1);
			tr[tr[k].r].lz+=lz; tr[tr[k].r].sum+=lz*(r-mid);
		}
	}
	inline void mdf(int &k,int l,int r,int L,int R,int v)
	{
		if(L>R) return;
		if(!k) k=++tot;
		if(l>=L&&r<=R)
		{
			tr[k].lz+=v; tr[k].sum+=(r-l+1)*1ll*v; return;
		}
		pushdown(k,l,r);
		int mid=(r-l>>1)+l;
		if(L<=mid) mdf(tr[k].l,l,mid,L,R,v);
		if(R>mid) mdf(tr[k].r,mid+1,r,L,R,v);
		pushup(k);
	}
	inline LL que(int k,int l,int r,int L,int R)
	{
		if(L>R) return 0;
		if(!k) return 0;
		if(L<=l&&r<=R) return tr[k].sum;
		pushdown(k,l,r);
		int mid=(r-l>>1)+l; LL res=0;
		if(L<=mid) res+=que(tr[k].l,l,mid,L,R);
		if(R>mid) res+=que(tr[k].r,mid+1,r,L,R);
		return res;
	}
} using namespace DSEG;

main()
{
	freopen("goods.in","r",stdin);
	freopen("goods.out","w",stdout);
	scanf("%lld%lld",&n,&d); rt=++tot;
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	for(int i=1;i<n;i++)
	{
		LL l=min(a[i],a[i+1]),r=a[i+1]-l+a[i];
		mdf(rt,1,MAX,l+1,r,1);
	}
	LL ans=0;
	for(int i=1;i<=n;i++)
	{
		ans=max(ans,que(rt,1,MAX,a[i]+1,min(1ll*a[i]+d,1ll*MAX)));
		ans=max(ans,que(rt,1,MAX,max(1ll,a[i]-d+1),a[i]));
	}
	printf("%lld\n",ans);
	return 0;
}

、# 二分

求 \(\sum_{i=1}^{n-1}|b_i-b_{i+1}|\),另 \(b_i,b_{i+1}\) 中较大的为 \(a\),较小的为 \(b\)。

求 \(\sum a-b=\sum a-\sum b\)。排序后,对于每个 \([l,r]\) 区间,\(a,b\) 都会被分成三段,二分找到转折点,两边直接求和,中间前缀和维护好求。

无码。。。

T2 价值

巨型树上分讨。

题意就是树的叶子加一圈边,求独立集方案数(一条边只能选一个点)。

先考虑没有那一圈边,直接 dp,加上那一圈边,那么就要讨论叶子是否连边。

设计状态 \(f_{u,0/1,0/1/2,0/1/2}\) 表示根为 \(0/1\),选或不选,\(0/1/2\),子树最左/右侧的叶子 一定不选/可以被选(还没选)/已经选了。

树型分讨还得多练。

code
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 1e5+5,mod = 998244353;
int n,mn=1e9,mx;
vector<int> g[N];
LL f[N][2][3][3],ff[2][3][3];
void dfs(int u)
{
	if(g[u].empty()) return mn=min(mn,u),mx=max(mx,u),void(0);
	for(int v:g[u]) dfs(v);
}
void dp(int u,int tp)
{
	if(tp&&(u==mn||u==mx)) return f[u][1][2][2]=(mn!=mx),void(0);
	if(g[u].empty())
	{
		f[u][0][0][0]=1; f[u][1][2][1]=1; f[u][1][1][2]=1;
		return;
	}
	for(int v:g[u]) dp(v,tp);
	int v=g[u][0];
	for(int j=0;j<=2;j++)
		for(int k=0;k<=2;k++)
				f[u][0][j][k]=(1ll*f[v][1][j][k]+f[v][0][j][k])%mod,
				f[u][1][j][k]=f[v][0][j][k];

	for(int i=1;i<g[u].size();i++)
	{
		int v=g[u][i];
		for(int j=0;j<=2;j++)
			for(int k=0;k<=2;k++)
			{
				ff[1][j][k]=ff[0][j][k]=0;
				for(int x=0;x<=1;x++)
					for(int y=0;y<=1;y++) if(!(x==0&&y==1))
						ff[1][j][k]=(1ll*ff[1][j][k]+
									f[u][x][j][0]*f[v][y][0][k]%mod+
									f[u][x][j][0]*f[v][y][2][k]%mod+
									f[u][x][j][2]*f[v][y][0][k]%mod+
									f[u][x][j][2]*f[v][y][2][k]%mod+
									f[u][x][j][1]*f[v][y][1][k]%mod)%mod;
				for(int x=0;x<=1;x++)
					ff[0][j][k]=(1ll*ff[0][j][k]+
								f[u][0][j][0]*f[v][x][0][k]%mod+
								f[u][0][j][0]*f[v][x][2][k]%mod+
								f[u][0][j][2]*f[v][x][0][k]%mod+
								f[u][0][j][2]*f[v][x][2][k]%mod+
								f[u][0][j][1]*f[v][x][1][k]%mod)%mod;
			}
		for(int j=0;j<=2;j++)
			for(int k=0;k<=2;k++)
				for(int x=0;x<=1;x++)
					f[u][x][j][k]=ff[x][j][k];
	}
}
int main()
{
	freopen("value.in","r",stdin);
	freopen("value.out","w",stdout);
	scanf("%d",&n);
	for(int i=2;i<=n;i++)
	{
		int x; scanf("%d",&x);
		g[x].push_back(i);
	}
	for(int i=1;i<=n;i++) sort(g[i].begin(),g[i].end());
	dfs(1);	dp(1,0);
	LL ans=(1ll*f[1][1][0][0]+f[1][0][0][0]+f[1][0][2][0]+f[1][1][2][0]+f[1][0][0][2]+f[1][0][2][2]+f[1][1][0][2]+f[1][1][2][2])%mod;
	memset(f,0,sizeof(f));
	dp(1,1);
	ans=(1ll*ans+f[1][0][2][2]+f[1][1][2][2])%mod;
	printf("%lld\n",ans);
	return 0;
}

小凸玩密室

完全二叉树上分讨,注意这个重要的性质。

可以根据完全二叉树下标的规律直接遍历。

观察遍历顺序,对于一个节点,先遍历以它为根的子树,从某一个叶子跳到父亲,然后遍历它的兄弟子树。其中一个叶子可以跳到根节点的另一个儿子,

由于完全二叉树,考虑倍增跳父亲,设计状态 \(f_{u,i}\) 表示遍历完 \(u\) 的子树向上跳到第 \(i\) 级祖先。

发现有一个问题就是已经走过父亲,怎么直接跳到兄弟。

不妨直接加一个 dp 数组,记录从某一个叶子直接跳到兄弟的代价。\(f_{u,i,0/1}\) 表示跳到父亲/兄弟的代价。

转移直接分讨。不放了。注意边界。

code
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define bro(x,i) ((x>>(i-1))^1)
#define fa(i,j) ((i>>(j-1)>=1)?(i>>(j)):-1)
const int N = 2e5+5;
const LL inf = 1e17;
int n;
LL f[N][20][2],ans=1e18,dis[N][20],a[N];
void work()
{
	for(int i=n;i>=1;i--) for(int j=1;~fa(i,j);j++)
	{
		if(ls(i)>n) f[i][j][0]=dis[i][j]*a[fa(i,j)],f[i][j][1]=(dis[bro(i,j)][1]+dis[i][j])*a[bro(i,j)];
		else if(rs(i)>n) f[i][j][0]=f[ls(i)][j+1][0]+dis[ls(i)][1]*a[ls(i)],f[i][j][1]=f[ls(i)][j+1][1]+dis[ls(i)][1]*a[ls(i)];
		else f[i][j][0]=min(f[rs(i)][1][1]+f[ls(i)][j+1][0]+dis[rs(i)][1]*a[rs(i)],f[ls(i)][1][1]+f[rs(i)][j+1][0]+dis[ls(i)][1]*a[ls(i)]),
			f[i][j][1]=min(f[rs(i)][1][1]+f[ls(i)][j+1][1]+dis[rs(i)][1]*a[rs(i)],f[ls(i)][1][1]+f[rs(i)][j+1][1]+dis[ls(i)][1]*a[ls(i)]);			
	}
	for(int i=1;i<=n;i++)
	{
		LL tmp=f[i][1][0];
		for(int j=fa(i,1),k=i;j;j=fa(j,1),k=fa(k,1))
		{
			if(bro(k,1)<=n) tmp+=dis[bro(k,1)][1]*a[bro(k,1)]+f[bro(k,1)][2][0];
			else tmp+=dis[j][1]*a[fa(j,1)];
		}
		ans=min(ans,tmp);
	}
}
int main()
{
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	for(int i=2;i<=n;i++)
	{
		scanf("%lld",&dis[i][1]);
		for(int j=2;~fa(i,j);j++) dis[i][j]=dis[i][j-1]+dis[fa(i,j-1)][1];
	}
	work();
	printf("%lld\n",ans);
	return 0;
}

T3 货币

费用流板子。先咕。。。

T4 资本

生成函数。可做。咕咕咕。。。

标签:24,rs,int,2024.9,CSP4,tr,ls,LL,dis
From: https://www.cnblogs.com/ppllxx-9G/p/18440644

相关文章

  • Docker配置代理访问网络ubuntu24.04
    本文将详细介绍如何根据系统代理配置,正确设置Docker的代理环境变量,使其能够通过代理服务器进行网络访问。一、查看系统代理配置首先,我们查看了系统的代理配置:以下是图片内容的文字描述:Proxy设置NetworkProxy:已开启Configuration:手动(Manual)HTTPProxyURL:12......
  • YC342A [ 20240922 CQYC NOIP 模拟赛 T1 ] 前缀(lcp)
    题意给定\(n,m\)以及长为\(n\)的字符串\(S\)。你需要构造字符串\(T\)使得\(\sumLCP(S,T[i,...,m])\)最大。求出这个最大值。\(n,m\le5\times10^3\)。Sol首先不难发现答案一定可以由若干\(S\)的前缀拼成。考虑找到最小的无法被拆为前缀的子段,显然这个......
  • 20240918
    CardScoring这题当\(k=3\)时还无法解决,但是\(k=2\)与\(k=4\),\(k=2\)时可以直接用前缀和和\(dp\)解决,而\(k=4\)时可以用李超线段树MarshmallowMolecules这题直接启发式合并#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconst......
  • 2024初秋集训——提高组 #28
    B.车轮战题目描述你将进行\(N\)场决斗。一开始你的战斗力为\(s\),咒术强度为\(x\)。每次决斗之前你可以选择:令\(s\leftarrows+x\)。令\(x\leftarrowx+1\)。每次决斗,如果你的\(s\gef_i\),则你赢得决斗。求最多能赢多少场决斗。思路我们可以发现,你最多会进行\(80......
  • Acwing-246. 区间最大公约数
    本蒟蒻的第二篇题解qwq.题目大意:给定一个长度为\(N\)的数组,需要在数组上进行两种操作:1.Clrd,表示把\(A[l],A[l+1],...,A[r]\)都加上\(d\).2.Qlr,表示询问\(A[l],A[l+1],...,A[r]\)的最大公约数\((GCD)\).错误解法:如果你是一个只会打暴力的小蒟蒻(就像我),看......
  • 2024/09/30 模拟赛总结
    \(0+0+42+40\),T1在写正解的时候突然比赛还有1分钟结束,然后把freopen注释的暴力在最后几秒交了上去#A.博弈唐氏xor-hashing,首先博弈游戏很简单,如果有一个数的出现次数是奇数则先手必胜,否则先手必败那么先手必败的条件就是路径上所有边权都是两两配对的,即异或和为\(0\)。那......
  • 2024.10.1 总结(集训;数据结构 主要是线段树)
    XK又来给我们讲课了。开心!1.Baka'sTrick两种理解:双栈模拟队列。[找到若干个划分点,使得每个区间包含恰好一个划分点。维护划分点到划分点段的前缀、后缀信息。在在线的实现中,在队列中维护仅仅一个划分点,维护它到前面每个点和它到后面每个点的信息。当这个划分点出队时,把队......
  • 代码随想录算法训练营第六天|242.有效的字母异位词 ● 349. 两个数组的交集 ● 202.
    ​学习链接:https://programmercarl.com/哈希表理论基础.html学习笔记:遇到“要判断一个值是否在集合中出现过”的问题时,可以考虑hash表。hash表的形式包括数组、set、dict。当数的位数比较统一、或比较小,可用数组,快;当数的位数可变,可用set;当要同时考虑数的下标和值,可以用dict。......
  • [20240930]关于共享池-表对象在库缓存探究2.txt
    [20240930]关于共享池-表对象在库缓存探究2.txt--//以前探究过sql语句在共享池存在父子游标,父游标存在堆0,子游标堆0,堆6,通过各种指针链接起来,--//父游标的堆0上保存了所有子游标的列表和各个子游标的句柄指针,子游标的堆6中保存了解析过的执行计划等解析信息。--//前几天测试表对象......
  • 2024/09/29 模拟赛总结
    \(0+0+0+0=0\),感觉不如#include<bits./stdc++.h>#A.你相信()吗\(70\)分的\(O(n^3)\)算法很好解决,枚举出三盏灯的亮度后,剩下一个灯的亮度一定固定。对于每个格子剩余亮度需求取max即可。然后我们充分发扬人类智慧,当\(n\le400\)时跑暴力,否则考虑推式子,下面的\(=\)表......