首页 > 其他分享 >【题解】暑假集训CSP提高模拟14

【题解】暑假集训CSP提高模拟14

时间:2024-08-06 19:27:22浏览次数:15  
标签:ri 14 int 题解 CSP que 游戏币 节点 define

目录

Rank&挂分

image
T4暴搜后来改了记搜,不知道哪里锅了,挂5pts。

A. BA

题目内容

现在有 \(m\) 块烙板,\(n\) 张饼,第 \(i\) 张饼需要烙 \(a_i\) 个单位时间,一张饼一个单位时刻只能在一张烙板上,问都烙熟所需最少时间。

部分分

10pts

暴力深搜,每次枚举在锅里放什么饼,然后在所有合法方案里找最优解。

10+20pts

对Subtask 2进行特判,由于饼只有一面或两面,所以优先处理两面一定更优,配合前面的10分,可以拿下30分。

正解

思路

首先由于一张饼在同一时间只能出现在一口锅里的限制(以下简称时间冲突),可知答案的下界是所有 \(a_i\) 的 \(max\)。
image
从上图可以看出,如果耗时最长的饼都不会发生时间冲突,则一定存在一种方案使得没有饼会产生时间冲突。不考虑时间冲突的因素,那么只要保证 \(m\times t\ge\sum\limits^{n}_{i=1}a_i\) 即可。这里的处理既可以二分,也可以直接求。

代码

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ri register int
#define inf 0x3f3f3f3f
int a,b;
long long sm,ans,mx,c;
int main()
{
	scanf("%d%d",&a,&b);
	for(ri i=1;i<=a;i++)
	{
		scanf("%lld",&c);
		mx=max(mx,c);
		sm+=c;
	}
	ans=sm/b;
	if(sm%b)
	{
		ans++;
	}
	ans=max(ans,mx);
	printf("%lld",ans);
	return 0;
}

B. BB

题目内容

洛谷原题
\(n\) 个节点的有根树,其中 \(1\) 号节点为根,每个节点都有一个价格为 \(w\)。
对于树上两个不同的节点 \(x,y\),若 \(x\) 是 \(y\) 的祖先节点,则称 \(x\) 支配 \(y\)。
游戏过程中,A 和 B 轮流购买树上的一个未被人购买过的节点,直到树上的 \(n\) 个节点都被 A 或 B 购买。(游戏开始前,树上的所有节点都没有被购买。)
对于一次购买,假设买方购买了 \(x\) 号节点,那么他首先要向系统支付 \(w_x\) 个游戏币。假设此时 \(x\) 支配着 \(n_1\) 个已被买方的对手购买了的节点,同时又被 \(n_2\) 个已被对手购买了的节点支配。若 \(n_1\gt n_2\),那么对手要向买方支付 \(n_1-n_2\) 个游戏币,若 \(n_1\lt n_2\),那么买方要向对手支付 \(n_2-n_1\) 个游戏币。
A 和 B 都绝顶聪明,会在游戏中采用最优策略,来赚到尽量多的游戏币。如果 A 先手,A 最终能赚到多少个游戏币?(你可以认为,游戏开始前,A 和 B 手中都有足够数量的游戏币。注意:答案可能为负数。)

部分分

5pts

树剖,不知道哪里锅了,WA,但是没TLE。

正解

思路

设 A 选择的点的点集为 U,B 选择的点的点集为 V。考虑一个点 \(n\) 对 A 的收益的贡献:如果 n 祖先有 \(p\) 个属于 V 的点,则选 \(n\) 会使 A 的收益减少 \(p\);如果 n 儿子有 \(q\) 个属于 V 的点,则选 \(n\) 会使 A 的收益增加 \(q\);总收益就是 \(q-p\)。关于这个可以对在选 \(n\) 前和选 \(n\) 后进行分讨来理解。
但是仅仅转化到此还是不好维护,我们从点集里所有的点的角度去考虑:
image
如果我们直接把祖先数和儿子数作为贡献,显然,同色的在计算时多计算的一部分会相互抵消。这个还是感性理解吧。
于是,一个点的权值被转化为儿子数减祖先数再减它本身的权值。儿子数可以类比树剖的 \(siz_x-1\) 计算,祖先数就是深度 \(dep_x-1\),两个 \(-1\) 抵消,最终的式子是 \(siz_x-dep_x-w_x\),然后贪心即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ri register int
#define inf 0x3f3f3f3f
int a,b[200002],fa[200002],f[200002],g,dep[200002],siz[200002];
priority_queue<int>que;
long long ans;
struct node
{
	int h,to;
}pic[200002];
il void ndin(int x,int y)
{
	g++;
	pic[g].to=y;
	pic[g].h=f[x];
	f[x]=g;
}
void dfs(int x)
{
	siz[x]=1;
	dep[x]=dep[fa[x]]+1;
	for(ri i=f[x];i;i=pic[i].h)
	{
		ri y=pic[i].to;
		if(y!=fa[x])
		{
			dfs(y);
			siz[x]+=siz[y];
		}
	}
}
int main()
{
	scanf("%d",&a);
	for(ri i=1;i<=a;i++)
	{
		scanf("%d",&b[i]);
	}
	for(ri i=2;i<=a;i++)
	{
		scanf("%d",&fa[i]);
		ndin(fa[i],i);
	}
	dfs(1);
	for(ri i=1;i<=a;i++)
	{
		que.push(siz[i]-dep[i]-b[i]);
	}
	while(que.size()>1)
	{
		ans+=que.top();
		que.pop();
		que.pop();
	}
	if(que.size())
	{
		ans+=que.top();
		que.pop();
	}
	printf("%lld",ans);
	return 0;
}

