Educational Codeforces Round 32 E. Maximum Subsequence

题目链接

题意：给你两个数n,m，和一个大小为n的数组。

让你在数组找一些数使得这些数的和模m最大。

解法：考虑 dfs但是，数据范围不允许纯暴力，那考虑一下折半搜索，一个从头开始往中间搜，一个从后往中间搜。在中间相遇的时间二分更新最大值即可。

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mp make_pair

#define pb push_back

using namespace std;

LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}

LL lcm(LL a,LL b){return a/gcd(a,b)*b;}

LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}

int n,m,cnt;

int a[37],b[37];

int ans;

int sum1[(1<<20)];

vector<int>v;

int main(){

	ios::sync_with_stdio(false);

	cin>>n>>m;

	for(int i=0;i<n;i++)cin>>a[i],a[i]%=m,ans=max(ans,a[i]);

	for(int i=0;i<(1<<(n/2));i++){

		for(int j=0;j<n/2;j++)if(i&(1<<j))sum1[i]=(0ll+sum1[i]+a[j])%m;

		ans=max(ans,sum1[i]);

		v.pb(sum1[i]);

	}

	sort(v.begin(),v.end());

	for(int i=n/2;i<n;i++)b[cnt++]=a[i];

	for(int i=0;i<(1<<cnt);i++){

		int A=0;

		for(int j=0;j<cnt;j++)if((1<<j)&i)A=(0ll+A+b[j])%m;

		ans=max(ans,A);

		auto pos=upper_bound(v.begin(), v.end(),m-A-1);

		pos--;

		ans=max(1ll*ans,(0ll+A+(*pos))%m);

	}

	cout<<ans%m;

	return 0;

}

巴特西

Educational Codeforces Round 32 E. Maximum Subsequence

最新文章

热门文章