ZJT's Blog

Keep your determination.

[BZOJ 4788] [CERC2016] Bipartite Blanket

2018-1-16 10:192018-1-16 10:19
BZOJHall定理结论题

传送门

这题需要一个引理:一个点集$C=A\cup B$($A$为左边的点集,$B$为右边的点集)能被某个匹配覆盖,当且仅当$A$与右边的某个大小相等的点集$A'$之间存在完美匹配,且$B$与左边的某个大小相等的点集$B'$之间存在完美匹配。

证明大概是这样的:我们构造一个有向图,对于$A$到$A'$之间的匹配,我们从左往右连边,对于$B$到$B'$的匹配,我们从右往左连边。由于每个点入度、出度都至多为$1$,所以这个有向图一定是由一些环和链组成的。环的话一定是偶环,我们每两个点连一条匹配边就行了。链的末端一定不在$C$中,如果链长是偶数就两两连边,否则就可以不管最后一个点了。

有这个引理就好做了,我们直接用Hall定理判断两边点集的每一个子集符不符合引理的条件,然后把所有符合条件的排个序,双指针扫一遍就行了。

#include <bits/stdc++.h>
#define MAXN 30
#define MAXS 1100000
#define LL long long
#define lowbit(x) (x&(-x))
using namespace std;

int n,m;
int g[MAXN][MAXN];
int v1[MAXN],v2[MAXN],lim;
vector<int> s1,s2;

void gao1(){
    static int t[MAXN],h[MAXS],f[MAXS],s[MAXS];
    for(int i=1;i<=n;i++){
        t[i]=0;
        for(int j=1;j<=m;j++)
            if(g[i][j]) t[i]|=1<<(j-1);
    }
    s[0]=h[0]=0; f[0]=1;
    int maxs=1<<n;
    for(int i=1;i<maxs;i++){
        f[i]=1;
        s[i]=0;
        int c1=0,c2=0;
        for(int j=1;j<=n;j++)
            if(i&(1<<(j-1))){
                h[i]=h[i^(1<<(j-1))]|t[j];
                if(!f[i^(1<<(j-1))]) f[i]=0;
                s[i]+=v1[j];
                c1++;
            }
        for(int j=1;j<=m;j++)
            if(h[i]&(1<<(j-1)))
                c2++;
        if(c2<c1) f[i]=0;
    }
    for(int i=0;i<maxs;i++) if(f[i]) s1.push_back(s[i]);
}

void gao2(){
    static int t[MAXN],h[MAXS],f[MAXS],s[MAXS];
    for(int i=1;i<=m;i++){
        t[i]=0;
        for(int j=1;j<=n;j++)
            if(g[j][i]) t[i]|=1<<(j-1);
    }
    s[0]=h[0]=0; f[0]=1;
    int maxs=1<<m;
    for(int i=1;i<maxs;i++){
        f[i]=1;
        s[i]=0;
        int c1=0,c2=0;
        for(int j=1;j<=m;j++)
            if(i&(1<<(j-1))){
                h[i]=h[i^(1<<(j-1))]|t[j];
                if(!f[i^(1<<(j-1))]) f[i]=0;
                s[i]+=v2[j];
                c1++;
            }
        for(int j=1;j<=n;j++)
            if(h[i]&(1<<(j-1)))
                c2++;
        if(c2<c1) f[i]=0;
    }
    for(int i=0;i<maxs;i++) if(f[i]) s2.push_back(s[i]);
}

int main(){
#ifdef DEBUG
    freopen("4788.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        static char str[MAXN];
        scanf("%s",str+1);
        for(int j=1;j<=m;j++) g[i][j]=(str[j]=='1');
    }
    for(int i=1;i<=n;i++) scanf("%d",v1+i);
    for(int i=1;i<=m;i++) scanf("%d",v2+i);
    scanf("%d",&lim);
    gao1();
    gao2();
    sort(s1.begin(),s1.end());
    sort(s2.begin(),s2.end());
    LL ans=0;
    int now=s2.size()-1;
    for(int i=0;i<s1.size();i++){
        while(now>=0 && s1[i]+s2[now]>=lim) now--;
        ans+=s2.size()-1-now;
    }
    printf("%lld\n",ans);
    return 0;
}

查看详细内容

集训队作业之AGC007-C

2017-12-19 12:542017-12-19 12:54
集训队作业AtCoder结论题

传送门

结论题,可以发现每次推一个球之后,剩下的相邻两项的期望距离还是一个等差数列,所以递归下去算就行了。每次是$O(1)$的,所以总复杂度是$O(n)$的。

#include <cstdio>
#include <cstring>

long double solve(int n,long double a,long double d){
    if(!n) return 0;
    long double res=a+d*(2*n-1)/2;
    long double a1=(a*(n-1)*2+(a+2*d)+(3*a+3*d))/(2*n);
    long double a2=((a+d)*(2*(n-1)-1)+(a+3*d)*2+(3*a+6*d))/(2*n);
    return res+solve(n-1,a1,a2-a1);
}

int main(){
    int n;
    double a,d;
    scanf("%d%lf%lf",&n,&a,&d);
    printf("%.20lf\n",(double)solve(n,a,d));
}

查看详细内容

集训队作业之ARC066-E

2017-12-16 10:262017-12-16 10:26
集训队作业AtCoder结论题DP

传送门

有个结论就是三层以上的括号没有意义。。。有了这个结论随便DP一下就做完了。。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 100010
#define LL long long
using namespace std;

int n;
LL a[MAXN];
int b[MAXN];
LL f[MAXN][3];

inline void update(LL &x,LL y){ if(y>x) x=y; }

