首要思路是构造辅助线性规划,若最优值为0则删除辅助变量得到存在初始可行解线性规划.

具体看代码吧.

#include<cstdio>
#include<cctype>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define inf 0x3f3f3f3f
struct Linear_Programming{
    static const int N=10010;
    static const int M=1010;
    int n,m,A[M][N],b[M],c[N],v,B[M],nB[N];
    int _c[N],_v,Bins[N+M],nBins[N+M],_nB[N];
    inline void pivot(int l,int e){
        int i,j;
        for(i=1;i<=n;++i)
            if(i!=e)
                A[l][i]/=A[l][e];
        b[l]/=A[l][e];
        A[l][e]=1/A[l][e];
        for(i=1;i<=m;++i)
            if(i!=l&&A[i][e]!=0){
                for(j=1;j<=n;++j)
                    if(j!=e)
                        A[i][j]-=A[i][e]*A[l][j];
                b[i]-=A[i][e]*b[l];
                A[i][e]*=-A[l][e];
            }
        for(i=1;i<=n;++i)
            if(i!=e)
                c[i]-=c[e]*A[l][i];
        v+=c[e]*b[l];
        c[e]*=-A[l][e];
        swap(B[l],nB[e]);
    }
    inline int Simplex(){
        int i,j,l,e,lim;
        while(1){
            for(e=0,i=1;i<=n;++i)
                if(c[i]>0){
                    e=i;
                    break;
                }
            if(!e)
                return v;
            for(lim=inf,i=1;i<=m;++i)
                if(A[i][e]>0&&lim>b[i]/A[i][e]){
                    l=i;
                    lim=b[i]/A[i][e];
                }
            if(lim==inf)
                return inf;
            pivot(l,e);
        }
    }
    inline bool init(){
        int i,j,l,e,min_b=inf;
        for(l=0,i=1;i<=m;++i)
            if(b[i]<min_b){
                min_b=b[i];
                l=i;
            }
        if(min_b>=0)
            return 1;
        nB[++n]=0;
        memcpy(_c,c,sizeof c);
        _v=v;
        memcpy(_nB,nB,sizeof nB);
        memset(c,0,sizeof c);
        v=0;
        c[n]=-1;
        for(i=1;i<=m;++i)
            A[i][n]=-1;
        pivot(l,n);
        if(Simplex()<0)
            return 0;
        else{
            for(i=1;i<=m;++i)
                if(B[i]==0){
                    for(j=1;j<=n;++j){
                        if(A[i][j]!=0)
                            pivot(i,j);
                        break;
                    }
                }
            for(i=1;i<=n;++i)
                if(nB[i]==0)
                    e=i;
            --n;
            for(i=e;i<=n;++i)
                nB[i]=nB[i+1];
            for(i=1;i<=m;++i)
                for(j=e;j<=n;++j)
                    A[i][j]=A[i][j+1];
            for(i=1;i<=n;++i)
                nBins[nB[i]]=i;
            for(i=1;i<=m;++i)
                Bins[B[i]]=i;
            memset(c,0,sizeof c);
            v=_v;
            for(i=1;i<=n;++i){
                if(nBins[_nB[i]])
                    c[nBins[_nB[i]]]+=_c[i];
                else{
                    v+=_c[i]*b[Bins[_nB[i]]];
                    for(j=1;j<=n;++j)
                        c[j]-=_c[i]*A[Bins[_nB[i]]][j];
                }
            }
            return 1;
        }
    }
}g;
 
int main(){
    int tim,typ;
    cin>>tim>>typ;
    int i,j;
    for(i=1;i<=tim;++i){
        scanf("%d",&g.b[i]);
        g.b[i]=-g.b[i];
    }
    int s,t,c;
    for(i=1;i<=typ;++i){
        scanf("%d%d%d",&s,&t,&c);
        for(j=s;j<=t;++j)
            g.A[j][i]=-1;
        g.c[i]=-c;
    }
    g.n=typ;
    g.m=tim;
    for(i=1;i<=g.n;++i)
        g.nB[i]=i;
    for(i=1;i<=g.m;++i)
        g.B[i]=g.n+i;
    g.init();
    cout<<-g.Simplex()<<endl;
    return 0;
}

题解:

首先我们用Fib贪心的找出一组解.

假如我们利用二进制存储得到的那组解.

例如15=13+2

就是(从小到大)010001,分别代表1,2,3,5,8,13.

由于我们知道由于Fib数列的性质,001等价于110.

所以我们需要知道找到的那组解一共能够变换出多少方案.

我们依次考虑得到的那组解中的每个1,令$f[i][0]$表示第$i$个一在变换后的方案中是$0$的方案数,$f[i][1]$同理.

我们首先观察001变换出110的性质,我们不难发现只能变换出这样的形式:

1->110->11010

即如果有$k$个空位,则有$\lfloor\frac{k}{2}\rfloor$种方案,知道了这些就不难dp了.

详情见代码.

代码:

#include<cstdio>
#include<cctype>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;
ll f[90][2];
ll fib[90];
int ins[90],cnt;
int main(){
	ll n;
	cin>>n;
	int i,j;
	for(fib[1]=1,fib[2]=2,i=3;i<=88;++i)
		fib[i]=fib[i-1]+fib[i-2];
	for(i=88;i>=1;--i)
		if(n>=fib[i])
			n-=fib[ins[++cnt]=i];
	f[cnt][1]=1;
	f[cnt][0]=(ins[cnt]-1)>>1;
	for(i=cnt-1;i>=1;--i){
		f[i][1]=f[i+1][0]+f[i+1][1];
		f[i][0]=f[i+1][0]*((ins[i]-ins[i+1])>>1)+f[i+1][1]*((ins[i]-ins[i+1]-1)>>1);
	}
	cout<<f[1][0]+f[1][1]<<endl;
	return 0;
}

