首页 > 其他分享 >高一上十月上旬日记

高一上十月上旬日记

时间：2024-10-04 08:53:17浏览次数：11  
标签：300010 GCC siz ll optimize 上旬 高一上 pragma 日记

10.1

闲话

做题纪要

10.2

闲话

做题纪要

10.3

闲话

做题纪要

luogu P3241 [HNOI2015] 开店

  • 不难发现两个点在点分树上的 \(\operatorname{LCA}\) 是一个求距离的好的分割点，考虑点分树。

  • 暂且不考虑 \([l,r]\) 的限制，因为只是一个限制范围的查找。

  • 设 \(siz_{x}\) 表示点分树上以 \(x\) 为根的子树大小， \(sum_{0/1,x}\) 表示点分数上以 \(x\) 为根的子树内的所有节点到 \(x\) / \(x\) 在点分树上的父亲节点的距离和。

  • 设当前开店节点为 \(x\) ，在点分树上跳到了 \(rt\) 。

  • 仍考虑枚举 \(\operatorname{LCA}\) ，除去 \(rt\) 方向上的贡献，此时对答案产生的贡献为 \(sum_{0,fa_{rt}}-sum_{1,rt}+(siz_{fa_{rt}}-siz_{rt}) \times dis_{x,fa_{rt}}\) 。

  • 对于年龄 \(\in [l,r]\) 的限制，套一个支持单点插入、区间查询的数据结构即可。

  • 离散化后使用动态开点线段树貌似空间还是会爆炸，又因为没有修改操作，所以使用 vector 代替即可。具体地，原区间查询距离和转化为二分端点后的两个前缀和相减，原查询大小和转化为二分端点后两个端点相减。

    点击查看代码 
    struct node
{
	ll nxt,to,w;
}e[300010];
ll head[300010],a[300010],cnt=0;
void add(ll u,ll v,ll w)
{
	cnt++;
	e[cnt].nxt=head[u];
	e[cnt].to=v;
	e[cnt].w=w;
	head[u]=cnt;
}
struct LCA
{
	ll siz[300010],fa[300010],dep[300010],son[300010],top[300010],dis[300010];
	void init()
	{
		dfs1(1,0);
		dfs2(1,1);
	}
	void dfs1(ll x,ll father)
	{
		siz[x]=1;
		fa[x]=father;
		dep[x]=dep[father]+1;
		for(ll i=head[x];i!=0;i=e[i].nxt)
		{
			if(e[i].to!=father)
			{
				dis[e[i].to]=dis[x]+e[i].w;
				dfs1(e[i].to,x);
				siz[x]+=siz[e[i].to];
				son[x]=(siz[e[i].to]>siz[son[x]])?e[i].to:son[x];
			}
		}
	}
	void dfs2(ll x,ll id)
	{
		top[x]=id;
		if(son[x]!=0)
		{
			dfs2(son[x],id);
			for(ll i=head[x];i!=0;i=e[i].nxt)
			{
				if(e[i].to!=fa[x]&&e[i].to!=son[x])
				{
					dfs2(e[i].to,e[i].to);
				}
			}
		}
	}
	ll lca(ll u,ll v)
	{
		while(top[u]!=top[v])
		{
			if(dep[top[u]]>dep[top[v]])
			{
				u=fa[top[u]];
			}
			else
			{
				v=fa[top[v]];
			}
		}
		return (dep[u]<dep[v])?u:v;
	}
	ll get_dis(ll x,ll y)
	{
		return dis[x]+dis[y]-2*dis[lca(x,y)];
	}
}L;
struct SMT
{
	struct quality
	{
		ll val,sum;
		bool operator < (const quality &another) const
		{
			return val<another.val;
		}
	};
	vector<quality>e[300010];
	void update(ll x,ll val,ll sum)
	{
		e[x].push_back((quality){val,sum});
	}
	void init(ll n)
	{
		for(ll i=1;i<=n;i++)
		{
			sort(e[i].begin(),e[i].end());
			for(ll j=1;j<e[i].size();j++)
			{
				e[i][j].sum+=e[i][j-1].sum;
			}
		}
	}
	ll query_sum(ll x,ll l,ll r)
	{
		l=lower_bound(e[x].begin(),e[x].end(),(quality){l,0})-e[x].begin();
		r=upper_bound(e[x].begin(),e[x].end(),(quality){r,0})-e[x].begin()-1;
		ll ans=0;
		if(0<=r&&r<e[x].size())
		{
			ans+=e[x][r].sum;
		}
		if(0<=l-1&&l-1<e[x].size())
		{
			ans-=e[x][l-1].sum;
		}
		return ans;
	}
	ll query_siz(ll x,ll l,ll r)
	{
		l=lower_bound(e[x].begin(),e[x].end(),(quality){l,0})-e[x].begin();
		r=upper_bound(e[x].begin(),e[x].end(),(quality){r,0})-e[x].begin()-1;
		return r-(l-1);
	}
}T[2];
struct Divide_On_Tree
{
	ll siz[300010],weight[300010],vis[300010],fa[300010],center=0;
	void init(ll n)
	{
		center=0;
		get_center(1,0,n);
		get_siz(center,0);
		build(center);
	}	
	void get_center(ll x,ll fa,ll n)
	{
		siz[x]=1;
		weight[x]=0;
		for(ll i=head[x];i!=0;i=e[i].nxt)
		{
			if(e[i].to!=fa&&vis[e[i].to]==0)
			{
				get_center(e[i].to,x,n);
				siz[x]+=siz[e[i].to];
				weight[x]=max(weight[x],siz[e[i].to]);
			}
		}
		weight[x]=max(weight[x],n-siz[x]);
		if(weight[x]<=n/2)
		{
			center=x;
		}
	}
	void get_siz(ll x,ll fa)
	{
		siz[x]=1;
		for(ll i=head[x];i!=0;i=e[i].nxt)
		{
			if(e[i].to!=fa&&vis[e[i].to]==0)
			{
				get_siz(e[i].to,x);
				siz[x]+=siz[e[i].to];
			}
		}
	}
	void build(ll x)
	{
		vis[x]=1;
		for(ll i=head[x];i!=0;i=e[i].nxt)
		{
			if(vis[e[i].to]==0)
			{
				center=0;
				get_center(e[i].to,x,siz[e[i].to]);
				get_siz(center,0);
				fa[center]=x;
				build(center);
			}
		}
	}
	void update(ll x)
	{
		T[0].update(x,a[x],0);
		for(ll rt=x;fa[rt]!=0;rt=fa[rt])
		{
			T[0].update(fa[rt],a[x],L.get_dis(fa[rt],x));
			T[1].update(rt,a[x],L.get_dis(fa[rt],x));
		}
	}
	ll query(ll x,ll l,ll r)
	{
		ll ans=T[0].query_sum(x,l,r);
		for(ll rt=x;fa[rt]!=0;rt=fa[rt])
		{
			ans+=T[0].query_sum(fa[rt],l,r)-T[1].query_sum(rt,l,r);
			ans+=(T[0].query_siz(fa[rt],l,r)-T[0].query_siz(rt,l,r))*L.get_dis(fa[rt],x);
		}
		return ans;
	}
}D;
int main()
{
	ll n,m,mod,u,v,w,x,l,r,ans=0,i;
	cin>>n>>m>>mod;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(i=1;i<=n-1;i++)
	{
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,w);
	}
	L.init();
	D.init(n);
	for(i=1;i<=n;i++)
	{
		D.update(i);
	}
	T[0].init(n);
	T[1].init(n);
	for(i=1;i<=m;i++)
	{
		cin>>x>>l>>r;
		l=(l+ans)%mod;
		r=(r+ans)%mod;
		if(l>r)
		{
			swap(l,r);
		}
		ans=D.query(x,l,r);
		cout<<ans<<endl;
	}
	return 0;
}

