首页 > 其他分享 >NOIP2024 前集训：多校A层冲刺NOIP2024模拟赛26

NOIP2024 前集训：多校A层冲刺NOIP2024模拟赛26

时间：2024-11-26 21:22:06浏览次数：6  
标签：26 unlocked int void 多校 Tp read inline NOIP2024

前言

点击查看代码 
《看得最远的地方》

你是第一个发现我

越面无表情越是心里难过

所以当我不肯落泪地颤抖

你会心疼的抱我在胸口

你比谁都还了解我

内心的渴望比表面来得多

所以当我跌断翅膀的时候

你不扶我但陪我学忍痛

我要去看得最远的地方

和你手舞足蹈聊梦想

像从来没有失过望受过伤

还相信敢飞就有天空那样

我要在看得最远的地方

披第一道曙光在肩膀

被泼过太冷的雨滴和雪花

更坚持微笑要暖得像太阳

你比谁都还了解我

内心的渴望比表面来得多

所以当我跌断翅膀的时候

你不扶我但陪我学忍痛

我要去看得最远的地方

和你手舞足蹈聊梦想

像从来没有失过望受过伤

还相信敢飞就有天空那样

我要在看得最远的地方

披第一道曙光在肩膀

被泼过太冷的雨滴和雪花

更坚持微笑要暖得像太阳

有时候觉得我们很不一样

你能看见我看不到的地方

有时候又觉得我们很像

都爱仰起头不听命运的话

我要去看得最远的地方

和你手舞足蹈聊梦想

像从来没有失过望受过伤

还相信敢飞就有天空那样

我要在看得最远的地方

披第一道曙光在肩膀

被泼过太冷的雨滴和雪花

更坚持微笑要暖得像太阳

今天是拉开座位完全断网并强制使用 windows 打的，用局长 long long time ago 放在 ftp 上的虚拟机，我去不知道为啥那么“好用”，蚌埠煮了。

然后下虚拟机耽误了好长时间……

T1 又放贪心，丫的小样例没过我怎么敢测大样例的？大样例过了？我去那我做法是不是假的为啥小样例过不去……

之后做 T2，因为 T1 没过动不动回去看……

赛后看题解发现 T1 是对的，但我忘记算他连父亲那条边了……

昨天推了首毛不易的歌，所以【数据删除】了，后来发现太唐了不可能写完，就咕着吧，刚才又看了别人的【数据删除】，有点震撼，原谅我过于冷血只感到了震撼，好像这种无法与我的经历引起共鸣的东西，我看了只会感到自卑与同情，原谅我这卑微的一生。

明天还有模拟赛，打了没啥问题，但我后天不想打，想打打板子，不知道能不能商量一下，huge 不是说可以在三场里选一场不打吗？

T1 随机游走

是道贪心，考虑临项交换（好吧我之前不知道这玩意叫这名字），发现 \(x\) 在 \(y\) 前有 \(\dfrac{t_x}{w_x}<\dfrac{t_y}{w_y}\)，按这个排序即可。

点击查看代码 
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
const int N=5e5+10;
template<typename Tp> inline void read(Tp&x)
{
	x=0;register bool z=true;
	register char a=getchar_unlocked();
	for(;!isdigit(a);a=getchar_unlocked()) if(a=='-') z=0;
	for(;isdigit(a);a=getchar_unlocked()) x=(x<<1)+(x<<3)+(a^48);
	x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x){if(x>9)wt(x/10);putchar_unlocked((x%10)+'0');}
template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);}
int n,c[N],w[N],dis[N],sum[N]; ll ans,tim; vector<int>e[N];
inline void dfs1(int x)
{
	dis[x]=c[x],sum[x]=w[x];
	for(int y:e[x]) dfs1(y),dis[x]+=dis[y],sum[x]+=sum[y];
}
inline void dfs2(int x) {ans+=tim*w[x]; for(int y:e[x]) tim+=c[y],dfs2(y);}
signed main()
{
	freopen("walk.in","r",stdin),freopen("walk.out","w",stdout);
	read(n);
	for(int i=2,fa;i<=n;i++) read(fa,c[i]),e[fa].push_back(i);
	for(int i=1;i<=n;i++) read(w[i]);  dfs1(1);
	for(int i=1;i<=n;i++) sort(e[i].begin(),e[i].end(),[&](int x,int y){return 1ll*dis[x]*sum[y]<1ll*dis[y]*sum[x];});
	dfs2(1),write(ans);
}

T2 分发奖励

类似线段树分治到一个节点就把贡献加进去，出来就撤销，但这题本来就在树上所以直接跑就好，用线段树维护最小值个数。

