首页 > 其他分享 >合集:NJPC2017

合集:NJPC2017

时间:2023-09-24 21:55:36浏览次数:71  
标签:const int MAX fa static inline NJPC2017 合集

太长了不放缺省源了,代码都只有主程序部分,不知道这个风格怎么样。

个人认为难度顺序:A < B < C < E < F < H < D < G。

A 入力フォーム/洛谷/AT

对 \(L\) 和 \(|S|\) 取较小值,输出前这些位即可,复杂度 \(\mathcal O(\min(L,|S|))\)。

namespace LgxTpre
{
    static const int MAX=500010;
    static const int inf=2147483647;
    static const int INF=4557430888798830399;
    
	int n,m;
	char s[MAX];
	
    inline void lmy_forever()
    {
    	scanf("%lld%s",&n,s+1),m=strlen(s+1);
    	for(int i=1;i<=min(n,m);++i) putchar(s[i]);
    	return puts(""),void();
	}
}

B 格子グラフ/洛谷/AT

如果一个 x 都没有,那么答案为 \(H \times (W - 1) + W \times (H - 1)\)。当加入一个 x 时,它会使四周合法的边被标记,合法指的是指向的点存在且未被标记过。可以通过 map 来存储坐标查询点之前是否被标记过,复杂度 \(\mathcal O(n \log n)\)。

namespace LgxTpre
{
    static const int MAX=0010;
    static const int inf=2147483647;
    static const int INF=4557430888798830399;
    
	int n,m,k,x,y,ans;
	map<pii,bool> v;
	constexpr int dx[]={0,0,1,-1};
	constexpr int dy[]={1,-1,0,0};
	
    inline void lmy_forever()
    {
    	read(n,m,k),ans=n*(m-1)+m*(n-1);
    	auto ok=[&](int x,int y)->bool{return x>=1&&x<=n&&y>=1&&y<=m&&v.find(mp(x,y))==v.end();};
    	for(int i=1;i<=k;++i) {read(x,y),v[mp(x,y)]=1; for(int j=0;j<4;++j) ans-=ok(x+dx[j],y+dy[j]);}
		write(ans,'\n');
	}
}

C ハードル走/洛谷/AT

类似于 CF1873D,当遇到一个跨栏时是必须要跳的,维护当前所在的位置,然后再向后跳 \(L\) 的距离看会不会到下一个跨栏,贪心加单指针暴力后跳即可。复杂度 \(\mathcal O(n)\)。

namespace LgxTpre
{
    static const int MAX=100010;
    static const int inf=2147483647;
    static const int INF=4557430888798830399;
    
    int n,L,a[MAX],now;
	
    inline void lmy_forever()
    {
    	read(n,L);
    	for(int i=1;i<=n;++i) read(a[i]);
    	int i=1;
    	while(i<=n)
    	{
    		int j=i;
    		while(j<n&&a[j+1]<L+a[i]) ++j;
    		cmax(now,now+L,a[j]),now+=L,i=j+1;
    		if(i<=n&&a[i]<=now) return puts("NO"),void();
		}
		puts("YES");
	}
}

D NMパズル/洛谷/AT

根本想不到啊,感觉挺神秘的。首先我们让行上能够拥有的逆序对数尽可能多,即如果 \(n > m\),就交换 \(n,m\),最后输出再换过来就好了。一个矩阵最多能拥有的逆序对数为 \(A = \dfrac{n \times m \times (m - 1)}{2} + \dfrac{m \times n \times (n - 1)}{2}\),注意到此时行上贡献的逆序对数一定是大于等于 \(\dfrac{A}{2}\) 的。如果 \(k \leq \dfrac{A}{2}\),那么初始矩阵从左到右从上到下从小到大的填数,此时逆序对数为 \(0\);否则从大到小的填数,此时逆序对数为 \(A\)。此时就不需要考虑列上的贡献,只需要对每一行分别操作。按照冒泡排序的操作顺序,前者每次可以增加一个逆序对,后者则是每次减少一个。这一部分暴力构造即可,视 \(n,m\) 同阶,复杂度是 \(\mathcal O(n^3)\) 的。

namespace LgxTpre
{
    static const int MAX=110;
    static const int inf=2147483647;
    static const int INF=4557430888798830399;
    
    int n,m,K,fl,all;
    int a[MAX][MAX];
	