10.4

闲话

做题纪要

luogu P4211 [LNOI2014] LCA

  • 考虑点分树。

  • 对于点分树上经过分治中心 \(x\) 的路径 \(u \to v\) ，\(\operatorname{LCA}(u,v)\) 一定在 \(u \to x\) 或 \(x \to v\) 的路径上。

  • 处理出每个点到分治中心的 \(\operatorname{LCA}\) 做前缀和即可。

    点击查看代码

luogu P3345 [ZJOI2015] 幻想乡战略游戏

luogu P5311 [Ynoi2011] 成都七中

[ABC373F] Knapsack with Diminishing Values

  • 暴力

    • 分组背包写个常数小点的加 \(C++20\) 加手动开 \(O3\) 就过了（赛时直接把火车头粘上了），算下来 \(AT\) 神机能跑 \(1e10\) 。

      点击查看代码 
      #include<bits/stdc++.h>
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
using namespace std;
#define ll long long 
#define ull unsigned long long
#define sort stable_sort 
#define endl '\n'
ll w[3010],v[3010],f[2][3010];
int main()
{
	ll n,m,ans=0,i,j,k;
	cin>>n>>m;
	for(i=1;i<=n;i++)
	{
		cin>>w[i]>>v[i];
	}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			f[i&1][j]=f[(i-1)&1][j];
		}
		for(k=1;k*w[i]<=m;k++)
		{
			for(j=k*w[i];j<=m;j++)
			{
				f[i&1][j]=max(f[i&1][j],f[(i-1)&1][j-k*w[i]]+k*v[i]-k*k);
			}
		}
	}
	for(i=1;i<=m;i++)
	{
		ans=max(ans,f[n&1][i]);
	}
	cout<<ans<<endl;
	return 0;
}

