傳送門

文章目錄

• 題意：
• 思路：

題意：

給你一個數組$a$，保證$a$中每個數都互不相同，讓你構造一個數組$b$，滿足對于任意的$S=x_1,x_2,...,x_k,1\le x_i\le n,0\le k<n$，都有${\sum }_{i=1}^k{a}_{x_i}={\sum }_{i=1}^k{b}_{x_i}$.

$1\le n\le 22,0\le a_i\le 1e9$

思路：

千萬不要被數據范圍迷惑了，構造題有時候真的不能看數據范圍。

考慮$a$是有序的時候，那么$a$一定是一個嚴格遞增的序列，考慮將$a$集體向左移動一位，$a_1$到$a_n$的位置，我們將其視為$b$，容易證明這個時候$b$是合法的，下面給出證明。

首先，如果$S$不包含$n$的話，那么選出來的集合的和一定有${\sum }_{i=1}^k{a}_{x_i}<{\sum }_{i=1}^k{b}_{x_i}$，這個比較顯然，因為每個位置$b_i>a_i$。

如果選出來的位置包含$n$怎么辦？利用補集的思想，對于上面的每個集合$S$我們都做其補集$S^{\prime }$，此時$S^{\prime }$一定一一對應包含$n$的所有情況，不難發現，對于每個$S^{\prime }$我們都有${\sum }_{i=1}^k{a}_{x_i}>{\sum }_{i=1}^k{b}_{x_i}$，此時合法。

綜上所述，這個$b$數組在$a$遞增的時候構造出來是合法的。

對于$a$無序怎么辦？顯然只需要給相應位置分配$b$即可。

// Problem: B. Gluttony // Contest: Codeforces - Codeforces Round #446 (Div. 1) // URL: https://codeforces.com/problemset/problem/891/B // Memory Limit: 256 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native") //#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #include<random> #include<cassert> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid ((tr[u].l+tr[u].r)>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define db puts("---") using namespace std;//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); } //void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); } //void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII;const int N=1000010,mod=1e9+7,INF=0x3f3f3f3f; const double eps=1e-6;int n; int a[N]; int ans[N]; struct Node {int id,val;bool operator < (const Node &W) const {return val<W.val;} }b[N];int main() { // ios::sync_with_stdio(false); // cin.tie(0);scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i].val=a[i],b[i].id=i;sort(b+1,b+1+n); sort(a+1,a+1+n);for(int i=1;i<=n-1;i++) ans[b[i].id]=a[i+1];ans[b[n].id]=a[1];for(int i=1;i<=n;i++) printf("%d ",ans[i]);return 0; } /**/

總結

以上是生活随笔為你收集整理的Codeforces Round #446 (Div. 1) B. Gluttony 构造 + 补集思想的全部內容，希望文章能夠幫你解決所遇到的問題。

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