问一道站外提
  • 板块灌水区
  • 楼主封禁用户
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/5/31 20:47
  • 上次更新2023/10/28 00:11:53
查看原帖
问一道站外提
716011
封禁用户楼主2022/5/31 20:47

代码如下

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N 100005
#define pii pair<int,int> 
#define x first
#define y second
#define mp make_pair
struct edge{pii a; int p; friend bool operator<(edge ac,edge ak){return ac.a.x*ak.a.y<ac.a.y*ak.a.x;}};
multiset<edge>s;
int t,n,l,d[N],v[N],vis[N];
pii ans;
pii lzm_is_sb(pii p,pii q){pii w=mp(p.x*q.y+p.y*q.x,p.y*q.y);return w;} 
pii dis(int p,int q){int lwz_1hao,lwz_2hao ;lwz_1hao=(d[p]-d[q]+l)%l ; lwz_2hao=(v[p]-v[q]);if(lwz_2hao<0)lwz_2hao=-lwz_2hao,lwz_1hao=l-lwz_1hao;return mp(lwz_1hao,lwz_2hao);}
bool check(pii k,pii t){return (k.x*t.y)>(k.y*t.x);}
int gcd(int x,int y){if(x>y)swap(x,y);while(x){int t=x;x=y%x;y=t;}return y;}
signed main(){cin>>t;while(t--){memset(vis,0,sizeof(vis));
		cin>>n>>l;for(int i=1;i<=n;++i)cin>>d[i];for(int i=1;i<=n;++i)cin>>v[i];ans=mp(0,1);for(int i=1;i<=n;++i)for(int j=i+1;j<=n;++j)s.insert(edge({dis(i,j),i}));
		while(!s.empty()){edge h=*s.begin();s.erase(s.begin()); if(vis[h.p])continue;vis[h.p]=1;ans=lzm_is_sb(ans,h.a);}int g=gcd(ans.x,ans.y);cout<<ans.x/g<<'/'<<ans.y/g<<endl;
	}
	return 0 ; 
}
2022/5/31 20:47
加载中...