题外话

这一次考试由 boshi 大佬负责译题,出数据,评测。
然而 boshi 大佬显然不满足于译题,出数据,评测。
于是他更改数据范围,缩短时间限制,出卡常数据,提前评测。
litble 同学,您的 L 降为 0,F 降为 1,还剩 1 次怼大佬机会。[^HNOI2017 Day2 T1 大佬的题目描述]

考试策略

看完题目发现只会做 T2,于是高高兴兴花了 40 多分钟的时间打好 T2,调试。

接下来就懵逼了。根据 CY 喜欢把 T1 作为最难的题目定律,我去看了 T3,然后灵机一动想到了一个解法,高高兴兴打好 T3。

又看了 T4,首先以为 T4 是一个以状态作为点的最短路,打完发现样例都过不了(QAQ),接下来又以为 T4 是网络流,打完发现样例都过不了(QAQ),接下来想到了一个暴力搜索+最短路解法,因为 n 的数据范围很小,所以应该还能过一些点,就写了,当时估计会爆栈(结果拿了 85 分?boshi 大佬数据水了?)。

T4 打了一个半小时多,心态爆炸。距离下考还有半个小时,T1 果断输出 “0.000” 骗分,然后检查打了的题,发现 T3 我的解法只能做第一问不能做第二问(QAQ),心想自己要爆 0 了,可是时间又不够了,默默膜了一发 boshi 大佬(弱的人膜强的人会涨 RP 的),就咬牙交了知道是错的程序。

以及……boshi 大佬出的这套题的数据范围全部只给最大范围然后 “数据有梯度”,梯度个鬼啊!天知道是太阳山的梯度还是珠穆朗玛峰的梯度!!!!

T1

期望得分:10 实际得分:15

题目描述:poj3621

题目分析

赋一首押韵的诗:

分数规划
那是个啥
我不会啊
不如爆炸

首先我们令 X={0,1},Y={0,1}。$V_i$表示点权,$W_i$是边权, 那么 $ANS=\frac{\sum X_iV_i}{\sum Y_jW_j}$。把原式变形可得:$ANS\sum Y_j W_j=\sum X_i V_i$。如果 $ANS$小于 $\frac{\sum X_iV_i}{\sum Y_jW_j}$即 $ANS\sum Y_j W_j $小于 $\sum X_i V_i$时,我们需要把 ANS 缩小。变形得 $ANS \sum Y_j W_j – \sum X_i V_i$小于 0 时。

我们知道奶牛走过的路径一定是一个环(不会是多个环联合,可以用数学方法证明多个环得不到最优解),二分答案,把环上每条边变成(ANS 乘边权-起点点权),然后用 spfa 判断是否有负环即可判断二分下一步干什么。

代码

(在 poj 上要使用 C++而非 G++才能 A 掉,是因为%lf 的问题)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=1005,M=100005;
int h[N],to[M],ne[M],inq[N],num[N];
double v[N],w[M],dis[N];
int n,m,tot;
int spfa(double lim){
    int i,x;queue<int>q;
    for(i=1;i<=n;++i)dis[i]=num[i]=0,q.push(i),inq[i]=1;
    while(!q.empty()){
        x=q.front(),q.pop(),inq[x]=0;
        for(i=h[x];i!=-1;i=ne[i])
            if(dis[x]-v[x]+w[i]*lim<dis[to[i]]){
            dis[to[i]]=dis[x]-v[x]+w[i]*lim;
            if(!inq[to[i]]){
                inq[to[i]]=1,q.push(to[i]);
                ++num[to[i]];if(num[to[i]]==n)return 1;
            }
        }
    }
    return 0;
}
void add(int x,int y,double z)
{to[++tot]=y,ne[tot]=h[x],h[x]=tot,w[tot]=z;}
int main()
{
    int i,x,y;double l=0,r=1e6,mid,z;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;++i)scanf("%lf",&v[i]),h[i]=-1;
    for(i=1;i<=m;++i)scanf("%d%d%lf",&x,&y,&z),add(x,y,z);
    while(l+1e-4<r){
        mid=(l+r)/2;
        if(spfa(mid))l=mid;
        else r=mid;
    }
    printf("%.2lf",l);
    return 0;
}

T2

期望得分:100 实际得分:100

题目描述:HDU3768,其中去的超市数量改为小于等于 15,n 小于等于 10000

题目分析

显然只有超市和家是有用的节点。我们以每一个超市为起点跑一遍 spfa,得到每个超市和家之间的最短距离,然后状态压缩 dp。用 f(i,zt) 表示当前在 i 号节点(当然超市和家重编号了)时,遍历状态为 zt 的最短路。zt 写成二进制后,如果某一位是 1,则该节点去过了。

方程:f(i,zt)=min(f(j,zt-bin[i])),bin 表示 i 在二进制下哪一位是 1.

