国庆集训 Test 3

国庆集训 Test 3

T1

由式 $a_i\%a_j$ 易知，考虑暴力枚举 $a_j$ 然后发现取模后结果是 $\frac{n}{a_j}$ 个区间 $[0,a_j)$，然后这样的区间个数为 $\sum \frac{n}{i}$ 即调和级数，那么考虑再开个 st 表维护区间最大值，单次查询 $\text{O}(1)$，总时间复杂度为 $\text{O}(m\log m)$，$m$ 表示值域大小。

#include <iostream>
#include <cstdio>
#include <cctype>
#include <cmath>
using namespace std;

template <typename T>
inline T read(){
	T x=0,f=1;char c=getchar();
	while(!isdigit(c)) {if(c=='-') f=-f;c=getchar();}
	while(isdigit(c)) {x=x*10+(c^48);c=getchar();}
	return x*f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read<int>()
#define readlint read<lint>()
const int inf=1e9+1e7,MAXN=1e6+1e1;
const lint INF=1e18+1e9;

int st[MAXN][21],a[MAXN],n,l,r,s,maxn,Tp;

int main(void){
	
	scanf("%d", &n);
	for(int i=1;i<=n;i++) s=readint,++a[s],Tp=max(s,Tp);
	for(int i=1;i<=Tp;i++) st[i][0]=(a[i] ? i : 0);
	for(int j=1;j<=log2(Tp);j++) for(int i=1;i+(1<<j)-1<=Tp;i++) {
		st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
	}
	if(a[2]) for(int i=3;i<=Tp;i+=2) if(a[i]) maxn=i%2;
	for(int i=3;i<=Tp;i++) for(int j=i;j<=Tp;j+=i) if(a[i]){
		if(j+i-1>Tp) l=j,r=Tp;
		else l=j,r=i+j-1;
		s=log2(r-l+1);
		maxn=max(max(st[l][s],st[r-(1<<s)+1][s])%i,maxn);
	}
	printf("%d\n",maxn);
	
	return 0;
}

话说为什么 $\text{O}(n \cdot {\log n})$ 时间复杂度算法跑不过 $\text{O}(n \cdot {\log n}^2)$ 啊

T2

考虑一个性质即两辆车相撞我们可以视为交换编号，然后穿过彼此。

每辆车即可表示为一个形如 $y = x + b$ 或 $y = -x + b$ 一次函数，由于我们发现初始时的位置相对大小不会改变，那么每次询问 $(x,t)$ 考虑在所有的一次函数里取值为 $t$ 时找到第 $x$ 大的值即为所求。那么可以对于位置二分答案，然后二分查找统计答案。时间复杂度为 $\text{O}(q \cdot {\log n}^2)$。

#include<bits/stdc++.h>
using namespace std;

template <typename T>
inline T read(){
	T x=0,f=1;char c=getchar();
	while(!isdigit(c)){	if(c=='-') f=-f;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read<int>()
#define readlint read<lint>()
const int inf=1e9+1e7,MAXN=2e5+1e1,Tp=2e9+2e2;
const lint INF=1e18+1e9;

struct Node{
	lint w;
	int id;
}q[MAXN];
lint b[MAXN];
int k[MAXN],a[MAXN],to[MAXN],n,m,cnt;
string s;

bool CmpW(Node A,Node B){
	return (A.w<B.w);
}

bool CmpK(Node A,Node B){
	return (A.id==B.id ? A.w<B.w : A.id<B.id);
}

bool Check(lint x,lint y,int num){
	int pos0=lower_bound(b+1,b+cnt,x+y)-b-1,
		pos1=lower_bound(b+cnt,b+n+1,y-x)-b-cnt;
	return (pos0+pos1>=num ? false : true);
}

int main(void){

	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) b[i]=readlint;
	for(int i=1;i<=n;i++) q[i]=(Node){b[i],i};
	sort(q+1,q+n+1,CmpW);
	for(int i=1;i<=n;i++) to[q[i].id]=i;
	cin>>s;
	for(int i=1;i<=n;i++) k[i]=(s[i-1]=='L' ? -1 : 1);
	for(int i=1;i<=n;i++) q[i]=(Node){b[i],k[i]};
	sort(q+1,q+n+1,CmpK);
	for(int i=1;i<=n;i++) b[i]=q[i].w;
	for(int i=1;i<=n;i++) if(q[i].id>0){
		cnt=i;break;
	}
	while(m--){
		int x=to[readint],t=readint;
		lint l=-Tp,r=Tp,Ans=1217041137;
		while(l<=r){
			lint mid=l+r>>1;
			if(Check(t,mid,x)) l=mid+1;
			else Ans=r=mid-1;
		}
		printf("%d\n",abs(Ans));
	}

	return 0;
}

细节上我们使用 lower_bound 函数二分查找时需要注意边界处理，还有就是本题需要开 long long。

其次还有一个做法，那么我们形象的看成是坐在车上的人进行跳车，那么我们二分答案枚举一个跳车次数，然后排序后，双指针模拟向左向右跳车，大概就可以实现 check 了？时间复杂度为 $\text{O}(q \cdot \log n)$。

感觉很难码

T3

大模拟所有的操作，超级玛丽题。咕咕咕~

u1s1随机化输出或者全出 1 或 -1 居然可以拿 50 pts，太雷了