牛客多校第十场

August 11, 2020 · 算法 · 200次阅读

总结

(本场全程跟跑)到了牛客的最后一场,仍然是全方面的不行。数论的题到现在看来部分都是规律题,实际上就算场上推不出来关系也能多少猜出来关系,不能想的太多。模拟题跟着题目走暴力基本都能过,但一旦扯到dp、搜索的变形、并查集等数据结构就会不知所措,还是题目做的太少了。
先开坑。

Permutation

AC代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
const int maxn = 1000000 + 10;
const int mod = 1e9 + 7;

inline bool read(int &num) {
    //quick read
    char in;
    bool IsN = false;
    in = getchar();
    if (in == EOF) return false;
    while (in != '-' && (in < '0' || in > '9')) in = getchar();
    if (in == '-') {
        IsN = true;
        num = 0;
    } else num = in - '0';
    while (in = getchar(), in >= '0' && in <= '9') { num *= 10, num += in - '0'; }
    if (IsN) num = -num;
    return true;
}

void solve() {
    int ans = 1, a[maxn], n, x = 1;
    bool flag[maxn];
    memset(flag, false, sizeof(flag));
    read(n);
    flag[1] = true;
    a[0] = 1;
    for (int i = 1; i <= n - 2; i++) {
        bool flags = false;
        if (x * 2 < n && !flag[x * 2]) {
            x *= 2;
            flag[x] = true;
            flags = true;
            a[ans++] = x;
        } else if (x * 2 % n < n && !flag[x * 2 % n]) {
            x = x * 2 % n;
            flag[x] = true;
            flags = true;
            a[ans++] = x;
        } else if (x * 3 % n < n && !flag[x * 3 % n]) {
            x = x * 3 % n;
            flag[x] = true;
            flags = true;
            a[ans++] = x;
        }
        if (!flags) {
            cout << "-1" << endl;
            return;
        }
    }
    for (int i = 0; i < ans - 1; i++) {
        cout << a[i] << " ";
    }
    cout << a[ans - 1] << endl;
}

int main() {
    int T;
    for (cin >> T; T--;) solve();
    return 0;
}
本题参考cyl大佬代码

Game

STD代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
ll a[maxn];
int main()
{
    int t,n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        int x,ans=0;double sum=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&a[i]);
            sum+=a[i];
            x=ceil(sum/i);
            ans=max(ans,x);
        }
        printf("%d\n",ans);
    }
    return 0;
}

Tournament

AC代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
const int maxn = 300 + 10;
const int mod = 1e9 + 7;

inline bool read(int &num) {
    //quick read
    char in;
    bool IsN = false;
    in = getchar();
    if (in == EOF) return false;
    while (in != '-' && (in < '0' || in > '9')) in = getchar();
    if (in == '-') {
        IsN = true;
        num = 0;
    } else num = in - '0';
    while (in = getchar(), in >= '0' && in <= '9') { num *= 10, num += in - '0'; }
    if (IsN) num = -num;
    return true;
}

int verify(int x, int y, int n) {
    return (x - 1) - (n - y);
}

bool cmp(const pi &a, const pi &b) {
    if (a.second != b.second) return a.second < b.second;
    return a.first < b.first;
}

void solve() {
    int n;
    vector<pi> v;
    bool vis[maxn][maxn];
    memset(vis, true, sizeof(vis));
    read(n);
    for (int i = 1; i <= n - 1; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (verify(i, j, n) < 0) {
                v.emplace_back(i, j);
                vis[i][j] = false;
            }
        }
    }
    sort(v.begin(), v.end(), cmp);
    for (auto it:v) {
        cout << it.first << " " << it.second << endl;
    }
    for (int i = 1; i <= n - 1; i++)
        for (int j = i + 1; j <= n; j++)
            if (vis[i][j]) cout << i << " " << j << endl;
}

int main() {
    int T;
    for (cin >> T; T--;) solve();
    return 0;
}

Identical Trees

AC代码

待补

牛客多校模拟搜索网络流

最后编辑于1年前

添加新评论