比赛总结

暑期第一次打牛客团队赛，居然运气不错的就中奖了。不过这次的题总体都不难，差1题就可以AK了呢。
还是来总结下吧，先附上算法大纲。

easy：B(模拟)、C(高精度)、G(排序)、H(BF)、I(规律题)、J(简单DP)、L(打表BF)
mid：K(floyd传递闭包)、D(复杂模拟)、F(最短路+二分)
hard：E(二分+并查集)、A(树形DP求最小支配集合)

其中蒟蒻的我写了BCGHIF(果然我只配写简单题)

B-iCow

题意

有N(1 <= N <= 1,000)首歌曲，按照1-N编号。

第i首曲子有一个初始权值R_i(1 <= R_i <= 10,000)。
当一首曲子播放完毕，接下来播放的将是所有曲子中权值最大的那首（如果有两首或多首曲子的权值相同，那么这些曲子中编号最小的那首会被选中）。
一首曲子在播放结束后，它的权值会被平均地分给其他N-1首曲子，它本身的权值清零。

如果一首曲子的权值无法被平均分配（也就是说，无法被N-1整除），那么被N-1除的余数部分将会以1为单位，顺次分配给排名靠前的曲子（也就是说，顺序为曲目1、曲目2...依次下去。当然，刚播放过的那首曲子需要被跳过），直到多出的部分被分配完。
在选定的下一首曲子播放完毕后，这个算法再次被执行，调整曲子的权值，并选出再接下来播放的曲目。

请你计算一下，按FJ的算法，最先播放的T(1 <= T <= 1000)首曲子分别是哪些。

分析

数据不大，简单模拟题。

AC代码

#include <bits/stdc++.h>
#define FAST_IO std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0)
#define pause system("pause")
using namespace std;
typedef long long ll;
typedef unsigned int UINT;
typedef unsigned long long ull;
int const maxn = 1000 + 10;
int a[maxn];
int main(void) {
    FAST_IO;
    int n, t;
    cin >> n >> t; 
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < t; i++) {
        int pos = max_element(a + 1, a + 1 + n) - a;
        cout << pos << endl;
        int x = a[pos] % (n - 1);
        int s = a[pos] / (n - 1);
        a[pos]= 0;
        for (int i = 1; i <= n; i++) {
            if (i == pos) continue;
            a[i] += s;
            if (x) {
                a[i]++;
                x--;
            }
        }
    }

    // pause;
    return 0;
}

C-阶乘之和

题目传送门

分析

python大法真好。

AC代码

n = int(input())
def fact(x):
    s = 1
    for i in range(1, x + 1):
        s *= i
    return s

sum = 0

for i in range(1, n + 1):
    sum += fact(i)
if sum == 0:
    sum += 1
print(sum)

G-Election Time

题目传送门

题意

一场比赛，规则有两轮，再第一轮中选出前k个牛，再在这k只牛中选取第二轮中票数最多的牛，输出它的编号。

分析

进行两次排序就行。

AC代码

#include <bits/stdc++.h>
#define FAST_IO std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0)
#define pause system("pause")
using namespace std;
typedef long long ll;
typedef unsigned int UINT;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
int const maxn = 50000 + 10;
struct node {
    ll a, b;
    int x;
};
node a[maxn];
int main(void) {
    FAST_IO;
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].a >> a[i].b;
        a[i].x = i; 
    }
    sort(a + 1 , a + 1 + k, [](const node &x, const node &y){
        return x.a > y.a;
    });
    sort(a + 1 , a + 1 + k, [](const node &x, const node &y){
        return x.b > y.b;
    });
    cout << a[1].x << endl;
    // pause;
    return 0;
}

H-Costume Party

题目传送门

分析

真的暴力就行了emmm.

AC代码

#include <bits/stdc++.h>
#define FAST_IO std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0)
#define pause system("pause")
using namespace std;
typedef long long ll;
typedef unsigned int UINT;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
int const maxn = 50000 + 10;

