首页 > 其他分享 >AtCoder Regular Contest 065

AtCoder Regular Contest 065

时间：2025-01-04 12:22:00浏览次数：1  
标签：tmp AtCoder 065 int t1 Regular My id allx

\(AT\_arc065\_a\)
https://www.luogu.com.cn/problem/solution/AT_arc065_a
题解：在读到\(d\)或\(e\)时判断是不是\(dream,dreamer,erase,eraser\)即可。
注意\(dreamer\)和\(erase,eraser\)有重叠，于是在\(d\)时要特判，具体见代码。

#include <bits/stdc++.h>

using namespace std;

const int N=1e5+10;

int n;
char s[N];

int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=1; i<=n; i++){
		if(s[i]=='d'){
			if(s[i+1]=='r'&&s[i+2]=='e'&&s[i+3]=='a'&&s[i+4]=='m'){
				if(s[i+5]=='e'&&s[i+6]=='r'&&s[i+7]=='a'&&s[i+8]=='s'&&s[i+9]=='e') i+=4;
				else{
					if(s[i+5]=='e'&&s[i+6]=='r') i+=6;
					else i+=4;
				}
			}
		}
		else if(s[i]=='e'){
			if(s[i+1]=='r'&&s[i+2]=='a'&&s[i+3]=='s'&&s[i+4]=='e'){
				if(s[i+5]=='r') i+=5;
				else i+=4;
			}
		}
		else{
			cout << "NO" << endl;
			return 0;
		}
	}
	cout << "YES" << endl;
	return 0;
}

\(AT\_arc065\_b\)
https://www.luogu.com.cn/problem/AT_arc065_b
题解：用并查集处理分别处理两张图下，每个点所属联通块。
两点可互达，等价于两点在两张图下所属集合相等。于是枚举第一张图的所有联通块，用桶记录第二张图里每个连通块内有多少点在当前图一所枚举的连通块内，然后对当前图一所枚举的联通块内的点，查询桶内有多少点在图二和其所属同一联通块，即为答案。

	#include <bits/stdc++.h>
	
	using namespace std;
	
	const int N=2e5+10;
	
	int n,k,l;
	int buc[N],ans[N];
	vector<int> q[N];
	struct Dsu{
		int p[N],sz[N];
		int find(int x){
			if(x==p[x]) return x;
			return p[x]=find(p[x]);
		}
	}G1,G2;
	
	int main(){
		cin >> n >> k >> l;
		for(int i=1; i<=n; i++) G1.p[i]=G2.p[i]=i;
		for(int i=1; i<=k; i++){
			int a,b;
			cin >> a >> b;
			a=G1.find(a),b=G1.find(b);
			if(a!=b) G1.p[a]=b;
		}
		for(int i=1; i<=n; i++) q[G1.find(i)].push_back(i);
		for(int i=1; i<=l; i++){
			int a,b;
			cin >> a >> b;
			a=G2.find(a),b=G2.find(b);
			if(a!=b) G2.p[a]=b;
		}
		for(int i=1; i<=n; i++){
			for(int j=0; j<q[i].size(); j++) buc[G2.find(q[i][j])]++;
			for(int j=0; j<q[i].size(); j++) ans[q[i][j]]+=buc[G2.find(q[i][j])];
			for(int j=0; j<q[i].size(); j++) buc[G2.find(q[i][j])]--;
		}
		for(int i=1; i<=n; i++) cout << ans[i] << " ";
		cout << endl;
		return 0;
	}

\(AT\_arc065\_c\)
https://www.luogu.com.cn/problem/AT_arc065_c
题解：先转为切比雪夫距离，发现能到达的点即为以当点为中心的正方形边框上的点，于是考虑\(bfs\)找出能到达的点。先对每个\(x,y\)建立\(set\)，搜索时在正方形四边对应\(set\)里找到符合要求的点加入队列即可，加入某点之后在\(set\)里删除该点即可保证复杂度。找到所有可达点后，为统计答案还需对每个点记录对应正方形四边上的点数，用此时用\(vector\)存储和最初\(set\)一样的信息，然后在正方形四边对应的\(vector\)上二分即可，注意正方形四角贡献要特判。

// LUOGU_RID: 196977639
// LUOGU_RID: 196977594
#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> PII;
const int N=1e5+10;

int n,a,b;
int x[N],y[N];
int dx[4]={-1,-1,1,1};
int dy[4]={-1,1,-1,1};
bool st[N];
map<PII,bool> M;
set<PII> Sx[N],Sy[N];
vector<int> Tx[N],Ty[N];
vector<int> allx,ally;
map<int,int> Mx,My;

