首页 > 其他分享 >atcoder 杂题 #01

atcoder 杂题 #01

时间：2024-12-05 16:33:33浏览次数：4  
标签：atcoder lower 01 int 杂题 bound p1 bx fo

atcoder 杂题 #01

arc163_c

可能因为数学不好，所以栽在了这道 Luogu 评的绿题上。

题目大意：求一个长为 \(n\) 的正整数序列 \(a\) 使得 \(\sum\frac 1 {a_i} =1\)，要求 \(a_i\) 互不相同，且 \(a_i\le10^9\)。

这题开始想着往通分后的 \(lcm\) 的 \(n\) 个因数的和等于 \(lcm\) 方向考虑，发现并没有什么有趣的性质。

最终看了题解后知道，这道题要依靠这样一个式子不断拆解分数：

\[\frac 1 x=\frac 1 {x+1}+\frac 1{x(x+1)} \]

然后首先特判 \(n\le 2\) 的情况，\(n=1\) 就是 \(a_1=1\)，\(n=2\) 就是无解。

然后考虑从 \(\frac 1 2,\frac 1 3,\frac 1 6\) 开始拆，把这些东西加入一个 set 里，每次取出最小的数然后拆，这样才能使最终序列的分母尽可能小，注意到可能拆完后与原来序列中的数有重复，比如 \(\frac12=\frac13+\frac16\)，所以如果有重复就直接把它加入 \(a\) 数组里，以后不再拆它。

由于重复的很少，所以最后一定能达成 \(n\) 个，我们也可写完后验证可不可行。

AC 代码：

int T,n;
set<int> s;
const int N=1005;
int a[N];
signed main(){
	cin>>T;
	while(T--){
		cin>>n;
		if(n==1){
			cout<<"Yes\n1\n";
			continue;
		}
		if(n==2){
			cout<<"No\n";
			continue;
		}
		s={2,3,6};
		int tot=0;
		while(tot+s.size()<n){
			int x=*s.begin();
			if(s.find(x+1)!=s.end()||s.find((ll)(x+1)*x)!=s.end())a[++tot]=x,s.erase(s.begin());
			else{
				s.erase(s.begin());
				s.insert(x+1);
				s.insert((ll)x*(x+1));
			}
		}
		cout<<"Yes\n";
		fo(i,1,tot)cout<<a[i]<<" ";
		for(auto i:s)cout<<i<<" ";
	}
	return 0;
}

arc065_c

第一次自己想出来黑题！纪念一下。
（其实感觉这道题的思维难度并没有黑题，代码也都是重复性的内容，并不难写）。

题目大意：给定 \(n\) 个点，和初始无序点对 \((a,b)\)，记 \(dis(a,b)\) 表示点 \(a,b\) 的曼哈顿距离，可以不断操作，每次操作可以从一个无序点对 \((a,b)\) 移动到另一个满足 \(dis(a,c)=dis(a,b)\) 的无序点对 \((a,c)\) 问你最终能到达多少个无序点对。

首先，套路地，把曼哈顿距离转化为切比雪夫距离，把 \((x,y)\to (x+y,x-y)\)。
实际上就是考虑到一个点曼哈顿距离相等的点，形成了一个倾斜 \(45\) 度的正方形。把正方形转正，就从原来坐标系下的 \((x,y)\) 变成了新坐标系下的 \((x+y,x-y)\)，曼哈顿就变成了切比雪夫距离。

切比雪夫距离就是对于两个点 \((x,y),(x',y')\)，距离为 \(\max(|x-x'|,|y-y'|)\)。

回到题目上来，我们每次 \((a,b)\to(a,c)\) 实际上可以看作 \((b,a)\to(a,c)\)。
我们只关心这个无序对的第二个点 \(a\)，然后每次移动就是把无序对的第二个点换成满足 \(dis(a,b)=L\) 的 \(b\)，\(L\) 为初始点对的距离。

然后我们能求出所有能出现在最终点对中的点，再对这些点统计答案。

