题外话

这一次考试由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

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

发表评论

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

你是机器人吗? =。= *