首页 > 其他分享 >2023.10.5测试

2023.10.5测试

时间:2023-10-06 16:23:58浏览次数:45  
标签:return int LL 2023.10 tree 测试 const sum

\[\text{NOIP模拟赛-2023.10.5} \]

T1 魔法少女

定义 \(f(i)\) 为 \(i\) 所有约数的异或和,求 \(f(1)\sim f(n)\) 的异或和

\(1\leq n\leq 10^{14}\)

容易想到枚举约数然后计算出约数出现的次数并对答案做贡献,复杂度 \(\mathcal{O}(n)\)

发现约数 \(x\) 出现的次数即 \(\left\lfloor\dfrac{n}{x}\right\rfloor\),这可以用整除分块求出出现次数相同的一段区间 \([l,r]\),复杂度 \(\mathcal{O}(\sqrt{n})\)

问题是如何快速计算一段区间异或和??

考场思路是,发现两个相邻的偶数和奇数的异或和为 \(1\),所以知道一段区间的头或尾再考虑一下区间长度就可以 \(\mathcal{O}(1)\) 计算出来

当然你打表就可以发现 \(1\sim x\) 的异或和与 \(x\bmod 4\) 的结果有关

code
#include<bits/stdc++.h>
#pragma GCC optimize(3,"Ofast","inline")
#define LL long long 
using namespace std;

LL n,ans;

int main()
{
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	
	scanf("%lld",&n);
	
	for(LL l=1,r; l<=n; l=r+1)
	{
		r=n/(n/l);
		LL tmp=n/l,cnt=r-l+1;
		if(tmp%2==0)
			continue;
		if((l&1) && (r&1))
			ans^=l,cnt--;
		else if((l&1) && (r%2==0))	
			ans^=l^r,cnt-=2;
		else if((l%2==0) && (r%2==0))
			 ans^=r,cnt--;
		ans^=((cnt/2)%2); 
	} 
	
	printf("%lld",ans);

	return 0;
}

T2 亿只只因的回家路

UOJ #747.【UNR #6】面基之路

出题人???

注意到一个关键的性质,题意等价于让所有人同时到同一个点的最短时间,没看出来的话很难做

那这样我们就可以枚举他们的汇合点或者汇合边。在点上汇合比较容易,考虑在边上汇合的情况。只要枚举每个人是从边的左侧还是右侧进入即可,复杂度可以做到 \(\mathcal{O}(km\log n+kn2^k+m2^k)\),可以获得 \(85\) 分

其实处理点的情况可以做到 \(\mathcal{O}(km\log n+kn)\),但为了处理边的情况多了一个 \(2^k\),所以瓶颈在于处理边的情况

我们一开始是枚举每个人从哪侧进入,但最后只考虑进入边时间最晚的人,所以一定存在一种方案,将人进入左侧的时间从小到大排序后,一个前缀从左侧进入,剩余的后缀从右侧进入,时间复杂度 \(\mathcal{O}(km\log n+kn+mk\log k)\),可以通过

(在 GJOJ 被卡了……)

code
#include<bits/stdc++.h>
#pragma GCC optimize(3,"Ofast","inline")
#define LL long long
#define pli pair<LL,int>
using namespace std;

const int N=1e5+10,M=2e5+10,K=20+10;
const LL INF=1e18;

int n,m,k,a[N];
LL d[N],ans1[N][K],ans2[M],ans=INF;
struct node{int y,z;};vector <node> g[N];
struct E{int x,y,z;}e[M];
bool v[N];

void dijkstra(int s)
{
	priority_queue <pli> q;
	memset(v,0,sizeof(v));
	memset(d,0x3f,sizeof(d));
	d[s]=0;  q.push({0,s});
	while(q.size())
	{
		int x=q.top().second;  q.pop();
		if(v[x])
			continue;
		v[x]=1;
		for(auto v:g[x])
		{
			if(d[v.y]>d[x]+(LL)v.z)
			{
				d[v.y]=d[x]+(LL)v.z;
				q.push({-d[v.y],v.y});
			}
		} 
	}
}