    inline void lmy_forever()
    {
    	read(n,m,K),all=n*m*(m-1)/2+m*n*(n-1)/2;
    	if(n>m) Swp(n,m),fl=1;
    	if(K<=all/2) for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) a[i][j]=(i-1)*m+j;
		if(K>all/2) {for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) a[i][j]=n*m-((i-1)*m+j)+1; K=all-K;}
		for(int i=1;K&&i<=n;++i) for(int j=m-1;K&&j;--j) for(int k=1;K&&k<=j;++k) --K,Swp(a[i][k],a[i][k+1]);
		if(!fl) for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) write(a[i][j],j==m?'\n':' ');
		if(fl)  for(int i=1;i<=m;++i) for(int j=1;j<=n;++j) write(a[j][i],j==n?'\n':' ');
	}
}

E 限界集落/洛谷/AT

树形 DP 杂糅题。根据直径定理,一棵无根树以任意节点为根,最长根链一定取自任意一条直径的两个端点之一。可以直接两遍 dfs 求出一条直径的两个端点,然后倍增暴力求出以每个节点为根的最长根链长度。剩下的部分是 CF219D,先一次 dfs 求出以 \(1\) 为根有哪些边需要翻转;再一遍 dfs 根据子树大小计算以其它节点为根的答案。最后对所有合法情况取最小值即可。复杂度 \(\mathcal O(n \log n)\),瓶颈在于树上倍增求两点间距离,不过换根 DP 也能求出以每个节点为根的最长根链,这样就是 \(\mathcal O(n)\) 的了。

namespace LgxTpre
{
    static const int MAX=100010;
    static const int inf=2147483647;
    static const int INF=4557430888798830399;
    
    int n,d,ans,A,B,x,y,z;
    int f[MAX],fa[MAX][20],tag[MAX];
    int dep[MAX],dis[MAX],dps;
    vector<pair<pii,int>> G[MAX];
    #define to it.fi
    #define val it.se
	
    inline void lmy_forever()
    {
    	read(n,d),ans=INF;
    	for(int i=1;i<n;++i) read(x,y,z),G[x].eb(mp(mp(y,z),0)),G[y].eb(mp(mp(x,z),1));
    	
    	auto GetDiameter=[&](auto GetDiameter,int now,int father)->void
    	{
    		if(dep[now]>dep[dps]) dps=now;
    		for(auto [it,tow]:G[now]) if(to!=father) dep[to]=dep[now]+val,GetDiameter(GetDiameter,to,now);
		};
		GetDiameter(GetDiameter,1,0),A=dps,GetDiameter(GetDiameter,dps,0),B=dps;
		
		auto dfs1=[&](auto dfs1,int now,int father)->void
		{
			fa[now][0]=father,dep[now]=dep[father]+1;
			for(int i=1;i<=__lg(dep[now]);++i) fa[now][i]=fa[fa[now][i-1]][i-1];
			for(auto [it,tow]:G[now]) if(to!=father) dis[to]=dis[now]+val,dfs1(dfs1,to,now),tag[to]=!tow;
		};
		dfs1(dfs1,1,0); for(int i=1;i<=n;++i) f[1]+=tag[i];
		
		auto dfs2=[&](auto dfs2,int now,int father)->void
		{
			for(auto [it,tow]:G[now]) if(to!=father) f[to]=f[now]+(tow?1:-1),dfs2(dfs2,to,now);
		};
		dfs2(dfs2,1,0);
		
		auto LongestChain=[&](int p)->int
		{
			auto LCA=[&](int x,int y)->int
			{
				if(dep[x]<dep[y]) Swp(x,y);
        		while(dep[x]>dep[y]) x=fa[x][__lg(dep[x]-dep[y])];
        		if(x==y) return x;
        		for(int i=__lg(dep[x]);~i;--i) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
        		return fa[x][0];
			};
			
			int lcaA=LCA(A,p),lcaB=LCA(B,p);
			return max(dis[A]+dis[p]-dis[lcaA]*2,dis[B]+dis[p]-dis[lcaB]*2);
		};
		for(int i=1;i<=n;++i) if(LongestChain(i)<=d) cmin(ans,f[i]);
		
		write(ans==INF?-1:ans,'\n');
	}
}

F ダブルス/洛谷/AT

