T1 地铁

标签

图论

最短路

题目大意

有很多个地铁站，现在给定哪些地铁站是相连的。

我们定义任意两个地铁站之间都可以走过去，只有相连的地铁站才可以乘坐地铁。

求从 A 到 B 的最短路径。

思路

由于数据很水，所以普通的 Floyd 就可以过了。

我们先建边。

第一步：把所有地铁站两两相连，权值为距离除以步行的速度。

第二步：把所有联通的地铁站都建上一条权值为距离除以地铁速度的边。

第三步：如果 A 或 B 不是地铁站，令 A 和 B 与其他点建边。

第四步：求最短路，输出

赛事情况

用时 $1$ 小时。

代码长度 $188$ 行。

代码

#include <bits/stdc++.h>
using namespace std;
double vw, vs;//vw = Vwalk,vs = Vsubway
int n;
typedef pair <double, double> pdd;
#define mkp make_pair
vector <int> e[1005];
vector <double> v[1005];
pdd a[201];
map <pdd, int> mp;
double dis[205];
int vis[205];
double mmp[205][205];

double di(double x_, double y_, double x__, double y__) {
    return sqrt(abs(x_ - x__) * abs(x_ - x__) + abs(y_ - y__) * abs(y_ - y__));
}

void addedge(int x, int y, double z) {
    e[x].push_back(y);
    e[y].push_back(x);
    v[x].push_back(z);
    v[y].push_back(z);
    mmp[x][y] = mmp[y][x] = z;
}

struct node {
    int d, p;
    const bool operator <(const node &x) const {
        return x.d < d;
    }
};
priority_queue <node> q;

int main() {
    cin >> vw >> vs;
    cin >> n;

    for (int i = 0; i <= n + 1; i ++) {
        for (int j = 0; j <= n + 1; j ++) {
            mmp[i][j] = 0x7fffffff;
        }
    }

    for (int i = 1; i <= n; i ++) {
        cin >> a[i].first >> a[i].second;
        mp[a[i]] = i;
        dis[i] = 0x7fffffff;
        mmp[i][i] = 0;
    }

    mmp[0][0] = mmp[n + 1][n + 1] = 0;

    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j < i; j ++) {
            int x = i, y = j;
            e[x].push_back(y);
            e[y].push_back(x);
            double z = di(a[x].first, a[x].second, a[y].first, a[y].second) / vw;
            v[x].push_back(z);
            v[y].push_back(z);
            mmp[x][y] = mmp[y][x] = z;
        }
    }

    int x, y;

    while (cin >> x >> y && x != 0 && y != 0) {
        e[x].push_back(y);
        e[y].push_back(x);
        double z = di(a[x].first, a[x].second, a[y].first, a[y].second) / vs;
        v[x].push_back(z);
        v[y].push_back(z);
        mmp[x][y] = mmp[y][x] = z;
    }

    pdd A, B;
    cin >> A.first >> A.second >> B.first >> B.second;

    if (mp[A] == 0) {
        a[0] = A;
        mp[A] = 0;

        for (int i = 1; i <= n; i ++) {
            addedge(0, i, di(a[0].first, a[0].second, a[i].first, a[i].second) / vw);
        }
    }

    if (mp[B] == 0) {
        a[n + 1] = B;
        mp[B] = n + 1;

        for (int i = 1; i <= n; i ++) {
            addedge(n + 1, i, di(a[n + 1].first, a[n + 1].second, a[i].first, a[i].second) / vw);
        }
    }
    for (int k = 0; k <= n + 1; k ++) {
        for (int i = 0; i <= n + 1; i ++) {
            for (int j = 0; j <= n + 1; j ++) {
                mmp[i][j] = min(mmp[i][j], mmp[i][k] + mmp[k][j]);
            }
        }
    }
    printf("%.7lf", mmp[mp[A]][mp[B]]);
}

T2 硬币

标签

DP

思路

一眼 DP。

我们定义 dp[i][j] 为前重量总和为 $i$，价值总和为 $j$。

状态转移方程式就是：

