T1 毛一琛

考慮折半搜索，每個數的系數只能是-1，0，1之中的一個，因此可以先通過的搜索分別搜索出兩邊每個狀態的和以及數字的選擇情況。

然后將后一半的狀態按照和排序，枚舉前一半的每一個選擇情況的狀態，將該選擇情況下所有狀態按和排序，然后通過雙指針求出所有合法狀態。

1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 5 int n,mid,ans,a[30],num,tmp[1<<11]; 6 int tot=1,pre[60010],son[60010],now[1<<11]; 7 bool b[1<<21]; 8 9 int cnt; 10 struct Node{int sum,set;}f[60010]; 11 12 bool cmp(Node a,Node b){return a.sum<b.sum;} 13 14 void DFS1(int dep,int sum,int set){ 15 if(dep==mid+1){ 16 tot++;pre[tot]=now[set]; 17 now[set]=tot;son[tot]=sum; 18 } 19 else{ 20 DFS1(dep+1,sum,set); 21 DFS1(dep+1,sum+a[dep],set|(1<<(dep-1))); 22 DFS1(dep+1,sum-a[dep],set|(1<<(dep-1))); 23 } 24 } 25 26 void DFS2(int dep,int sum,int set){ 27 if(dep==n+1){ 28 ++cnt; 29 f[cnt].sum=sum;f[cnt].set=set; 30 } 31 else{ 32 DFS2(dep+1,sum,set); 33 DFS2(dep+1,sum+a[dep],set|(1<<(dep-1))); 34 DFS2(dep+1,sum-a[dep],set|(1<<(dep-1))); 35 } 36 } 37 38 int main(){ 39 scanf("%d",&n);mid=n/2; 40 for(int i=1;i<=n;i++)scanf("%d",&a[i]); 41 DFS1(1,0,0);DFS2(mid+1,0,0); 42 sort(f+1,f+cnt+1,cmp); 43 for(int i=0;i<=(1<<mid)-1;i++){ 44 num=0; 45 for(int p=now[i];p;p=pre[p]) 46 tmp[++num]=son[p]; 47 sort(tmp+1,tmp+num+1); 48 for(int j=1,k=1;j<=cnt;j++){ 49 while(k<=num&&tmp[k]<f[j].sum) 50 k++; 51 if(k==num+1)break; 52 if(tmp[k]==f[j].sum) 53 b[i|f[j].set]=1; 54 } 55 } 56 for(int i=1;i<=(1<<n)-1;i++) 57 if(b[i])ans++; 58 printf("%d\n",ans); 59 return 0; 60 }

T2 毛二琛

考慮排列p中的每個數怎樣才能被移動到該到的地方。 問題轉化為一個大小為n-1的排列，某些地方限定了相鄰兩數的大小關系。 直接DP即可，fi表示前i個數，第i個數在前i個數中是第j小的。前綴和優化可以做到O(n^2)

?

T3 毛三琛

暴力枚舉x然后二分最大重量，復雜度為O(nPlogn)。

考慮對x枚舉的順序隨機一下，這樣枚舉到一個x時候，可以先去check一下是否比目前的最優解要優，如果是，那么再去二分，否則直接continue。 由于一個隨機排列中比前面所有數都大的數的數量期望為log，所以復雜度為O(nP+nlognlogP)。

我不會隨機算法，考場的時候只拿了暴力分。。哭暈

轉載于:https://www.cnblogs.com/olm2598827139/p/9800867.html

總結

以上是生活随笔為你收集整理的10.16 多校联测的全部內容，希望文章能夠幫你解決所遇到的問題。

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