Gym 101655：2013Pacific Northwest Regional Contest（寒假自训第13场）

A .Assignments

题意：给定距离D，以及N个飞机的速度Vi，单位时间耗油量Fi，总油量Ci。问有多少飞机可以到达目的地。

思路：即问多少飞机满足(Ci/Fi)*Vi>=D ----> Ci*Vi>=Fi*D;

#include<bits/stdc++.h>

#define ll long long

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

int main()

{

    int T,N,f,v,c,D,ans;

    scanf("%d",&T);

    while(T--){

        scanf("%d%d",&N,&D); ans=;

        rep(i,,N){

             scanf("%d%d%d",&v,&f,&c);

            if(f*v>=D*c) ans++;

        }

        printf("%d\n",ans);

    }

    return ;

}

B .Bones’s Battery

题意：N城市，M条双向带权路（权值表示耗电量），满足他们连通。每个城市可以给电车充满电。现在需要一种电车，满足任意路线(即任意点到任意点)，它充电的次数不超过K。一开始车的没电的，即起点必须充电。

思路：先Floyd求得两两最短路。然后我们把dis小于电车电量的路径距离看为1，然后需要满足任意点对距离不大于K。显然就是一个二分+Floyd。

二分的时候可以直接二分[1,inf]；复杂度O(N^3*loginf).

优化：二分的这个电量，一定是其中两点间距离，我们我们把点对距离排序，然后对他们二分即可。复杂度O(2*N^3*logN);

#include<bits/stdc++.h>

#define ll long long

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

const ll inf=;

int N,M,K;ll dis[maxn][maxn],dp[maxn][maxn];

bool check(ll Mid)

{

    rep(i,,N)

      rep(j,,N) dp[i][j]=(dis[i][j]>Mid?inf:);

    rep(k,,N)

      rep(i,,N)

       rep(j,,N)

        dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);

    rep(i,,N)

      rep(j,i+,N)

          if(dp[i][j]>K) return false;

    return true;

}

int main()

{

    int T,u,v;ll w;

    scanf("%d",&T);

    while(T--){

       scanf("%d%d%d",&N,&K,&M);

       rep(i,,N) rep(j,,N) dis[i][j]=inf;

       rep(i,,M){

         scanf("%d%d%lld",&u,&v,&w); u++; v++;

         dis[u][v]=min(dis[u][v],w);

         dis[v][u]=min(dis[v][u],w);

       }

       rep(k,,N)

        rep(i,,N)

         rep(j,,N)

          dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);

       ll L=,R=inf,Mid,ans;

       while(L<=R){

         Mid=(L+R)/;

         if(check(Mid)) ans=Mid,R=Mid-;

         else L=Mid+;

       }

       printf("%lld\n",ans);

    }

    return ;

}

C .Crusher’s Code

题意：给定长度为N的序列a[];

Alice每次随机选择一个i，j；如果a[min(i,j)]>a[max(i,j)]，则交换他们两个。

Bob每次随机选择一个i(i<N)；如果a[i]>a[i+1]，则交换他们两个。

思路：然后是一个有限状态的数学期望DP，我们可以记忆化搜索。把a数组看成一个N位数，假设为x，那么每次它要么不变，要么变小。