dp[i][j] |=a[i - wei[i]][j - val[i]]

代码

#include <bits/stdc++.h>
using namespace std;

struct str {
    int w, v;
} a[1005];
int n, W, tot, cnt;
int dp[105][10005];
#define V 10005

int main() {
    cin >> W >> n;

    for (int i = 1; i <= n; i ++) {
        int mi, ma, v;
        cin >> v >> mi >> ma;

        for (int j = mi; j <= ma; j ++) {
            a[++cnt].v = v;
            a[cnt].w = j;
        }
    }

    dp[0][0] = 1;

    for (int i = 1; i <= cnt; i ++) {
        for (int j = a[i].w; j <= W; j ++) {
            for (int k = a[i].v; k <= V; k ++) {
                dp[j][k] |= dp[j - a[i].w][k - a[i].v];
            }
        }
    }

    int ans = 0;

    for (int i = 1; i <= V; i ++) {
        if (dp[W][i])
            ans ++;
    }

    cout << ans;
}

T3 旗帜

标签

数学

题意

给定 $n$ 个黄色旗子和 $n$ 个红色旗子排成一排，我们定义如果两个左右挨着的旗子的颜色不同，那么不同度加一。

给定 $n$ 和 $m$，求 $n$ 个黄色旗子和 $n$ 个红旗子排成一列且不同度为 $m$ 的情况下，符合要求的拜访方式有几种。

思路

典型的数学题。

我们可以用 插板法 来推出公式。

公式：
$$
f(n, m) = A_2^2 \times C_{n – 1}^{\frac{m+1}{2}-1} \times C_{n – 1}^{\frac{m+2}{2}-1}
$$
我们直到 $C_a^b$ 的定义就是从 $a$ 里面无序的选取 $b$ 个的排列组合数量。

所以我们可以发现第一种颜色可以被分成 $\frac{m+1}{2}$ 段，第二种颜色可以被分成 $\frac{m+2}{2}$ 段。

而且每种颜色可以交换。

所以就得到这个公式了。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long

int C(int a, int b) {
    //C^a_b
    long long ans = 1;

    for (int i = b; i >= b - a + 1; i --) {
        ans *= i;
    }

    for (int i = 1; i <= a; i ++) {
        ans /= i;
    }

    return ans;
}

signed main() {
    int n, m;
    cin >> n >> m;

    if (m == 1) {
        cout << 2;
        return 0;
    }

    cout << C((m + 2) / 2 - 1, n - 1) * 2ll * C((m + 1) / 2 - 1, n - 1);
}

T4 序列还原

题目

　　给定一棵N个结点的树(即无环连通图)(2<=N<=10000)。所有点编号1到N。我们按照如下顺序打印一个序列：

1、取编号最小的叶子结点(即只连有一条边的点)。
2、打印这个结点的父结点的编号。
3、把这个结点连同他所连的边从树中删去（父结点保留）。
4、重复以上步骤，直到剩下一个点。（显然最后剩下的点编号为N。）

　　按照这样的顺序，我们打印出了N-1个数。
　　给定打印出的序列，请你还原出原来的树。

思路

运用拓扑排序。

自己看代码吧。

代码

#include <bits/stdc++.h>
using namespace std;
int a[10005], n, cnt[10005];
vector <int> e[10005];

int main() {
    int x;
//  cin >> x;

    while (cin >> x) {
        a[++n] = x;
        cnt[x] ++;
    }

    for (int i = 1; i <= n; i ++) {
        int flag;

        for (int j = 1; j <= n + 1; j ++) {
            if (a[i] == j)
                continue;

            if (cnt[j] == 0) {
                flag = j;
                break;
            }
        }

        cnt[flag] --;
        cnt[a[i]] --;
        e[flag].push_back(a[i]);
        e[a[i]].push_back(flag);
    }

    for (int i = 1; i <= n + 1; i ++) {
        sort(e[i].begin(), e[i].end());
        cout << i << ": ";

        for (int j = 0; j < e[i].size(); j ++) {
            cout << e[i][j] << " ";
        }

        cout << "\n";
    }
}