文章目錄

• 考試復盤
• nmd

考試復盤

$T1$

我可太喜歡這種不要腦子的莽試題了！！

考場上猜的結論$d>3$無解

$d=1,d=2$的填法也試出來了

$d=3$只試出來了$n,m$是$3$的倍數的填法

但是另外的情況就$GG$了

最后交上去竟然還敲掛了(ˉ▽ˉ；)…烏雞鲅魚

這道題應該是這一段考試以來唯幾接近整正解的題目了

思考的：大討論，猜結論

$T2$

發現了很多小性質，想到了與根號有關的因子上面去

但是，呃emmmmmm~~

我不知道這個集合應該怎么填

所以找到的那些小性質并沒有什么卵用

（和善的微笑

思考的：質數/因子有關的各種算法，$DP$

$T3$

考場上敲得暴力——又掛了w(ﾟДﾟ)waz

鏈想的樹形$DP$但是也沒打，沒想明白

看到無環的部分分也想不出做法

思考的：$tarjan$強連通，樹形$DP$，暴力，后綴數組（純粹是看到了字符串比較

nmd

大討論好哇b（￣▽￣）d

• $n,m,d$都是奇數

  $?1$

• $d>3$

  $?1$

  在考場上肯定是猜的結論，就是反復試啊，就是連不出來

  從$(1,1)$先開始滿足，要往外連$>3$條線，肯定跨越了一個小正方格

  感性理解都感覺最后幾行會有點被困住連不出去

• $d=1$

  • 點數為奇數

    $?1$

  • 點數為偶數

    相鄰兩個連邊即可

• $d=2$

  • 點數為奇數
    
  • 點數為偶數
    

• $d=3$

  • $n=3$

    • $m=4$

      $?1$

    • $m=6$
      

    • $otherwise$

      排除掉兩邊的對稱，中間一定是偶數列，兩兩配對即可
      

  • $n,m$為偶數
    

  • $otherwise$

    • $m=5$
      
    • $otherwise$
      

代碼雖然有三百多行，7K大，但是是非常不動腦子的莽敲，請不要感到害怕，ㄟ(▔=▔)ㄏ

