526互联

test1007

发布时间 2023-10-08 09:30:36作者: Diavolo-Kuang

写在前面的话

不好评价这场比赛。。。

\(T1\)

简要题意

现在有两个点 \(P(x_1,y_1),Q(x_2,y_2)\) 以及一条直线 \(y=k\) 。

现在姬子要从 \(P\) 经过直线 \(y=k\) 之后去找位于 \(Q\) 的Kiana ，问最短路径长度？

思路点拨

这个问题就是将军饮马问题，不会可以看初中数学书去。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int k,x,y,x2,y2;
signed main(){
	cin>>k>>x>>y>>x2>>y2;
	if(y>y2){
		swap(x,x2);
		swap(y,y2);
	}
	if(k<y||k>y2) y=2*k-y;
	cout<<(x-x2)*(x-x2)+(y-y2)*(y-y2);
	return 0;
}

\(T2\)

简要题意

有 \(n\) 个不相交的靶子，对于第 \(i\) 个靶子，位于区间 \([l_i,r_i]\) ，并且 \([x_i,y_i]\) 的部分是红色的。保证 \(l_i \leqslant x_i \leqslant y_i \leqslant r_i\) 。

Kiana会以此 \(k\) 此打靶。第 \(i\) 此命中 \(p_i\) 处。每一次，你需要进行如下判断：

  • 如果没有命中靶子，输出 Failed 。
  • 如果命中了曾经命中的靶子，输出 Again 。
  • 如果第一次命中一个靶子但是没有命中红色部分，输出 Normal 。
  • 如果第一次命中一个靶子并且命中了红色部分，输出 Perfect 。

思路点拨

因为靶子之间是不想交的，所以每一次最多击中一个靶子。

我们可以将全部的靶子按照端点从小到大排序，每一次二分 \(p_i\) 位于那个靶子之后进行判断。

时间复杂度 \(O(n \log n)\) 。

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-f;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
const int MAXN=1e5+10;
int n,m,k;
struct node{
	int l,r,x,y;
	bool friend operator<(const node &A,const node &B){
		return A.l<B.l;
	}
}a[MAXN];
bool vis[MAXN];
signed main(){
	n=read(),m=read(),k=read();
	for(int i=1;i<=n;i++)
		a[i].l=read(),a[i].x=read(),a[i].y=read(),a[i].r=read();
	sort(a+1,a+n+1);
	for(int i=1;i<=k;i++){
		int x=read();
		int l=1,r=n;
		while(l<r){
			int mid=(l+r)>>1;
			if(a[mid].r>=x) r=mid;
			else l=mid+1;
		}
		if(a[l].l<=x&&x<=a[l].r){
			if(vis[l]) printf("Again\n");
			else{
				vis[l]=1;
				if(a[l].x<=x&&x<=a[l].y)
					printf("Perfect\n");
				else printf("Normal\n");
			}
		}
		else printf("Failed\n");
	}
	return 0;
}

\(T3\)

简要题意

现在有一个长度为 \(n\) 的静态序列 \(a\) ，保证 \(|a_i| \leqslant 10^9\) 。

每一次询问给出 \(l,r\) ，查询这个区间内 绝对值最大 的非空连续子序列。

\(n \leqslant 2\times 10^5,m \leqslant 3 \times 10^6\) 。

思路点拨

本题有两种做法。

猫树

我们可以查询这个区间内的最大字段和和最小子段和。然后取一个绝对值最大值。

我们可以使用猫树，用更多的预处理时间和空间换快速询问。

考虑对于一个线段树上的区间，这个区间的 \(mid\) 过询问区间 \([l,r]\) 。答案考虑四部分：

  • \([l,mid]\) 的绝对值最大子段和。

  • \([mid+1,r]\) 的绝对值最大子段和。

  • \([l,mid]\) 的最大后缀加上 \([mid+1,r]\) 的最大前缀。

  • \([l,mid]\) 的最小后缀加上 \([mid+1,r]\) 的最小前缀。

这个的每一部分都可以在 \(O(n \log n)\) 的时间内预处理出来，所以我们的询问可以做到 \(O(1)\) 。