对于Alice和Bob，我们可以列出方程：dp[x]=(dp[a]+dp[b]+dp[c]+dp[d]....dp[cnt]）/cnt+1；其中abcd...是x能到达的状态。

显然总状态数小于N!~4e4；我们可以过，假设map保存dp值，复杂度O(N!*log);

优化：我们可以把map换为康拓展开，这样可以优化掉一个log。

#include<bits/stdc++.h>

#define ll long long

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

int a[],b[],f[],N,Tar;

map<int,double>mp;

double dfs1(int x)

{

    if(x==Tar) return ;

    int c[];

    if(mp.find(x)!=mp.end()) return mp[x];

    double res=; int cnt=,tx=x;

    for(int i=N;i>=;i--) c[i]=tx%,tx/=;

    rep(i,,N)

     rep(j,,N){

        int mn=min(i,j),mx=max(i,j);

        if(c[mn]>c[mx]) res+=dfs1(x-(c[mn]*f[N-mn]+c[mx]*f[N-mx])+(c[mx]*f[N-mn]+c[mn]*f[N-mx]));

        else cnt++;

    }

    return mp[x]=(res+N*N)/(N*N-cnt);

}

double dfs2(int x)

{

    if(x==Tar) return ;

    int c[];

    if(mp.find(x)!=mp.end()) return mp[x];

    double res=; int cnt=; int tx=x;

    for(int i=N;i>=;i--) c[i]=tx%,tx/=;

    rep(i,,N-) {

        int mn=i,mx=i+;

        if(c[mn]>c[mx]) res+=dfs2(x-(c[mn]*f[N-mn]+c[mx]*f[N-mx])+(c[mx]*f[N-mn]+c[mn]*f[N-mx]));

        else cnt++;

    }

    mp[x]=(res+N-)/(N--cnt);

    return mp[x];

}

int main()

{

    int T; scanf("%d",&T);

    f[]=; rep(i,,) f[i]=f[i-]*;

    while(T--){

        scanf("%d",&N);

        rep(i,,N) scanf("%d",&a[i]),b[i]=a[i];

        sort(b+,b+N+);

        int tot=unique(b+,b+N+)-(b+);

        rep(i,,N) a[i]=lower_bound(b+,b+tot+,a[i])-b;

        int x=; rep(i,,N) x=x*+a[i],b[i]=a[i];

        sort(b+,b+N+);

        Tar=; rep(i,,N) Tar=Tar*+b[i];

        mp.clear(); double ans1=dfs1(x);

        mp.clear(); double ans2=dfs2(x);

        printf("Monty %.6lf Carlos %.6lf\n",ans1,ans2);

    }

    return ;

}

D .Delta Quadrant

题意：给定大小为N的一棵带权树，让你找一条最快的路径，遍历至少N-K个点，然后回到起点，K<=20。

思路：树型DP，dp[i][j]表示选择以i为根的子树，子树里有j个点不选的最小权值和。

和一般的树DP做背包不一样，这里必须选一个，所以我们用一个临时数组tmp来更新。

更新答案的时候，选择的连通块的根也不一定是1号节点。

复杂度O(N*K^2)；

#include<bits/stdc++.h>

#define ll long long

#define rep2(i,a,b) for(int i=a;i>=b;i--)

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

const int inf=1e9;

int  Laxt[maxn],Next[maxn],To[maxn],Len[maxn];

int dp[maxn][],tmp[],sz[maxn],cnt,K;

void add(int u,int v,int w)

{

    Next[++cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v; Len[cnt]=w;

}

void dfs(int u,int f)

{

    rep(i,,K) dp[u][i]=;

    dp[u][]=; sz[u]=;

    for(int i=Laxt[u];i;i=Next[i]){

        int v=To[i]; if(v==f) continue;

        dfs(v,u); sz[u]+=sz[v];

        rep(j,,K) tmp[j]=inf;

        rep(j,,min(sz[v],K)){

            rep2(k,K,j)

            tmp[k]=min(tmp[k],dp[u][k-j]+dp[v][j]+(j==sz[v]?:Len[i]));

        }

        rep(j,,K) dp[u][j]=tmp[j];

    }

}

int main()

{

    int T,N,u,v,w; scanf("%d",&T);

    while(T--){

        scanf("%d%d",&N,&K);

        cnt=; rep(i,,N) Laxt[i]=;

        rep(i,,N-) {

            scanf("%d%d%d",&u,&v,&w);

            u++; v++;

            add(u,v,w); add(v,u,w);

        }

        dfs(,); int ans=dp[][];

        rep(i,,K)  ans=min(ans,dp[][K]);

        rep(i,,N) rep(j,,K-(N-sz[i])) ans=min(ans,dp[i][j]);

        printf("%d\n",ans*);

    }

    return ;

}

E .Enterprising Escape

题意：给定N*M的迷宫，迷宫由大写字母组成，每种不同的字母对应穿过这个格子的时间，‘E’是起点，问从起点走到迷宫边界的最小时间。

思路：没有负权，所以直接BFS或者跑最短路即可。

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

const int inf=1e9;

int dis[maxn][maxn],inq[maxn][maxn],id[maxn],C,N,M,Sx,Sy,ans;

int dx[]={,,,-},dy[]={,,-,};char c[maxn][maxn];

struct in{

    int x,y,d;

    in(){}

    in(int xx,int yy,int dd):x(xx),y(yy),d(dd){}

    bool friend operator<(in w,in v){ return w.d>v.d; }

};

void dijs()

{

    rep(i,,N) rep(j,,M) dis[i][j]=inf,inq[i][j]=;

    dis[Sx][Sy]=;  priority_queue<in>q;

    q.push(in(Sx,Sy,));

    while(~q.empty()){

        int x=q.top().x,y=q.top().y; q.pop(); inq[x][y]=;

        if(x==||x==N||y==||y==M){

            ans=dis[x][y]; return;

        }

        rep(i,,){

            int tx=x+dx[i],ty=y+dy[i];

            if(tx>=&&tx<=N&&ty>=&&ty<=M&&dis[tx][ty]>dis[x][y]+id[c[tx][ty]]){

                dis[tx][ty]=dis[x][y]+id[c[tx][ty]];

                if(!inq[tx][ty]) inq[tx][ty]=,q.push(in(tx,ty,dis[tx][ty]));

            }

        }

    }

}

int main()

{

    int T,x; char s[];

    scanf("%d",&T);

    while(T--){

        scanf("%d%d%d",&C,&M,&N);

        rep(i,,C){

            scanf("%s",s); scanf("%d",&x);

            id[s[]]=x;

        }

        rep(i,,N) scanf("%s",c[i]+);

        rep(i,,N) rep(j,,M) {

            if(c[i][j]=='E') {

                Sx=i; Sy=j; break;

            }

        }

        dijs();

        printf("%d\n",ans);

    }

    return ;

}

F .Federation Favorites

题意：问一个数是否是真因子（不含本身的因子）之和。

思路：根号分解即可。

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=a;i<=b;i++)

#define rep2(i,a,b) for(int i=a;i>=b;i--)

using namespace std;

const int maxn=;

int tot,a[maxn],b[maxn],tot2;

int main()

{

    int N;

    while(~scanf("%d",&N)&&N!=-){

        int res=; a[tot=]=; tot2=;

        for(int i=;i*i<=N;i++){

            if(N%i==) {

                res+=i; a[++tot]=i;

                if(i*i!=N) res+=N/i,b[++tot2]=N/i;

            }

        }

        if(res!=N) printf("%d is NOT perfect.\n",N);

        else {

            printf("%d = %d",N,);

            rep(i,,tot) printf(" + %d",a[i]);

            rep2(i,tot2,) printf(" + %d",b[i]);

            puts("");

        }

    }

    return ;

}

G .Generations of Tribbles

题意：给一个递推式，求第N项。

思路：模拟。

#include<bits/stdc++.h>

#define ll long long

#define rep(i,a,b) for(int i=a;i<=b;i++)

#define rep2(i,a,b) for(int i=a;i>=b;i--)

using namespace std;

const int maxn=;

ll a[maxn]; int N,T;

int main()

{

    a[]=a[]=; a[]=; a[]=;

    rep(i,,) a[i]=a[i-]+a[i-]+a[i-]+a[i-];

    scanf("%d",&T);

    while(T--){

        scanf("%d",&N);

        printf("%llf\n",a[N]);

    }

    return ;

}

H .Holodeck Hacking

题意：rev(X)是把X的各个数位倒序过来，给定Y，问多少X满足X+rev(X)=Y；Y<1e18;

思路：假设X=abcd，那么X+rev(X)=(a+d)(b+c)(b+c)(a+d)，然后进位。即在不进位的情况下是对称的。那么我们枚举不进位的情况下的右半部分，然后对称到左半部分，然后考虑进位，进位后如果值为Y，然后分别考虑每一位的贡献。

这样的话复杂度是O(2^((L+1)/2); 然后累乘每一位的贡献即可。估计数位DP也可以做，但是复杂度一样。

#include<bits/stdc++.h>

#define ll long long

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

int a[maxn],b[maxn],c[maxn],tot;ll x,ans;

void dfs(int L,int pos,int p)

{

    if(pos==(L+)/+){

        for(int i=pos;i<=L;i++) b[i]=b[L+-i];

        for(int i=;i<=tot+;i++) c[i]=;

        for(int i=;i<=L;i++){

                c[i]+=b[i];

                c[i+]=c[i]/;

                c[i]%=;

        }

        if(c[tot+]) return ;

        for(int i=;i<=tot;i++) if(c[i]!=a[i]) return ;

        ll res;

        if(b[]<){

            if(L==) res=b[]&?:;

            else res=b[];

        }

        else {

            if(L==) res=b[]&?:;

            else res=-b[];

        }

        for(int i=;i<pos;i++){

            if(b[i]<){

                if(L+-i==i) res*=b[i]&?:;

                else res*=1LL*(b[i]+);

            }

            else{

                if(L+-i==i) res*=b[i]&?:;

                else res*=1LL*(-b[i]);

            }

        }

        ans+=res;

        return ;

    }

    if(a[pos]-p>=) b[pos]=a[pos]-p,dfs(L,pos+,);

    b[pos]=a[pos]-p+; dfs(L,pos+,);

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--){

        scanf("%lld",&x); tot=; ans=;

        while(x) a[++tot]=x%,x/=;

        dfs(tot,,);

        if(a[tot]==) dfs(tot-,,);

        printf("%lld\n",ans);

    }

    return ;

}

I .Interstellar Trade

题意：X轴有处于整点的N个点，现在你可以任选两个点（不一定在整点上），使得这两个点可以互相瞬移，求最小化最大距离。

思路：比赛的时候写了个O(N^3)的代码，显然过不去，然后乱改成N^2的假代码，瞎交了一发，估计是数据水了A了。

（下面的别人的代码，还未理解。

#include<bits/stdc++.h>

#define ll long long

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

int N,a[maxn];

int main()

{

    int T,ans;

    scanf("%d",&T);

    while(T--){

        scanf("%d",&N);

        rep(i,,N) scanf("%d",&a[i]);

        sort(a+,a+N+); ans=;

        rep(i,,N) ans=max(ans,min(a[N]-a[i],a[i]-a[]));

        printf("%d\n",ans);

    }

    return ;

}

巴特西