首页 > 其他分享 >【2023.11.16】NOIP2023模拟试题-35

【2023.11.16】NOIP2023模拟试题-35

时间:2023-11-16 19:37:09浏览次数:24  
标签:return bas 16 int 2023.11 35 read ctz fi

《信心赛》

《信心赛》

《很简单》

《很简单》

T1

\(O(n\log n)\) 居然卡不过去(愤怒)

所以我们需要研发 \(O(n)\) 的算法:单调队列。

维护两个指针 \(l,r\) 从最左边开始扫,只要极差小于 \(k\) 就把 \(r\) 一直往右边挪,只要极差大于 \(k\) 就把 \(l\) 往右边挪,这样能确保永远是能取最大的一段区间 。

查看代码
#include<bits/stdc++.h>
using namespace std;
#define fi(l,r) for(int i=l;i<=r;++i)
#define ff(i,l,r) for(int i=l;i<=r;++i)
#define ll long long
#define ly __int128
#define lp ll
#define lson(x) ((x)<<1)
#define rson(x) (lson(x)|1)
#define Lson(x) tr[lson(x)]
#define Rson(x) tr[rson(x)]
#define mod %P
#define N 3000005
int len,n,d,p[N][2],h[2],t[2],l,r,ans;
ll a[N],q[N][2],mx[N],mn[N];
char buf[100000000],*it=buf;//0最小 1最大
void movr(){
	++r;
	while(h[0]<=t[0]&&q[t[0]][0]>=a[r])--t[0];
	q[++t[0]][0]=a[r];
	p[t[0]][0]=r;
	while(h[1]<=t[1]&&q[t[1]][1]<=a[r])--t[1];
	q[++t[1]][1]=a[r];
	p[t[1]][1]=r;
}
void movl(){
	++l;
	while(p[h[0]][0]<l)++h[0];
	while(p[h[1]][1]<l)++h[1];
	return;
}
void reread(){
	fread(buf,1,sizeof buf,stdin);
	it=buf;
	return;
}
template<typename T>
void read(T &x){
	x=0;
	while(!isdigit(*it))if(*(++it)==EOF)reread();
	while(isdigit(*it)){
		x=x*10+(*it)-'0';
		if(*(++it)==EOF)reread();
	}
	return;
}
int main(){
	freopen("sequence.in","r",stdin);
	freopen("sequence.out","w",stdout);
	fread(buf,1,sizeof buf,stdin);
	read(d);read(n);
	fi(1,n)read(a[i]);
	l=h[0]=h[1]=1,r=t[0]=t[1]=0;
	while(r<=n){
		while(l<r&&q[h[1]][1]-q[h[0]][0]>d)movl();
		while(r<=n&&q[h[1]][1]-q[h[0]][0]<=d)movr();
		ans=max(ans,r-l);
		movr();
	}
	printf("%d\n",ans);
	return 0;
}

T2

打个表:

打表

用小金方括号框起来的是值不为 \(0\) 的数,总结规律发现用以下代码

#define ctz __builtin_ctz
	fi(1,n)
		if((i&1)==0)
			for(int bas=i>>ctz(i),j=max(bas,(i*2-n+bas-1)/bas*bas);j<=n&&j<i*2;j+=bas)
					printf("x=%d y=%d val=%d\n",j,i*2-j,ctz(i)+1-ctz(j));

可以筛出所有值不为 \(0\) 的数的值。一共 \(97\) 万个,因此我们要寻找一个 \(n\log n\) 的做法。

首先我们考虑 \(a_i=i\) 的情况怎么做,其实就是问一个倒三角形区间里包含的所有 \(f\) 的和,比如询问 \(l=8,r=18\) 就是求这个区间内金色中括号数值的和:

小红帽

看到三角形面积覆盖驱使我们想到扫描线或者树状数组,这里选择用树状数组来写,因为更简单。

把一个一个金色小括号看成是点,我们按照每个点的 \(x\) 坐标排序,依次按照 \(x : 1 \rightarrow n\) 的顺序加入点,每加入一列的点,就处理所有以 \(x\) 为右端点的询问:

<iframe height="auto" src="https://www.bilibili.com/video/BV1Xv411F7SL/?spm_id_from=333.999.0.0&vd_source=be404a4185b5f151323a68f64d1fb0a3" width="100%">

(视频还在 B 站审核当中……)

我们把加入的点放进树状数组里,每次只需要 \(O(\log n)\) 查询 \(y\) 坐标 \(\ge l\) 的就行了。

再考虑 \(a_i\) 是排列的情况,只需要把坐标轴按照 \(a_i\) 的顺序逆变换就行了:

