首页 > 其他分享 >CSP-S 模拟赛 32

CSP-S 模拟赛 32

时间:2024-10-04 21:50:52浏览次数:7  
标签:int 32 MAXN dp 答案 big 倍增 CSP 模拟

CSP-S 模拟赛 32

rnk25,\(0+0+9+0=9\)。

T1 [CF1578K] Kingdom of Islands

还没改出来。

T2 [CF1578L] Labyrinth

警钟嚼烂:改代码改干净。

首先考虑如果从 \(a\) 走到 \(b\),人最胖是多少。毫无疑问,这是一个最大生成树问题。在这个基础上考虑原问题,我们发现由于人会越来越胖,一定有边就逐渐断掉了,且最先断掉的边一定是最窄的边。

那么我们需要在这条边断掉以前吃掉这条边连接的两棵子树的任意一边的所有糖果,否则就再也过不去了,也就没有办法吃掉所有糖果。

然后我们易证:最先吃掉这条边的一颗子树上的所有糖果一定不劣于其他选择。

设这条边连接的子树为 \(u,v\),这两棵子树的糖果和分别为 \(s_u,s_v\)。

考虑如果先吃树 \(v\) 的一些糖,然后再过去吃掉树 \(u\) 的所有糖,且还能从 \((u,v)\) 这条边返回,则证明这个过程中人的宽度一定不超过 \(w(u,v)\)。那么如果先吃树 \(u\) 的所有糖之后再吃树 \(v\),总宽度一定也是不超过 \(w(u,v)\) 的。所以不会劣。

我们发现:如果原问题在树 \(v\) 上的答案为 \(f_v\),则新加入边 \((u,v)\) 后,答案就是 \(\min\big(f_v-s_u,w(u,v)-s_u\big)\)。如果是先吃完树 \(v\),答案也是同理。所以当前总的答案就是

\[\max\Big(\min\big(f_v-s_u,w(u,v)-s_u\big),\min\big(f_u-s_v,w(u,v)-s_v\big)\Big)~. \]

在 Kruskal 求最大生成树的过程中,用并查集可以很方便的维护这些信息。

最后一点,如何在最后输出答案时找到那一条宽度最小的边?因为 Kruskal 最大生成树是按边权从大到小加的,所以最后加的那条边就是宽度最小的边。

#include<bits/stdc++.h>
#define fw fwrite(obuf,p3-obuf,1,stdout)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define putchar(x) (p3-obuf<1<<20?(*p3++=(x)):(fw,p3=obuf,*p3++=(x)))
#define int long long
using namespace std;

char buf[1<<20],obuf[1<<20],*p1=buf,*p2=buf,*p3=obuf,str[20<<2];
int read(){
	int x=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x;
}
template<typename T>
void write(T x,char sf='\n'){
	if(x<0)putchar('-'),x=~x+1;
	int top=0;
	do str[top++]=x%10,x/=10;while(x);
	while(top)putchar(str[--top]+48);
	putchar(sf);
}
constexpr int MAXN=2e5+5;
mt19937 wdz(chrono::steady_clock::now().time_since_epoch().count());
int n,m,c[MAXN];
struct Edge{
	int u,v;
	long long w;
	bool operator<(const Edge&x)const{
		return w>x.w;
	}
}e[MAXN];
int f[MAXN];
int find(int x){
	if(f[x]^x)f[x]=find(f[x]);
	return f[x];
}
long long dp[MAXN],sum[MAXN],rt;

