题解 CF1301D

· · 题解

题意

给你一个n\times m的网格,相邻的格子之间有双向边(来回两条边).

问是否能不经过重复的边的情况下从左上角出发遍历k条边.

1\le n,m\le 500,1\le k\le10^9

题解

将格子抽象为点,可以注意到所有点的点度均为偶数,整张图是一个欧拉图.

故可以走完所有2(2nm-n-m)条边.

一种简单可行的走法为:

$2.$向下走$n-1$步再向上走$n-1$步回到原处. $3.$向左走一步. $4.$重复$2,3$步骤$m-1$遍,回到左上角. $5.$向下走一步. $6.$向右走$m-1$步再向左走$m-1$步回到原处. $7.$重复$5,6$步骤$n-1$遍,到达左下角. $8.$向上走$n-1$步,回到左上角.

当所需要走的剩余步数不足以完成当前步骤时输出答案退出即可.

inline void Out(){
    printf("%d\n",(int)Ans.size());
    for(auto i:Ans)printf("%d %c\n",i.first,i.second);
    exit(0);
}
inline void Run(int s,char c){
    if(!s)return;
    if(k<=s)Ans.push_back({k,c}),Out();
    k-=s;Ans.push_back({s,c});
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    if(k>2*(2*n*m-n-m))return puts("NO"),0;
    puts("YES");Run(m-1,'R');
    for(int i=1;i<m;++i)
        Run(n-1,'D'),Run(n-1,'U'),Run(1,'L');
    fp(int i=1;i<n;++i)
        Run(1,'D'),Run(m-1,'R'),Run(m-1,'L');
    Run(n-1,'U');
return 0;
}