概述

C 可以一做。

别问为什么就三道题。

A

Description

给定两个数，每次用大数减去小数的差代替这个数，并称为一次操作。问有一个数为 $0$ 的时候一共有多少次操作。

输入：第一行是一个正整数 $n$，表示数据的组数。接下来 $n$ 行，每行两个正整数 $a_i$ 和 $b_i$ 表示给定的两数。

$a_i,b_i\leq10^9$。

Solution

发现这就是一个辗转相减求最大公约数的流程，显然暴力不行。

但我们在普通辗转相除求最大公约数的时候统计一下答案就行。

属实是考验了对基础算法的理解。

Code

#include <iostream>
#include <algorithm>
using std::cin;
using std::cout;

int ans = 0;

int gcd(int x, int y)
{
    if (y == 0)
        return x;
    ans += x / y;
    return gcd(y, x % y);
}

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int a, b;
        cin >> a >> b;
        if (a < b)
            std::swap(a, b);
        ans = 0;
        gcd(a, b);
        cout << ans << std::endl;
    }
}

B

Description

给定 $n$ 和 $n$ 个二元组 $(a_i,b_i)$ 。

你可以任意排列这几个二元组，也可以任意更换一个二元组之间的两个元素的顺序。

是否存在一种解，使得任意相邻的两个二元组中，相邻的两个元素相等。

输出其排列顺序，并输出其是否需要改变两个元素的顺序。

Solution

这个东西一看就非常欧拉路，我们把二元组的两个数之间连一个双向边，然后找欧拉路即可。

最后输出边的方案。

Code

#include <iostream>
#include <stack>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::cerr;

const int maxn = 110;

struct edge
{
    int y, i, pos;
};

std::vector<edge> e[maxn];
inline void add(int x, int y, int i) { e[x].push_back({y, i, 1}), e[y].push_back({x, i, 0}); }

std::stack<edge> ans;

int vis[maxn];

void dfs(int x)
{
    edge i;
    while (e[x].size())
    {
        int y = e[x].back().y;
        i = e[x].back();
        e[x].pop_back();
        if (vis[i.i])
            continue;
        vis[i.i] = 1;
        dfs(y);
        ans.push(i);
    }
}

int deg[maxn], n;

int main()
{
    std::ios::sync_with_stdio(false);
    cin >> n;
    int mx = 0;
    int s = 0;
    for (int i = 1, x, y; i <= n; i++)
        cin >> x >> y, add(x, y, i), deg[x]++, deg[y]++, s = y, mx = std::max(mx, std::max(x, y));
    int flag = 0;
    for (int i = 0; i <= mx; i++)
    {
        if (deg[i] & 1)
            s = i, flag++;
    }
    if (flag != 0 && flag != 2)
    {
        puts("No solution");
        return 0;
    }
    dfs(s);
    if ((int)ans.size() != n)
    {
        puts("No solution");
        return 0;
    }
    while (!ans.empty())
    {
        auto p = ans.top();
        ans.pop();
        cout << p.i << " " << (p.pos ? '+' : '-') << endl;
    }
}

C

Description

给定一张 $n$ 点 $m$ 边的无向的网络流，源点为 $1$，汇点为 $n$。

第 $i$ 条边用有序数对 $(a_i,b_i) (a_i\not= b_i)$ 和容量值 $c_i$ 描述，表示连接 $a_i$ 与 $b_i$，容量为 $c_i$。

你应当给这条边赋一个实数流量 $x_i$，满足 $|x_i|\le c_i$，如果是正的表示从 $a_i$ 流向 $b_i$ 大小为 $x_i$，否则表示从 $b_i$ 流向 $a_i$ 大小为 $-x_i$。

你构造的流需要满足：

  • 流守恒。即对所有不为 $1$ 或 $n$ 的点 $u$，进入 $u$ 的流等于从 $u$ 出去的流。

  • 对任意两个连通的节点 $x,y$，从 $x$ 到 $y$ 的所有路径 $x_i$（流量）的和都是相等的。

现在请输出最大流（可以理解为 $\sum_v x_{1,v}$），并构造一个方案。

$1\leq n\leq100,1\leq m\leq5000$。

Solution

这个题看上去挺莫名其妙的。把样例二画出来：

sample

看看这个图，和红的数字，似乎能发现什么东西…

我们给每个点一个高度（即图中红色的数字）。

根据第二个要求，任意两点之间，不管怎么走，高度的差值是一定的，而相邻两点高度差值就是这条边的流量。

再仔细想一想，在这道题中，图的形态固定，每条边的流量应该是有一个固定的比例的。

根据第一个要求：每个点出的流量和入的流量相等。

设 $out(i)$ 表示 $i$ 连向的点，$in(i)$ 表示连向 $i$ 的点，可以列出来一个方程：$\sum (h_i-h_{in(i)})=\sum(h_{out(i)}-h_i)$。

那么总共有 $n-2$ 个方程。

因为我们实际上是想要求流量，那么源点和汇点高度具体的值是无所谓的，减一下都会按照比例消掉。

我们自己设一下源点和汇点高度。

这样总共就有 $n$ 个方程，我们就可以解出来所有点的高度。（高斯消元）

很显然，如果我们把所有点高度都按照一定比例缩放，这两个限制仍然是成立的。

我们找到能缩放的最大比例，然后进行缩放，就得到了最大流（即和汇点相连的边的流量之和）和每条边的流量。

重边是不用特殊处理的。

复杂度是高斯消元的 $O(n^3)$。

Code

注意除以 $0$。

#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::cerr;

const int maxn = 110;
const double eps = 1e-8;

int e[maxn][maxn], n, m;

inline double change(double x) { return x < eps ? eps : x; }

double a[maxn][maxn];
double root[maxn];

void guass()
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (i == j)
                continue;
            if (fabs(a[i][i]) < eps)
                continue;
            double d = a[j][i] / a[i][i];
            for (int k = i; k <= n + 1; k++)
                a[j][k] -= a[i][k] * d;
        }
    }
    for (int i = 1; i <= n; i++)
        if (fabs(a[i][i]) > eps)
            root[i] = a[i][n + 1] / a[i][i];
}

struct edge
{
    int x, y;
    double cap;
};
std::vector<edge> edges;

inline void add(int x, int y, double cap)
{
    edges.push_back({x, y, cap});
    if (x != 1 && x < n)
        a[x][x]--, a[x][y]++;
    if (y != 1 && y < n)
        a[y][y]--, a[y][x]++;
}
    
int main()
{
    cin >> n >> m;
    double c;
    for (int i = 1, x, y; i <= m; i++)
        cin >> x >> y >> c, add(x, y, c);
    a[1][n + 1] = 1, a[n][n + 1] = n + 1, a[1][1] = 1, a[n][n] = 1;
    guass();
    double mul = 1e18;
    int flag = 0;
    for (auto k : edges)
    {
        if (fabs(root[k.y] - root[k.x]) < eps)
            continue;
        mul = std::min(mul, 1.0 * k.cap / fabs(root[k.y] - root[k.x])), flag = 1;
    }
    if (!flag)
        mul = 0;
    for (int i = 1; i <= n; i++)
        root[i] *= mul;
    double sum = 0;
    for (auto k : edges)
        if (k.x == n || k.y == n)
            sum += fabs(root[k.y] - root[k.x]);
    printf("%lf\n", sum);
    for (auto k : edges)
        printf("%lf\n", root[k.y] - root[k.x]);
}