signed main(){
	freopen("fat.in","r",stdin);
	freopen("fat.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;++i)sum[i]=c[i]=read();
	for(int i=1;i<=m;++i)e[i]={read(),read(),read()};
	sort(e+1,e+m+1);
	iota(f+1,f+n+m+1,1);
	memset(dp,0x3f,sizeof(int)*(n+5));
	for(int i=1,u,v,fu,fv;i<=m;++i){
		u=e[i].u,v=e[i].v;
		fu=find(u),fv=find(v);
		if(fu==fv)continue;
		f[fu]=f[fv]=i+n;
		rt=i+n;
		dp[i+n]=max(min(e[i].w-sum[fu],dp[fv]-sum[fu]),min(e[i].w-sum[fv],dp[fu]-sum[fv]));
		sum[i+n]=sum[fu]+sum[fv];
	}
	write(dp[rt]<=0?-1:dp[rt]);
	return fw,0;
}

T3 [CF1578J] Just Kingdom

警钟搅烂:浮点数注意精度保留 eps。

初看这给来给去的很麻烦,事实上,我们发现:如果当前节点 \(u\) 需要 \(x\) 块钱,则他父亲需要的钱为 \(x+\sum_{v\in\text{bro}}\min(\mathit{siz}_v,x)\) 块钱。可以理解为一个香槟塔的东西(wzw 说的)。

这题的关键在于,题目要求每个节点的答案,这导致对于每个节点,每个父亲要求的这个儿子都不一样。如果我们对每个节点都暴力向上跳父亲,然后按照刚刚推出来的这个东西跑 DFS,这就是一个 \(O(n^2)\) 的做法,可以拿到 63pts 的好成绩。

下面是题解的话。

那我们看怎么快速地维护这个东西,想到倍增。我们发现如果 \(x\le\mathit{siz}_v\),那么它父亲得到的 \(x\) 至少翻倍,令这个点为 “倍增点”。注意到在一个树中的任意一点 \(u\) 跳到根节点中至多有 \(\log\sum m\) 个倍增点,而在跳到倍增点之前的路径,其对 \(x\) 的增量是容易预处理的。

于是考虑一个倍增,\(f_{u,i}\) 代表从 \(u\) 到第 \(2^i\) 级父亲,要求 \(x\le\;?\) 才不会遇到倍增点。统计答案的时候就是倍增跳倍增点,在倍增点上的答案计算可以通过提前给该点儿子点权和排序然后二分来快速求得。复杂度 \(O(n\log n(\log n+\log m))\)。

#include<bits/stdc++.h>
#define fw fwrite(obuf,p3-obuf,1,stdout)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define putchar(x) (p3-obuf<1<<20?(*p3++=(x)):(fw,p3=obuf,*p3++=(x)))
using namespace std;

char buf[1<<20],obuf[1<<20],*p1=buf,*p2=buf,*p3=obuf,str[20<<2];
int read(){
	int x=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x;
}
template<typename T>
void write(T x,char sf='\n'){
	if(x<0)putchar('-'),x=~x+1;
	int top=0;
	do str[top++]=x%10,x/=10;while(x);
	while(top)putchar(str[--top]+48);
	putchar(sf);
}
constexpr int MAXN=3e5+5;
int n,F;
int head[MAXN],tot;
struct{int v,nxt;}e[MAXN];
void addedge(int u,int v){
	e[++tot]={v,head[u]};
	head[u]=tot;
}
int fa[MAXN][31];
long long val[MAXN];
void dfs(int u){
	for(int i=head[u];i;i=e[i].nxt){
		dfs(e[i].v);
		val[u]+=val[e[i].v];
	}
}
int son[MAXN];
long long dp[MAXN];
long long su[MAXN][31],f[MAXN][31];
vector<long long>s[MAXN],va[MAXN];
void dfs2(int u,int x){
	if(u==x)return;
	dfs2(son[u],x);
	dp[u]+=dp[son[u]];
	for(int i=head[u];i;i=e[i].nxt){
		if(e[i].v==son[u])continue;
		dp[u]+=min(val[e[i].v],dp[son[u]]);
	}
}
void dfs3(int u){
	for(int i=1;i<=F;++i)fa[u][i]=fa[fa[u][i-1]][i-1];
	if(u^1){
		f[u][0]=va[fa[u][0]].size()==1?0:va[fa[u][0]][va[fa[u][0]].size()-1-(va[fa[u][0]][va[fa[u][0]].size()-1]==val[u])];
		su[u][0]=s[fa[u][0]][s[fa[u][0]].size()-1]-val[u];
		for(int i=1;i<=F;++i){
			su[u][i]=su[u][i-1]+su[fa[u][i-1]][i-1];
			f[u][i]=max(f[u][i-1],f[fa[u][i-1]][i-1]-su[u][i-1]);
		}
	}
	for(int i=head[u];i;i=e[i].nxt)dfs3(e[i].v);
}

int main(){
	freopen("share.in","r",stdin);
	freopen("share.out","w",stdout);
	n=read()+1;
	F=log2(n);
	for(int i=2,f;i<=n;++i){
		f=read(),val[i]=read();
		addedge(f+1,i);
		fa[i][0]=f+1;
	}
	dfs(1);
	for(int i=2;i<=n;++i){
		va[fa[i][0]].emplace_back(val[i]);
		s[fa[i][0]].emplace_back(0);
	}
	for(int i=1;i<=n;++i){
		if(va[i].empty())continue;
		sort(va[i].begin(),va[i].end());
		s[i][0]=va[i][0];
		if(va[i].size()==1)continue;
		for(int j=1;j<(int)va[i].size();++j)
			s[i][j]=s[i][j-1]+va[i][j];
	}
	dfs3(1);
	for(int i=2;i<=n;++i){
		int x=i;
		long long t=val[i];
		while(x){
			for(int j=F;~j;--j){
				if(x&&t>=f[x][j]){
					t+=su[x][j];
					x=fa[x][j];
				}
			}
			if(!x)continue;
			int p=upper_bound(va[fa[x][0]].begin(),va[fa[x][0]].end(),t)-va[fa[x][0]].begin()-1;
			long long lst=t;
			if(p<0){
				t+=lst*s[fa[x][0]].size();
				t-=min(val[x],lst);
			}else{
				t+=lst*(s[fa[x][0]].size()-p-1);
				t+=s[fa[x][0]][p];
				t-=min(val[x],lst);
			}
			x=fa[x][0];
		}
		write(t);
	}
	return fw,0;
}

T4 [CF1578B] Building Forest Trails

好玩的:既然 \(n\) 个点平均分布在一个圆上,三角函数计算每个点的坐标,每修一条路就连一条直线计算解析式,和之前连的直线联立计算交点判断是否在圆内,然后统计答案。这是一个标准的 \(O(n^2)\),期望得分 20pts,实际得分 26pts(初中)或 27pts(高中)。

正解唐了。

标签:int,32,MAXN,dp,答案,big,倍增,CSP,模拟
From: https://www.cnblogs.com/laoshan-plus/p/18447342

相关文章

  • CSP-S模拟赛20241004
    A你考虑可以把这个数组当中的每个数表示成另一种形式:\(a_i=k_i\timesx+b\)(其中\(x\)是模数,\(b\)为余数)。对于求两个数是否对于某个余数同余,显然你要判断他们两个的差,即\(a_i-a_j\),那么我们用上面那种形式表示其实就是\(a_i-a_j=(k_i-k_j)\timesx\),所以你要判断整个数......
  • CSP-JS多省分数线分析!复赛如何准备?(附复赛流程视频)
    截止目前已经有多个省份CSP-JS的分数线已经出了,很多省份比去年提升了不少,像河南等地都提升了20多分,不过也有一些省份,天津比去年提升分数却不是很多。还有很多省份分数线没出,各位家长想要预估是否能够晋级的,以下是已出分数线省份表格统计:目前已出分数线省份省份入门组......
  • [CSP-J 2023] 小苹果(apple)-----------用数组
    1#include<iostream>2usingnamespacestd;3intmain(){4intn,m;5cin>>n>>m;6intg=n,t=0,li,s[n+1],b;7for(inti=1;i<=n;i++){8s[i]=i;9}10while(g){11t+=1,b=0,li=0,g-=(g+......
  • CSP小苹果详细解法
    #include<bits/stdc++.h>usingnamespacestd;intmain(){intn,ant=0,t,j;cin>>n;cout<<"小苞的桌上一共放了"<<n<<"个苹果。"<<endl;inta[n+5],b[n+5];for(inti=1;i<=n;i++){a[i......
  • 信息学奥赛复赛复习11-CSP-J2020-04方格取数-动态规划、斐波那契数列、最优子结构、重
    PDF文档公众号回复关键字:202410041P7074[CSP-J2020]方格取数[题目描述]设有n×m的方格图,每个方格中都有一个整数。现有一只小熊,想从图的左上角走到右下角,每一步只能向上、向下或向右走一格,并且不能重复经过已经走过的方格,也不能走出边界。小熊会取走所有经过的方格中......
  • 【C++】 string类的模拟实现
    目录string类各函数接口总览构造函数拷贝构造函数赋值运行符重载函数析构函数迭代器相关函数beginend容量和大小相关的函数sizecapacityresizereserveempty修改字符串相关函数push_backappendoperator+=inserteraseclearswapc_str访问字符串相关函数o......
  • 冲刺CSP联训模拟2
    冲刺CSP联训模拟2过T2了,赢了T3T4暴力没写满,输了A挤压我是唐诗老哥一个半小时才过T1发现要求的是\(E(s^2)\),因为有个异或,所以直接考虑拆贡献到每一位\[E(s^2)=E(\sums_i\sums_j)=\sumE(s_is_j)\]所以直接考虑后面那个咋做,就是\(i,j\)位同时是一的时候贡献\(2^......
  • 20241003 模拟赛
    这场...打得还行吧。(至少没有爆零A.旋律的总数难度:橙签到题。只要第一个都选\(1\),就能保证不同。答案为\(m^{n-1}\)。#include<bits/stdc++.h>#definelllonglong#definemod1000000007usingnamespacestd;intT;lln,m;llquickpow(lla,llb){llre......
  • 10.2 代码源 2024 CSP-S 模拟赛 Day 7
    省流:\(55+5+0+10=70\)简称:唐诗T1第一眼发现在二进制下加法不能进位,然后码了个DP就放那了……DP代码:intS=(1<<14)|1;fd(i,0,r[1])f[1][i]=1;fd(i,2,n){fd(j,0,S){f[i][j]=f[i-1][j];for(ints=j;s;s=(s-1)&j){(f......
  • 10.4 模拟赛(2025 炼石计划 NOIP 模拟赛 #7)
    2025--炼石计划--9月25日--NOIP模拟赛#7【订正】-比赛-梦熊联盟(mna.wang)复盘赢麻了。浏览题。T1没理解“中间节点”是啥意思,样例太大先不模拟了。T2什么东西,密铺?T3好像看懂了题。脑子中瞬间有一个\(n^3\)DP,发现\(n\le200\)感觉切了。但其实DP假的很......