发布于

lp3959 NOIP2017 宝藏

我们首先，如果两个点之间有连多条边，肯定只有最短的那条最优。
那么我们进行状压，对于某一个状态\(S_{0}\)，我们维护它的所有拓展的集合\(T_{S_{1}}\)
然后，记\(f_{i,k}\)表示，当前状态为\(i\)，当前的深度为\(k\)时的最小花费。
这样拓展，每一次拓展都相当于把深度加深了一层，因此就可以不要花费太多的精力去考虑\(k\)对贡献的影响。
而，从某一个根开始拓展，即相当于\(f_{(1<<i),0}\)
于是我们便可以开始DP。每一次拓展都会将可行集合纳入范围。这样拓展的花费也是可以被轻松计算出来的。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))
int n,m,f[1<<12][12],usf[1<<12];
int mp[15][15];
void init(){
    scanf("%d%d",&n,&m);
    int u,v,w;
    memset(mp,0x3f,sizeof(mp));
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&u,&v,&w);
        --u,--v; 
        mp[u][v]=Min(mp[u][v],w);
        mp[v][u]=Min(mp[v][u],w);
    }
    const int MAX=1<<n;
    for(int i=1;i<MAX;++i){
        for(int j=0;j<n;++j){
            if((i|(1<<j))!=i){
                continue;
            }
            for(int k=0;k<n;++k){
                if(mp[j][k]!=0x3f3f3f3f){
                    usf[i]|=(1<<k);
                }
            }
        }
    }
    memset(f,0x3f,sizeof(f));
    for(int i=0;i<n;++i){
        mp[i][i]=0;
        f[1<<i][0]=0;
    }
    long long sm,nw,x;
    for(int i=2;i<MAX;++i){
        for(int j=i-1;j;j=(j-1)&i){
            if(((usf[i]|j)!=usf[i])){
                continue;
            }
            sm=0,nw=i^j;
            for(int k=0;k<n;++k){
                if((nw>>k)&1){
                    x=0x3f3f3f3f;
                    for(int l=0;l<n;++l){
                        if((j>>l)&1){
                            x=Min(x,mp[l][k]);
                        }
                    }
                    sm+=x;
                }
            }
            for(int k=1;k<n;++k){
                f[i][k]=Min(f[i][k],f[j][k-1]+sm*k);
            }
        }
    }
    int ans=0x3f3f3f3f;
    for(int i=0;i<n;++i){
        ans=Min(ans,f[MAX-1][i]);
    }
    printf("%d\n",ans);
}
int main(){
    init();
    return 0;
}

 

发布于

lp4578 FJOI2018 所罗门王的宝藏

首先，我们可以知道，令每一行、列数字的变化为\(dx_{i},dy_{i}\)，那么对于\(z_{i,j}\)，一定有：
$$dx_{i}+dy_{j}=z_{i,j}$$
对这个线性方程组变形，我们可以发现，如果指定序列合法，那么：
$$ \forall x ,z_{x,j_{1}}-z_{x,j_{2}}=dy_{j_{1}}-dy_{j_{2}} $$
$$ \forall y ,z_{i_{1},y}-z_{i_{2},y}=dx_{i_{1}}-dx_{i_{2}} $$
而，当\(dx\)和\(dy\)的相对关系不矛盾时，一定可以导出一个符合题意的矩阵。
因此，我们对于每组\(x,y\)，统计它们的相对关系即可。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,k; 
int dx[1005][1005],dy[1005][1005];
bool visx[1005][1005],visy[1005][1005];
int x[1005],y[1005],z[1005];
void init(){
    memset(dx,0,sizeof(dx));
    memset(dy,0,sizeof(dy));
    memset(visx,0,sizeof(visx));
    memset(visy,0,sizeof(visy));
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=k;++i){
        scanf("%d%d%d",&x[i],&y[i],&z[i]);
    }
    int nw;
    for(int i=1;i<k;++i){
        for(int j=i+1;j<=k;++j){
            if(x[i]==x[j]&&y[i]==y[j]&&z[i]!=z[j]){
                puts("No");
                return; 
            }
            if(x[i]==x[j]){
                nw=y[i]>y[j]?z[j]-z[i]:z[i]-z[j];
                if(visx[y[i]][y[j]]&&dx[y[i]][y[j]]!=nw){
                    puts("No");
                    return;
                }
                dx[y[i]][y[j]]=dx[y[j]][y[i]]=nw;
                visx[y[i]][y[j]]=visx[y[j]][y[i]]=1; 
            }
            if(y[i]==y[j]){
                nw=x[i]>x[j]?z[j]-z[i]:z[i]-z[j];
                if(visy[x[i]][x[j]]&&dy[x[i]][x[j]]!=nw){
                    puts("No");
                    return;
                }
                dy[x[i]][x[j]]=dy[x[j]][x[i]]=nw;
                visy[x[i]][x[j]]=visy[x[j]][x[i]]=1; 
            }
        }
    }
    for(int i=1;i<=n;++i){
        if(dx[i][i]||dy[i][i]){
            puts("No");
            return;
        }
    }
    puts("Yes");
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        init();
    }
    return 0;
}

 

