文章目錄

• T1：CF1227G Not Same
• • solution
  • code
• T2：CF1364E X-OR
• • solution
  • code
• T3：CF1375H Set Merging
• • solution
  • code

~~腦子是個(gè)好東西，希望人人都有

構(gòu)造真的不是個(gè)東西，看了一天視頻，沒有一道題會(huì)做~~

T1：CF1227G Not Same

點(diǎn)擊查看

solution

通過(guò)觀察樣例輸出，像01矩陣，事實(shí)證明，的確如此
將問(wèn)題轉(zhuǎn)化一下，變成矩陣思考
每一列的和一定，每一行互不相同

先考慮如果全是$n$，可以怎么構(gòu)造？？
——很簡(jiǎn)單
將$n\times n$的全是$1$的矩陣，挖掉對(duì)角線，然后再填一行全是$1$

這個(gè)做法提供了正解方向
考慮能否構(gòu)造出一個(gè)$n+1$行$n$列的符合要求的矩陣？？
——答案是當(dāng)然可以

將所有數(shù)字從大到小排序，對(duì)于第$i$列，就從第$i$行開始填
一直往下填，如果不夠就跳到第$1$行再繼續(xù)填

---

簡(jiǎn)單證明一下，為什么這么填就保證了行行之間互不相同？？——反證法

假設(shè)第$i$行和第$j$行相同$(i<j)$，用$(i,j)$表示第$i$行第$j$列

必有$(i,j)=1,(j,i)=1$
第$j$行和第$i$行的$j$列都為$1$，表明$a_j>1$

思考$i+1$列，有$a_i\ge a_{i+1}$
因?yàn)樗袛?shù)字取值$[1,n]$，而我們構(gòu)造的矩陣為$n+1$行，所以必有$(i,i+1)=0$
對(duì)應(yīng)過(guò)去必有$(j,i+1)=0$

$(i,i+1)=0$這個(gè)條件能說(shuō)明什么？？
——$a_i>a_{i+1}$，即$a_i$一定嚴(yán)格大于$a_{i+1}$

再思考$i+2$列，有$a_i>a_{i+1}\ge a_{i+2},(i+1,i+2)=0$
可以畫畫圖，發(fā)現(xiàn)如果想要$(i,i+2)=1$，必有$a_i=a_{i+1}$，矛盾
所以$(i,i+2)=0$，對(duì)應(yīng)有$(j,i+2)=0$

$(i+1,i+2)=0,(i,i+2)=0$這個(gè)條件又能說(shuō)明什么？？
——$a_i>a_{i+1}>a_{i+2}$

以此類推，可以推出$a_i>a_{i+1}>...>a_{j?1}$
且$(j,i+1)=0,(j,i+2)=0...(j,j?1)=0$
關(guān)注$(j,j?1)=0$，翻譯一下：第$j?1$列的第$j$行為$0$
然而根據(jù)我們的規(guī)則，第$j?1$列應(yīng)當(dāng)從$j?1$行開始填
于是得到$a_{j?1}=1$，又因?yàn)榕判蚴菑拇蟮叫?#xff0c;$a\in [1,n]$，所以$a_{j?1}=a_j=1$
與上面求出的$a_j>1$矛盾

故證明了構(gòu)造的不重復(fù)性

code

#include <cstdio> #include <algorithm> using namespace std; #define maxn 1005 int n, opt; int a[maxn], id[maxn], pos[maxn]; int matrix[maxn][maxn];bool cmp( int i, int j ) {return a[i] > a[j]; }int main() {scanf( "%d", &n );for( int i = 1;i <= n;i ++ )scanf( "%d", &a[i] ), id[i] = i;sort( id + 1, id + n + 1, cmp );for( int i = 1;i <= n;i ++ )pos[id[i]] = i;for( int i = 1;i <= n;i ++ )for( int j = 1;j <= a[id[i]];j ++ ) {int p = ( i + j - 1 ) > n + 1 ? i + j - n - 2 : i + j - 1;matrix[p][i] = 1;}printf( "%d\n", n + 1 );for( int i = 1;i <= n + 1;i ++ ) {for( int j = 1;j <= n;j ++ )printf( "%d", matrix[i][pos[j]] );printf( "\n" );}return 0; }

T2：CF1364E X-OR

點(diǎn)擊查看

solution

首先要了解$|$操作原理，兩個(gè)數(shù)的二進(jìn)制上對(duì)應(yīng)位置有一個(gè)為$1$，則$|$的結(jié)果便為$1$
故有兩個(gè)很顯然的結(jié)論

1.$0|x=x$
2.$x|y\ge x,x|y\ge y$

觀察總操作次數(shù)比$2n$多了幾次常數(shù)操作
于是乎，想到如何在$n$次查詢左右找出$0$所在的位置
然后將其余位置依次與$0$詢問(wèn)，就能得到位置上的數(shù)值大小了