细节看代码,另外在 HDU 上可过的搜索做法此处会 T 得很惨。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
#define LL long long
int read(){
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
    return q;
}
const int N=100005,M=200005,MAXN=(1<<15);
int n,m,num,tot,T;
LL f[16][MAXN],dis[N];int a[17],bin[17],inq[N];
int h[N],to[M],ne[M];LL w[M],ll[17][17];
void add(int x,int y,LL z)
{to[++tot]=y,ne[tot]=h[x],h[x]=tot,w[tot]=z;}
void spfa(int x){
    queue<int>q;int i,kl;
    for(i=0;i<n;++i)dis[i]=1e14,inq[i]=0;
    dis[a[x]]=0,q.push(a[x]);
    while(!q.empty()){
        kl=q.front(),q.pop(),inq[kl]=0;
        for(i=h[kl];i!=-1;i=ne[i])
            if(dis[kl]+w[i]<dis[to[i]]){
            dis[to[i]]=dis[kl]+w[i];
            if(!inq[to[i]])q.push(to[i]),inq[to[i]]=1;
        }
    }
    for(i=0;i<=num;++i)ll[x][i]=dis[a[i]];
}
void work(){
    int i,zt,lim,j;LL ans=1e14;
    lim=(1<<num)-1;
    for(i=0;i<=num;++i)for(j=0;j<=lim;++j)f[i][j]=1e14;
    f[0][0]=0;
    for(zt=1;zt<=lim;++zt){
        for(i=1;i<=num;++i){
            if(!(zt&bin[i]))continue;
            for(j=1;j<=num;++j){
                if(!(zt&bin[j]))continue;
                f[i][zt]=min(f[i][zt],f[j][zt-bin[i]]+ll[j][i]);
            }
            f[i][zt]=min(f[i][zt],f[0][zt-bin[i]]+ll[0][i]);
        }
        for(i=1;i<=num;++i)f[0][zt]=min(f[0][zt],f[i][zt]+ll[i][0]);
    }
    for(i=1;i<=num;++i)ans=min(ans,f[i][lim]+ll[i][0]);
    printf("%lld\n",ans);
}
int main()
{
    int i,j,x,y;LL z;
    T=read();bin[1]=1;
    for(i=2;i<=15;++i)bin[i]=bin[i-1]<<1;
    while(T--){
        n=read(),m=read();
        tot=0;for(i=0;i<n;++i)h[i]=-1;
        for(i=1;i<=m;++i){
            x=read(),y=read(),z=read();
            add(x,y,z),add(y,x,z);
        }
        num=read();
        for(i=1;i<=num;++i)a[i]=read();
        for(i=0;i<=num;++i)spfa(i);
        work();
    }
    return 0;
}

T3

期望得分:0 实际得分:12

题目描述:HDU2363,n 改为小于等于 1000

题目分析

二分海拔差,枚举最小高度,spfa 判断解可行性。

听着不是很难,不过可能被卡时?:

1. 把所有海拔都排个序,二分查找,可以进行 spfa 的最小海拔要求是 $h(i) \leq h(1),h(n) \leq h(i)+lim$。因为 1 号和 n 号节点是必然经过的。

2.spfa 发现满足条件的海拔差后,直接记录答案跳出这次二分枚举。最后再根据记录的答案重新枚举最低点,求出最短路。

关于第二点:显然出题人 boshi 大佬并没有注意这一点,他在记录答案挑出二分枚举的同时直接记录的最短路,这种行为是非常不对的,我用 HDU 的 discuss 区的这组数据 Hack 掉了他的代码(我才不说我 Hack 的理由是看别人的代码都跑得比我的快非常不爽呢):

1
7 9
4
6
1
3
3
6
4
1 2 1
2 5 1
3 4 1
4 7 1
1 5 4
5 6 4
6 7 4
5 3 4
6 4 2

不过或许是因为在纯随机数据中,出现相同海拔差但是最低最高点不同,导致最短路不同的情况非常罕见,所以像 boshi 大佬那样的代码依然可以 AC。可惜 HDU 没有 Hack 功能啊。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
int read(){
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
    return q;
}
const int N=1005,M=10005;
int h[N],to[M],ne[M],w[M],g[N],inq[N],dis[N],t[N];
int T,n,m,tot,ans1,ans2,inf=1e9+5;
void add(int x,int y,int z)
{to[++tot]=y,ne[tot]=h[x],h[x]=tot,w[tot]=z;}
int spfa(int mi,int mx){
    int i,x;queue<int>q;
    for(i=1;i<=n;++i)dis[i]=inf,inq[i]=0;
    q.push(1),dis[1]=0;
    while(!q.empty()){
        x=q.front(),q.pop(),inq[x]=0;
        for(i=h[x];i!=-1;i=ne[i]){
            int v=to[i];
            if(g[v]>=mi&&g[v]<=mx&&dis[x]+w[i]<dis[v]){
                dis[v]=dis[x]+w[i];
                if(!inq[v])inq[v]=1,q.push(v);
            }
        }
    }
    if(dis[n]>=inf)return 0;
    else return 1;
}
int ok(int lim){
    int i,x=g[1],y=g[n];
    if(x>y)swap(x,y);
    i=lower_bound(t+1,t+1+n,x)-t;
    for(;i>=1&&t[i]+lim>=y;--i)
        if(spfa(t[i],t[i]+lim)){ans1=lim;return 1;}
    return 0;
}
int main()
{
    int i,l,r,mid,x,y,z;
    T=read();
    while(T--){
        n=read(),m=read();tot=l=r=0;
        for(i=1;i<=n;++i)
            h[i]=-1,g[i]=read(),t[i]=g[i],r=max(r,g[i]);
        sort(t+1,t+1+n);
        for(i=1;i<=m;++i){
            x=read(),y=read(),z=read();
            add(x,y,z),add(y,x,z);
        }
        while(l<=r){
            mid=(l+r)>>1;
            if(ok(mid))r=mid-1;
            else l=mid+1;
        }
        x=g[1],y=g[n];if(x>y)swap(x,y);ans2=inf;
        i=lower_bound(t+1,t+1+n,x)-t;
        for(;i>=1&&t[i]+ans1>=y;--i)
        if(spfa(t[i],t[i]+ans1))ans2=min(ans2,dis[n]);
        printf("%d %d\n",ans1,ans2);
    }
    return 0;
}

