【noip2017】

noip2017

小凯的疑惑

看到了一个简单易懂的证明

设\(x\)，\(x\equiv ma(mod\ b)(0\le m<b)\)（因为\(m\ge b\)的话可以表示为\(ma=(m\%b)*a+\lfloor m/b\rfloor*b*a=(m\%b)a+(n+\lfloor m/b\rfloor)b\)而\(0\le m\%b< b\)）

即\(x=ma+nb\) 显然\(n\ge0\)时一定能表示出来，所以\(n=-1\)，\(0\le m<b-1\)

所以最大值为\((b-1)a-b=ab-a-b\)

时间复杂度

我lxy就是死，从这里跳下去，也不会做这道恶熏熏的题的！

逛公园

先dij跑一遍最短路 然后再类似dp来计算有多少条

若当前\(used[u][val]==1\)说明这个点还未走完又被进入了，构成了一个\(0\)环 无解

int tot=0,head[N];
struct edge{int v,w,nxt;}e[M];
void add(int u,int v,int w){e[++tot]=(edge){v,w,head[u]},head[u]=tot;}

int dis[N];bool vis[N];
priority_queue<pii>q;
void clean(){memset(dis,inf,sizeof(dis)),memset(vis,0,sizeof(vis));}
void dij(int st){
    clean();
    q.push(make_pair(dis[st]=0,st));
    while(!q.empty()){
        int u=q.top().second;q.pop();
        if(vis[u]) continue;vis[u]=1;
        for(int i=head[u],v;i;i=e[i].nxt)
        if((i&1)&&dis[v=e[i].v]>dis[u]+e[i].w) q.push(make_pair(-(dis[v]=dis[u]+e[i].w),v));
    }
}

int f[N][55],used[N][55];
int dfs(int u,int val){
    if(used[u][val]==1||fl) return fl=1;
    if(used[u][val]==2) return f[u][val];
    used[u][val]=1;
    for(int i=head[u],v,w;i;i=e[i].nxt) if(!(i&1)){
        w=dis[u]+val-dis[v=e[i].v]-e[i].w;
        if(w>K||w<0) continue;
        f[u][val]+=dfs(v,w),f[u][val]%=P;
    }used[u][val]=2;
    return f[u][val];
}


int main(){
#ifndef ONLINE_JUDGE
    freopen("T1.txt","r",stdin);
#endif
    int T;rd(T);
    while(T--){
        memset(head,0,sizeof(head)),tot=ans=fl=0;
        memset(used,0,sizeof(used)),memset(f,0,sizeof(f));
        rd(n),rd(m),rd(K),rd(P);
        for(int i=1,u,v,w;i<=m;++i) rd(u),rd(v),rd(w),add(u,v,w),add(v,u,w);
        dij(1);f[1][0]=1;
        for(int i=0;i<=K&&!fl;++i) ans+=dfs(n,i),ans%=P;
        if(fl) puts("-1");
        else printf("%d\n",ans);    
    }
    return 0;
}

奶酪

dfs？搜一下有没有一个在最底层的洞能延伸到最顶层

long long x[maxn],y[maxn],z[maxn];
int vis[maxn];
long long su(long long int x1,long long x2,long long y1,long long y2,long long z1,long long z2){
    long long wa=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2);
    return wa;
}
void dfs(int x1,int y1,int z1,int cnt){
    if(z1+r>=h) {fnd=1;return;}
    vis[cnt]=1;
    for(int i=1;i<=n;i++)
        if(!vis[i]&&su(x1,x[i],y1,y[i],z1,z[i])<=4*r*r) dfs(x[i],y[i],z[i],i);
}
int main(){
    scanf("%d",&t);
    for(int i=1;i<=t;i++){
        memset(vis,0,sizeof(vis));fnd=0;
        scanf("%d%d%lld",&n,&h,&r);
        for(int i=1;i<=n;i++) scanf("%lld%lld%lld",&x[i],&y[i],&z[i]);
        for(int i=1;i<=n;i++)
            if(z[i]-r<=0) dfs(x[i],y[i],z[i],i);
        if(fnd) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

宝藏

康代码把 枚举从哪个洞开始打

int cnt[N];
void dfs(int st){
    for(int i=1;i<=n;++i)
    if(st&(1<<(i-1))){
        for(int j=1,nw,ret;j<=n;++j)
        if(!(st&(1<<(j-1)))&&mp[i][j]!=inf)
            if(nw=st|(1<<(j-1)),f[nw]>f[st]+mp[i][j]*cnt[i])
                ret=cnt[j],f[nw]=f[st]+mp[i][j]*cnt[i],cnt[j]=cnt[i]+1,dfs(nw),cnt[j]=ret;
    }
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("T1.txt","r",stdin);
#endif
    rd(n),rd(m);
    memset(mp,inf,sizeof(mp));
    for(int i=1,u,v,w;i<=m;++i) rd(u),rd(v),rd(w),mp[u][v]=mp[v][u]=Min(mp[u][v],w);
    for(int i=1;i<=n;++i){
        memset(f,inf,sizeof(f)),f[1<<(i-1)]=0;
        memset(cnt,inf,sizeof(cnt)),cnt[i]=1;
        dfs(1<<(i-1)),ans=min(ans,f[(1<<n)-1]);
    }
    printf("%d",ans);
    return 0;
}

列队

【noip2017】

原文：https://www.cnblogs.com/lxyyyy/p/11826003.html