C. BC

->to be continue.

D. BD

->to be contniue.

标签:ri,14,int,题解,CSP,que,游戏币,节点,define
From: https://www.cnblogs.com/ywhhdjser-97/p/18345153

相关文章

  • CSP14
    暴力最高\(50\)吧,本地测试不太准跑得快的只得了\(10\)分,慢的却得了\(50\)分暴力#include<bits/stdc++.h>#definepbpush_back#definelllonglong#definebsbitset<70>#definespeed()ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);usingnamespacestd;con......
  • 暑假集训CSP提高模拟14
    刚放假回来,好困……赛时rank38,T1100,T20,T30,T40打了T1后迷迷糊糊,半睡不睡的。这还能抢一个T1首切?T1BA烙饼问题。答案是\(\max(\max(a_i),\left\lceil\frac{\sum_{i=1}^na_i}{\min(n,m)}\right\rceil)\)还有一个二分答案的做法。但我们好像没有人写……点此查看......
  • 2024MX-MF-DAY1-text题解
    T1【题目描述】有\(n\)个人按编号从\(1\)到\(n\)坐成一圈,即第\(i\in[1,n]\)个人右边是\(i+1\),第\(n\)个人右边的人是\(1\)。初始,每个人手上有\(m\)个球。随后,\(n\)个人按编号从小到大的顺序依次执行如下操作:把自己手中的球分成数量相同且尽可能多的三份,......
  • AkSoundSeedAir.dll修复指南:游戏音频问题解决与预防技巧
    AkSoundSeedAir.dll是一个与声音引擎相关的动态链接库(DynamicLinkLibrary,简称DLL)文件,尤其与Wwise(AudiokineticWwise)声音设计和游戏音效中间件有关。Wwise是一个广泛应用于游戏开发的声音引擎,用于处理游戏中的音频和音效,AkSoundSeedAir.dll就是Wwise的一部分,用于实现声音处理......
  • 花园改造 题解
    题目id:9989题目描述小\(X\)开始改造她的环形的花园了,具体来说她要在花园的环上种满\(n\)棵树。她现在有\(3\)种树:种子、小树苗和大树。每个位置上种不同的树会产生不同的满意度,具体来说在第\(i\)个位置,种种子会产生\(a_i\)的满意度,种小树苗会产生\(b_i\)的满意度,种大树会产生\(c......
  • 『模拟赛』暑假集训CSP提高模拟14
    Rank题目泰国尼添所以暴力挂一点分也能拿到22/98A.BA签到题。总记得小时候在《冒险岛数学奇遇记》的第28册左右看到过这道题,关键在于你可以分次烙完一张饼。举例2口锅5张饼,54433,最优策略的一种是先将5的那张饼烙3单位时间,然后烙一张4一张3;另一口锅......
  • [AGC005B] Minimum Sum 题解
    题目传送门看到这道题很多人用单调栈,其实用笛卡尔树本质差不多,但是思维难度更小。不知道笛卡尔树的同学可以看这里简单说来,笛卡尔树的一个子树可以代表一个区间,且左子树上点的下标小于根节点,右子树上点的坐标大于根节点。这道题要求所有子区间的\(\texttt{min}\)值之和,其实......
  • Mac开发基础14-NSTextView(二)
    进阶使用和技巧1.扩展查找和替换功能可以自定义查找和替换功能,包括高亮查找结果、批量替换等。查找并高亮Objective-C-(void)highlightOccurrencesOfString:(NSString*)searchString{//清除之前的高亮效果[textView.layoutManagerremoveTemporaryAttribute:N......
  • 迟钝的舞会 题解
    题目id:1329题目描述牛是公认的笨拙的舞者。然后,约翰发现富有音乐细胞的母牛能产更多的奶。因此,他把他的整圈的牛都拉进了舞蹈培训班,包括所有的公牛(因为跳舞的时候得一男一女-_-)。这些牛正好有\(n\)头是公的,有\(n\)头是母的。在第一堂课开始之前,舞蹈老师想将他们分成一对一对的(......
  • 14. a+aa+...=sum
    题目:求s=a+aa+aaa+aaaa+aa...a的值,其中a是一个数字。例如2+22+222+2222+22222(此时共有5个数相加),几个数相加有键盘控制。代码:#include<stdio.h>#include<stdlib.h>voidtest(){intsum=0;inta;inttemp;intn;scanf("%d%d",&a,&......