接下來(lái)就只說(shuō)說(shuō)如何找$0$？？
——其實(shí)很簡(jiǎn)單
先隨便選兩個(gè)$x,y$，然后與剩下的數(shù)依次查詢
1.$P_x|P_y>P_y|P_z?P_x=0,x=z$
2.$P_x|P_y<P_y|P_z$，此時(shí)不進(jìn)行任何操作
3.$P_x|P_y=P_y|P_z?P_y=0,y=z$
這樣就鎖定了$x,y$中必有一個(gè)為$0$
再隨機(jī)$z$，或$P_z$的值更小的，便是$0$

code

#include <cstdio> #include <algorithm> using namespace std; #define maxn 5000 int n; int s[maxn], ans[maxn];int ask( int x, int y ) {printf( "? %d %d\n", x, y );fflush( stdout );int z;scanf( "%d", &z );return z; }int main() {scanf( "%d", &n );for( int i = 1;i <= n;i ++ )s[i] = i;random_shuffle( s + 1, s + n + 1 );int x = s[1], y = s[2];int val = ask( x, y ); for( int i = 3;i <= n;i ++ ) {int z = s[i];if( z == x || z == y ) continue;else {int w = ask( z, y );if( w < val ) val = w, x = z; else if( w == val ) y = z, val = ask( x, y);}}while( 1 ) {int z = s[rand() % n + 1];if( z == x || z == y ) continue;else {int v1 = ask( x, z );int v2 = ask( y, z );if( v1 == v2 ) continue;/*不能刪去!!可能出現(xiàn)x,y其中一個(gè)為0另外一個(gè)又恰好是z的子串(其二進(jìn)制上為1的每一位,z對(duì)應(yīng)的也是1)此時(shí)或起來(lái)的值都是z無(wú)法判斷誰(shuí)是0 */ if( v1 > v2 ) swap( x, y );break;}}for( int i = 1;i <= n;i ++ )if( i == x ) continue;else ans[i] = ask( i, x );printf( "!" );for( int i = 1;i <= n;i ++ )printf( " %d", ans[i] );return 0; } /* P(x)|P(y)>P(y)|P(z) ——> P(x)≠0 z代替x P(x)|P(y)<P(y)|P(z) 不操作 P(x)|P(y)=P(y)|P(z) ——> P(y)≠0 z代替y 最后隨機(jī)一個(gè)z來(lái)判斷x,y誰(shuí)是0 */

T3：CF1375H Set Merging

點(diǎn)擊查看

solution

先從最原始的暴力下手，即找到$[l,r]$里的每一個(gè)數(shù)，然后依次合并起來(lái)即可
——這當(dāng)然不是正解，但告訴我們單次查詢的操作次數(shù)上限為$n$
優(yōu)化暴力
考慮構(gòu)建權(quán)值線段樹，每個(gè)節(jié)點(diǎn)存儲(chǔ)節(jié)點(diǎn)區(qū)間$[l,r]$中每個(gè)值出現(xiàn)的位置，再?gòu)男〉酱笈判?br /> 線段樹上每個(gè)節(jié)點(diǎn)最多有$n^2$種不同本質(zhì)的查詢（即查詢的$l,r$不同）
可以套一個(gè)$map$來(lái)記錄（記憶化），存在即出現(xiàn)過(guò)，即有現(xiàn)成的集合使用

時(shí)間復(fù)雜度分析詳見第一篇

code

#include <map> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; #define maxn 100005 #define maxq 2200005 #define Pair pair < int, int > struct node {vector < int > num;map < Pair, int > Hash; }t[maxn << 2]; Pair vis[maxq]; int n, Q, cnt; int a[maxn], pos[maxn], ans[maxn];void build( int now, int l, int r ) {for( int i = l;i <= r;i ++ )t[now].num.push_back( pos[i] );sort( t[now].num.begin(), t[now].num.end() );if( l == r ) return;int mid = ( l + r ) >> 1;build( now << 1, l, mid ), build( now << 1 | 1, mid + 1, r ); }int query( int now, int l, int r ) {int left = lower_bound( t[now].num.begin(), t[now].num.end(), l ) - t[now].num.begin();int right = upper_bound( t[now].num.begin(), t[now].num.end(), r ) - t[now].num.begin() - 1;if( right < left ) return 0;if( left == right ) return t[now].num[left];int pos = t[now].Hash[make_pair( left, right )];if( pos ) return pos;int lson = query( now << 1, l, r ), rson = query( now << 1 | 1, l, r );if( ! lson || ! rson ) return t[now].Hash[make_pair( left, right )] = lson | rson;vis[++ cnt] = make_pair( lson, rson );return t[now].Hash[make_pair( left, right )] = cnt; }int main() {scanf( "%d %d", &n, &Q );cnt = n;for( int i = 1;i <= n;i ++ )scanf( "%d", &a[i] ), pos[a[i]] = i; build( 1, 1, n );for( int i = 1, l, r;i <= Q;i ++ ) {scanf( "%d %d", &l, &r );ans[i] = query( 1, l, r );}printf( "%d\n", cnt );for( int i = n + 1;i <= cnt;i ++ )printf( "%d %d\n", vis[i].first, vis[i].second );for( int i = 1;i <= Q;i ++ )printf( "%d ", ans[i] );return 0; }

總結(jié)

以上是生活随笔為你收集整理的[构造训练]CF1227G Not Same，CF1375H Set Merging，CF1364E X-OR的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。