警告：本文内容可能影响您思考的乐趣，观看前请三思 ---- 防雷页 ---- 第一题： 解 4x4 的数独，输出其字典序最小的一组解，以及解的个数 一般看到数独时，很容易会去思考能否用一般我们解数独时的方法 但是这样很难实作，毕竟要用一堆技巧交叉利用，也很容易漏掉或不小心写错 而难以 debug，因此这里必须借助电脑的运算能力，使用笨一点的方法 加上所求为所有解，也就是说可能有多重解的情形，这在手写上也是很不利的一点 一个最笨的想法是，在每一个空格填上 1~4 的数字，看会不会矛盾 对於不会矛盾的情形，去填下一个空格，矛盾就试其它数字，都试过了就回去改上一格 如果可以填到没有空格可以填，那麽表示我们找到了一组可行解 这里我们可以用递回的特性来解这一题 一开始我们先找出所有的空格，并建成一张表，假设表的大小是 n 则从 0 开始，对於每一个空格 i 试着填入 1~4 的数字，如果发现有数字可以填 那麽就填上去，并递回去填 i+1 格，直到 i==n 表示我们找到了一组解 所有可能都试过後，就 return 回去继续试上一格，如此反覆即可得到所有解 可以想像成「以第 i 格填上 j 为前提的情形，尝试第 i+1 格能够填些什麽」 实际画画看可以得到一个树状的展开图，这样对於它的运作原理应该会清楚一点 至於每行、每列和每个 2x2 的小区域都必须有 1~4 且恰出现一次 可以对於每行、每列记录 1~4 哪些数字出现过、哪些没有，例如 row[i][j] = 1 表示第 i 列数字 j 出现过，而 row[i][j] = 0 表示第 i 列数字 j 没出现过，等等，2x2 的小区域的话 会发现若座标用 0~3 则同一区域的格子，其 x/2 和 y/2 会相同 弄个图帮助思考一下 0 1 2 3 0 A A B B 1 A A B B 2 C C D D 3 C C D D 所以用 block[i][j][k] 记录 x/2=i, y/2=j 的小区域，k 是否出现过即可 注意在读入时需注意，有可能出现 <0 或 >4 的数字，这种情况一律视为无解 也有可能一列或一行已被填了重覆的数字，这些情形也要注意一下 ---- 第二题 对一个只包含 +、- 运算子且系数、幂次均为整数的多项式微分 由於给的输入并不保证降幂排序，所以要在分析并存下每一项微分後的结果 最後依幂次排序，排序的部份使用 qsort() 即可，困难的部份在於如何分析 这里想办法抓出每一项的共通点并想办法切开它们 从字串的第一个字开始，要嘛是正负号，要嘛是数字 如果是数字那系数一定是正的，是正负号就记一下正负 接下来处理掉这个数字後，看数字的下一个符号为何 如果不是 x 就可以忽略，因为一定是常数项，微分後就不见了 如果是 x 那麽下一个字要嘛是^，要嘛是正负号 如果是正负号，因为没有 ^ 所以可以认定它是和下一项连接的符号 恰可当作下一项系数正负的判断依据，所以当作是下一项的东西 如果有 ^ 那麽接下来要嘛是正负号，要嘛是数字，之後就一定是和下一项连接的符号了 就这样慢慢分析即可，每项都对它微分後存起来，最後对分析出来的资料排序 要小心有可能出现 x^0 这种东西 ---- 第三题 依 bmi 排序并输出前十高者 bmi 算法：体重(kg) / 身高^2 (m) qsort() 一下，再输出前十笔即可 比较方式的话，由於身高的单位转换会抵消，所以可以不用管它 将 a/b 与 c/d 的比较转换成 a*d, b*c 的比较也可以避免误差的出现 一个比较好的方式是，每输入一笔资料就把它和现有的资料比较，然後保留前十高的 在过程中无法保持在前十高的，拿掉也不影响结果 这样每笔资料只要找到在现有资料中，自己是第几高，就可以直接放在那个位置 其它比自己低的就往後挪一格，然後限制长度永远 <= 10 即可，这样效率是比较高的 ---- 第四题 用 出门 => 吃掉 dorayaki => 回家 => 出门 => 吃掉 dorayaki => 回家 => ... 的策略来吃 dorayaki 问最多可以吃多少个 所以吃掉每个 dorayaki 後，hp 的变化量是 -(2dis - g)，且能吃到的前提是 hp > dis 越远的能吃的条件越高，变化量也越不利，因此先吃较近的铜锣烧并不会比较差 也就是说，可能先吃近的铜锣烧能导致可以吃较远且原本吃不到的铜锣烧 反之却不可能，因为吃不到近的铜锣烧就一定吃不到远的铜锣烧 所以从最近的开始吃，吃到没 hp 可以吃下一个铜锣烧为止即可 先算出距离并排序就可以了 ---- 第五题 以 a < z < b < ... 的顺序来对字串排序 如果要硬写会有点麻烦，不过这里我们可以自己写一个 strcmp() 用自己的方式比 为方便起见，可以先赋予每个字母一个 value，之後用这个 value 来比较字母大小 建表的方式可以如下： for(i='a', j='z', k=1; i<=j; i++, j--) { tbl[i] = k; k++; if(i != j) { tbl[j] = k; k++; } } 如此即可得到每个字母的 value，再以这 value 代替 ASCII 码写个自定的 strcmp() 就可以解决这题了，一样使用 qsort() 排序即可 ---- 为直接 end 的人着想，安全起见，故留此文末防雷页 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.91.122