点击查看代码 
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
#define mid (l+r>>1)
#define ls (mid<<1)
#define rs (mid<<1|1)
using namespace std;
const int N=5e5+10;
template<typename Tp> inline void read(Tp&x)
{
	x=0;register bool z=true;
	register char a=getchar_unlocked();
	for(;!isdigit(a);a=getchar_unlocked()) if(a=='-') z=0;
	for(;isdigit(a);a=getchar_unlocked()) x=(x<<1)+(x<<3)+(a^48);
	x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x){if(x>9)wt(x/10);putchar_unlocked((x%10)+'0');}
template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);}
int n,m,tot,in[N],out[N],dep[N],ans[N],sum[N<<1],val[N<<1],add[N<<1];
vector<int>e[N]; set<int>s[N];
inline void dfs(int x)
{in[x]=++tot; for(int y:e[x]) dep[y]=dep[x]+1,dfs(y); out[x]=tot;}
inline void pushup(int p,int l,int r)
{
	if(val[ls]<val[rs]) val[p]=val[ls],sum[p]=sum[ls];
	else if(val[ls]>val[rs]) val[p]=val[rs],sum[p]=sum[rs];
	else val[p]=val[ls],sum[p]=sum[ls]+sum[rs];
}
inline void build(int p,int l,int r)
{
	if(l==r) return sum[p]=1,void();
	build(ls,l,mid),build(rs,mid+1,r),pushup(p,l,r);
}
inline void spread(int p,int l,int r)
{val[ls]+=add[p],add[ls]+=add[p],val[rs]+=add[p],add[rs]+=add[p],add[p]=0;}
inline void change(int p,int l,int r,int vl,int vr,int d)
{
	if(vl<=l&&vr>=r) return val[p]+=d,add[p]+=d,void();
	if(add[p]) spread(p,l,r); if(vl<=mid) change(ls,l,mid,vl,vr,d);
	if(vr>mid) change(rs,mid+1,r,vl,vr,d); pushup(p,l,r);
}
inline void solve(int x)
{
	for(int y:s[x]) change(1,1,n,in[y],out[y],1);
	ans[x]=val[1]?n-1:max(0,n-1-sum[1]); for(int y:e[x]) solve(y);
	for(int y:s[x]) change(1,1,n,in[y],out[y],-1);
}
signed main()
{
	freopen("reward.in","r",stdin),freopen("reward.out","w",stdout);
	read(n,m); for(int i=2,x;i<=n;i++) read(x),e[x].push_back(i);
	dfs(1),build(1,1,n); for(int i=1,x,y;i<=m;i++)
	{
		read(x,y); if(dep[x]>dep[y]) swap(x,y);
		if(in[x]<=in[y]&&out[x]>=in[y]) s[x].insert(x);
		else s[x].insert(x),s[y].insert(y),s[x].insert(y),s[y].insert(x);
	}
	solve(1); for(int i=1;i<=n;i++) write(ans[i]),putchar_unlocked(' ');
}

T3 卡路里

好像比前两题简单，赛时还没看，直接单调栈加二维查分就可以了。

点击查看代码 
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=210,M=5010;
template<typename Tp> inline void read(Tp&x)
{
	x=0;register bool z=true;
	register char a=getchar_unlocked();
	for(;!isdigit(a);a=getchar_unlocked()) if(a=='-') z=0;
	for(;isdigit(a);a=getchar_unlocked()) x=(x<<1)+(x<<3)+(a^48);
	x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x){if(x>9)wt(x/10);putchar_unlocked((x%10)+'0');}
template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);}
int n,m,l[M],r[M],sta[M],a[N][M]; ll ans=-1e9,d[M],sum[M][M];
signed main()
{
	freopen("calorie.in","r",stdin),freopen("calorie.out","w",stdout);
	read(n,m); for(int i=2;i<=m;i++) read(d[i]),d[i]+=d[i-1];
	for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) read(a[j][i]);
	for(int i=1;i<=n;i++)
	{
		sta[0]=0; for(int j=1,top=0;j<=m;j++)
		{
			while(top&&a[i][sta[top]]<=a[i][j]) top--;
			l[j]=sta[top]+1,sta[++top]=j;
		}
		sta[0]=m+1; for(int j=m,top=0;j;j--)
		{
			while(top&&a[i][sta[top]]<a[i][j]) top--;
			r[j]=sta[top]-1,sta[++top]=j;
		}
		for(int j=1;j<=m;j++)
		{
			sum[l[j]][j]+=a[i][j],sum[j+1][r[j]+1]+=a[i][j];
			sum[j+1][j]-=a[i][j],sum[l[j]][r[j]+1]-=a[i][j];
		}
	}
	for(int i=1;i<=m;i++) for(int j=1;j<=m;j++)
		sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
	for(int i=1;i<=m;i++) for(int j=i;j<=m;j++)
		ans=max(ans,sum[i][j]-d[j]+d[i]); write(ans);
}