求极值,先二分答案转成判定性问题。一个非常经典的思路是如果能够完成 \(X_{i + 1}\) 上的操作,那么必然有一个点在 \(X_{i}\) 上,于是只需要考虑如何刻画另一个人所在的位置。不妨记完成 \(X_{i + 1}\) 的人为 \(P\),另一个人为 \(Q\)。因为每个时刻 \(Q\) 可以往两个方向走,所以容易发现 \(Q\) 可以存在的位置是一个区间,那么起初是 \(L = R = 0\)。记当前二分出的速度为 \(V\),从当前球过来的时刻到下一个球过来的时刻为 \(t = T_{i + 1} - T_{i}\),那么这段时间可以走 \(S = Vt\) 的路程,于是 \(P\) 可以到达 \([X_i - S,X_i + S]\),\(Q\) 可以到达 \([L - S,R + S]\)。如果这两个区间都不能包含 \(X_{i + 1}\),那么说明到不了了,返回无解。如果 \(P\) 能到达,\(Q\) 不能到达,那么 \(Q\) 就可以接着行走,下一个时刻 \(Q\) 可以出现的区间扩展为 \(L = L - S,R = R + S\)。如果 \(Q\) 能到达,\(P\) 不能到达,那么两个人的身份就要互换了,新的 \(Q\) 的区间变为了 \(L = X_i - S,R = X_i + S\)。如果两者都能到达,那么 \(L\) 和 \(R\) 的取值对上面两种情况分别贪心的取最值即可。要做实数域上的二分,check 是 \(\mathcal O(n)\) 的,于是复杂度为 \(\mathcal O(n \log V)\)。

namespace LgxTpre
{
    static const int MAX=100010;
    static const int inf=2147483647;
    static const int INF=4557430888798830399;
    
    int n,T[MAX],X[MAX];
    double l,r,mid;
    constexpr double eps=1e-9;
	
    inline void lmy_forever()
    {
    	read(n),l=0.0,r=1e7;
    	for(int i=1;i<=n;++i) read(T[i],X[i]);
    	auto check=[&](double V)->bool
    	{
    		double L=0,R=0;
    		for(int i=0;i<n;++i)
    		{
    			double s=V*((double)(T[i+1]-T[i]));
    			bool bet=(i&&fabs(X[i+1]-X[i])<=s+eps),nbet=(L-s<=X[i+1]+eps&&X[i+1]-eps<=R+s);
    			if(!bet&&!nbet) return 0;
    			if(bet&&!nbet) L-=s,R+=s;
    			if(!bet&&nbet) L=X[i]-s,R=X[i]+s;
    			if(bet&&nbet) L=min(L-s,X[i]-s),R=max(R+s,X[i]+s);
			}
			return 1;
		};
    	while(l+eps<r) {mid=(l+r)/2.0; if(check(mid)) r=mid; else l=mid;}
    	printf("%.9lf\n",r);
	}
}

G 交換法則/洛谷/AT

考虑什么样的串能够进行重构得到。假设说我们的串 \(S = a \cdots\cdots\),那么操作 \(a @ S_2 @ S_3 @ \cdots @ S_n\) 就有可能重构出 \(S\) 串。如果我们的串 \(S = \cdots a \cdots\),那么有两种操作:对以 \(a\) 开头的字符串和由 \(a\) 以外的字符串进行 \(@\) 操作,得到一个以 \(a\) 开头的字符串;对 \(a\) 和由 \(a\) 以外的字符串进行 \(@\) 操作,得到的还是一个以 \(a\) 开头的字符串。由此可知,上面那种情形无论如何都不能由重构得到。由此可以推广到,如果 \(c\) 是序列中最小的字符,\(S\) 是任意字符串,那么我们无法构造出 \(Sc\),证明是因为 \(c\) 是除了空序列之外字典序最小的串。将给定的串翻转,维护一个栈的结构,倒序考虑每一个字符。如果当前考虑到的字符字典序要小于栈顶那么就将其和栈顶合并。这样反复操作,如果最后栈中剩余多于一个字符串,那么无解,否则必定存在方法进行构造。

namespace LgxTpre
{
    static const int MAX=100010;
    static const int inf=2147483647;
    static const int INF=4557430888798830399;
    
    string s;
    vector<string> v;
	
    inline void lmy_forever()
    {
    	cin>>s,reverse(s.begin(),s.end());
    	for(auto c:s)
    	{
    		v.eb((string)""+c);
    		while(v.size()>1)
    		{
    			int n=v.size();
    			if(v[n-1]<=v[n-2]) v[n-2]=v[n-1]+v[n-2],v.pb(); else break;
			}
		}
		puts(v.size()>1?"No":"Yes");
	}
}