LL calc(LL a,LL b,LL z)
{
	if(min(a,b)+z<=max(a,b))
		return max(a,b);
	z-=max(a,b)-min(a,b);
	return max(a,b)+z/2; 
}

int main()
{
    freopen("b.in","r",stdin);
    freopen("b.out","w",stdout);
    
	memset(ans2,0x3f,sizeof(ans2));
	
	scanf("%d%d",&n,&m,&k);
	for(int i=1; i<=m; i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		z*=2;
		e[i]={x,y,z};
		g[x].push_back({y,z});
		g[y].push_back({x,z});
	}
	scanf("%d",&k);
	a[1]=1;  k++;
	for(int i=2; i<=k; i++)
		scanf("%d",&a[i]);
	
	int S=(1<<k)-1;
	for(int i=1; i<=k; i++)
	{
		dijkstra(a[i]);
		
		for(int j=1; j<=n; j++)
			ans1[j][i]=d[j],ans1[j][0]=max(ans1[j][0],d[j]);
	}

	for(int i=1; i<=n; i++)
		ans=min(ans,ans1[i][0]);
	for(int i=1; i<=m; i++)
	{
		priority_queue <pli> q1,q2;
		for(int j=1; j<=k; j++)
			q1.push({ans1[e[i].x][j],j});
		while(q1.size())
		{
			int x=q1.top().second;  q1.pop();
			q2.push({ans1[e[i].y][x],x});
			ans2[i]=min(ans2[i],calc(q1.top().first,q2.top().first,e[i].z));
		}
		ans=min(ans,ans2[i]);
	}
	
	printf("%lld",ans);
	
	return 0;
}

T3 西琳的魔法字符串

CCPC Finals 2021 I. Reverse LIS

一道题炸出很多前置题

这个题有一个弱化版 CF933A A Twisty Movement。但那题用 \(\rm dp\) 可以通过

这里我们转化一下题意,我们枚举 \(0\) 和 \(1\) 的断点 \(i\),那最后的不下降子序列就是 \(i\) 前面的 \(0\) 的个数加上 \(i\) 后面的 \(1\) 的个数。如果我们将 \(0\) 的权值赋成 \(1\),\(1\) 的权值赋成 \(-1\),设权值数组为 \(a\),那么子序列的长度就是 \(\text{count}(S,\,'1')+\sum a[1:i]\)。所以我们就需最大化 \(\sum a[1:i]\)

回到原问题,它支持 \(k\) 次区间翻转的操作,最后最大化一个前缀和。其实可以转化为在原串中选出 \(k+1\) 个不相交的区间,其中一段为前缀,使得子段和最大

这个可以参考 [DS/贪心记录] CF280D k-Maximum Subsequence Sum 的实现

code
#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N=2e5+10;
const LL INF=1e18;

int n,q,a[N];
LL last,ans[N];
queue < pair<int,int> > qq;
struct Ask{int k,id;}Q[N];

struct node{int l,r;LL s;};  node zinf={0,0,INF},finf={0,0,-INF};
node operator + (const node &a,const node &b){return {a.l,b.r,a.s+b.s};}
bool operator < (const node &a,const node &b){return a.s<b.s;}

#define lc(p) p<<1
#define rc(p) p<<1|1
struct Seg
{
	node mx,mn,lmx,rmx,lmn,rmn,sum;
	int rev;  
	#define rev(x) tree[x].rev 
	
	void write(int l,int r,LL s)
	{
		mx=mn=lmx=rmx=lmn=rmn=sum={l,r,s};
		rev=0;
	}
	
