当前位置:网站首页>AtCoder Beginner Contest 169(題解)

AtCoder Beginner Contest 169(題解)

2021-08-10 09:34:10 wx6110fa547fd20

AtCoder Beginner Contest 169(題解)

E - Count Median

結論題

給定 n n n x i ∈ [ a i , b i ] x_i\in[a_i,b_i] xi[ai,bi],求中比特數的個數。

定義: k = ⌊ n 2 ⌋ k=\lfloor\dfrac{n}{2}\rfloor k=2n,對 a , b a,b a,b進行排序後,為 a k + 1 a_{k+1} ak+1 a i a_i ai的中比特數, b k + 1 b_{k+1} bk+1 b i b_i bi的中比特數。

1. n n n為奇數,則範圍是 [ a k + 1 , b k + 1 ] [a_{k+1},b_{k+1}] [ak+1,bk+1]

2. n n n為偶數,定義則範圍是 [ a k + a k + 1 , b k + b b + k + 1 ] [a_{k}+a_{k+1},b_k+b_{b+k+1}] [ak+ak+1,bk+bb+k+1]


F - Knapsack for All Subsets

轉移與物品個數有關的背包問題

考慮令 d p [ i ] [ j ] dp[i][j] dp[i][j] i i i個物品答案為 j j j的方案數。目標是 d p [ n ] [ s ] dp[n][s] dp[n][s]

初始 d p [ 0 ] [ 0 ] = 1 × 2 n − 0 = 2 n dp[0][0]=1\times 2^{n-0}=2^n dp[0][0]=1×2n0=2n

有轉移方程: d p [ i ] [ j ] = ( d p [ i ] [ j ] + d p [ i − 1 ] [ j − a [ i ] ] 2 ) dp[i][j]=(dp[i][j]+\dfrac{dp[i-1][j-a[i]]}{2}) dp[i][j]=(dp[i][j]+2dp[i1][ja[i]])

因為每多選一個物品,剩餘未選的物品數就少一,而方案數與 2 n − k 2^{n-k} 2nk有關, k k k為子集大小。

可以利用滾動數組倒序,優化到一維。

c o d e code code

// Problem: F - Knapsack for All Subsets
// Contest: AtCoder - AtCoder Beginner Contest 169
// URL: https://atcoder.jp/contests/abc169/tasks/abc169_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// Date: 2021-03-12 20:17:55
// --------by Herio--------

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull; 
const int N=3e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=998244353;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb emplace_back
#define SZ(a) (int)a.size()
#define IOS ios::sync_with_stdio(false),cin.tie(0) 
void Print(int *a,int n){
	for(int i=1;i<n;i++)
		printf("%d ",a[i]);
	printf("%d\n",a[n]); 
}
int n,s,a[N];
ll ksm(ll a,ll n,int m=mod){
	ll ans=1;
	while(n){
		if(n&1) ans=ans*a%m;
		a=a*a%m;
		n>>=1;
	}
	return ans;
}
ll dp[N];
int main(){
	scanf("%d%d",&n,&s);
	ll inv2=ksm(2,mod-2);
	dp[0]=ksm(2,n);
	//printf("--%lld %lld\n",dp[0],inv2);
	for(int i=1;i<=n;i++){
		int x;scanf("%d",&x);
		for(int j=s;j>=x;j--)
			dp[j]=(dp[j]+dp[j-x]*inv2%mod)%mod;
	}printf("%lld\n",dp[s]);
	return 0;
}

      
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.
  • 33.
  • 34.
  • 35.
  • 36.
  • 37.
  • 38.
  • 39.
  • 40.
  • 41.
  • 42.
  • 43.
  • 44.
  • 45.
  • 46.
  • 47.
  • 48.

版权声明
本文为[wx6110fa547fd20]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/08/20210810093345030M.html