## T4

期望得分:20 实际得分:85

题目描述:HDU3311

题目分析

—斯坦纳树是什么,能吃吗?

—不能。

—那为什么要考(烤)?

好吧好吧,此题其实是一道斯坦纳树模板题…

我也是无话可说。

或者你说就是一个状压 dp 也行。

我们把开凿水井看作有一个水源,引水入城 [^noip2010]。则水源要和所有寺庙连通。

首先我们玩 n+m+1 次 spfa 来求出任意两点之间的距离 dis(i,j)(很暴力,我喜欢)

我们令 f(zt,i) 为树根为 i,寺庙与树根的连通状态为 zt 的最小权值。那么我们有两种转移方法:

1. 更改树根 f(zt,i)=min(f(zt,j)+dis(i,j))

2. 枚举子集 f(zt,i)=min(f(s,i)+f(zt^s,i))(s 是 zt 的子集)

具体是为什么我也不知道…

什么?你问我 85 分咋拿的?暴力搜索+贪心思想啊。(显然贪心思想是错的,但是 boshi 大佬的数据比较水…)

然后,boshi 大佬这题标程跑了 4 秒多(卡常技巧多到令人发指),就给 5 秒时限,把我们卡得嗷嗷嗷的。

不过,我有特殊的卡常技巧 [^“我有特殊的××技巧” 体,实际上我没有]

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
inline int read(){
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
    return q;
}
int n,m,p,tot,inf=1100000000;
const int N=1010,M=13000;
int h[1010],to[M],ne[M],w[M],dis[N][N],inq[N],bin[7];
int f[(1<<5)][N];
inline void add(int x,int y,int z)
{to[++tot]=y,ne[tot]=h[x],h[x]=tot,w[tot]=z;}
inline void spfa(){
    int x,i,s;queue<int>q;
    for(s=0;s<=n+m;++s){
        for(i=0;i<=n+m;++i)inq[i]=0,dis[s][i]=inf;
        dis[s][s]=0,q.push(s);
        while(!q.empty()){
            x=q.front(),q.pop(),inq[x]=0;
            for(i=h[x];i!=-1;i=ne[i])
                if(dis[s][x]+w[i]<dis[s][to[i]]){
                dis[s][to[i]]=dis[s][x]+w[i];
                if(!inq[to[i]])inq[to[i]]=1,q.push(to[i]);
            }
        }
    }
}
inline void dp(){
    int i,j,zt,s;
    for(i=1;i<bin[n+1];++i)
        for(j=0;j<=n+m;++j)f[i][j]=inf;
    for(i=0;i<=n;++i)
        for(j=0;j<=n+m;++j)f[bin[i]][j]=dis[i][j];
    for(zt=1;zt<bin[n+1];++zt){
        if(!(zt&(zt-1)))continue;//跳过只有一个村庄的情况(因为已经搞过了)
        for(i=0;i<=n+m;++i){
            for(s=zt;s>0;s=(s-1)&zt)
            if(f[s][i]+f[zt^s][i]<f[zt][i])
                f[zt][i]=f[s][i]+f[zt^s][i];
        }
        for(i=0;i<=n+m;++i)
            for(j=0;j<=n+m;++j)
            if(f[zt][j]+dis[j][i]<f[zt][i])
                f[zt][i]=f[zt][j]+dis[j][i];
    }
}
int main()
{
    int x,y,z,i;
    bin[1]=1;for(i=2;i<=6;++i)bin[i]=bin[i-1]<<1;
    while(scanf("%d%d%d",&n,&m,&p)==3){
        tot=0;for(i=0;i<=n+m;++i)h[i]=-1;
        for(i=1;i<=n+m;++i)z=read(),add(0,i,z),add(i,0,z);
        for(i=1;i<=p;++i){
            x=read(),y=read(),z=read();
            add(x,y,z),add(y,x,z);
        }
        spfa();dp();printf("%d\n",f[bin[n+1]-1][0]);
    }
    return 0;
}
分类: 文章

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

发表评论

电子邮件地址不会被公开。 必填项已用*标注