TopCoder SRM 675 Div2 题解 (填坑速度感天动地)

232.66+368.81+685.73=1287.2
T2花的时间有点久，T1也没上240…
不过难得A了还是很开心的~~
题解要不就坑着叭QAQ
反正也不会被钦定到

反正也没什么事干我来填坑了

T1 LengthUnitCalculator

就是个单位换算，模拟一波就行。

#include <bits/stdc++.h>
using namespace std;
const string a[4]={"mi","yd","ft","in"};
const int b[3]={1760,3,12};

class LengthUnitCalculator {
public:
    double calc( int amount, string fromUnit, string toUnit );
};
double LengthUnitCalculator::calc(int amount, string fromUnit, string toUnit) {
    int x,y;
    for(int i=0;i<4;i++) if (a[i]==fromUnit) x=i;
    for(int i=0;i<4;i++) if (a[i]==toUnit) y=i;
    if (x==y) return (double)amount;
    if (x<y){
        for(int i=x;i<y;i++)
         amount*=b[i];
        return (double)amount;
    }
    cout<<x<<' '<<y;
    double ans=amount;
    for(int i=x-1;i>=y;i--)
     ans/=(double)b[i];
    return ans;
}

T2 ShortestPathWithMagic

Description $Description$

你有 k $k$瓶魔法药水，每次可以将一条路的长度减半，一条路最多只能用一瓶药水，不一定要用所有药水。求0到1的最短路。

Solution $Solution$

用 f[i][j] $f\left[i\right]\left[j\right]$表示到 i $i$点时用了 j $j$瓶药水的最短路，跑最短路就行。博主懒，直接上没堆优化的 Dijkstra $Dijkstra$了。
不过我的代码里 f[i][j] $f\left[i\right]\left[j\right]$是实际值的两倍，这样就没小数。

#include <bits/stdc++.h>
using namespace std;
const int N=55;
int n;
int f[N][N],b[N][N];

class ShortestPathWithMagic {
public:
    double getTime( vector <string> dist, int k );
};
double ShortestPathWithMagic::getTime(vector <string> dist, int k) {
    n=dist.size();
    memset(f,0x3f,sizeof f);
    for(int i=0;i<=k;i++) f[0][i]=0;
    for(int o=1;o<=n*(k+1);o++){
        int x=n,y=k+1;
        for(int i=0;i<n;i++)
         for(int j=0;j<=k;j++)
          if (f[i][j]<f[x][y]&&!b[i][j]){
            x=i;y=j;
          }
        b[x][y]=1;
        for(int i=0;i<n;i++)
         {
            f[i][y]=min(f[i][y],f[x][y]+2*(dist[x][i]-'0'));
            f[i][y+1]=min(f[i][y+1],f[x][y]+dist[x][i]-'0');
         }
    }
    int ans=2e9;
    for(int i=0;i<=k;i++) ans=min(ans,f[1][i]);
    cout<<ans;
    return (double)ans/2.0;
}

T3 TreeAndPathLength2

Description $Description$

问是否存在 n $n$个点，长度为 2 $2$的简单路径有 s $s$条的树。

Solution $Solution$

对于点 i $i$，假设它的度数为 d[i] $d\left[i\right]$，很明显以i为中心的长度为 2 $2$的简单路径的条数为 d[i]×(d[i]−1)2 $\frac{d\left[i\right]\times \left(d\right[i]-1)}{2}$
由于是一棵树，共有 n−1 $n-1$条边，所以所有点的度数加起来是 2n−2 $2n-2$。
并且，对于任意总度数为 2n−2 $2n-2$的连通图，它必然是一棵树。
那么题目就是求 ∑ni=1d[i]=2n−2 $\sum _{i=1}^{n}d\left[i\right]=2n-2$且 ∑ni=1d[i]×(d[i]−1)2=s $\sum _{i=1}^n\frac{d\left[i\right]\times \left(d\right[i]-1)}{2}=s$的树是否存在。
考虑DP。
用 f[i][j][k] $f\left[i\right]\left[j\right]\left[k\right]$表示 ∑iu=1d[u]=j $\sum _{u=1}^{i}d\left[u\right]=j$且 ∑iu=1d[u]×(d[u]−1)2=k $\sum _{u=1}^i\frac{d\left[u\right]\times \left(d\right[u]-1)}{2}=k$的方案是否存在，然后枚举下一个点的度数，就可以转移了，注意必须 d[i]>0 $d\left[i\right]>0$，因为树是联通的。
这个复杂度看起来非常玄学，但是仔细想一下感觉还是非常有道理的。

#include <bits/stdc++.h>
using namespace std;
int f[51][101][1001];

class TreeAndPathLength2 {
public:
    string possible( int n, int s );
};
string TreeAndPathLength2::possible(int n, int s) {
    f[0][0][0]=1;
    int m=(n-1)<<1;int w;
    for(int i=0;i<n;i++)
     for(int j=0;j<m;j++)
      for(int k=0;k<s;k++)
       if (f[i][j][k])
        for(int l=1;j+l<=m;l++){
            w=l*(l-1)>>1;
            if (k+w>s) break;
            f[i+1][j+l][k+w]=1;
        }
    if (f[n][m][s]) return "Possible";
     else return "Impossible";
}