题目链接：点击查看
题目大意：初始时给出一个长度为 n 的序列，每个位置 a[ i ] = i ，再给出一个映射 f( x , y ) = z，现在规定每次操作可以使得：
t = f( a[ i ] , a[ j ] )a[ i ] = ta[ j ] = t对于完全相同的 x 和 y，得到的 f( x , y ) 是相同的
现在需要给出一种操作顺序，使得无论映射 f 如何定义，最后都能使得整个序列最多有两种不同的元素
题目分析：自己手玩一下不难发现，如果 n 是 2 的幂次的话，总是有办法可以将其变为同一种元素的，以 n = 8 为例：
1 2 3 4 5 6 7 89 9 10 10 11 11 12 1213 13 13 13 14 14 14 1415 15 15 15 15 15 15 15这样可以类比于 st 表的思想，找出最大的小于等于 n 的 2 的幂次记为 k，对于区间 ( 1 , 1 + k - 1 ) 和 ( n - k + 1 , n ) 进行上述操作，就可以保证所有的 n 个元素都能被覆盖到，且最后最多有两种不同的元素了
因为对应的过程比较麻烦，写分治的话相对比较简单一些，时间复杂度是 nlogn 级别的，换句话说最后的答案也是 nlogn 级别的
代码：
//#pragma GCC optimize(2) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> using namespace std; typedef long long LL; typedef unsigned long long ull; const int inf=0x3f3f3f3f; const int N=2e5+100; vector<pair<int,int>>ans; void dfs(int l,int r) { if(l==r) return; int mid=l+r>>1; dfs(l,mid); dfs(mid+1,r); for(int i=l,j=mid+1;i<=mid;i++,j++) ans.emplace_back(i,j); } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false); int n; scanf("%d",&n); int p=1; while(p*2<=n) p*=2; dfs(1,1+p-1); if(n!=p) dfs(n-p+1,n); printf("%d\n",ans.size()); for(auto t:ans) printf("%d %d\n",t.first,t.second); return 0; }
