CFR 201 A. Clear Symmetry ( Ad hoc, Math )
題意:
一個方陣,初始所有值為 0,塞 1 進去,1 彼此不相鄰,且最後方陣必須上下、左右分別成對稱。給 1 的數量,求至少要邊長多少的方陣才能塞下。
資料規模:
1 的個數 1 ≤ X ≤ 100
解法:
先注意到因為必須對稱,奇數邊長的方陣一定可以容下比較多。接著,假設邊長 N 的方陣最多可以容下 v 個 1,奇數最中央的格子可以讓我們 -1,中央列 / 行也能讓我們 -2,顯然亂做也可以做很多次 -4,因此這樣的方陣一定可以讓我們做所有滿足 4k, 4k - 1, 4k - 2, 4k - 1 - 2 = 4k - 3, k 為整數且結果不大於 v 的所有 1 的置放。因此只要算最小的奇數邊長方陣,最多可放的 1 不少於需要放的 1。但要特別注意,當 X 為 3 的時候是個例外,因為 3 * 3 的方陣無法做 -2 的操作。
時間 / 空間複雜度:
O( N ) / O( 1 )
需要注意:
抽象的構造題,一定要想清楚基層( 最小的幾組測資 )。
int X; void init(){ cin >> X; } void solve(){ if( X == 3 ) cout << 5 << endl; else{ for( int i = 1; ; i += 2 ){ int maxc = ( i + 1 ) / 2 * ( ( i + 1 ) / 2 ) + i / 2 * ( i / 2 ); if( maxc >= X ) cout << i << endl, exit( 0 ); } } }