ABC D题求调
  • 板块学术版
  • 楼主rqzhangzehao
  • 当前回复1
  • 已保存回复1
  • 发布时间2025/8/30 21:47
  • 上次更新2025/8/31 14:31:27
查看原帖
ABC D题求调
1219848
rqzhangzehao楼主2025/8/30 21:47
#include<bits/stdc++.h>
#define int long long
using namespace std;
int rt,ct,ra,ca,n,m,l;
struct node{
	int xr,xc,st;
}a[1000005],b[1000005];
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin>>rt>>ct>>ra>>ca>>n>>m>>l;
	int diffr=rt-ra,diffc=ct-ca;
	for(int i=1;i<=m;i++){
		char s;
		cin>>s;
		int x;
		cin>>x;
		if(s=='U')a[i]={-1,0,x};
		else if(s=='D')a[i]={1,0,x};
		else if(s=='L')a[i]={0,-1,x};
		else a[i]={0,1,x};
	}
	for(int i=1;i<=l;i++){
		char s;
		cin>>s;
		int x;
		cin>>x;
		if(s=='U')b[i]={-1,0,x};
		else if(s=='D')b[i]={1,0,x};
		else if(s=='L')b[i]={0,-1,x};
		else b[i]={0,1,x};
	}
	int ans=0;
	int i=1,j=1,oks=0,okt=0;
	while(i<=m&&j<=l){
		auto s=a[i],t=b[j];
		int sta=max({oks,okt}),ed=min({oks+s.st-1,okt+t.st-1,n-1});
		if(sta<=ed){
			int c=s.xc-t.xc,r=s.xr-t.xr;
			if(!c&&!r){
				if(!diffr&&!diffc){
					ans+=ed-sta+1;
				}
			}
			/*
			o-----o
			7-1=6;
			6/2=3->3步
			*/
			else if(!c){
				if(!diffc&&diffr%r==0&&r!=0){
					if(sta<=(-diffr)/r&&(-diffr)/r<=ed)ans++;
				}
			}
			else if(!r){
				if(!diffr&&diffc%c==0&&c!=0){
					if(sta<=(-diffc)/c&&(-diffc)/c<=ed)ans++;
				}
			}
			else{
				if(diffr%r==0&&diffc%c==0){
					if((-diffr)/r==(-diffc)/c&&sta<=(-diffc)/c&&(-diffc)/c<=ed&&sta<=(-diffr)/r&&(-diffr)/r<=ed)ans++;
				}
			}
		}
		int nows=oks+s.st,nowt=okt+t.st;
		if(nows<=nowt){
			diffc+=s.xc*s.st;
			diffr+=s.xr*s.st;
			oks=nows,i++;
		}
		else{
			diffc-=t.xc*t.st;
			diffr-=t.xr*t.st;
			okt=nowt,j++;
		}
	}
	cout<<ans;
	return 0;
}

样例全过,AC*11 https://atcoder.jp/contests/abc421/submissions/68945398

2025/8/30 21:47
加载中...