[ABC366G] XOR Neighbors

CF341D Iahub and Xors

标签：300010,GCC,siz,ll,optimize,上旬,高一上,pragma,日记
From： https://www.cnblogs.com/The-Shadow-Dragon/p/18446256

相关文章

  • 【闲话】高一上运动会
    心跳节拍·弥梦离“加油，加油！”虽然没有上场，但记忆也为本次运动会的举办做出了许多努力！想喝矿泉水的话，就请记忆帮你拿一瓶吧！活力四射·超神龙女代表着竞技的绿茵场上，我们的脚步永不停息，少年热血和梦想华章，才刚刚开始。在她指尖的彩球上，炽热的青春有迹可循。“运动会的开幕仪......
  • 2024.10 训练日记
    我们将难度分为\(5\)个等级:\(\color{grey}\bigstar\)简单题，根本不配进入NOI的考场，做着玩玩。或者为模板题。\(\color{green}\bigstar\)签到题，在NOI赛场上强银选手几乎人人都会，如果赛场上不会的话对冲银的影响是非常大的，要避免。\(\color{blue}\bigstar\)中等题，在NOI......
  • 9月30日记录
    完成了一个能够列出30道四则运算的java程序，题目要求：乘法不超过四位数，减法大于零，除法结果为整数；实现可视化界面，并且能够计算得分与计时；点击查看代码importjavax.swing.*;importjava.awt.*;importjava.awt.event.ActionEvent;importjava.awt.event.ActionListener;impo......
  • 嵌入式开发学习日记——第五天（c语言）
    循环控制语句 while循环        基本语法while(循环条件表达式){循环体语句;}        流程图案例——计数循环   实现计数循环要满足：        ①必须初始化循环变量        ②循环变量比较作为循环条件       ......
  • 【日记】这下真要穷得吃不起饭了（1504 字）
    正文忽然想起，昨天有一个财政局的工作人员，过来转款。那时候已经快下班了。我们给他办完之后，他说他没想到这么快。看来还得回去，明明都打算不回去了来着。我有些疑惑。照理来说，财政局应该挺好玩。我这么问他。他苦笑了一下，说要是好玩就回去上班了，天天都不想去单位。然后开......
  • d2l-ai深度学习日记(四)-深度学习计算
    前言:这个博客《d2l-ai深度学习日记》将记录我在深度学习领域的学习与探索，特别是基于《动手学深度学习》这本经典教材的学习过程。在这个过程中，我不仅希望总结所学，还希望通过分享心得，与志同道合的朋友一起交流成长。这不仅是对知识的沉淀，也是我备战研究生考试、追逐学术进阶之......
  • d2l-ai深度学习日记(三)-多层感知机
     前言:这个博客《d2l-ai深度学习日记》将记录我在深度学习领域的学习与探索，特别是基于《动手学深度学习》这本经典教材的学习过程。在这个过程中，我不仅希望总结所学，还希望通过分享心得，与志同道合的朋友一起交流成长。这不仅是对知识的沉淀，也是我备战研究生考试、追逐学术进阶......
  • 9月28日记录
    一个管理流水线的MES系统的java实现：代码如下：点击查看代码importjava.util.Scanner;importjava.util.Objects;publicclassPlanInformation{privatestaticintcounter=0;//用于ID递增privateintid;privateStringplanid;privateStringp......
  • 演化日记：从数据仓库到数据中台与文娱业的数据飞轮
    在文娱行业，每一帧画面、每一段音符都埋藏着用户偏好的密码。解锁这些密码并非易事，但借助数据技术的演化，我们终于可以高效地挖掘这些珍贵信息，推动业务的革新和增长。本文将探讨数据技术如何从简单的数据仓库演变为强大的数据飞轮，并具体说明这一进程如何在文娱行业具体应用。数据技术......
  • 【日记】苟命要紧（1118 字）
    正文今天把假请到了，而且前后没有超过1个小时，十分诧异。就我们行现在的人手分配来看，一旦我有点事情，好像还找不到人代班……巨搞。下午上班，左边胸部有点不舒服。回想一下心功能不全最接近的症状，应该是稳定型心绞痛……但就心绞痛的程度而言，是不是有点太轻微了……而......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99