Code
#include<map>
#include<set>
#include<list>
#include<queue>
#include<vector>
#include<string>
#include<time.h>
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define N 20
#define M 1024
#define E 60000
#define reg register
#define ll long long
#define inf 2147483647
#define lowbit(x) ((x)&-(x))
#define abs(x) ((x)<0?-(x):(x))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define isd(c) ('0'<=(c)&&(c)<='9')
#define isa(c) ('a'<=(c)&&(c)<='z')
#define isA(c) ('A'<=(c)&&(c)<='Z')
#define ckmax(a,b) ((a)=max((a),(b)))
#define ckmin(a,b) ((a)=min((a),(b)))
#define swap(a,b) ((a)==(b)?(a)=(b):((a)^=(b)^=(a)^=(b)))
using namespace std;
template<typename T> inline void read(T&x){T f=1;x=0;char c;
for (c=getchar(); !isd(c); c=getchar()) f=(c=='-')?-1:f;
for (; isd(c); c=getchar()) x=(x<<3)+(x<<1)+(c^48);x*=f;
}
template<typename T> inline void wt(T x,char c=0){char ch[(sizeof(T)+1)<<1];if (x<0) x=-x,putchar('-');
int t=-1; do ch[++t]=x%10+'0',x/=10; while(x); do putchar(ch[t]); while(t--); if (c!=0) putchar(c);
}
int n,n0,i,j,k,a[N],g[M],v[E],nxt[E],ed,m,q[M],ce,ans,vis[1<<N];
struct P{int s,S;}e[E];
inline bool cmp(const P&a,const P&b){return a.s<b.s;}
inline void dfsl(int x,int s,int S){
if(x==n0){v[++ed]=s;nxt[ed]=g[S];g[S]=ed;return;}
dfsl(x+1,s,S);dfsl(x+1,s+a[x],S|(1<<x));dfsl(x+1,s-a[x],S|(1<<x));
}
inline void dfsr(int x,int s,int S){
if(x==n){e[ce].s=s;e[ce++].S=S;return;}
dfsr(x+1,s,S);dfsr(x+1,s+a[x],S|(1<<x));dfsr(x+1,s-a[x],S|(1<<x));
}
int main(){
read(n);n0=(n+1)/2;
for(i=0;i<n;i++)read(a[i]);
dfsl(0,0,0),dfsr(n0,0,0);
sort(e+1,e+ce+1,cmp);
for(i=0;i<1<<n0;i++){
for(m=0,j=g[i];j;j=nxt[j])q[m++]=v[j];
sort(q,q+m);
for(j=k=0;j<ce;j++){
while(k<m&&q[k]<e[j].s)k++;
if(k==m)break;
if(q[k]==e[j].s)vis[i|e[j].S]=1;
}
}
for(i=1;i<1<<n;i++)if(vis[i])ans++;
return wt(ans),0;
}
T2题意
坑先挖着，搞明白了再填。
Solution
坑先挖着，搞明白了再填。
Code
坑先挖着，搞明白了再填。
T3题意
给你N个数，让你给这N个数加上x并对P取模，把这N个数操作后分成K堆，求值最大的那一堆的最小值。(给定N、P、K)
Solution
通过读入我们可以算出每个数变为0需要的x的值，然后就可以随机生成这个序列，枚举x，并不断的二分、判断，从而求出最优解。
Code
#include<map>
#include<set>
#include<list>
#include<queue>
#include<vector>
#include<string>
#include<time.h>
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define maxn 500010
#define reg register
#define ll long long
#define inf 2147483647
#define lowbit(x) ((x)&-(x))
#define abs(x) ((x)<0?-(x):(x))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define isd(c) ('0'<=(c)&&(c)<='9')
#define isa(c) ('a'<=(c)&&(c)<='z')
#define isA(c) ('A'<=(c)&&(c)<='Z')
#define ckmax(a,b) ((a)=max((a),(b)))
#define ckmin(a,b) ((a)=min((a),(b)))
#define swap(a,b) ((a)==(b)?(a)=(b):((a)^=(b)^=(a)^=(b)))
using namespace std;
template<typename T> inline void read(T&x){T f=1;x=0;char c;
for (c=getchar(); !isd(c); c=getchar()) f=(c=='-')?-1:f;
for (; isd(c); c=getchar()) x=(x<<3)+(x<<1)+(c^48);x*=f;
}
template<typename T> inline void wt(T x,char c=0){char ch[(sizeof(T)+1)<<1];if (x<0) x=-x,putchar('-');
int t=-1; do ch[++t]=x%10+'0',x/=10; while(x); do putchar(ch[t]); while(t--); if (c!=0) putchar(c);
}
ll ans;
int n,P,K,mx,a[maxn],d[maxn],A[maxn];
inline int ck(ll now){
if (mx>now) return 0;
ll s=a[1],t=1;
for (int i=2; i<=n; ++i)
if (s+a[i]>now){
if (++t>K) return 0;
s=a[i];
}else s+=a[i];
return 1;
}
int main(){
srand(time(NULL)),srand(rand()),srand(rand());
//freopen("moiezen.in","r",stdin);
//freopen("moiezen.out","w",stdout);
read(n),read(P),read(K);ans=1ll*n*P;
for (int i=1; i<=n; ++i) read(A[i]);
for (int i=1; i<=P; ++i) d[i]=i-1;
random_shuffle(d+1,d+P-1);
for (int now=1; now<=P; ++now){
mx=0;
for (int i=1; i<=n; ++i)
a[i]=A[i]+d[now],a[i]%=P,ckmax(mx,a[i]);
if (!ck(ans)) continue;
ll l=1,r=ans;
while (l<r){
ll mid=(l+r)>>1;
if (ck(mid)) r=mid;
else l=mid+1;
}
ans=r;
}
wt(ans,'\n');
return 0;
}
