AtCoder Reguler Contest 109
A Hands
判断下是横向走两次更优还是纵向走更优，也可以建图。
B log
由于长度超过 \(n\) 的只有 \(n+1\)，考虑把 \(n+1\) 尽可能多的拆成其他长度的木材，二分即可。
正确性的证明可以考虑如果把 \(n+1\) 拆成 \(k\) 再把 \(k\) 拆成其余的木材，那么有可能有损耗，不会更优。
C Large RPS Tournament
\(n\) 很小，初始状态有循环节，每次的胜者也有循环节。暴力模拟最后输出第一个字符即可。
D L
分类讨论做法
规定一个 L 的位置为其对应 \(2\times 2\) 方格的左下角，设坐标 \((X,Y)\)。
\(X=0,Y=0\) 时只需判断是不是初始状态。
\(X=0\) 或 \(Y=0\) 时只有一个方向的移动，每次移动硬盘一个单位需要 \(2\) 步，容易发现因为初始状态贴近左下方，所以纵向移动时填满下面两格的步数不变，在向上移动时，结束状态填满下面两格是比填满上面两格少 \(1\) 的，而向下移动时，结束状态填满上面两格是比填满下面两格少 \(1\) 的。横向移动同理。
其余情况第一个样例已经给出的最优解法，以 \(X>0,Y>0\) 为例，可以用 \(1\) 步调整到合适状态，之后每次移动都可以在横向或纵向增加 \(1\)。实际上合适状态有两种，因此需要向上或向右再移动时会选择更优的一种。
|3|.|@|.|.| |3|.|.|.|.| |3|.|.|.|.| |3|.|.|.|.| |3|.|#|.|.|
|2|.|@|@|.| |2|.|.|.|.| |2|.|#|.|.| |2|.|#|#|.| |2|.|#|#|.|
|1|#|.|.|.| -> |1|#|#|.|.| -> |1|#|#|.|.| -> |1|.|#|.|.| -> |1|.|.|.|.|
|0|#|#|.|.| |0|#|.|.|.| |0|.|.|.|.| |0|.|.|.|.| |0|.|.|.|.|
|~|0|1|2|3| |~|0|1|2|3| |~|0|1|2|3| |~|0|1|2|3| |~|0|1|2|3|
-----------------------------------------------------------------------
|3|.|.|.|.| |3|.|.|.|.| |3|.|.|.|.| |3|.|.|.|.| |3|.|.|.|.|
|2|.|.|@|.| |2|.|.|.|.| |2|.|.|.|.| |2|.|.|#|.| |2|.|.|#|.|
|1|#|.|@|@| -> |1|.|#|.|.| -> |1|.|#|#|.| -> |1|.|#|#|.| -> |1|.|.|#|#|
|0|#|#|.|.| |0|#|#|.|.| |0|.|#|.|.| |0|.|.|.|.| |0|.|.|.|.|
|~|0|1|2|3| |~|0|1|2|3| |~|0|1|2|3| |~|0|1|2|3| |~|0|1|2|3|
上面的演示可以很好的证明两种合适状态分别需要向上或向右移动时的优越性。
其余三种情况类似，注意 \(X<0,Y<0\) 时调整到合适状态的最优方法是移动一格，而另两种情况本身处于合适状态，再横向纵向移动时的初始情况是 \(2\) 种而不是 \(3\) 种。
可能需要一个代码。
点击查看代码
int t;
int ax,ay,bx,by,cx,cy;
int mnX,mxX,mnY,mxY;
map<pair<int,int>,int> mp;
int type;
int main(){
t=read();
while(t--){
ax=read(),ay=read(),bx=read(),by=read(),cx=read(),cy=read();
mnX=min({ax,bx,cx}),mxX=max({ax,bx,cx}),mnY=min({ay,by,cy}),mxY=max({ay,by,cy});
mp.clear();
mp[make_pair(ax,ay)]=1,mp[make_pair(bx,by)]=1,mp[make_pair(cx,cy)]=1;
if(!mp[make_pair(mxX,mxY)]) type=0;//左下
else if(!mp[make_pair(mnX,mxY)]) type=1;//右下
else if(!mp[make_pair(mnX,mnY)]) type=2;//右上
else type=3;//左上
if(!mnX&&!mnY) printf("%d\n",(type!=0));
else if(!mnX&&mnY>0) printf("%d\n",2*mnY+(type>=2));
else if(!mnX&&mnY<0) printf("%d\n",-2*mnY-(type>=2));
else if(mnX>0&&!mnY) printf("%d\n",2*mnX+(type==1||type==2));
else if(mnX<0&&!mnY) printf("%d\n",-2*mnX-(type==1||type==2));
else if(mnX>0&&mnY>0){
int ans=1+2*min(mnX,mnY);
if(mnX==mnY) ans+=(type==2);
if(mnX>mnY) ans+=2*(mnX-mnY)-(!type||type==3);
if(mnX<mnY) ans+=2*(mnY-mnX)-(type<=1);
printf("%d\n",ans);
}
else if(mnX<0&&mnY>0){
int ans=2*min(-mnX,mnY);
if(-mnX==mnY) ans+=(type>=2);
if(-mnX>mnY) ans+=2*(-mnX-mnY)-(type==1||type==2);
if(-mnX<mnY) ans+=2*(mnY+mnX)+(type>=2);
printf("%d\n",ans);
}
else if(mnX<0&&mnY<0){
int ans=2*min(-mnX,-mnY);
if(-mnX==-mnY) ans+=(!type);
if(-mnX>-mnY) ans+=2*(-mnX+mnY)-(type==1||type==2);
if(-mnX<-mnY) ans+=2*(-mnY+mnX)-(type>=2);
printf("%d\n",ans);
}
else{
int ans=2*min(mnX,-mnY);
if(mnX==-mnY) ans+=(type==1||type==2);
if(mnX>-mnY) ans+=2*(mnX+mnY)+(type==1||type==2);
if(mnX<-mnY) ans+=2*(-mnY-mnX)-(type>=2);
printf("%d\n",ans);
}
}
return 0;
}
强大的转化做法
CF 上讨论区给出强大转化，在此复述一下。
定义一个 L 的重心为其对应直角三角形的重心（中线交点），这样每个 L 与每个重心一一对应，每个方格内含有 \(4\) 个重心，设重心坐标 \((ctX,ctY)\)。
根据上图可以看出在方格内的 \(3\) 种移动以及纵向或横向的 \(4\) 的移动都可以改变重心的位置，在八连通中只有左下方向是无法移动的。
假设八连通都可以移动，答案显然是 \(\max(|ctX|,|ctY|)\)，而左下方无法移动只存在于这条对角线上的点（注意到即便向右上方移动后也不能继续向右上方移动），因此当 \(ctX=ctY\) 时，可以先向单个方向移动再正常进行，答案会增加 \(1\)。（\(X=0\) 或 \(X=1\) 的情况除外）