H 白黒ツリー/洛谷/AT

注意到子树颜色翻转是假的,因为边由两个端点的颜色异同性来决定,两个端点同时翻转并不会有影响,改变的只有翻转的那一个节点和它父亲间的边。有 LCT 惯用的套路,将边重编号建成点,衔接在原树上的两个端点。可以一遍 dfs 知道每条边的两个端点的颜色异同性,并完成对边重编号的工作。对于颜色相同的,即不合法的边,将其在 LCT 上的点权设为 \(1\)。于是翻转子树操作变成了 LCT 单点取反,注意要先将边在 LCT 上对应的点 makeroot 一下再修改。对于路径信息直接 split 出来查询路径上最大值是否为 \(1\) 即可。复杂度 \(\mathcal O(n \log n)\)。

namespace LgxTpre
{
    static const int MAX=200010;
    static const int inf=2147483647;
    static const int INF=4557430888798830399;
    
    int n,q,N,op,u,v;
	int p[MAX],col[MAX],id[MAX];
    vector<int> G[MAX];
    
    namespace Link_Cat_Tree
    {
    	int fa[MAX],ch[MAX][2],rev[MAX],siz[MAX],val[MAX],mix[MAX];
    	inline bool get(int i)      {return ch[fa[i]][1]==i;}
    	inline bool noroot(int i)   {return ch[fa[i]][get(i)]==i;}
    	inline void pushup(int i)   {siz[i]=siz[ch[i][0]]+siz[ch[i][1]]+1,mix[i]=max({mix[ch[i][0]],mix[ch[i][1]],val[i]});}
    	inline void down(int i)     {if(!i) return; rev[i]^=1,Swp(ch[i][0],ch[i][1]);}
    	inline void pushdown(int i) {if(rev[i]) down(ch[i][0]),down(ch[i][1]),rev[i]=0;}
    	inline void pushall(int i)  {if(noroot(i)) pushall(fa[i]); pushdown(i);}
    	inline void rotate(int x)
    	{
    		int y=fa[x],z=fa[y]; bool k1=get(x),k2=get(y);
    		if(noroot(y)) ch[z][k2]=x;
			fa[x]=z;
    		ch[y][k1]=ch[x][!k1],fa[ch[x][!k1]]=y;
    		ch[x][!k1]=y,fa[y]=x;
    		pushup(y),pushup(x);
		}
		inline void splay(int x)
		{
			pushall(x);
			while(noroot(x))
			{
				int y=fa[x];
				if(noroot(y)) (get(x)^get(y))?rotate(x):rotate(y);
				rotate(x);
			}
		}
		inline void access(int x)      {for(int y=0;x;y=x,x=fa[x]) splay(x),ch[x][1]=y,pushup(x);}
		inline void makeroot(int x)    {access(x),splay(x),down(x);}
		inline int  findroot(int x)    {access(x),splay(x); while(ch[x][0]) pushdown(x),x=ch[x][0]; return splay(x),x;}
		inline void split(int x,int y) {makeroot(x),access(y),splay(y);}
		inline void link(int x,int y)  {makeroot(x); if(findroot(y)!=x) fa[x]=y;}
		inline void cut (int x,int y)  {makeroot(x); if(findroot(y)==x&&fa[y]==x&&!ch[y][0]) fa[y]=ch[x][1]=0,pushup(x);}
	}
	using namespace Link_Cat_Tree;
	
    inline void lmy_forever()
    {
    	read(n),iota(siz+1,siz+2*n+1,1),N=n;
    	for(int i=2;i<=n;++i) read(p[i]),G[p[i]].eb(i);
    	for(int i=1;i<=n;++i) read(col[i]);
    	
    	auto dfs=[&](auto dfs,int now)->void
    	{
    		for(auto to:G[now]) id[to]=++N,link(now,N),link(N,to),val[N]=mix[N]=(col[now]==col[to]),dfs(dfs,to);
		};
		dfs(dfs,1);
		
		read(q);
		for(int i=1;i<=q;++i)
		{
			read(op);
			if(op==1) read(u),(u!=1?(makeroot(id[u]),val[id[u]]=1-val[id[u]],1):1);
			if(op==2) read(u,v),split(u,v),puts(mix[v]==1?"NO":"YES");
		}
	}
}