int a[maxn];
int main(void) {
    FAST_IO;
    int num = 0;
    int n, s;
    cin >> n >> s;
    for (int i = 0; i < n;i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = i + 1;j < n; j++) {
            if (a[i] + a[j] <= s) 
                ++num;
        }
    }
    cout << num << endl;
    // pause;
    return 0;
}

I-Cantor表

题目传送门

分析

数表提示我们按照斜线分类。第1条斜线有1个数，第2条有2个数，第3条有3个数……第k条有k个数。这样，前k条斜线一共有 $S=1+2+3+……+k$ 个数。

第n项在哪条斜线上呢？只要找到一个最小的k，使得 $S \geq n$ ，那么第n项就是第k条斜线上倒数第S-n+1个数（最后一个元素是倒数第1个元素，而不是倒数第0个元素）。

而k的奇偶决定着第k条斜线上数的顺序：若k是奇数，第k条斜线上倒数第i个元素是 $i \over (k+1-i)$ ；若k是偶数，第k条斜线上倒数第i个元素是 $(k+1-i) \over i$ 。

AC代码

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,h=1;
    cin>>n;
    while(n-h>0)
    {
        n=n-h;
        h++;
    }
    if(!h%2)
    cout<<n<<"/"<<h+1-n<<endl;
    else
    cout<<h+1-n<<"/"<<n<<endl;
    return 0;
}

F-Telephone Lines

题目传送门

题意

找出1-n的通路中，第K+1大的路径权值最小的值。

分析

经典的二分+最短路解法。由于答案具有单调性，所以可以对其二分答案，若路径i的权值大于mid则为1，否则为0。然后进行找1到n的最短路。那么跑完最短路之后，由于小于mid的边权值均为0，1-n最短路的值就是路径上所有比mid大的边的总数。

AC代码

#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned int UINT;
typedef unsigned long long ull;
typedef unsigned long long ull;
#define FAST_IO std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0)
#define PAUSE system("pause")
using namespace std;
int const maxn = 10000 + 10;

struct Node {
    int v, w, next;
}e[maxn << 1];

struct node {
    int u;
    int w;
    node(int const &u = 0, int const &w = 0) : 
        u(u), w(w) {}
    bool operator<(const node &p) const{
        return w > p.w;
    }  
};

int head[maxn], vis[maxn];
int dis[maxn];
int cnt = 0;
int n, m, k;

void add(int u, int v, int w) {
    e[cnt].v = v;
    e[cnt].w = w;
    e[cnt].next = head[u];
    head[u] = cnt++;
}

void dijkstra(int mid) {
    priority_queue<node> q;
    for (int i = 1; i <= n; i++) {
        dis[i] = INT_MAX;
        vis[i] = 0;
    }
    dis[1] = 0;
    q.push(node(1, dis[1]));
    while (!q.empty()) {
        int u = q.top().u;
        q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].v;
            int w = e[i].w > mid ? 1 : 0;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                q.push(node(v, dis[v]));
            }
        }
    }
}

int main(void) {
    FAST_IO;
    memset(head, -1, sizeof(head));

    cin >> n >> m >> k;
    int l = 0, r = -1;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        r = max(r, w);
        add(u, v, w);
        add(v, u, w);
    }
    int mx = r;
    while (l < r) {
        int mid = (l + r) / 2;
        dijkstra(mid);
        if (dis[n] <= k) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    if (mx == r) {
        cout << -1 << endl;
    } else {
        cout << r << endl;
    }
    // PAUSE;
    return 0;
}

牛客假日团队赛8-部分题解

比赛总结

B-iCow

题意

分析

AC代码

C-阶乘之和

分析

AC代码

G-Election Time

题意

分析

AC代码

H-Costume Party

分析

AC代码

I-Cantor表

分析

AC代码

F-Telephone Lines

题意

分析

AC代码