互联网网站案例,平台公司市场化转型,建站教程的特点,制作网页网站哪个好用文章目录T1#xff1a;CF1227G Not SamesolutioncodeT2#xff1a;CF1364E X-ORsolutioncodeT3#xff1a;CF1375H Set Mergingsolutioncode~~脑子是个好东西#xff0c;希望人人都有构造真的不是个东西#xff0c;看了一天视频#xff0c;没有一道题会做~~
T1#xff…
文章目录T1CF1227G Not SamesolutioncodeT2CF1364E X-ORsolutioncodeT3CF1375H Set Mergingsolutioncode~~脑子是个好东西希望人人都有构造真的不是个东西看了一天视频没有一道题会做~~
T1CF1227G Not Same
点击查看
solution
通过观察样例输出像01矩阵事实证明的确如此 将问题转化一下变成矩阵思考 每一列的和一定每一行互不相同
先考虑如果全是nnn可以怎么构造 ——很简单 将n×nn\times nn×n的全是111的矩阵挖掉对角线然后再填一行全是111
这个做法提供了正解方向 考虑能否构造出一个n1n1n1行nnn列的符合要求的矩阵 ——答案是当然可以
将所有数字从大到小排序对于第iii列就从第iii行开始填 一直往下填如果不够就跳到第111行再继续填 简单证明一下为什么这么填就保证了行行之间互不相同——反证法
假设第iii行和第jjj行相同(ij)(ij)(ij)用(i,j)(i,j)(i,j)表示第iii行第jjj列
必有(i,j)1,(j,i)1(i,j)1,(j,i)1(i,j)1,(j,i)1 第jjj行和第iii行的jjj列都为111表明aj1a_j1aj1
思考i1i1i1列有ai≥ai1a_i\ge a_{i1}ai≥ai1 因为所有数字取值[1,n][1,n][1,n]而我们构造的矩阵为n1n1n1行所以必有(i,i1)0(i,i1)0(i,i1)0 对应过去必有(j,i1)0(j,i1)0(j,i1)0
(i,i1)0(i,i1)0(i,i1)0这个条件能说明什么 ——aiai1a_ia_{i1}aiai1即aia_iai一定严格大于ai1a_{i1}ai1
再思考i2i2i2列有aiai1≥ai2,(i1,i2)0a_ia_{i1}\ge a_{i2},(i1,i2)0aiai1≥ai2,(i1,i2)0 可以画画图发现如果想要(i,i2)1(i,i2)1(i,i2)1必有aiai1a_ia_{i1}aiai1矛盾 所以(i,i2)0(i,i2)0(i,i2)0对应有(j,i2)0(j,i2)0(j,i2)0
(i1,i2)0,(i,i2)0(i1,i2)0,(i,i2)0(i1,i2)0,(i,i2)0这个条件又能说明什么 ——aiai1ai2a_ia_{i1}a_{i2}aiai1ai2
以此类推可以推出aiai1...aj−1a_ia_{i1}...a_{j-1}aiai1...aj−1 且(j,i1)0,(j,i2)0...(j,j−1)0(j,i1)0,(j,i2)0...(j,j-1)0(j,i1)0,(j,i2)0...(j,j−1)0 关注(j,j−1)0(j,j-1)0(j,j−1)0翻译一下第j−1j-1j−1列的第jjj行为000 然而根据我们的规则第j−1j-1j−1列应当从j−1j-1j−1行开始填 于是得到aj−11a_{j-1}1aj−11又因为排序是从大到小a∈[1,n]a∈[1,n]a∈[1,n]所以aj−1aj1a_{j-1}a_j1aj−1aj1 与上面求出的aj1a_j1aj1矛盾
故证明了构造的不重复性 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;
}T2CF1364E X-OR
点击查看
solution
首先要了解∣|∣操作原理两个数的二进制上对应位置有一个为111则∣|∣的结果便为111 故有两个很显然的结论 1.0∣xx0|xx0∣xx 2.x∣y≥x,x∣y≥yx|y\ge x,x|y\ge yx∣y≥x,x∣y≥y 观察总操作次数比2n2n2n多了几次常数操作 于是乎想到如何在nnn次查询左右找出000所在的位置 然后将其余位置依次与000询问就能得到位置上的数值大小了
接下来就只说说如何找000 ——其实很简单 先随便选两个x,yx,yx,y然后与剩下的数依次查询 1.Px∣PyPy∣Pz⇒Px≠0,xzP_x|P_yP_y|P_z\Rightarrow P_x≠0,xzPx∣PyPy∣Pz⇒Px0,xz 2.Px∣PyPy∣PzP_x|P_yP_y|P_zPx∣PyPy∣Pz此时不进行任何操作 3.Px∣PyPy∣Pz⇒Py≠0,yzP_x|P_yP_y|P_z\Rightarrow P_y≠0,yzPx∣PyPy∣Pz⇒Py0,yz 这样就锁定了x,yx,yx,y中必有一个为000 再随机zzz或PzP_zPz的值更小的便是000
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;/*不能删去!!可能出现x,y其中一个为0另外一个又恰好是z的子串(其二进制上为1的每一位,z对应的也是1)此时或起来的值都是z无法判断谁是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
最后随机一个z来判断x,y谁是0
*/T3CF1375H Set Merging
点击查看
solution
先从最原始的暴力下手即找到[l,r][l,r][l,r]里的每一个数然后依次合并起来即可 ——这当然不是正解但告诉我们单次查询的操作次数上限为nnn 优化暴力 考虑构建权值线段树每个节点存储节点区间[l,r][l,r][l,r]中每个值出现的位置再从小到大排序 线段树上每个节点最多有n2n^2n2种不同本质的查询即查询的l,rl,rl,r不同 可以套一个mapmapmap来记录记忆化存在即出现过即有现成的集合使用
时间复杂度分析详见第一篇
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;
}