这个问题可以 BFS 做，具体地，对每个 \(x'\) 用 set 维护当前还没有遍历到的 \(x=x'\) 的点及其 \(y\)， 对每个 \(y'\) 也这样。
我们每次对 \(x=x_u-L\) 的 set，二分位置取出 \(y_u-L\le y\le y_u+L\) 的点，然后把这些点加入队列，对于 \(x=x_u+L,y=y_u-L,y=y_u+L\) 的也类似。

每当一个点加入队列时，就把它对应 set 中的点删掉，这样就能保证每个遍历到的点都是新的点，保证了复杂度。
每个点在 set 中遍历 \(O(1)\) 次，且加入队列更新其他点 1 次，所以这一部分的复杂度是 \(O(n\log n)\) 的。

求出所有能遍历到的点后，距离其中一个点为 \(L\) 的点与这个点都能形成合法点对。
再用类似方法求出个数即可。把点扔到 \(x\) 和 \(y\) 的 vector 里。二分位置，两个位置相减求个数。注意正方形的四个角可能算重。

最后由于是无序对，答案需要除以 2。

AC 代码，AC 记录：

const int N=1e5+5;
int n,t1,t2;
int X[N],Y[N];
int qx[N],qy[N];
int bx[N],by[N];
int bz[N];
set<pair<int,int> > x1[N],y1[N];
vector<int> x2[N],y2[N];
signed main(){
	read(n,t1,t2);
	fo(i,1,n){
		int x,y; read(x,y);
		X[i]=x+y,Y[i]=x-y;
		bx[i]=X[i],by[i]=Y[i];
	}
	sort(bx+1,bx+1+n);
	sort(by+1,by+1+n);
	int len=unique(bx+1,bx+1+n)-bx-1;
	fo(i,1,n)qx[i]=lower_bound(bx+1,bx+1+len,X[i])-bx;
	int lx=len;
	len=unique(by+1,by+1+n)-by-1;
	fo(i,1,n)qy[i]=lower_bound(by+1,by+1+len,Y[i])-by;
	fo(i,1,n)x1[qx[i]].insert({Y[i],i}),y1[qy[i]].insert({X[i],i});	
	queue<int> q;
	q.push(t1),bz[t1]=1;
	x1[qx[t1]].erase({Y[t1],t1}),y1[qy[t1]].erase({X[t1],t1});
	q.push(t2),bz[t2]=1;
	x1[qx[t2]].erase({Y[t2],t2}),y1[qy[t2]].erase({X[t2],t2});
	int L=max(abs(X[t1]-X[t2]),abs(Y[t1]-Y[t2]));
	while(q.size()){
		int u=q.front(); q.pop();
		int l=lower_bound(bx+1,bx+1+lx,X[u]-L)-bx;
		vector<int> add;
		if(bx[l]==X[u]-L){
			auto p1=x1[l].lower_bound({Y[u]-L,0}),p2=x1[l].lower_bound({Y[u]+L+1,0});
			while(p1!=p2){
				add.push_back(p1->second);
				++p1;
			}
		}
		l=lower_bound(bx+1,bx+1+lx,X[u]+L)-bx;
		if(bx[l]==X[u]+L){
			auto p1=x1[l].lower_bound({Y[u]-L,0}),p2=x1[l].lower_bound({Y[u]+L+1,0});
			while(p1!=p2){
				add.push_back(p1->second);
				++p1;
			}
		}
		l=lower_bound(by+1,by+1+len,Y[u]-L)-by;
		if(by[l]==Y[u]-L){
			auto p1=y1[l].lower_bound({X[u]-L,0}),p2=y1[l].lower_bound({X[u]+L+1,0});
			while(p1!=p2){
				add.push_back(p1->second);
				++p1;
			}
		}
		l=lower_bound(by+1,by+1+len,Y[u]+L)-by;
		if(by[l]==Y[u]+L){
			auto p1=y1[l].lower_bound({X[u]-L,0}),p2=y1[l].lower_bound({X[u]+L+1,0});
			while(p1!=p2){
				add.push_back(p1->second);
				++p1;
			}
		}
		sort(add.begin(),add.end());
		add.resize(unique(add.begin(),add.end())-add.begin());
		for(auto i:add){
			bz[i]=1;
			q.push(i);
			x1[qx[i]].erase({Y[i],i}),y1[qy[i]].erase({X[i],i});
		}
	}
	fo(i,1,lx)x1[i].clear();
	fo(i,1,len)y1[i].clear();
	fo(i,1,n)x1[qx[i]].insert({Y[i],i}),y1[qy[i]].insert({X[i],i});	
	fo(i,1,lx)for(auto j:x1[i])x2[i].push_back(j.first);
	fo(i,1,len)for(auto j:y1[i])y2[i].push_back(j.first);
	ll ans=0;
	fo(i,1,n){
		if(bz[i]){
			int l=lower_bound(bx+1,bx+1+lx,X[i]-L)-bx;
			if(bx[l]==X[i]-L)ans+=upper_bound(x2[l].begin(),x2[l].end(),Y[i]+L-1)-lower_bound(x2[l].begin(),x2[l].end(),Y[i]-L);
			l=lower_bound(bx+1,bx+1+lx,X[i]+L)-bx;
			if(bx[l]==X[i]+L)ans+=upper_bound(x2[l].begin(),x2[l].end(),Y[i]+L)-lower_bound(x2[l].begin(),x2[l].end(),Y[i]-L+1);
			l=lower_bound(by+1,by+1+len,Y[i]-L)-by;
			if(by[l]==Y[i]-L)ans+=upper_bound(y2[l].begin(),y2[l].end(),X[i]+L)-lower_bound(y2[l].begin(),y2[l].end(),X[i]-L+1);
			l=lower_bound(by+1,by+1+len,Y[i]+L)-by;
			if(by[l]==Y[i]+L)ans+=upper_bound(y2[l].begin(),y2[l].end(),X[i]+L-1)-lower_bound(y2[l].begin(),y2[l].end(),X[i]-L);
		}
	}
	write(ans/2);
	return 0;
}

abc303_f

首先考虑二分答案，然后在时间 \(j\) 用 \(i\) 方式攻击的贡献就确定了，我们要判断以最优方式攻击的贡献和是否不小于 \(H\)。

考虑把攻击方式按 \(t_i\) 排序，我们依次确定时间为 \(t_i\sim t_{i+1}\) 这一段以最优方式攻击的贡献和。

那么对于 \(j\le i\) 的攻击方式，一个时间的贡献就是 \(\max\{t_j\times d_j\}\)。
而对于 \(j>i\) 的攻击方式，时间 \(k\) 的贡献就是 \(k\times \max\{d_j\}\)。

在每个段，我们可以 \(O(1)\) 计算一个分界点，分界点前以 \(j\le i\) 的作为攻击方式更优，分界点后以 \(j>i\) 的作为攻击方式更优。
具体地，就是解

\[x\times \max_{j>i}\{d_j\}>\max_{j\le i}\{t_j\times d_j\} \]

细节：我们可以插入一个 \(t=1,d=0\) 的攻击方式，可以方便实现。check 时需要注意特判 \(mid\) 的边界，同时记得开 __int128。

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

AC 代码：

const int N=3e5+5;
ll h;
int n;
pair<int,int> a[N];
int mx[N];
int check(ll x){
	it128 sum=0;
	ll Max=0;
	fo(i,1,n){
		Max=max(Max,(ll)a[i].first*a[i].second);
		if(a[i].first>x)break;
		if(a[i].first!=a[i+1].first){
			if(i==n)sum+=(it128)(x-a[i].first+1)*Max;
			else {
				ll t=floor((ld)Max/mx[i+1]);
				if(t<a[i].first)t=a[i].first-1;
				if(t>=a[i+1].first)t=a[i+1].first-1;
				if(t>=x){
					sum+=(it128)(x-a[i].first+1)*Max;
					break;
				}
				sum+=(it128)(t-a[i].first+1)*Max;
				int up=a[i+1].first;
				if(up>x)up=x+1;
				sum+=(it128)(t+up)*(up-t-1)/2*mx[i+1];
			}
		}
	}
	return sum>=h;
}
signed main(){
	read(n,h);
	fo(i,1,n)read(a[i].first,a[i].second);
	++n;
	a[n]={1,0};
	sort(a+1,a+1+n);
	fd(i,n,1)mx[i]=max(mx[i+1],a[i].second);
	ll l=1,r=1e18,ans=0;
	while(l<=r){
		ll mid=(l+r)>>1;
		if(check(mid))ans=mid,r=mid-1;
		else l=mid+1;
	}
	write(ans);
	return 0;
}

arc065_d

不知道怎么回事，十分钟内秒掉了，感觉难度评高了（洛谷上评紫，kenkoooo 上评了橙色）。

这道题首先直接对每个位置填 0 或 1 计数，又由于 \(n\le 3000\) 所以考虑设 \(f_{i,j}\) 表示前 \(i\) 个填了 \(j\) 个 0 的方案数。

然后考虑怎么限制，我们直接猜结论。
以 0 为例，如果我们要填第 \(j\) 个 0，那么就要满足前 \(i\) 个位置在 0 尽量多的情况下的 0 的个数要不小于 \(j\)。
我们可以依次对每个 \([l,r]\) 的区间排序，就能把 0 尽可能往前放。

可以感性地感受到这个结论应该是正确的。

打完后，发现样例过了，验证了我们的猜想是正确的。

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

AC 代码也非常短：

const int N=3005;
char s[N],t[N];
int n,m;
int l[N],r[N];
int a[N],b[N];
int f[N][N];
const int mod=1e9+7;
signed main(){
	read(n,m),read(s+1);
	fo(i,1,m){
		read(l[i],r[i]);
	}
	fo(i,1,n)t[i]=s[i];
	fo(i,1,m){
		sort(s+l[i],s+r[i]+1);
		sort(t+l[i],t+r[i]+1,greater<>());
	}
	fo(i,1,n){
		a[i]=a[i-1],b[i]=b[i-1];
		a[i]+=s[i]=='0';
		b[i]+=t[i]=='1';
	}
	f[0][0]=1;
	fo(i,1,n){
		fo(j,0,i){
			if(j>0)(f[i][j]+=f[i-1][j-1]*(a[i]>=j))%=mod;
			(f[i][j]+=(f[i-1][j]*(b[i]>=i-j)))%=mod;
		}
	}
	int ans=0;
	fo(i,0,n)(ans+=f[n][i])%=mod;
	write(ans);
	return 0;
}

标签：atcoder,lower,01,int,杂题,bound,p1,bx,fo
From： https://www.cnblogs.com/dccy/p/18588851

相关文章

  • SpringSecurity - [01] 概述
    SpringSecurity是一个灵活且强大的工具，可以帮助你构建安全可靠的Spring应用程序。它不仅简化了认证和授权的过程，而且还提供了丰富的特性和扩展点，使得开发者可以根据项目的独特需求定制安全策略。无论是小型的内部工具还是大型的企业级应用，SpringSecurity都能提供必要的安全保......
  • vs2012 cmake dll工程 调试dll launch.vs.json 附加到进程
    在VisualStudio中，当你有一个DLL项目并且想要附加调试这个DLL时，你需要指定宿主应用程序（在这个例子中是bt.exe），因为DLL本身不是独立可执行的。以下是如何配置launch.vs.json文件以便附加到bt.exe并调试limit-ml-model.dll的步骤：确定宿主应用程序（bt.exe）的路径：你需要知道bt.exe的......
  • 农民工人数、本地农民工人数、外出农民工人数、农民工月收入数据集（2010-2022年）
    数据简介：在外出农民工中，跨省流动7061万人，比上年减少69万人，下降1.0%；省内流动10129万人，比上年增加87万人，增长0.9%。从输出地看，中部地区跨省流动农民工占外出农民工的比重为55.6%，西部地区为47.5%，东北地区为31.4%，东部地区为15.0%。  2022年农民工月均收入4615元，比上年增加183......
  • 真题-桂城2017年六年级(答案+题目)
    今天我给大家出一套C++真题-桂城2017年六年级考题限时2.5小时,大家加油!!!题目1:更多闰年题目描述在smoj网站上，有很多针对小学信息学入门的课程，把这些入门课程的题都刷一遍并理解之后，你就算正式的信息学选手啦。例如课程9的某一道题是这样的：输入两个正整数a和b，表......
  • 01-什么是C语言
    01-什么是C语言C语言是一门通用计算机编程语言，广泛应用于底层开发。C语言的设计目标是提供一种能以简易的方式编译、处理低级存储器、产生少量的机器码以及不需要任何运行环境支持便能运行的编程语言。一、语言人和人交流的语言：汉语、英语、日语、等等。人和计算机交流语言（计......
  • 01-什么是C语言
    一、什么是C语言C语言是一门通用计算机编程语言，广泛应用于底层开发。C语言的设计目标是提供一种能以简易的方式编译、处理低级存储器、产生少量的机器码以及不需要任何运行环境支持便能运行的编程语言。1、语言人和人交流的语言：汉语、英语、日语、等等。人和计算机交流语言（计......
  • OSG开发笔记（三十七）：OSG基于windows平台msvc2017x64编译器官方稳定版本OSG3.4.1搭建环境
    前言  自行编译的osg版本插件比较多，如果对版本没有特定要求，但是对环境编译器有特定要求，可以反向融合编译器符合要求的osg版本。 OSG下载过程  osg官网：http://www.osgchina.org        由于我们不使用osgQt模块，下载了也无所谓，反正不用，这里是osg3.6.4......
  • OpenTelemetry 101：面向 IT 领导者和爱好者的非技术指南
    如果您从事软件开发、SRE或DevOps工作，您可能听说过可观察性、遥测和跟踪等术语。这些概念对于理解应用程序在生产环境中的行为至关重要，并且它们是现代软件开发实践的重要组成部分。您可能还听说过在可观测性方面提到过OpenTelemetry。在本文中，我们将介绍OpenTelemetry101：它是......
  • ABB机器人3HAC036260-001驱动器维修看点
    ABB机器人驱动器是机器人运动控制系统的核心组件之一，负责为机器人提供必要的动力和控制信号，以确保其能够准确、稳定地完成各种工作任务。然而，由于长时间运行、环境因素或操作不当等原因，abb机械臂驱动器3HAC036260-001可能会出现各种故障，影响机器人的正常运行。常见故障及维修方法1......
  • 01 【初学者】引子
     第一次接触CFD，原本以为进去就是吃老本，做软件开发，没想到里面需要学的东西这么多，数学物理都是我感兴趣的，但是这是在我们也接触它们之前，规划了一下未来的学习之路，计算结果解释->网格生成->数值计算->力学建模。计算机入门无疑是最难的！↓高等数学↓线性代数应↓数值计算↓......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99