void bfs(int now,int len){
	queue<int> q;
	q.push(now);
	st[now]=1;	
	//cout << now << endl;
	while(q.size()){
		int now=q.front();
		q.pop();
		
		Sx[x[now]].erase({ally[y[now]],now});
		Sy[y[now]].erase({allx[x[now]],now});
		int t=allx[x[now]]-len,l=ally[y[now]]-len,r=ally[y[now]]+len;
		if(Mx.count(t)&&Sx[Mx[t]].size()){
			vector<PII> q1;
			for(set<PII>::iterator it=Sx[Mx[t]].lower_bound({l,0}); it!=Sx[Mx[t]].end(); it++){
				int id=(*it).second;
				if(ally[y[id]]>r) break;
				if(!st[id]) q.push(id),st[id]=1,q1.push_back(*it);
			}
			for(int i=0; i<q1.size(); i++) Sx[Mx[t]].erase(q1[i]);
		}
		t=allx[x[now]]+len;
		//for(int i=0; i<allx.size(); i++) cout << allx[i] << " ";
		//cout << endl;
		//cout << allx[x[now]] << endl;
		//cout << Mx.count(t) << endl;
		if(Mx.count(t)&&Sx[Mx[t]].size()){
			//cout << now << " YES" << endl;
			vector<PII> q1;
			for(set<PII>::iterator it=Sx[Mx[t]].lower_bound({l,0}); it!=Sx[Mx[t]].end(); it++){
				int id=(*it).second;
				if(ally[y[id]]>r) break;
				if(!st[id]) q.push(id),st[id]=1,q1.push_back(*it);
			}
			for(int i=0; i<q1.size(); i++) Sx[Mx[t]].erase(q1[i]);
		}
		t=ally[y[now]]-len,l=allx[x[now]]-len,r=allx[x[now]]+len;
		if(My.count(t)&&Sy[My[t]].size()){
			vector<PII> q1;
			for(set<PII>::iterator it=Sy[My[t]].lower_bound({l,0}); it!=Sy[My[t]].end(); it++){
				int id=(*it).second;
				if(allx[x[id]]>r) break;
				if(!st[id]) q.push(id),st[id]=1,q1.push_back(*it);
			}
			for(int i=0; i<q1.size(); i++) Sy[My[t]].erase(q1[i]);
		}
		t=ally[y[now]]+len;
		if(My.count(t)&&Sy[My[t]].size()){
			vector<PII> q1;
			for(set<PII>::iterator it=Sy[My[t]].lower_bound({l,0}); it!=Sy[My[t]].end(); it++){
				int id=(*it).second;
				if(allx[x[id]]>r) break;
				if(!st[id]) q.push(id),st[id]=1,q1.push_back(*it);
			}
			for(int i=0; i<q1.size(); i++) Sy[My[t]].erase(q1[i]);
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> a >> b;
	for(int i=1; i<=n; i++){
		int tx,ty;
		cin >> tx >> ty;
		x[i]=tx+ty,y[i]=tx-ty;
		allx.push_back(x[i]);
		ally.push_back(y[i]);
	}
	sort(allx.begin(),allx.end());
	allx.erase(unique(allx.begin(),allx.end()),allx.end());
	for(int i=0; i<allx.size(); i++) Mx[allx[i]]=i;
	for(int i=1; i<=n; i++) x[i]=Mx[x[i]];
	sort(ally.begin(),ally.end());
	ally.erase(unique(ally.begin(),ally.end()),ally.end());
	for(int i=0; i<ally.size(); i++) My[ally[i]]=i;
	for(int i=1; i<=n; i++) y[i]=My[y[i]];
	for(int i=1; i<=n; i++){
		Sx[x[i]].insert({ally[y[i]],i});
		Sy[y[i]].insert({allx[x[i]],i});
		Tx[x[i]].push_back(y[i]);
		Ty[y[i]].push_back(x[i]);
	}
	for(int i=0; i<allx.size(); i++) sort(Tx[i].begin(),Tx[i].end());
	for(int i=0; i<ally.size(); i++) sort(Ty[i].begin(),Ty[i].end());
	int len=max(abs(allx[x[a]]-allx[x[b]]),abs(ally[y[a]]-ally[y[b]]));
	bfs(a,len);
	long long ans=0;
	
	for(int i=1; i<=n; i++){
		if(!st[i]) continue;
			int now=i,t=allx[x[now]]-len,l=ally[y[now]]-len,r=ally[y[now]]+len;
			if(Mx.count(t)&&Tx[Mx[t]].size()){
				int t1=Mx[t];
				int L=0,R=Tx[t1].size()-1;
				while(L<R){
					int mid=(L+R)/2;
					if(ally[Tx[t1][mid]]>l) R=mid;
					else L=mid+1;
				}
				if(ally[Tx[t1][L]]>l){
					int tmp=L;
					L=0,R=Tx[t1].size()-1;
					while(L<R){
						int mid=(L+R+1)/2;
						if(ally[Tx[t1][mid]]<r) L=mid;
						else R=mid-1;
					}
					if(ally[Tx[t1][L]]>=r) tmp=1e9;
					ans+=max(0,L-tmp+1);
				}
			}
			t=allx[x[now]]+len;
			if(Mx.count(t)&&Tx[Mx[t]].size()){
				int t1=Mx[t];
				int L=0,R=Tx[t1].size()-1;
				while(L<R){
					int mid=(L+R)/2;
					if(ally[Tx[t1][mid]]>l) R=mid;
					else L=mid+1;
				}				
				if(ally[Tx[t1][L]]>l){
					int tmp=L;
					L=0,R=Tx[t1].size()-1;
					while(L<R){
						int mid=(L+R+1)/2;
						if(ally[Tx[t1][mid]]<r) L=mid;
						else R=mid-1;
					}
					if(ally[Tx[t1][L]]>=r) tmp=1e9;
					ans+=max(0,L-tmp+1);
				}
			}
			t=ally[y[now]]-len,l=allx[x[now]]-len,r=allx[x[now]]+len;
			if(My.count(t)&&Ty[My[t]].size()){
				int t1=My[t];
				int L=0,R=Ty[t1].size()-1;
				while(L<R){
					int mid=(L+R)/2;
					if(allx[Ty[t1][mid]]>l) R=mid;
					else L=mid+1;
				}			
				if(allx[Ty[t1][L]]>l){
					int tmp=L;
					L=0,R=Ty[t1].size()-1;
					while(L<R){
						int mid=(L+R+1)/2;
						if(allx[Ty[t1][mid]]<r) L=mid;
						else R=mid-1;
					}
					if(allx[Ty[t1][L]]>=r) tmp=1e9;
					ans+=max(0,L-tmp+1);
				}
			}
			t=ally[y[now]]+len;
			if(My.count(t)&&Ty[My[t]].size()){
				int t1=My[t];
				int L=0,R=Ty[t1].size()-1;
				while(L<R){
					int mid=(L+R)/2;
					if(allx[Ty[t1][mid]]>l) R=mid;
					else L=mid+1;
				}	
				if(allx[Ty[t1][L]]>l){
					int tmp=L;
					L=0,R=Ty[t1].size()-1;
					while(L<R){
						int mid=(L+R+1)/2;
						if(allx[Ty[t1][mid]]<r) L=mid;
						else R=mid-1;
					}
					if(allx[Ty[t1][L]]>=r) tmp=1e9;
					ans+=max(0,L-tmp+1);
				}
			}
	}
	for(int i=1; i<=n; i++) M[{allx[x[i]],ally[y[i]]}]=1;
	for(int i=1; i<=n; i++){
		if(!st[i]) continue;
		for(int j=0; j<4; j++){
			int x1=allx[x[i]]+dx[j]*len,y1=ally[y[i]]+dy[j]*len;
			ans+=M[{x1,y1}];
   		}
	}
	cout << ans/2 << endl;
	return 0;
}

\(AT\_arc065\_d\)
https://www.luogu.com.cn/problem/AT_arc065_d
题解：考虑\(dp\)，设\(f(i,j)\)为最终前\(i\)个位置放了\(j\)个\(1\)的方案数。有转移\(f(i,j)=f(i-1,j)+f(i-1,j-1)\)，但还需考虑对每个\(i\)，\(j\)的取值范围。由于是任意排列，大胆猜想\(j\)的取值范围应该是连续的，于是只需确定\(j\)的上下确界即可。每次对\(l_i,r_i\)内数从小到大排序，即可得到下界，从大到小排序，即可得到上界，在此范围内\(dp\)即可。

#include <bits/stdc++.h>

using namespace std;

const int N=3010,P=1e9+7;

int n,m;
int s1[N],s2[N],f[N][N];
char s[N],t[N];

int main(){
	cin >> n >> m;
	for(int i=1; i<=n; i++) cin >> s[i];
	memcpy(t,s,sizeof s);
	for(int i=1; i<=m; i++){
		int l,r;
		cin >> l >> r;
		sort(s+l,s+r+1);
		sort(t+l,t+r+1);
		reverse(t+l,t+r+1);
	}
	for(int i=1; i<=n; i++){
		s1[i]=s1[i-1]+(s[i]=='1');
		s2[i]=s2[i-1]+(t[i]=='1');
	}
	f[0][0]=1;
	for(int i=1; i<=n; i++)
		for(int j=s1[i]; j<=s2[i]; j++)
			f[i][j]=(f[i-1][j]+f[i-1][j-1])%P;
	cout << f[n][s1[n]] << endl;	
	return 0;
}

标签：tmp,AtCoder,065,int,t1,Regular,My,id,allx
From： https://www.cnblogs.com/lastxuans/p/18651034

相关文章

  • Xshell 8 Build 0065中文免安装绿色版
    前言Xshell8是一个非常受欢迎的远程连接管理软件，它的界面简单易懂，用起来特别方便。能支持好多种连接方式，比如SSH1、SSH2、SFTP、TELNET等等，还有串行协议和其他一些高级功能，基本上你想连什么都能满足。而且，它还支持好多种不同的终端类型，比如VT100、VT220、XTERM、LINUX等等，适应面......
  • 题解：AtCoder [ARC176D] Swap Permutation
    题意原题链接给定一个长度为\(n\)的排列\(p\)，并执行以下操作\(m\)次：选择\(1\leqi<j\leqn\)，交换\(p_i\)和\(p_j\)。定义一个序列\(p\)的权值为\(\sum_{i=1}^{n-1}|p_i-p_{i-1}|\)。求在\(\binom{n}{2}^m\)种可能的操作后，\(p\)的价值之和。答案对\(998244353\)......
  • AtCoder Beginner Contest 386 补题
    E-MaximizeXOR题目大意给出\(n\)个数，要选\(k\)个使异或和最大。\(n\leq2\times10^5,k\leqn\)\(C_n^k\leq10^6\)思路由于那个组合数的性质，发现应该是直接深搜就可以的。可是发现T了。发现如果\(k\)很大那么还是不好处理。但是发现搜\(k\)个数和搜\(n-k\)个......
  • 关于此题E - Maximize XOR（Atcoder ABC 386）搜索技巧的一些总结
    传送门题目要求n个数中选k个数异或起来最大，我们想到字典树中最大异或和这一经典问题，但是很明显字典树只能解决任选两个数的最大异或，而此题是任选k个，那我们走投无路只能考虑爆搜。首先可以很容易写出一个暴力的搜索：voiddfs1(longlongpos,longlongsum,longlongkk){i......
  • AtCoder Beginner Contest 386（补题）
    AtCoderBeginnerContest386C-Operate1https://atcoder.jp/contests/abc386/tasks/abc386_c思路简单的条件判断题代码#include<bits/stdc++.h>typedefstd::pair<int,int>pii;#defineINF0x3f3f3f3f#defineMOD998244353usingi64=longlong;cons......
  • atcoder ABC385 部分题解
    G-CountingBuildings简要题义一个排列的\(L(P)\)为\(\sum_{i=1}^n[premax(i)=P_i]\)，即前缀最大值为自身的位置数，\(R(P)\)同理为后缀最大值。有多少个排列使得\(L(P)-R(P)=k\)题解假设\(n,k\)是同阶的。我们从\(n\)到\(1\)依次插入数，考虑朴素的DP：设\(f_{i,k......
  • AtCoder Beginner Contest 386 赛后总结
    赛时A-D。菜。A-C模拟即可。D先检查一下竖着的一列有没有出现：白黑或者黑白黑的情况。有的话一定不行。因为每个白点的右下角一定都得是白的，就相当于对下面的行数取后缀最小值，这个可以使用差分实现。点击查看代码#include<bits/stdc++.h>#definelllonglong#def......
  • [题解]（更新中）AtCoder Beginner Contest 386(ABC386) A~E
    A-FullHouse2容易发现，答案为Yes\(\iff\)输入中恰好出现了\(2\)种不同的数，可以用set等数据结构来计算不同元素的个数。点击查看代码#include<bits/stdc++.h>usingnamespacestd;set<int>se;signedmain(){ for(inti=1,a;i<=4;i++){ cin>>a; se.insert(a); } c......
  • AtCoder DP Contest(刷题记录)
    A-Frog1题意:给定\(n\)个石头，第\(i\)个石头的高度为\(h_i\).现在要求小青蛙从\(1\)号石头跳到\(n\)号石头，每次小青蛙可以选择从\(i\)号石头跳到\(i+1\)或\(i+2\)号石头，代价是起跳点与落点的高度差的绝对值。询问你最小代价。解法:\(dp[i]\)表示小青蛙跳到第号石头时的最小代......
  • AtCoder Regular Contests
    \[\begin{matrix}\color{#d9d9d9}\blacksquare\color{#D9C5B2}\blacksquare\color{#B2D9B2}\blacksquare\color{#B2ECEC}\blacksquare\color{#B2B2FF}\blacksquare\color{#ECECB2}\blacksquare\color{#FFD9B2}\blacksquare\color{#FFB2B2}\blacksqu......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99