题解:

首先暴力连边匹配肯定是不行的...

由于$200$以内的质数仅有$46$个,我们构造三类点$ab(p_1,p_2),ac(p_1,p_2),bc(p_1,p_2)$分别表示参数1能被$p_1$整除,参数2能被$p_2$整除,剩下的依此类推.

然后对于左侧的点向符合条件的中间点连边.

对于右侧的点从符合条件的中间点连边.

这样做事实上是边分组,很显然是正确的.

直接用dinic玩就行了.

代码:

#include<cstdio>
#include<cctype>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
 
#define inf 0x3f3f3f3f
 
struct Solver{
    static const int V=100010;
    static const int E=3000010;
    int head[V],next[E],flow[E],end[E],ind,d[V];
    inline void reset(){
        memset(head,-1,sizeof head);
        ind=0;
    }
    inline void addedge(int a,int b,int f){
        int q=ind++;
        end[q]=b;
        next[q]=head[a];
        head[a]=q;
        flow[q]=f;
    }
    inline void make(int a,int b,int f){
        addedge(a,b,f);
        addedge(b,a,0);
    }
    inline bool bfs(int s,int t){
        static int q[V];
        int fr=0,ta=0;
        memset(d,-1,sizeof d);
        d[q[ta++]=s]=0;
        while(fr!=ta){
            int i=q[fr++];
            for(int j=head[i];j!=-1;j=next[j])
                if(flow[j]&&d[end[j]]==-1)
                    d[q[ta++]=end[j]]=d[i]+1;
        }
        return d[t]!=-1;
    }
    inline int dinic(int p,int t,int Maxflow){
        if(p==t)
            return Maxflow;
        int last=Maxflow;
        for(int j=head[p];j!=-1;j=next[j])
            if(flow[j]&&d[end[j]]==d[p]+1){
                int to=dinic(end[j],t,flow[j]>last?last:flow[j]);
                if(to){
                    flow[j]-=to;
                    flow[j^1]+=to;
                    if(!(last-=to))
                        return Maxflow;
                }
            }
        d[p]=-1;
        return Maxflow-last;
    }
    inline int Maxflow(int s,int t){
        int re=0;
        while(bfs(s,t))
            re+=dinic(s,t,inf);
        return re;
    }
}g;
 
#define N 210
int p[N],cnt;
bool np[N];
inline void pre(){
    int i,j;
    for(i=2;i<=200;++i){
        if(!np[i])
            p[++cnt]=i;
        for(j=1;j<=cnt&&p[j]*i<=200;++j){
            np[i*p[j]]=1;
            if(i%p[j]==0)
                break;
        }
    }
}
int a[51][51],b[51][51],c[51][51];
int x[2][30010],y[2][30010],z[2][30010];
 
vector<int>v[N];
int main(){
    pre();
    int n,m;
    cin>>n>>m;
    int i,j,k;
    for(i=1;i<=n;++i)
        scanf("%d%d%d",&x[0][i],&y[0][i],&z[0][i]);
    for(i=1;i<=m;++i)
        scanf("%d%d%d",&x[1][i],&y[1][i],&z[1][i]);
     
    for(i=1;i<=200;++i)
        for(j=1;j<=cnt;++j)
            if(i%p[j]==0)
                v[i].push_back(j);
     
    int id=n+m;
    for(i=1;i<=cnt;++i)
        for(j=1;j<=cnt;++j){
            a[i][j]=++id;
            b[i][j]=++id;
            c[i][j]=++id;
        }
     
    int s=0,t=++id;
     
    g.reset();
    for(i=1;i<=n;++i)
        g.make(s,i,1);
    for(i=1;i<=m;++i)
        g.make(n+i,t,1);
     
    int p,q;
    for(i=1;i<=n;++i){
        for(j=0;j<v[x[0][i]].size();++j)
            for(k=0;k<v[y[0][i]].size();++k){
                p=v[x[0][i]][j];
                q=v[y[0][i]][k];
                g.make(i,a[p][q],1);
            }
        for(j=0;j<v[x[0][i]].size();++j)
            for(k=0;k<v[z[0][i]].size();++k){
                p=v[x[0][i]][j];
                q=v[z[0][i]][k];
                g.make(i,b[p][q],1);
            }
        for(j=0;j<v[y[0][i]].size();++j)
            for(k=0;k<v[z[0][i]].size();++k){
                p=v[y[0][i]][j];
                q=v[z[0][i]][k];
                g.make(i,c[p][q],1);
            }
    }
    for(i=1;i<=m;++i){
        for(j=0;j<v[x[1][i]].size();++j)
            for(k=0;k<v[y[1][i]].size();++k){
                p=v[x[1][i]][j];
                q=v[y[1][i]][k];
                g.make(a[p][q],n+i,1);
            }
        for(j=0;j<v[x[1][i]].size();++j)
            for(k=0;k<v[z[1][i]].size();++k){
                p=v[x[1][i]][j];
                q=v[z[1][i]][k];
                g.make(b[p][q],n+i,1);
            }
        for(j=0;j<v[y[1][i]].size();++j)
            for(k=0;k<v[z[1][i]].size();++k){
                p=v[y[1][i]][j];
                q=v[z[1][i]][k];
                g.make(c[p][q],n+i,1);
            }
    }
     
    cout<<g.Maxflow(s,t)<<endl;
     
    return 0;
}