ToB企服应用市场:ToB评测及商务社交产业平台

标题: codeforces 54B Cutting Jigsaw Puzzle题解 [打印本页]
作者: 铁佛    时间: 2022-9-5 08:55
标题: codeforces 54B Cutting Jigsaw Puzzle题解
详情请见：CSDN 阿史大杯茶   https://blog.csdn.net/weixin_66946161/article/details/126093709
题目意思

本题主要意思就是切成 一个个小块（小块的面积相同，但小块不相同），使小块之间互不相等，而且旋转之后相同，也算小块相同！例：
  1. AB    CA
  2. CD    DB
  3. 这两个是相同的!
复制代码
最后输出一共可以有多少种切法，使他们互不相等，然后输出切出的最小块 （这里要注意如果面积相等，则输出 a 小的那一个）比如说： 和 ，是要输出 !
思路：

这道题主要就是取块以及旋转判断：
取块：这个很简单，只需双重for循环，不停的枚举中的 a 和 b，如果a或b不能被N或M整除，那么是不行的所以要continue！
旋转判断：这个就比较麻烦了！首先就是旋转，旋转要么是180度、90度或270度。但是长方形只用转180度，因为长方形转其他两个度数会改变形状，那么和其他长方形就不可能相等！
180度旋转：
  1. A0,0 A0,1 A0,2        A2,2 A2,1 A2,0
  2. A1,0 A1,1 A1,2        A1,2 A1,1 A1,0
  3. A2,0 A2,1 A2,2        A0,2 A0,1 A0,0
复制代码
我们可以发现Ax,y旋转180度之后 x是从a-1->0，y是从b-1->0,所以我们就for循环按前面的顺序读进一个string里
  1. for (int xx=i-1;xx>=0;xx--){//i就是a
  2.     for (int yy=j-1;yy>=0;yy--){//j就是b
  3.         pc+=pzl[x+xx][y+yy];
  4.     }
  5. }
复制代码
90度旋转：
  1. A0,0 A0,1 A0,2        A2,0 A1,0 A0,0
  2. A1,0 A1,1 A1,2        A2,1 A1,1 A0,1
  3. A2,0 A2,1 A2,2        A2,2 A1,2 A0,2
复制代码
我们可以发现Ax,y旋转90度之后 x是从a-1->0，y是从0->b-1,但是我们发现每一行y没在变化，所以y的for循环要在外面
  1. for (int yy=0;yy<j;yy++){
  2.     for (int xx=i-1;xx>=0;xx--){
  3.         pc+=pzl[x+xx][y+yy];
  4.     }
  5. }
复制代码
270度旋转：
  1. A0,0 A0,1 A0,2        A0,2 A1,2 A2,2
  2. A1,0 A1,1 A1,2        A0,1 A1,1 A2,1
  3. A2,0 A2,1 A2,2        A0,0 A1,0 A2,0
复制代码
我们可以发现Ax,y旋转270度之后 x是从0->a-1，y是从b-1->0,但是我们发现每一行y没在变化，所以y的for循环要在外面
[code]for (int yy=j-1;yy>=0;yy--){        for (int xx=0;xx>N>>M;    mina=N,minb=M;    for (int i=0;i>pzl;    for (int i=1;i



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4