#define ctz __builtin_ctz
	fi(1,n){
		read(a[i]);
		rev[a[i]]=i;
	}
	fi(1,n)
		if((i&1)==0)
			for(int bas=i>>ctz(i),j=max(bas,(i*2-n+bas-1)/bas*bas);j<=n&&j<i*2;j+=bas)
				if(rev[j]>rev[i*2-j])
					fri[rev[j]].push_back((Pi){rev[i*2-j],ctz(i)+1-ctz(j)});//筛出所有 f

拼合起来就得到了最终代码:

查看代码
#include<bits/stdc++.h>
using namespace std;
#define fi(l,r) for(int i=l;i<=r;++i)
#define ff(i,l,r) for(int i=l;i<=r;++i)
#define ll long long
#define ly __int128
#define lp ll
#define lson(x) ((x)<<1)
#define rson(x) (lson(x)|1)
#define Lson(x) tr[lson(x)]
#define Rson(x) tr[rson(x)]
#define mod %P
#define N 300005
#define M 1000005
#define ctz __builtin_ctz
char buf[100000005],*it;
void reread(){
	fread(buf,1,sizeof buf,stdin);
	it=buf;
	return;
}
template<typename T>
void read(T &x){
	x=0;
	while(!isdigit(*it))if(*(++it)==EOF)reread();
	while(isdigit(*it)){
		x=x*10+(*it)-'0';
		if(*(++it)==EOF)reread();
	}
	return;
}
int lowbit(int x){return x&(-x);}
int n,m,l,r,a[N],rev[N],c[N];
ll ans,ansof[M];
struct Pi{
	int x,y;
	bool operator < (Pi b){
		return x<b.x;
	}
};
vector<Pi>fri[N],queat[N];
bool book[N]={0};
void add(int x,int val){//存储 fri[i].x > que[i].x 的个数
	while(x<=n){
		c[x]+=val;
		x+=lowbit(x);
	}
}
int query(int r){
	int ret=0;
	while(r>0){
		ret+=c[r];
		r-=lowbit(r);
	}
	return ret;
}
int query(int l,int r){//查询 fri[i].x > l
	return query(r)-query(l-1);
}
int main(){
	freopen("perm.in","r",stdin);
	freopen("perm.out","w",stdout);
	reread();
	int x,y;
	read(n);
	fi(1,n){
		read(a[i]);
		rev[a[i]]=i;
	}
	fi(1,n)
		if((i&1)==0)
			for(int bas=i>>ctz(i),j=max(bas,(i*2-n+bas-1)/bas*bas);j<=n&&j<i*2;j+=bas)
				if(rev[j]>rev[i*2-j])
					fri[rev[j]].push_back((Pi){rev[i*2-j],ctz(i)+1-ctz(j)});
	read(m);
	fi(1,m){
		read(x);read(y);
		queat[y].push_back((Pi){x,i});
	}
	fi(1,n){
		for(Pi e:fri[i])add(e.x,e.y);
		for(Pi e:queat[i])ansof[e.y]=query(e.x,i);
	}
	fi(1,m)printf("%lld\n",ansof[i]);
	return 0;
}

T3

好不容易因为数据水做对了一遍 T3