总体时间复杂度 \(O(n \log n+ q)\) 。

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-f;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
inline void print(int x){
	if(x<10) putchar(x+'0');
	else{
		print(x/10);
		putchar(x%10+'0');
	}
	return ;
}
const int MAXN=2e5+10,inf=1e15;
int n,m,a[MAXN];
int pos[MAXN];
struct seg{
	int l,r;
}t[MAXN<<2];
vector<int> L[MAXN<<2],R[MAXN<<2];
vector<int> maxxL[MAXN<<2],maxxR[MAXN<<2],minxL[MAXN<<2],minxR[MAXN<<2];
vector<int> mxL[MAXN<<2],mxR[MAXN<<2],mnL[MAXN<<2],mnR[MAXN<<2];
void build(int i,int l,int r){
	t[i].l=l,t[i].r=r;
	if(l==r){
		pos[l]=i;
		return ;
	}
	int mid=(l+r)>>1;
	build(i<<1,l,mid);
	build(i<<1|1,mid+1,r);
	L[i].push_back(0);
	mxL[i].push_back(-inf),mnL[i].push_back(inf);
	maxxL[i].push_back(-inf),minxL[i].push_back(inf);
	for(int j=mid;j>=l;j--){
		L[i].push_back(L[i][mid-j]+a[j]);
		maxxL[i].push_back(max(L[i][mid-j+1],maxxL[i][mid-j]));
		minxL[i].push_back(min(L[i][mid-j+1],minxL[i][mid-j]));
		mxL[i].push_back(max(a[j],mxL[i][mid-j]+a[j]));
		mnL[i].push_back(min(a[j],mnL[i][mid-j]+a[j]));
	}
	R[i].push_back(0);
	mxR[i].push_back(-inf),mnR[i].push_back(inf);
	maxxR[i].push_back(-inf),minxR[i].push_back(inf);
	for(int j=mid+1;j<=r;j++){
		R[i].push_back(R[i][j-mid-1]+a[j]);
		maxxR[i].push_back(max(R[i][j-mid],maxxR[i][j-mid-1]));
		minxR[i].push_back(min(R[i][j-mid],minxR[i][j-mid-1]));
		mxR[i].push_back(max(a[j],mxR[i][j-mid-1]+a[j]));
		mnR[i].push_back(min(a[j],mnR[i][j-mid-1]+a[j]));
	}
	for(int j=mid;j>=l;j--){
		mxL[i][mid-j+1]=max(mxL[i][mid-j+1],mxL[i][mid-j]);
		mnL[i][mid-j+1]=min(mnL[i][mid-j+1],mnL[i][mid-j]);
	}
	for(int j=mid+1;j<=r;j++){
		mxR[i][j-mid]=max(mxR[i][j-mid],mxR[i][j-mid-1]);
		mnR[i][j-mid]=min(mnR[i][j-mid],mnR[i][j-mid-1]);
	}
}
int query(int l,int r){
	if(l==r) return abs(a[l]);
	int i,ans=-inf,x=pos[l],y=pos[r];
	while(x!=y){
		if(x<y) swap(x,y);
		x>>=1;
	}
	i=x;
	int mid=(t[i].l+t[i].r)>>1;
	ans=max(ans,max(mxL[i][mid-l+1],mxR[i][r-mid]));
	ans=max(ans,max(abs(mnL[i][mid-l+1]),abs(mnR[i][r-mid])));
	ans=max(ans,maxxL[i][mid-l+1]+maxxR[i][r-mid]);
	ans=max(ans,abs(minxL[i][mid-l+1]+minxR[i][r-mid]));
	return ans;
}
signed main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++) a[i]=read();
	build(1,1,n);
	while(m--){
		int l=read(),r=read();
		print(query(l,r));
		putchar('\n');
	}
	return 0;
}

\(ST\) 表

我们考虑前缀和数组 \(sum_i\) 表示 \(\sum_{i=1}^i a_i\) 。

那么对于一次询问，就是查询 \(\max\{|sum_i-sum_j|\}(l \leqslant i,j \leqslant r)\) 。

这个等价于求区间 \([l,r]\) 内前缀和数组的极差，可以使用 \(ST\) 表维护。

时间复杂度 \(O(n \log n +q)\) 。

\(T4\)

