2020 ICPC 上海站(gym 102900) 题解
Problem H Rice Arrangement
这题相对而言比较简单。
假设我们直到了每一碗饭能分给的人的区间，然后就可以发现，将这些区间排出来一定是这样：
[-------]-----
--[-------]---
-----[-------]
也就是右端点随左端点递增而递增。
如果我们将饭和人链接一条线。
大概是这样：
o----o------o-----o
| \ / /
x------x---x---x---
可以发现不可能出现这样的情况：
o-o--------
V
/ \
x---x------
由于覆盖的人可以看作区间。
所以确定了第一个人吃哪一碗饭，其它的都确定了。
我们先假设所有的都想左转，然后将度数排序。可以发现一定是一段后缀向右转。
时间复杂度为\(O(N^2\log N)\)
/*
{
######################
# Author #
# Gary #
# 2021 #
######################
*/
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
//inline int read(){
// int x=0;
// char ch=getchar();
// while(ch<'0'||ch>'9'){
// ch=getchar();
// }
// while(ch>='0'&&ch<='9'){
// x=(x<<1)+(x<<3)+(ch^48);
// ch=getchar();
// }
// return x;
//}
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
/*}
*/
int n,t;
int Q;
int a[1001],b[1001];
int dist(int A,int B){
if(A<=B) return B-A;
return n-A+B;
}
void solve(){
scanf("%d%d",&n,&t);
rep(i,t) scanf("%d",&a[i]);
rep(i,t) scanf("%d",&b[i]);
sort(a,a+t);
sort(b,b+t);
int ret=INF;
rep(i,t)
{
vector<int> v;
rep(j,t){
v.PB(dist(b[(i+j)%t],a[j]));
}
sort(ALL(v));
int tmp=min(v[t-1],n-v[0]);
rep(j,t-1){
check_min(tmp,min(v[j]+v[j]+n-v[j+1],v[j]+2*n-v[j+1]-v[j+1]));
}
check_min(ret,tmp);
}
printf("%d\n",ret);
}
int main(){
scanf("%d",&Q);
while(Q--) solve();
return 0;
}
Problem L Traveling in the Grid World
考虑这题的加强：
\[T\leq 1e6,n,m\leq 1e18 \]也就是要\(O(1)\)回答询问。
首先可以发现如果\((n,m)=1\)则一步到达。
否则我们只需要走最近的折线就一定不会存在格点。可以证明最优折线和对角线形成的三角形及其内部不存在格点，否则可以调整法变成更优答案。
然后原问题就可以迎刃而解了，只要枚举横坐标，然后选择最靠近对角线的点就可以了，时间复杂度为\(O(N)\)。
但是这题可以做到更优。
设\(x,y=n/(n,,m),m/(n,m)\)。
一个结论：
靠对角线最近的格点中最靠近中点的最优。
根据叉积的定义：
就是这个值最小的点(a,b)：
\[x*b-y*m/(\sqrt {x^2+y^2}) \]后面的那个是常数，不用管，前面的那个最小值为\(1\)，直接exgcd求解就可以了。
可以发现，所有距离\(> 1/(\sqrt{x^2+y^2})\)的至少为那个距离的两倍。
根据中位线可以发现一定存在格点，所以距离最近的中最靠近中间的最优。
code:
/*
{
######################
# Author #
# Gary #
# 2021 #
######################
*/
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
//inline int read(){
// int x=0;
// char ch=getchar();
// while(ch<'0'||ch>'9'){
// ch=getchar();
// }
// while(ch>='0'&&ch<='9'){
// x=(x<<1)+(x<<3)+(ch^48);
// ch=getchar();
// }
// return x;
//}
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
/*}
*/
int T;
LL exGcd(LL a,LL b,LL &x,LL &y)
{
if(b==0)
{
x = 1;
y = 0;
return a;
}
LL r = exGcd(b,a%b,x,y);
LL t = x; x = y;
y = t-a/b*y;
return r;
}
double dist(int x,int y){
double tmp=1ll*x*x+1ll*y*y;
return sqrt(tmp);
}
void solve(){
int x,y;
scanf("%d%d",&x,&y);
if(__gcd(x,y)==1){
printf("%.10f\n",dist(x,y));
return;
}
int g=__gcd(x,y);
int n=x,m=y;
x=n/g;
y=m/g;
LL a,b;
exGcd(x,y,b,a);
a=-a;
LL need=max(0ll,max((x-a)/x,(y-b)/y));
a+=need*x;
b+=need*y;
need=min((a-1)/x,(b-1)/y);
a-=need*x;
b-=need*y;
double rest=1e18;
LL can=min((n-a)/x,(m-b)/y);
can/=2;
for(LL i=can-5;i<=can+5;++i){
LL xx,yy;
xx=a;
yy=b;
xx+=x*i;
yy+=y*i;
if(xx>=0&&yy>=0&&xx<=n&&yy<=m){
check_min(rest,dist(xx,yy)+dist(n-xx,m-yy));
}
}
printf("%.10f\n",rest);
}
int main(){
scanf("%d",&T);
while(T--) solve();
return 0;
}