	void reverse()
	{
		swap(mx,mn);  swap(lmx,lmn);  swap(rmx,rmn);
		mx.s*=-1;  mn.s*=-1;
		lmx.s*=-1;  rmx.s*=-1;
		lmn.s*=-1;  rmn.s*=-1;
		sum.s*=-1;  rev^=1;
	}
}tree[N<<2];
Seg I={finf,zinf,finf,finf,zinf,zinf,{0,0,0},0};

Seg pushup(Seg p,Seg q)
{
	Seg val=I;
	if(p.mx.s>=1e16)
		return q;
	if(q.mx.s>=1e16)
		return p;
	val.mx=max(max(p.mx,q.mx),p.rmx+q.lmx);
	val.mn=min(min(p.mn,q.mn),p.rmn+q.lmn);
	val.lmx=max(p.lmx,p.sum+q.lmx);
	val.rmx=max(q.rmx,p.rmx+q.sum);
	val.lmn=min(p.lmn,p.sum+q.lmn);
	val.rmn=min(q.rmn,p.rmn+q.sum);
	val.sum=p.sum+q.sum;
	return val;
}

void spread(int p)
{
	if(rev(p))
	{
		tree[lc(p)].reverse();
		tree[rc(p)].reverse();
		rev(p)=0; 
	}
}

void build(int p,int l,int r)
{
	if(l==r)
	{
		tree[p].write(l,r,a[l]);
		return;
	}
	int mid=(l+r)>>1;
	build(lc(p),l,mid);
	build(rc(p),mid+1,r);
	tree[p]=pushup(tree[lc(p)],tree[rc(p)]); 
}

void change(int p,int l,int r,int x,int v)
{
	if(l==r)
	{
		tree[p].write(l,r,v);
		return;
	}
	spread(p);
	int mid=(l+r)>>1;
	if(x<=mid)
		change(lc(p),l,mid,x,v);
	else
		change(rc(p),mid+1,r,x,v);
	tree[p]=pushup(tree[lc(p)],tree[rc(p)]);
}

void reverse(int p,int l,int r,int ql,int qr)
{
	if(ql<=l && qr>=r)
		return tree[p].reverse(),void();
	spread(p);
	int mid=(l+r)>>1;
	if(ql<=mid)
		reverse(lc(p),l,mid,ql,qr);
	if(qr>mid) 
		reverse(rc(p),mid+1,r,ql,qr);
	tree[p]=pushup(tree[lc(p)],tree[rc(p)]); 
}

int main()
{
    freopen("c.in","r",stdin);
    freopen("c.out","w",stdout);
    
	scanf("%d",&n);
	for(int i=1; i<=n; i++)
	{
		int c,p;
		scanf("%d%d",&c,&p);
		a[i]=(c==0? 1:-1)*p;
		if(c==1)
			last+=(LL)p;
	}
	
	build(1,1,n);
	
	Seg tur=tree[1];
	if(tur.lmx.s>0)
	{
		last+=tur.lmx.s;
		reverse(1,1,n,tur.lmx.l,tur.lmx.r);
	}
	
	scanf("%d",&q);
	for(int i=1; i<=q; i++)
		scanf("%d",&Q[i].k),Q[i].id=i;
	
	sort(Q+1,Q+1+q,[](Ask a,Ask b){return a.k<b.k;});
	
	int cnt=0;
	for(int i=1; i<=q; i++)
	{
		while(cnt<Q[i].k)
		{
			Seg cur=tree[1];
			if(cur.mx.s<=0)
				break;
			last+=cur.mx.s; 
			reverse(1,1,n,cur.mx.l,cur.mx.r);
			qq.push({cur.mx.l,cur.mx.r});
			cnt++;
		}
		ans[Q[i].id]=last;
	}
	
	for(int i=1; i<=q; i++)
		printf("%lld\n",ans[i]);
	
	return 0;
}

/*
1
1 1
1
0
*/ 

\(100+80+0+0=180\),\(\rm rk16\)

标签:return,int,LL,2023.10,tree,测试,const,sum
From: https://www.cnblogs.com/xishanmeigao/p/17744225.html