发布于

lp3953 NOIP2017 逛公园

容易知道，对于每个点，最多只能偏移50。
由此可以跑记忆化搜索：\(f_{i,j}\)表示，在第i个点，比最短路长了j时的方案数。
那么，我们倒着搜即可。
具体来说，定义\(dn_{x}\)表示\(x->u\)的最短路。
那么我们可以得到状态转移方程：
$$f_{u,k}=\sum_{v,v\in S,st: \forall x \in S,x_{u}=u}f_{v,k-dn_{v}+dn_{u}-w}$$
答案为\(f_{1,K}\)
几个细节：
e[i].nxt不应写作e[i].v
不要使用长得差不多的变量。

#include<iostream>
#include<cstdio>
#include<queue> 
#include<cstring>
using namespace std;
struct ee{
    int v;
    int w;
    int nxt;
}e[400005];
int h[100005],h2[100005],et=0,n,m,K,p,dis[100005],dn[100005],f[100005][51];
bool usd[100005][51];
inline void add(int *_H,const int &u,const int &v,const int &w){
    e[++et]=(ee){v,w,_H[u]};
    _H[u]=et;
}
struct cmp2{
    inline bool operator ()(const int &X,const int &Y)const{
        return dn[X]>dn[Y];
    }
};
void dij2(){
    priority_queue< int,vector<int>,cmp2 > q;
    memset(dn,0x3f,sizeof(dn));
    dn[n]=0;
    q.push(n);
    int nw;
    while(!q.empty()){
        nw=q.top();
        q.pop();
        for(int i=h2[nw];i;i=e[i].nxt){
            if(dn[e[i].v]>dn[nw]+e[i].w){
                dn[e[i].v]=dn[nw]+e[i].w;
                q.push(e[i].v);
            }
        }
    }
}
int dfs(int u,int k){
    if(usd[u][k]){
        return -1;
    }
    if(f[u][k]){
        return f[u][k];
    }
    usd[u][k]=1;
    if(u==n){
        f[u][k]=1;
    }
    int X,sm;
    for(int i=h[u];i;i=e[i].nxt){
        //e[i].v不能写成e[i].nxt 
        sm=dn[e[i].v]-dn[u]+e[i].w;
        if(sm>k){
            continue;
        }
        X=dfs(e[i].v,k-sm);
        if(X==-1){
            return f[u][k]=-1;
        }
        f[u][k]+=X;
        f[u][k]%=p;
    }
    usd[u][k]=0;
    return f[u][k];
}
void init(){
    memset(h,0,sizeof(h));
    memset(h2,0,sizeof(h2));
    scanf("%d%d%d%d",&n,&m,&K,&p);
    et=0;
    int u,v,w;
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&u,&v,&w);
        add(h,u,v,w);
        add(h2,v,u,w);
    }
    dij2();
    memset(f,0,sizeof(f));
    memset(usd,0,sizeof(usd));
    printf("%d\n",dfs(1,K));
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        init();
    }
    return 0;
}

 

发布于

停课第四天。

停课第四天。距离NOIP2018还有9天。

只剩⑨天了，状态却还没有。

做了两套模拟赛的题，两套都有一定的难度。其中一题甚至是往年省选题。不过难度确实没有省选那么高。