标签:const,int,MAX,fa,static,inline,NJPC2017,合集
From: https://www.cnblogs.com/LittleTwoawa/p/17726418.html

相关文章

  • 状压DP合集
    目录2023百度之星初赛三-1石碑文[ABC318-]2023百度之星初赛三-1石碑文[ABC318-]......
  • 最短路基础实现方法模板合集
    $\color{#39c588}{关于最短路}$$\color{purple}{首先是最短路的算法选择思路捏,直接来个Y总的图}$++$\color{purple}{单源汇问题}$++$\color{orange}{朴素版Dijkstra}$实现思路//朴素版Dijkstrao(n^2)--处理稠密图--稠密图用邻接矩阵存储//1.初始化邻接......
  • 【专题】2022年中国跨境电商行业研究报告PDF合集分享(附原数据表)
    报告链接:http://tecdat.cn/?p=32044近年来,我国的跨境电子商务发展迅速,在过去五年中,其贸易额增长率达到了16.2%,已经成为稳定对外贸易的一支重要力量。阅读原文,获取专题报告合集全文,解锁文末52份跨境电商行业相关报告。一方面,随着跨境电子商务的发展,跨境电子商务的监管政策得到了......
  • 【题解】CF1817 合集
    CF1817AAlmostIncreasingSubsequence考虑几乎上升的序列的长度,就是我们的区间长度减去\(a_{i-2}\geqa_{i-1}\geqa_i\)的对数,然后维护即可,当然个人感觉自己的代码有点长,可以考虑看洛谷题解代码code:#include<bits/stdc++.h>usingnamespacestd;constintNN=2e5+......
  • 星臾计划 | 第六期优秀实习生访谈合集
    此处划重点:优秀实习生评比活动将每三个月进行一次,获评同学可获得优秀实习生证书和丰厚的奖励——是心动的感觉!作为实习生培养计划,星臾计划不但能帮助在校生提前了解企业、熟悉工作环境,还能提前锁定正式Offer。从今年起,DolphinDB各校招岗优先考虑有DolphinDB实习经历的同学,如......
  • CPU/内存/磁盘/网络/redis/MQ测试工具合集
    闲余时间为大家整理了CPU性能测试、内存带宽测试、内存延迟测试、磁盘IOPS测试、网络测试、数据库测试、Kafka/rabbitMQ性能测试工具合集,后续也会对工具进行简单使用说明。序号工具名称监控策略及内容1UnixBench-5.1.4CPU性能测试2stream内......
  • 【专题】2023年中国奢侈品市场数字化趋势洞察报告PDF合集分享(附原数据表)
    原文链接:https://tecdat.cn/?p=33672原文出处:拓端数据部落公众号2022年,中国的奢侈品消费市场一直处于不断变化和挑战之中,但随着2023年的到来,中国正在全面复苏,市场也充满了机遇和想象空间。自2019年以来,奢侈品品牌一直在中国尝试本地化和数字化策略,将中国的奢侈品消费者与国内市......
  • 【专题】2022年中国跨境电商行业研究报告PDF合集分享(附原数据表)
    报告链接:http://tecdat.cn/?p=32044近年来,我国的跨境电子商务发展迅速,在过去五年中,其贸易额增长率达到了16.2%,已经成为稳定对外贸易的一支重要力量。阅读原文,获取专题报告合集全文,解锁文末52份跨境电商行业相关报告。一方面,随着跨境电子商务的发展,跨境电子商务的监管政策得到了......
  • 软件开发中的资料整理与归档,软件产品开发文档合集
    [引言]本文旨在提供一份标准的软件开发文档模板,以便记录软件开发的全过程。该模板适用于各种类型的软件开发项目,包括Web应用程序、移动应用程序和桌面应用程序等。本文档将介绍软件开发的引言、概述、需求分析、设计、测试、维护以及总结等方面,帮助您撰写一份完整、清晰且易于理......
  • codeforces图论合集
    CyclicOperations给定一个数组$a$,每次构造一个数组$\spacel\space$长度为$\spacek\space$,数组$\spacea\space$与$\spacel\space$转换关系如下:$a_{l_1}\tol_2\space,\spacea_{l_2}\tol_3\space,\spacea_{l_3}\tol_4\space,\space...\space,\spacea_{l_n}\tol_1$......