#include <cstdio> #include <iostream> using namespace std; int T, n, m, d; bool flag;void print( int x1, int y1, int x2, int y2 ) {if( flag ) printf( "%d %d %d %d\n", y1, x1, y2, x2 );else printf( "%d %d %d %d\n", x1, y1, x2, y2 ); }void subtask1() {printf( "%d\n", ( n * m ) >> 1 );if( n & 1 ) swap( n, m ), flag = 1;for( int i = 1;i <= n;i ++ )for( int j = 1;j <= m;j ++ )if( i & 1 )print( i, j, i + 1, j ); }void subtask2() {printf( "%d\n", ( n * m * d ) >> 1 );if( ( n & 1 ) && ( m & 1 ) ) {//redprint( 1, 1, 2, 2 );print( n, 1, n, 2 );//yellowfor( int i = 1;i < n;i ++ )print( i, 1, i + 1, 1 );//bluefor( int i = 3;i <= n;i ++ )for( int j = 2;j < m;j ++ )print( i, j, i, j + 1 );//greenfor( int i = 3;i <= n;i ++ )if( ( n - i + 1 ) & 1 )print( i, m, i - 1, m );elseprint( i, 2, i - 1, 2 );//pinkfor( int i = 2;i <= m;i ++ )print( 1, i, 2, i ); //orangefor( int i = 2;i < m;i ++ )if( i & 1 )print( 2, i, 2, i + 1 );elseprint( 1, i, 1, i + 1 );} else {if( n & 1 ) swap( n, m ), flag = 1;//redprint( 1, 1, 1, 2 );print( n, 1, n, 2 );//yellowfor( int i = 1;i < n;i ++ )print( i, 1, i + 1, 1 );//bluefor( int i = 1;i <= n;i ++ )for( int j = 2;j < m;j ++ )print( i, j, i, j + 1 );//greenfor( int i = 1;i < n;i ++ )if( i & 1 )print( i, m, i + 1, m );elseprint( i, 2, i + 1, 2 ); } }void subtask3_0() {if( n != 3 ) swap( n, m ), flag = 1;if( m == 4 ) {printf( "-1\n" );return;}printf( "%d\n", ( n * m * d ) >> 1 );//red print( 1, 1, 2, 1 );print( 2, 1, 3, 1 );print( 1, m, 2, m );print( 2, m, 3, m );for( int i = 1;i < m;i ++ )print( 1, i, 1, i + 1 ), print( 3, i, 3, i + 1 );if( m == 6 ) {print( 1, 1, 2, 2 );print( 2, 1, 2, 2 );print( 3, 1, 2, 2 );print( 1, 2, 2, 3 );print( 3, 2, 2, 3 );print( 3, 3, 2, 3 );print( 1, 6, 2, 5 );print( 2, 6, 2, 5 );print( 3, 6, 2, 5 );print( 1, 5, 2, 4 );print( 1, 4, 2, 4 );print( 3, 5, 2, 4 );print( 1, 3, 3, 4 );}else {//yellowprint( 1, 1, 2, 2 );print( 2, 1, 2, 2 );print( 3, 1, 2, 2 );print( 1, 2, 2, 3 );print( 1, 3, 2, 3 );print( 3, 2, 2, 3 );print( 1, 4, 2, 4 );print( 3, 3, 2, 4 );print( 3, 4, 2, 4 );//greenfor( int i = 5;i <= m - 4;i ++ )print( 1, i, 2, i ), print( 2, i, 3, i );//pinkfor( int i = 5;i <= m - 4;i ++ )if( i & 1 )print( 2, i, 2, i + 1 );//blueprint( 1, m, 2, m - 1 );print( 2, m, 2, m - 1 );print( 3, m, 2, m - 1 );print( 1, m - 1, 2, m - 2 );print( 1, m - 2, 2, m - 2 );print( 3, m - 1, 2, m - 2 );print( 1, m - 3, 2, m - 3 );print( 3, m - 3, 2, m - 3 );print( 3, m - 2, 2, m - 3 );} }void subtask3_1() {printf( "%d\n", ( n * m * d ) >> 1 );if( ! ( n & 1 ) && ! ( m & 1 ) ) {//redprint( 1, 1, 2, 2 );print( 1, m, 2, m - 1 );//yellowfor( int i = 1;i < m;i ++ )print( 1, i, 1, i + 1 );//greenfor( int i = 1;i <= m;i ++ )print( 1, i, 2, i );//bluefor( int i = 1;i <= m;i ++ )if( i & 1 )print( 2, i, 2, i + 1 );for( int i = 2;i <= n - 2;i ++ ) {//pinkprint( i, 1, i + 1, 1 );print( i, m, i + 1, m );if( i & 1 ) {//greyprint( i, 2, i + 1, 2 );print( i, m - 1, i + 1, m - 1 );//orangefor( int j = 1;j < m;j ++ )print( i, j, i, j + 1 );//purplefor( int j = 1;j < m;j ++ )print( i + 1, j, i + 1, j + 1 );}else {//blackfor( int j = 3;j <= m - 2;j ++ )print( i, j, i + 1, j );}}//redprint( n, 1, n - 1, 2 );print( n, m, n - 1, m - 1 );//yellowfor( int i = 1;i < m;i ++ )print( n, i, n, i + 1 );//greenfor( int i = 1;i <= m;i ++ )print( n, i, n - 1, i );//bluefor( int i = 1;i <= m;i ++ )if( i & 1 )print( n - 1, i, n - 1, i + 1 );}else {if( n & 1 ) swap( n, m ), flag = 1;if( m == 5 ) {//redprint( 1, 1, 2, 2 );print( 1, 1, 2, 1 );print( 2, 1, 2, 2 );print( 1, 2, 2, 3 );print( 1, 3, 2, 3 );print( 1, m, 2, m - 1 );//yellowfor( int i = 1;i < m;i ++ )print( 1, i, 1, i + 1 );//greenfor( int i = 4;i <= m;i ++ )print( 1, i, 2, i );//bluefor( int i = 4;i <= m;i ++ )if( ! ( i & 1 ) )print( 2, i, 2, i + 1 );for( int i = 2;i <= n - 2;i ++ ) {//pinkprint( i, 1, i + 1, 1 );print( i, m, i + 1, m );if( i & 1 ) {//greyprint( i, m - 1, i + 1, m - 1 );//orangefor( int j = 1;j < m;j ++ )print( i, j, i, j + 1 );//purplefor( int j = 1;j < m;j ++ )print( i + 1, j, i + 1, j + 1 );}else {//blackfor( int j = 2;j <= m - 2;j ++ )print( i, j, i + 1, j );}}//redprint( n, 1, n - 1, 1 );print( n, 1, n - 1, 2 );print( n - 1, 1, n - 1, 2 );print( n, 2, n - 1, 3 );print( n, 3, n - 1, 3 );print( n, m, n - 1, m - 1 );//yellowfor( int i = 1;i < m;i ++ )print( n, i, n, i + 1 );//greenfor( int i = 4;i <= m;i ++ )print( n, i, n - 1, i );//bluefor( int i = 4;i <= m;i ++ )if( ! ( i & 1 ) )print( n - 1, i, n - 1, i + 1 );}else {//redprint( 1, 1, 2, 2 );print( 2, 1, 2, 2 );print( 2, 3, 2, 4 );print( 1, m, 2, m - 1 );//yellowfor( int i = 1;i < m;i ++ )print( 1, i, 1, i + 1 );//greenfor( int i = 1;i <= m;i ++ )print( 1, i, 2, i );//bluefor( int i = 4;i <= m;i ++ )if( ! ( i & 1 ) )print( 2, i, 2, i + 1 );for( int i = 2;i <= n - 2;i ++ ) {//pinkprint( i, 1, i + 1, 1 );print( i, m, i + 1, m );if( i & 1 ) {//greyprint( i, 2, i + 1, 2 );print( i, 4, i + 1, 4 );print( i, m - 1, i + 1, m - 1 );//orangefor( int j = 1;j < m;j ++ )print( i, j, i, j + 1 );//purplefor( int j = 1;j < m;j ++ )print( i + 1, j, i + 1, j + 1 );}else {//blackprint( i, 3, i + 1, 3 );for( int j = 5;j <= m - 2;j ++ )print( i, j, i + 1 , j);}}//redprint( n, 1, n - 1, 2 );print( n - 1, 1, n - 1, 2 );print( n - 1, 3, n - 1, 4 );print( n, m, n - 1, m - 1 );//yellowfor( int i = 1;i < m;i ++ )print( n, i, n, i + 1 );//greenfor( int i = 1;i <= m;i ++ )print( n, i, n - 1, i );//bluefor( int i = 4;i <= m;i ++ )if( ! ( i & 1 ) )print( n - 1, i, n - 1, i + 1 );}} }int main() {freopen( "nmd.in", "r", stdin );freopen( "nmd.out", "w", stdout );scanf( "%d", &T );while( T -- ) {scanf( "%d %d %d", &n, &m, &d );if( ( d > 3 ) || ( ( d & 1 ) && ( n & 1 ) && ( m & 1 ) ) )printf( "-1\n" );else if( d == 1 )subtask1();else if( n == 1 || m == 1 )printf( "-1\n" );else if( d == 2 )subtask2();else if( n == 2 || m == 2 )printf( "-1\n" );else if( n == 3 || m == 3 )subtask3_0();elsesubtask3_1();flag = 0;}return 0; }

總結

以上是生活随笔為你收集整理的2021-4-1 多校省选模拟赛的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。