20181016测试


T1题意


有多少个非空子集,能划分成和相等的两份。


Solution


BZOJ2679 折半搜索


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;
}

点我回到主页

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google+ photo

You are commenting using your Google+ account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s