int main(){
    scanf("%d",&n);
    b[1]=1;
    scanf("%lld",a+1);
    for(int i=2;i<=n;i++){
        char c;
        while((c=getchar())==' ');
        b[i]=(c=='+'?1:-1);
        scanf("%lld",a+i);
    }
    memset(f,0x88,sizeof f);
    f[1][0]=a[1];
    for(int i=2;i<=n;i++)
        if(b[i]==1){
            update(f[i][0],f[i-1][0]+a[i]);
            update(f[i][0],f[i-1][1]+a[i]);
            update(f[i][0],f[i-1][2]+a[i]);
            update(f[i][1],f[i-1][1]-a[i]);
            update(f[i][1],f[i-1][2]-a[i]);
            update(f[i][2],f[i-1][2]+a[i]);
        }else{
            update(f[i][0],f[i-1][0]-a[i]);
            update(f[i][1],f[i-1][0]-a[i]);
            update(f[i][0],f[i-1][1]-a[i]);
            update(f[i][1],f[i-1][1]+a[i]);
            update(f[i][2],f[i-1][1]+a[i]);
            update(f[i][0],f[i-1][2]-a[i]);
            update(f[i][1],f[i-1][2]+a[i]);
            update(f[i][2],f[i-1][2]+a[i]);
        }
    printf("%lld\n",max(max(f[n][0],f[n][1]),f[n][2]));
    return 0;
}

查看详细内容

集训队作业之AGC001-D

2017-11-27 20:382017-11-27 20:38
集训队作业AtCoder结论题

传送门

又是结论题。。。傻逼退役选手已经什么结论都看不出来了。。。

有个结论就是只要$a$里面有多于两个奇数,就一定无解。把等价关系看作边,根据边数的关系就能证明这个结论。

在最多两个奇数的情况下,我们可以把奇数放在两端,然后把$a$里面回文串之间的分界点整体左移一位作为$b$的分界点。可以证明,这样是能满足条件的。

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

int n,m;
vector<int> s1,s2,s;

int main(){
    scanf("%d%d",&n,&m);
    int c0=0;
    for(int i=1;i<=m;i++){
        int t;
        scanf("%d",&t);
        if(t&1) s2.push_back(t);
        else s1.push_back(t);
    }
    if(s2.size()>2){
        puts("Impossible");
        return 0;
    }
    if(!s2.empty()){
        s.push_back(s2.back());
        s2.pop_back();
    }
    while(!s1.empty()){
        s.push_back(s1.back());
        s1.pop_back();
    }
    if(!s2.empty()){
        s.push_back(s2.back());
        s2.pop_back();
    }
    for(int i=0;i<s.size();i++) printf("%d ",s[i]);
    if(s.size()==1){
        if(s[0]==1){
            printf("\n1\n1");
            return 0;
        }
        printf("\n2\n%d %d\n",s[0]-1,1);
        return 0;
    }
    printf("\n%d\n",s[0]==1?s.size()-1:s.size());
    if(s[0]!=1) printf("%d ",s[0]-1);
    for(int i=1;i<s.size()-1;i++) printf("%d ",s[i]);
    if(s.size()>1) printf("%d\n",s.back()+1);
}

查看详细内容

集训队作业之AGC018-D

2017-11-22 12:352017-11-22 12:35
集训队作业AtCoder重心结论题

传送门

一直在想怎么利用重心边来做,结果找不到什么结论,后来发现直接用重心就行了。。。

为了让总长最长,我们考虑每条边经过次数的上界,一定是两边子树大小的较小值*2。我们要尽量取到这个上界。

我们先找到树的重心。如果重心的某个儿子的大小达到了$n/2$,则重心到这棵子树的边只能经过$n-1$次,其他边经过次数都能达到上界。否则,我们可以证明,在重心连出去的所有边中,肯定至少有一条边达不到上界。同时,我们也可以构造一种方案,使得只有一条重心连出的边走上界-1次,其他所有边都达到上界。所以找一下重心连出去的权值最小的边就行了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
#define MAXN 100010
using namespace std;

struct edge{
    int to,next,w;
    edge(int _to=0,int _next=0,int _w=0):to(_to),next(_next),w(_w){}
}e[MAXN<<1];

int n;
int g[MAXN],nume;
int size[MAXN],maxs[MAXN];
LL ve[MAXN];

void addEdge(int u,int v,int w){
    e[nume]=edge(v,g[u],w);
    g[u]=nume++;
}

void dfs(int x,int p){
    size[x]=1; maxs[x]=0;
    for(int i=g[x];~i;i=e[i].next)
        if(e[i].to^p){
            ve[e[i].to]=e[i].w;
            dfs(e[i].to,x);
            size[x]+=size[e[i].to];
            if(size[e[i].to]>maxs[x]) maxs[x]=size[e[i].to];
        }
    if(n-size[x]>maxs[x]) maxs[x]=n-size[x];
}

int main(){
#ifdef DEBUG
    freopen("D.in","r",stdin);
#endif
    memset(g,-1,sizeof g);
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        addEdge(u,v,w);
        addEdge(v,u,w);
    }
    dfs(1,0);
    LL ans=0;
    for(int i=2;i<=n;i++) ans+=2*ve[i]*min(size[i],n-size[i]);
    for(int i=2;i<=n;i++)
        if(size[i]==n-size[i]){
            ans-=ve[i];
            printf("%lld\n",ans);
            return 0;
        }
    int root=1;
    for(int i=1;i<=n;i++)
        if(maxs[i]<maxs[root]) root=i;
    int temp=0x7FFFFFFF;
    for(int i=g[root];~i;i=e[i].next)
        if(e[i].w<temp) temp=e[i].w;
    ans-=temp;
    printf("%lld\n",ans);
    return 0;
}

查看详细内容