T4 传话游戏

咕咕咕。

标签：26,unlocked,int,void,多校,Tp,read,inline,NOIP2024
From： https://www.cnblogs.com/Charlieljk/p/18571007

相关文章

  • 2024/11/26 NFLS树上问题笔记
    树现在他想解决这样一个问题：给定一颗有根树（根为1），有以下两种操作：标记操作：对某个结点打上标记（在最开始，只有结点1有标记，其他结点均无标记，而且对于某个结点，可以打多次标记）。询问操作：询问某个结点最近的一个打了标记的祖先（这个结点本身也算自己的祖先）你能帮帮他吗?树剖但是暴力能......
  • 11.26
    100+40+40+20=200。总体上感觉还行，B赛时想了个神秘东西，不过没有实现（事实证明这是正确的选择），但是C不会启发式分裂吃大亏。闲话一个非常重要的问题是在不会手写哈希表的情况下应该使用什么来当作哈希表。\(\text{unordered_map}\)和\(\text{gp_hash_table}\)被卡的概率都......
  • 2024.11.26总结
    本文于github博客同步更新。A：学生大战一个半小时未果，结束前半小时发现是打表找规律。就是分讨一下，首先大于\(1\)的数不能超过两个，若有两个则其中一个必定为\(2\)，然后看一下\(1\)的个数是不是\(3\)的倍数即可。B：拆贡献，分为\(u\rightarrowlca\)和\(lca\rightarrow......
  • [ARC126E] Infinite Operations
    不妨把\(a\)排序。考虑一个特殊情况：\(a_1=a_2=\cdots=a_{n-1}=0\)，\(a_n=x\)。不妨设此时答案为\(F(n,x)\)。可以递归把\(a_2,a_3,\cdots,a_{n}\)全部变为\(\dfrac{x}{n-1}\)，然后全部取相反数后就是相同问题。可以归纳证明\(F(n,x)\)的下界是\(\dfrac{(n-1)x}{2}\)。对......
  • 『模拟赛』多校A层冲刺NOIP2024模拟赛26
    Rank有点唐A.随机游走签。重要的就后两句话。题意由此转化成：到每一个节点时，先后遍历其所有子节点的子树，使得\(\sumt_i\timesw_i\)最小。提前dfs一遍处理出便利完某棵子树所需要的总时间和子树总价值，容易发现对于两个子节点的子树来说，全部遍历完所需总时间是一样的，......
  • 20222326 2024-2025-1 《网络与系统攻防技术》实验五实验报告
    1.实验内容实验具体内容：一、从www.besti.edu.cn、baidu.com、sina.com.cn中选择一个DNS域名进行查询，获取如下信息：DNS注册人及联系方式该域名对应IP地址IP地址注册人及联系方式IP地址所在国家、城市和具体地理位置PS：使用whoisdignslookuptraceroute以及各类......
  • 11.26随笔
    这里是11.26随笔。题目留档：输入一组整型权值，构建哈夫曼树，实现哈夫曼编码，并输出带权路径长度。输入格式:第一行输入叶子结点个数，接着依次输入权值。若叶子数为0或1，则输出error输出格式:输出哈夫曼编码，输出带权路径长度。代码：includeincludeincludeincludetypedefstruct......
  • 11.26
    房屋租赁程序框架图分层模式，当软件比较复杂，需要模式管理1.系统有哪些类（文件）2.明确类与类的调用关系一、HouseView.java-->类【界面】1.显示界面2.接受用户的输入3.调用HouseService完成对房屋信息的各种操作（最重要）二、HouseService.java-->类【业务层】1.响应HouseView的......
  • 226. 翻转二叉树
    问题描述给你一棵二叉树的根节点root，翻转这棵二叉树，并返回其根节点。法一、递归单独递归函数，返回TreeNode*x，x是从当前层开始的逆转后的树的根结点classSolution{public:TreeNode*solve(TreeNode*root){if(root==nullptr){returnnull......
  • 如何使用Yolov5训练使用——航拍无人机视角垃圾数据集检测，26700余张无人机图像，超过4万
    无人机视角垃圾检测，26700余张无人机图像，超过4万标注信息，共3.6GB数据量，可用于环卫快速检查，垃圾快速定位等应用。好的，无人机视角垃圾检测是一个非常实用的应用，可以显著提高环卫工作的效率。以下是一个基于PyTorch的完整代码示例，涵盖了数据加载、模型构建、训练、验证和评估......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99