A. 战争尾声

题解

暴力通过：

image-20210123083541553

坐标范围不大，尝试每个点也就是200*200

还需要查看所有的国家 是否 距离当前尝试的点 距离相等 200*200 * n (n最大200)

O(8000000)

暴力可过

Code

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
const double M = 1e-4;

// 距离
double f(int x, int y, pair<int, int> p)
{
    return (sqrt(pow(x - p.first, 2) + pow(y - p.second, 2)));
}

vector<pair<int, int>> v;
int N;

void solve()
{
    for (int i = 1; i <= 200; i++)
    {
        for (int j = 1; j <= 200; j++)
        {
            int q = 0;
            double k = f(i, j, v[0]); // 求第一个点的距离 看后面的点是不是都相等
            for (int p = 1; p < N; p++)
            {
                double kt = f(i, j, v[p]);

                if (fabs(kt - k) > M) // 浮点数判相等
                {
                    q = 1;
                    break;
                }
            }
            if (q == 0)
            {
                cout << i << " " << j << endl;
                return;
            }
        }
    }
    cout << "War is cruel.";
}
int main()
{
    cin >> N;

    for (int i = 0; i < N; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        v.push_back({x, y});
    }

    solve();
    return 0;
}

B. 签订协议

题解

主要是超时，但AC代码也不难想

N最大10的6次方 所以N * N算法 和 N * NlongN 都是不行的

下面的是NlogN

观察样例1：

5
1 5 8 4 3

第一轮是8，8后面没有比他大的；所以需要第二轮：5 4 3 ，这三个之所以可以一轮完成，是因为 4的位置在5的后面，3的位置在4的后面；

故可将数与出现的位置练习起来，进行排序。

排完之后：

8 3

5 2
4 4
3 5

1 1

排完序之后的工作就成了找上升区间的个数

Code

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int main()
{
    int N;
    cin >> N;
    vector<pair<int, int>> v;
    int x;
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &x);
        v.push_back({x, i});
    }

    // greater 从大到小排序
    sort(v.begin(), v.end(), greater<pair<int, int>>());


    int k = 1;

    for (int i = 0; i < N - 1; i++)
    {
        if (v[i + 1].second < v[i].second)
            k++;
    }
    cout << k;
    return 0;
}

C. 照看小猫

题解

相当于是排列组合的分布原则(乘)

每个小猫名字的方案数乘其他小猫名字的方案数

乘的时候需要减去重复的

Code

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
using LL = long long;
int main()
{
    int N;
    cin >> N;
    int64_t sum = 1;
    int64_t a[15] = {0};
    // 提前算了
    for (int i = 1; i <= 10; i++)
        a[i] = int64_t(int64_t(pow(26, i)) % 77797 + a[i - 1]) % 77797;


    int v[N + 10];
    for (int i = 0; i < N; i++)
          cin >> v[i];

    sort(v, v + N);
    for (int i = 0; i < N; i++)
    {
        sum *= (a[v[i]] - i); // 这只小猫的情况数-之前小猫的数量 去掉了重复
        sum %= 77797;
    }
    if (sum != 0)
        cout << sum;
    else
        cout << -1;
    return 0;
}

D. 路线规划

模板题

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
using LL = long long;
vector<LL> dp;
struct node
{
    LL x, y, t;
    bool operator<(const node e)
    {
        return t < e.t;
    }
};

LL findt(LL x)
{
    return dp[x] == x ? x : dp[x] = findt(dp[x]);
}
int main()
{
    LL N, M;
    cin >> N >> M;
    dp.resize(N + 10);

    iota(dp.begin(), dp.end(), 0);
    LL x, y, t;
    vector<node> v;
    while (M--)
    {
        cin >> x >> y >> t;
        v.push_back({x, y, t});
    }

    sort(v.begin(), v.end());

    LL ans = 0;
    for (auto &e : v)
    {
        LL x = findt(e.x);
        LL y = findt(e.y);
        if (x == y)
            continue;

        ans += e.t;
        dp[x] = y;
    }
    cout << ans * 2;
    return 0;
}