简要题意

现在有 \(n\) 个二元组 \((A_i,B_i)\) ，我们需要将其按照任意顺序排列，满足如下条件：

  • 对于 \(1<i \leqslant n\) ，满足 \(A_i=A_{i-1}\) 或者 \(B_i=B_{i-1}\) 。

  • 对于 \(1<i<n\) ，不满足 \(A_i=A_{i-1}=A_{i+1}\) ，也不满足 \(B_i=B_{i-1}=B_{i+1}\) 。

现在Kiana想问是否有解，如果有解，输出字典序最小的排列方案。

\(n \leqslant 5\times 10^5\) 。

思路点拨

我们考虑答案的形式，类似于

1 2 2 3 3
4 4 5 5 1

如果 \(A_i=A_{i-1}\) ，那么 \(A_{i-1} \neq A_{i-2}\) 并且 \(B_{i-1}=B_{i-2}\) 。

如果 \(B_i=B_{i-1}\) ，那么 \(B_{i-1} \neq B_{i-2}\) 并且 \(A_{i-1}=A_{i-2}\) 。

我们考虑将二元组抽象一个连边关系，我们建立一个分层图。

每一次 \((A_i,B_i)\) 我们就从第一层节点 \(A_i\) 向第二层节点 \(B_i\) 连边。最后答案可以映射位该图上的一条欧拉路径。

Q:为什么这么建图？

A: 这个和本题的题目要求有关，我们这样保证了满足：

  • 对于 \(1<i<n\) ，不满足 \(A_i=A_{i-1}=A_{i+1}\) ，也不满足 \(B_i=B_{i-1}=B_{i+1}\) 。

读者可以自己思考一下。

要求字典序最小可以给边排序。

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-f;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
const int MAXN=1e6+10,inf=1e15;
int n,m,s,t,in[MAXN];
int fa[MAXN];
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
struct node{
	int to,w;
	node(int x=0,int y=0){
		to=x,w=y;
	}
	bool friend operator<(const node &A,const node &B){
		return A.w<B.w;
	}
};
vector<node> e[MAXN];
bool vis[MAXN];
int tmp[MAXN],top,ans[MAXN];
int now[MAXN];
void dfs(int x){
	for(int i=now[x];i<e[x].size();i=now[x]){
		now[x]=i+1;
		int to=e[x][i].to,p=e[x][i].w;
		if(!vis[p]){
			vis[p]=1;
			dfs(to);
			tmp[++top]=p;
		}
	}
}
void Euler(int x){
	top=0;
	for(int i=1;i<=(n<<1);i++){
		now[i]=0,vis[i]=0;
		sort(e[i].begin(),e[i].end());
	}
	dfs(x);
	for(int i=top;i;i--){
		if(ans[i]>tmp[i]){
			for(int j=1;j<=top;j++) ans[j]=tmp[j];
			break;
		}
		else if(ans[i]<tmp[i]) break;
	}
}
signed main(){
	freopen("2465.in","r",stdin);
	freopen("2465.out","w",stdout); 
	n=read();
	for(int i=1;i<=(n<<1);i++)
		fa[i]=i;
	for(int i=1;i<=n;i++){
		int u=read(),v=read()+n;
		if(i==1) s=u,t=v;
		e[u].push_back(node(v,i));
		e[v].push_back(node(u,i));
		fa[find(u)]=find(v);
		in[u]++,in[v]++;
	}
	int cnt=0,dad=-1;
	for(int i=1;i<=(n<<1);i++)
		if(in[i]){
			if(dad==-1) dad=find(i);
			if(find(i)!=dad){
				cout<<"No";
				return 0;
			}
		}
	for(int i=1;i<=(n<<1);i++)
		if(in[i]&1)
			cnt++;
	for(int i=1;i<=(n<<1);i++)
		ans[i]=inf;
	if(!cnt)
		Euler(s),Euler(t);
	else if(cnt==2){
		for(int i=1;i<=(n<<1);i++)
			if(in[i]&1) Euler(i);
	}
	else{
		cout<<"No";
		return 0;
	}
	cout<<"Yes"<<endl;
	for(int i=top;i;i--) printf("%lld ",ans[i]);
	return 0;
}