相关文章

  • 【GJOI 2023.10.5 T1】 雷老师的正偏态分布
    雷老师的正偏态分布题意:给出一个长度为\(n\)的\(a\)数组,其中\(1\lea_i\leV,1\lei\len\)。统计其中的满足平均数严格小于中位数且大小为奇数的子集数量,\(n\le100,V\le800\),时限\(4\)s。输入:510127910输出:8首先,可以考虑排序,保证一个子集中小......
  • gcc测试
    学习任务参考学习“资源”中的PPT和视频,然后编写一个程序打印自己学号姓名用gcc进行预处理,编译,汇编,链接上面程序生成的可执行文件中要有自己的8位学号提交预处理,编译,汇编,链接,运行过程截图,要全屏,包含自己的学号信息作业内容编程预处理编译汇编运行......
  • 性能测试学习笔记(四)
    一、关联和断言满足如下条件的数据都是需要关联的:1.数据是由服务器端生成的;2.数据在每一次请求时都是动态变化的;3.数据在后续的请求中需要再发送出去。JMeter中常用于数据关联的组件:1、JSON提取器(提取JSON格式的响应数据)2、Xpath提取器(提取HTML格式的响应数据)3、正则表......
  • 自动化测试工具列表
    1、LambdaTest(收费,免费试用100分钟)https://www.lambdatest.com/selenium-automation?utm_source=STH&utm_medium=Listing&utm_campaign=Automation-tools&utm_term=2、......
  • 板刷2023.10.04
    CF1878F.VasilijeLovesNumberTheory题解:约数个数+取模性质对\(n\)质因子分解得到,\(n=p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k}\)那么显然\(d(n)=(\alpha_1+1)\times(\alpha_2+1)...(\alpha_k+1)\)根据题意可以得到:\(n\%d(n)=0\)的时候一定......
  • 【AI测试】python文字图像识别tesseract
    [AI测试]python文字图像识别tesseractgithub官网:https://github.com/tesseract-ocr/tesseractpython版本:https://github.com/madmaze/pytesseractOCR,即OpticalCharacterRecognition,光学字符识别,是指通过扫描字符,然后通过其形状将其翻译成电子文本的过程。对于图形验证码来说,它们......
  • 【AI测试】已落地-python文字图像识别PaddleOCR
    python文字图像识别PaddleOCRPaddleOCR旨在打造一套丰富、领先、且实用的OCR工具库,助力开发者训练出更好的模型,并应用落地。国产之光,百度开源的paddleocr开源地址:https://github.com/PaddlePaddle/PaddleOCR官方电子书:https://github.com/PaddlePaddle/PaddleOCR/blob/release/2.7......
  • 数据库备份和Shell基础测试及AWK(运维)
    第一题:简述一下如何用mysql命令进行备份和恢复,请以test库为例,创建一个备份,并再用此备份恢复备份备份步骤:备份test库:使用mysqldump命令备份test库,并将备份写入一个.sql文件中。命令示例:mysqldump-u用户名-p密码test>backup.sql恢复的步骤:恢复备份:使用mysql命令将备份文件中的......
  • stepci 开源api 自动测试框架
    stepci是基于nodejs开发的,开源api自动测试框架包含的特性语言无关 可以基于yaml,json,js定义支持多种框架 rest,graphl,grpc,trpc,soap自托管 可以集成到ci/cd中,同时可以自己部署与行可集成 可以很好的与其他工具集成说明stepci目前也支持负载测试(预览状态),同时还支持f......
  • 2023.10.5
    A记\(\displaystylef(i)=\oplus_{d|i}d\),求\(\displaystyle\oplus_{i=1}^{n}f(i)\).\(n\le10^{14}\).考虑一个数是否出现计数次,对\(\lfloor\frac{n}{x}\rfloor\)整除分块,查询区间异或和即可。点击查看代码#include<bits/stdc++.h>#definelllonglongusingnames......