戴言老师有一天闲来无事，用1秒钟时间，随手切了18套题。这十八套题闪耀着戴言老师智慧的光芒飘向太空，多年后，它们成为了散落在宇宙中的十八大星系。0202年，太空旅行者duyi发现了它们，并穷尽必生精力游历了这十八个星系，将他的见闻整理成册。这就是「DY十八章」。
本套题来自正睿。under权限：19 csp-s 线上冲刺
旅行
考虑二分答案\(\text{mid}\)。那么，此时距离\(\geq 2\cdot \text{mid}\)的点之间就可以通过，否则就不能通过。我们反过来考虑：在所有距离\(<2\cdot \text{mid}\)的点之间连边，把上、下边界也看做两个“点”，那么，如果上、下边界之间连通，就说明有一段路被堵死了，当前\(\text{mid}\)无解。否则\(\text{mid}\)就是可以的。
但是二分答案复杂度太高。我们考虑这个过程等价于什么。
对于这张\(k+2\)个点的图，我们定义两点间的边权是它们欧几里得距离的一半。那么二分\(\text{mid}\)后，相当于只考虑所有边权\(<2\cdot \text{mid}\)的边，问有没有从上边界点（\(k+1\)）到下边界点（\(k+2\)）的路径。
在原图上，我们定义一条路径的长度，是路径上所有边边权的最大值。那么，\(\text{mid}\)无解，当且仅当存在一条从\(k+1\)到\(k+2\)的路径长度\(\leq \text{mid}\)（这样就被堵死了）。所以我们不用二分\(\text{mid}\)，而是直接求从\(k+1\)到\(k+2\)的最短路长度即可！
因为这个图非常特殊，点数很少而边数很多，所以可以直接用不加堆优化的dijkstra算法，时间复杂度\(O(k^2)\)。
参考代码（片段）：
const int MAXK=7000;
int n,m,K;
double dis[MAXK+5];
bool vis[MAXK+5];
struct Point_t{
int x,y;
}p[MAXK+5];
double get_dist(double x1,double y1,double x2,double y2){
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int main() {
cin>>n>>m>>K;
for(int i=1;i<=K;++i){
cin>>p[i].x>>p[i].y;
dis[i]=m-p[i].y;
}
dis[0]=m;
while(true){
int u=0;
for(int i=1;i<=K;++i)if(!vis[i] && dis[i]<dis[u])u=i;
if(!u){
cout<<setiosflags(ios::fixed)<<setprecision(10)<<dis[u]/2<<endl;
return 0;
}
vis[u]=1;
dis[0]=min(dis[0],max(dis[u],(double)p[u].y));
for(int i=1;i<=K;++i)if(!vis[i]){
dis[i]=min(dis[i],max(dis[u],get_dist(p[i].x,p[i].y,p[u].x,p[u].y)));
}
}
return 114514;
}
寻宝
乱搞做法
二分答案。
check时，每一轮，先把所有点把所有点random_shuffle一下。然后依次考虑每个点，如果从当前边界能走到该点，就直接走过去，然后立即更新边界，继续考虑后面的点。如果所有点都访问过，直接反回\(\texttt{true}\)。如果这一轮没走到任何点（边界没有被更新过），反回\(\texttt{false}\)。否则进行下一轮。
最坏时间复杂度是\(O(n^2\log x)\)。但可以AC。
参考代码（片段）：
bool check(long long mid){
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;++i){
if(p[i].x<=1 && p[i].y<=1){
vis[p[i].id]=1;
}
}
int curx=1,cury=1;
while(true){
random_shuffle(p+1,p+n+1);
bool allvis=true;
bool newpoint=false;
for(int i=1;i<=n;++i){
if(vis[p[i].id])continue;
allvis=false;
if(2LL*(max(0,p[i].x-curx)+max(0,p[i].y-cury))<=mid){
vis[p[i].id]=1;
newpoint=true;
curx=max(curx,p[i].x);
cury=max(cury,p[i].y);
}
}
if(allvis)return true;
if(!newpoint)return false;
}
}
正解
在任意的时刻，我们可以把“宝藏”分为四类：(1) 位于已经探索过的区域里的宝藏，(2) 位于区域右上角，(3) 位于区域正上方，(4) 位于区域正右方。
第(1)种可以直接加入，不需要新花费木棒。对于后面三种，我们想到一个贪心策略：算出加入每个点，需要新花费的木棒数，然后选花费最小的加入，并更新区域边界。考虑为什么这样贪心是对的。因为随着加点过程的进行，边界只会扩大不会缩小，所以加入每个点的代价只会不断减小。我们要最小化“新增数量的最大值”，所以显然每次选最小的加入是最优的。
那么问题转化为，如何快速选出花费最小的点。
考虑(2),(3),(4)三类点的花费分别是什么。假设当前已探索区域右上角为\((x_0,y_0)\)，新加入的点坐标为\((x_1,y_1)\)。那么，新加入第(2)类点的花费为\(2(x_1-x_0+y_1-y_0)\)。新加入第(3)类点的花费为\(2(y_1-y_0)\)。新加入第(4)类点的花费为\(2(x_1-x_0)\)。
对于第(3)类点，我们相当于对于一个横坐标的前缀，求里面\(y\)坐标最小的点。同理，对于第(4)类点，我们相当于对一个纵坐标的前缀，求里面\(x\)坐标最小的点。当然，这里面可能混杂着一些第(1)类的点，我们要支持把它们“删除”，下面会讲具体怎么做。
可以用两个小根堆维护。以第(3)类点的堆为例，这个堆里点按\(y\)坐标为关键字，每次弹出\(y\)坐标最小的。当已探索区域的\(x\)坐标扩大时，就把新加入的这些\(x\)坐标上的点放入这个堆里。当需要弹出堆顶元素时，用一个while循环，直到弹出的不是第(1)类为止（相当于用这种方法实现“把第(1)类点删除”的效果）。
对于第(2)类，可以不需要堆。一开始直接把所有点按\(x+y\)排序。用一个指针，初始时指向\(1\)。如果当前元素是第(1),(3),(4)类，就把指针\(\texttt{++}\)。直到找到第(2)类元素为止。仔细想想，第(2)类点不需要堆，是因为它们没有“横/纵坐标上一个前缀”这个限制，所以没有“加入”操作。直接用这个预先排好序的数组，指针指向的点，就相当于“堆顶”了。
每次，取(2),(3),(4)类的堆顶，比一比谁花费最小，就把谁加入。
时间复杂度\(O(n\log n)\)。
参考代码（片段）：
const int MAXN=3e5;
const ll INF=4e9;
int n,x[MAXN+5],y[MAXN+5];
int sorted_x[MAXN+5],sorted_y[MAXN+5],sorted_xy[MAXN+5];
bool vis[MAXN+5];
bool cmp_x(int i,int j){return x[i]<x[j];}
bool cmp_y(int i,int j){return y[i]<y[j];}
bool cmp_xy(int i,int j){return x[i]+y[i]<x[j]+y[j];}
int main() {
cin >> n;
for ( int i = 1 ; i <= n ; ++ i) {
cin >> x[i] >> y[i] ;
sorted_x[i] = sorted_y[i] = sorted_xy[i] = i ;
}
sort ( sorted_x + 1 , sorted_x + n + 1 , cmp_x ) ;
sort ( sorted_y + 1 , sorted_y + n + 1 , cmp_y ) ;
sort ( sorted_xy + 1 , sorted_xy + n + 1 , cmp_xy ) ;
priority_queue<pii>q_x,q_y;
int cur_x=1,cur_y=1;
int idx_x=0,idx_y=0,idx_xy=0;
for(int t=1;t<=n;++t){
while(idx_x+1<=n && x[sorted_x[idx_x+1]]<=cur_x){
++idx_x;
q_y.push(mk(-y[sorted_x[idx_x]],sorted_x[idx_x]));
}
while(idx_y+1<=n && y[sorted_y[idx_y+1]]<=cur_y){
++idx_y;
q_x.push(mk(-x[sorted_y[idx_y]],sorted_y[idx_y]));
}
while(idx_xy+1<=n && (vis[sorted_xy[idx_xy+1]] || x[sorted_xy[idx_xy+1]]<=cur_x || y[sorted_xy[idx_xy+1]]<=cur_y))
++idx_xy;
while(!q_x.empty() && vis[q_x.top().se])q_x.pop();
while(!q_y.empty() && vis[q_y.top().se])q_y.pop();
if(!q_x.empty() && -q_x.top().fi<=cur_x){
int res=q_x.top().se;
cout<<res<<" ";
vis[res]=1;
cur_x=max(cur_x,x[res]);
cur_y=max(cur_y,y[res]);
continue;
}
if(!q_y.empty() && -q_y.top().fi<=cur_y){
int res=q_y.top().se;
cout<<res<<" ";
vis[res]=1;
cur_x=max(cur_x,x[res]);
cur_y=max(cur_y,y[res]);
continue;
}
pair<ll,int>res=mk(INF,0);
if(!q_x.empty())
res=min(res,mk(2LL*(-q_x.top().fi-cur_x),q_x.top().se));
if(!q_y.empty())
res=min(res,mk(2LL*(-q_y.top().fi-cur_y),q_y.top().se));
if(idx_xy+1<=n)
res=min(res,mk(2LL*(x[sorted_xy[idx_xy+1]]-cur_x+y[sorted_xy[idx_xy+1]]-cur_y),sorted_xy[idx_xy+1]));
assert(res!=mk(INF,0));
cout<<res.se<<" ";
vis[res.se]=1;
cur_x=max(cur_x,x[res.se]);
cur_y=max(cur_y,y[res.se]);
}
return 0;
}
鞋子
我们先不考虑方向的问题，假设只要是相邻的左右脚就能匹配。那么，问题相当于求二分图最大匹配：左、右脚的格子分别是二分图的两边，两个格子相邻就连边。
然后考虑方向。如果有至少一只鞋子没有匹配，则可以通过它调整它周围所有鞋的方向。同理，也可以先通过它周围的鞋去调整更外面的鞋。所以最后一定能把每个格子调成任何我们想要的方向。
剩下的就是所有格子都匹配的情况。也就是\(nm\)为偶数，且最大匹配数为\(\frac{nm}{2}\)。根据上面的讨论，此时答案要么是\(\frac{nm}{2}\)，要么是\(\frac{nm}{2}-1\)（也就是空出一双鞋子用来调整别的鞋的方向）。发现，如果我们把四个方向编号为\(0,1,2,3\)，那么一次操作后，两个格子一个\(+1\)，一个\(-1\)（\(\bmod4\)意义下），总和\(\bmod4\)不变！于是我们猜想，所有格子如果能自己调整过来（答案等于\(\frac{nm}{2}\)），当且仅当它们总和\(\bmod 4\)与目标状态相等。而知道匹配关系以后，目标状态是很好计算的。
可以证明，这个结论是对的。具体来说，就是证明【所有完美匹配的权值和对\(4\)取模的结果相同】，以及【任意权值和对\(4\)取模后相同的状态是相互可达的】这两个结论。详见官方题解。
时间复杂度\(O(nm\sqrt{nm})\)。
参考代码（片段）：
const int MAXN=105,INF=1e9;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
string s1[MAXN],s2[MAXN];
int val[233];
int n,m,X1[MAXN],Y1[MAXN],X2[MAXN],Y2[MAXN];
bool inmap(int i,int j){return i>=1&&i<=n&&j>=1&&j<=m;}
int id(int i,int j){return (i-1)*m+j;}
struct EDGE{int nxt,to,w;}edge[2000005];
int head[10010],tot;
inline void add_edge(int u,int v,int w){
edge[++tot].nxt=head[u];edge[tot].to=v;edge[tot].w=w;head[u]=tot;
edge[++tot].nxt=head[v];edge[tot].to=u;edge[tot].w=0;head[v]=tot;
}
int dep[10010],cur[10010];
bool bfs(int s,int t){
queue<int>q;
q.push(s);
for(int i=1;i<=t;++i)dep[i]=0;
dep[s]=1;
while(!q.empty()){
int u=q.front();q.pop();
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].to;
if(edge[i].w&&!dep[v]){
dep[v]=dep[u]+1;
if(v==t)return 1;
q.push(v);
}
}
}
return 0;
}
int dfs(int u,int flow,int t){
if(u==t)return flow;
int rest=flow;
for(int &i=cur[u];i&&rest;i=edge[i].nxt){
int v=edge[i].to;
if(dep[v]==dep[u]+1&&edge[i].w){
int k=dfs(v,min(rest,edge[i].w),t);
if(!k){dep[v]=0;continue;}
edge[i].w-=k;
edge[i^1].w+=k;
rest-=k;
}
}
return flow-rest;
}
int eid[MAXN][MAXN][4];
int solve(){
tot=1;int s=n*m+1,t=n*m+2;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(s1[i][j]=='L'){
for(int k=0;k<4;++k){
int ii=i+dx[k],jj=j+dy[k];
if(inmap(ii,jj) && s1[ii][jj]=='R'){
add_edge(id(i,j),id(ii,jj),1);
eid[i][j][k]=tot;
}
}
}
}
}
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(s1[i][j]=='L')add_edge(s,id(i,j),1);
else add_edge(id(i,j),t,1);
}
}
int maxflow=0,tmp;
while(bfs(s,t)){
for(int i=1;i<=t;++i)cur[i]=head[i];
while(tmp=dfs(s,INF,t))maxflow+=tmp;
}
return maxflow;
}
int main() {
ios::sync_with_stdio(0);//syn!!!
cin>>n>>m;
for(int i=1;i<=n;++i){cin>>s1[i];s1[i]="@"+s1[i];}
for(int i=1;i<=n;++i){cin>>s2[i];s2[i]="@"+s2[i];}
val['U']=0;val['R']=1;val['D']=2;val['L']=3;
int ans=solve();
if((n*m)%2==0&&ans==n*m/2){
int v1=0,v2=0;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(s1[i][j]=='L'){
for(int k=0;k<4;++k){
if(eid[i][j][k] && edge[eid[i][j][k]].w){
//cout<<i<<" "<<j<<" "<<k<<endl;
v1+=val[(int)s2[i][j]]+val[(int)s2[i+dx[k]][j+dy[k]]];
v2+=k+k;
break;
}
}
}
}
}
if(v1%4!=v2%4)ans--;
}
cout<<ans<<endl;
return 0;
}