T3 是用 dfs 乱搞出来的。先枚举第一个点 \(p_1\) ,再用 dfs 算出后面的点。理论上复杂度可以卡到 \(n^3\) ,但是没想到就这样放我 AC 了(?

查看代码
#include<bits/stdc++.h>
using namespace std;
#define fi(l,r) for(int i=l;i<=r;++i)
#define ff(i,l,r) for(int i=l;i<=r;++i)
#define ll long long
#define N 1000005
#define M 2000005
int n,m,tot,fir[N],nxt[M],to[M],kk,dis[N],ans=0x3f3f3f2f,w[M],rge[N];//dis 存储 1 到 x 只经过一条边的最短距离,rge 存储 x 到 n 只经过一条边的最短距离。
void add(int x,int y,int z){
	nxt[++tot]=fir[x];
	fir[x]=tot;
	to[tot]=y;
	w[tot]=z;
}
bool vis[N]={0};
void dfs(int x,int len,int dep){
	if(len>ans)return;
	if(dep==kk-1){
		ans=min(ans,rge[x]+len);
		return;
	}
	for(int e=fir[x];e;e=nxt[e]){
		int u=to[e];
		if(vis[u])continue;
		vis[u]=1;
		dfs(u,len+w[e],dep+1);
		vis[u]=0;
	}
	return;
}
int main(){
	freopen("graph.in","r",stdin);
	freopen("graph.out","w",stdout);
	int x,y,z;
	memset(dis,0x3f,sizeof dis);
	memset(rge,0x3f,sizeof rge);
	scanf("%d %d %d",&n,&m,&kk);
	if(kk==0){
		printf("0");
		return 0;
	}
	fi(1,m){
		scanf("%d %d %d",&x,&y,&z);
		add(x,y,z);
		add(y,x,z);
		if(x==1)dis[y]=min(dis[y],z);
		if(y==1)dis[x]=min(dis[x],z);
		if(x==n)rge[y]=min(rge[y],z);
		if(y==n)rge[x]=min(rge[x],z);
	}
	if(kk==1){
		if(dis[n]>=0x3f3f3f2f)printf("-1");
		else printf("%d",dis[n]);
		return 0;
	}
	if(kk==2){
		fi(1,n)ans=min(ans,dis[i]+rge[i]);
		if(ans>=0x3f3f3f2f)printf("-1");
		else printf("%d",ans);
		return 0;
	}
	vis[1]=vis[n]=1;
	fi(2,n-1){
		if(dis[i]<ans){
			vis[i]=1;
			dfs(i,dis[i],1);
			vis[i]=0;
		}
	}
	if(ans>=0x3f3f3f2f)printf("-1");
	else printf("%d",ans);
	return 0;
}

而且还比 std 快 ( !

IQ 1e9+7

</iframe>

标签:return,bas,16,int,2023.11,35,read,ctz,fi
From: https://www.cnblogs.com/DZhearMins/p/17837074.html

相关文章

  • 231116校内赛
    T1玩具序列很简单的一道T1但某人的st表炸成灰灰了首先明确我们是需要维护区间最大和最小,那么容易想到的有以下几个:线段树,st表,单调队列对于线段树和st表而言\(3e6\)的数据都有点卡时间st表还卡空间,而且预处理慢的离谱,虽然最后卡过去了如此看来单调队列则是不二之选,我......
  • 11月16日自定义对象类型
    目录对象类型1.自定义对象2.给对象添加值3.修改对象的值4.循环取值的情况5.特别的情况对象类型1.自定义对象js内对象确实是键值对的集合,但并不仅限于使用字符串作为键。js对象可以使用字符串、数字或符号作为键。通常是用字符串当键值。通常的例子如下vara={name:"nick",......
  • 11.16鲜花
    最抽象的一次内含抽象内容昨天看了jijidawang的那张图晚上做梦就梦到我把天依一点一点的...肢解....然后每次挥刀都会响起那个存娘的《刀刀致命》不知哪里来的感觉...天依的血是甜的,像糖水一样然后..我套上天依的皮,去一点一点模仿她的生活....现在想来有点后怕....呃呃........
  • 11.16每日总结
    今天准备好明天的测试了,但是由于上周的作业太复杂了,于是又推迟了一周,但是今天上课我们进行了讨论。目前的状况是我们的原型已经搭建起来了要做的就是要把相应流程图和用例图搞明白流程还是不太熟悉,因为中间涉及到很多环节。 ......
  • Windows server 2012/2016安装SQL Server 2005和SP4补丁
    sqlserver2005安装包sqlserver2005SP4补丁包(非常难找,留作备用)链接:https://pan.baidu.com/s/1j5OOX-iV8gLrmSNqNLE-kg提取码:jvtr复制这段内容后打开百度网盘手机App,操作更方便哦 背景:在windowsserver2012/2016x64安装sqlserver2005的时候会提示如下错误,无法启......
  • 2023/11/16
    考试成绩,不好评价。从今天起,1)已经摒弃之前节约消费习惯,现在每次消费已经大于等于13元2)从今天起,摒弃良好用餐习惯,面包\奥利奥\维他奶在我心中已经取代传统饮食。(冬天是万物长胖的季节)。......
  • 20231116
    今天是个大晴天,18摄氏度,不知道为什么一堆人穿冬季校服。看来还是说明体锻太少了,大家都虚了。哦,上文和下文没有关系。下文是昨天总结出来的,也是也不是,是上高中后总结出来的。形式主义其实是一群傻逼满脑子都是他们认为的理想化,我觉得这种人脑子相当于是被格式化了。也是,生活中接......
  • 2023.11.16
    A给出两个点\(A\),\(B\)和\(n\)个圆,此外还有一个未知的圆\(O\)过\(A,B\)且不与任意圆相交。问\(O\)的最小可能半径。\(1\len\le10^5\),点和半径值域\([-10^5,10^5]\)。答案不超过\(10^{12}\),要求相对或绝对误差\(\le10^{-3}\)。二分一眼假但是放了\(80\)分。......
  • 11 16 更新用户密码
     @PatchMapping注解是因为接口文档的请求方式是patch,参数声明了map集合对象,@RequestBody是把json数据转化为map对象controller层:service层:  mapper层: 新增文章分类:下面分别是controller,service,mapper: 接口文档要求两个参数均非空,所以对实体参数进行校验:......
  • 2023.11.16日报
    今日猛肝,把大数据的实验做完了八个八个!!!无需多言附图为证 然后就是做完这个就要开始看ERP了今天先这样了学习时间已经不记得几个小时了反正不少于三小时......