Codeforces Round #519

2024-04-05 13:40:00

题目链接：传送门

A. Elections （思维+暴力）

思路：

　　从最小的k开始枚举就好了- -。

#include <bits/stdc++.h>

using namespace std;

const int MAX_N =  + ;

int a[MAX_N];

int main()

{

    int N;

    cin >> N;

    int m = -, sum = ;

    for (int i = ; i <= N; i++) {

        scanf("%d", a+i);

        m = max(m, a[i]);

        sum += a[i];

    }

    int ans = m;

    int Awruk = N*m-sum;

    while (Awruk <= sum) {

        Awruk += N;

        ans++;

    }

    cout << ans << endl;

    return ;

}

B. Lost Array （暴力枚举）

思路：

　　把差分预处理出来，枚举长度，可以跑到最后的就加入答案。

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e3 + ;

int a[MAX_N];

int b[MAX_N];

int ans[MAX_N];

int main()

{

    int N;

    cin >> N;

    a[] = ;

    for (int i = ; i <= N; i++) {

        scanf("%d", a+i);

        b[i] = a[i] - a[i-];

    }

    int cnt = ;

    for (int i = ; i <= N; i++) {

        int j;

        for (j = ; j <= N; j++) {

            if (b[j] != b[(j-)%i+])

                break;

        }

        if (j == N+)

            ans[cnt++] = i;

    }

    cout << cnt << endl << ans[];

    for (int i = ; i < cnt; i++)

        cout << ' ' << ans[i];

    cout << endl;

    return ;

}

C. Smallest Word （思维）

思路：

　　遇到连续的a就找到最后一个，翻转。

　　遇到连续的b也找到最后一个，如果下一个是a，翻转。

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e3 + ;

bool ans[MAX_N];

int main()

{

    string s;

    memset(ans, false, sizeof ans);

    cin >> s;

    int len = s.size();

    int i = ;

    while (i < len) {

        while (i < len && s[i] == 'a')

            i++;

        ans[i-] = true;

        while (i < len && s[i] == 'b')

            i++;

        if (i < len && s[i] == 'a')

            ans[i-] = true;

    }

    cout << ans[];

    for (int i = ; i < len; i++)

        cout << ' ' << ans[i];

    cout << endl;

    return ;

}

D. Mysterious Crime （尺取+暴力）

思路：

　　从第一行开始，往下面几行找最长的匹配。每行从上一行的最左端的数开始往右匹配，匹配到不同的就break，进入下一行。

　　预处理一个pos[i][j]，表示第i行的值为j的数在哪个位置。

　　找完最后一行后得到最长的匹配的长度为len，计算len对答案产生的贡献。

　　注意M为1的时候不能匹配要特判一下，答案就是N*（N+1）/2。

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5 + ;

const int MAX_M =  + ;

int N, M;

int a[MAX_M][MAX_N];

int pos[MAX_M][MAX_N];

bool vis[MAX_N];

int main()

{

    cin >> N >> M;

    memset(vis, false, sizeof vis);

    for (int i = ; i <= M; i++)

        for (int j = ; j <= N; j++) {

            scanf("%d", &a[i][j]);

            pos[i][a[i][j]] = j;

        }

    long long ans = ;

    for (int i = ; i <= N; i++) if (!vis[a[][i]]){

        int l = i, r = N;

        long long len = ;

        for (int j = ; j <= M; j++) {

            int nxtl, nxtr;

            nxtl = nxtr = pos[j][a[j-][l]];

            while (l <= r && nxtr <= N && a[j][nxtr] == a[j-][l]) {

                l++;

                nxtr++;

            }

            l = nxtl, r = nxtr-;

            if (j == M) {

                len = r-l+;

                for (int k = l; k <= r; k++)

                    vis[a[M][k]] = true;

            }

        }

        ans += (len+)*len/;

    }

    if (M == )

        ans = (long long)(N+)*N/;

    cout << ans << endl;

    return ;

}

E. Train Hard, Win Easy（思维+排序）

思路：

　　两个人（u，v）组队时他们的得分是min（x_u+y_v，x_v+y_u），考虑到：

　　 x_u+y_v ＜ x_v+y_u

　　=>y_v-x_v ＜ y_u-x_u

　　令d_i = y_i-x_i，则组队时d小的一方出y，d大的一方出x。

　　根据d排序后，对于（1 ≤ i ＜ j ≤ N）有d_i ＜ d_j，所以第i个人和第j个人组队的得分为y_i+x_j。

　　预处理x和y的前缀和，对于第i个人，他与在他之前的人组队的得分为：

　　　　$\sum_{j=1}^{i-1}y_{j}$ + x_i * （i-1）;

　　与在他之后的人组队的得分为：

　　　　$\sum_{j=i+1}^{N}x_{j}$ + y_i * （N-i）;

　　这样可以O(1)算出每个人的得分，然后再减去不能和自己比赛的人的贡献就好了。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAX_N = 3e5 + ;

struct Node{

    int ind;

    ll x, y;

    ll d;

    Node(int _i = , ll _x = , ll _y = ) : ind(_i), x(_x), y(_y) {d = y-x;}

    bool operator < (const Node& a) const {

        return d < a.d;

    }

}nodes[MAX_N];

ll sumx[MAX_N], sumy[MAX_N];

ll ans[MAX_N];

int main()

{

    int N, M;

    cin >> N >> M;

    memset(ans, , sizeof ans);

    for (int i = ; i <= N; i++) {

        ll x, y;

        scanf("%I64d%I64d", &x, &y);

        nodes[i] = Node(i, x, y);

    }

    for (int i = ; i <= M; i++) {

        int u, v;

        scanf("%d%d", &u, &v);

        ll tmp = ;

        if (nodes[u] < nodes[v])

            tmp = nodes[u].y + nodes[v].x;

        else

            tmp = nodes[v].y + nodes[u].x;

        ans[u] -= tmp;

        ans[v] -= tmp;

    }

    sort(nodes+, nodes++N);

    sumx[] = sumy[] = ;

    for (int i = ; i <= N; i++) {

        sumx[i] = sumx[i-] + nodes[i].x;

        sumy[i] = sumy[i-] + nodes[i].y;

    }

    for (int i = ; i <= N; i++) {

        Node cur = nodes[i];

        ans[cur.ind] += sumy[i-] + cur.x*(i-);

        ans[cur.ind] += sumx[N] - sumx[i] + cur.y*(N-i);

    }

    bool firstprint = true;

    for (int i = ; i <= N; i++) {

        if (firstprint)

            firstprint = false;

        else

            printf(" ");

        printf("%I64d", ans[i]);

    }

    puts("");

    return ;

}

F. Make It One（组合数学+数论+dp）

思路：

　　说实话这题比较玄学。

　　2 * 3 * 5 * 7 * 11 * 13 * 17 ≈ 5e5，所以3e5范围内一个数最多有6个质因数。所以答案是不会超过6的，考虑从1开始枚举答案。

状态：

　　f[i][j]表示选择的数字数量为i时，最大公约数为j的方案数，若f[i][1] ＞ 0，就说明符合题意，直接输出。

　　已知所有的ai中j的倍数有cnt[j]个，则由容斥原理知：

状态转移方程：

　　f[i][j] = $C_{cnt[j]}^{i}-\sum_{k=2}^{\infty}f[i][k*j]$

组合数预处理一个逆元可以O(1)求出，总时间复杂度为O(loga * (N + a))

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 3e5 + ;

const int MOD = 1e9 + ;

int fpow(int a, int p) {

    int ans = ;

    while (p) {

        if (p&) ans = (1LL * ans * a) % MOD;

        p >>= ;

        a = (1LL * a * a) % MOD;

    }

    return ans;

}

int N;

int a[MAX_N];

int f[][MAX_N], cnt[MAX_N];

int fac[MAX_N], inv[MAX_N];

int newton(int m, int n) {

    if (n <  || m < n) return ;

    return ((1LL * fac[m] * inv[n])%MOD * inv[m-n]) % MOD;

}

void init() {

    fac[] = ;

    for (int i = ; i <= MAX_N; i++)

        fac[i] = (1LL * fac[i-] * i) % MOD;

    inv[MAX_N-] = fpow(fac[MAX_N-], MOD-);

    for (int i = MAX_N-; i >= ; i--)

        inv[i-] = (1LL * inv[i] * i) % MOD;

}

void sub(int& a, int b) {

    a -= b;

    if (a < )

        a += MOD;

}

int main()

{

    init();

    scanf("%d", &N);

    memset(cnt, , sizeof cnt);

    for (int i = ; i <= N; i++) {

        scanf("%d", a+i);

        cnt[a[i]]++;

    }

    for (int i = ; i < MAX_N; i++) {

        for (int j = *i; j < MAX_N; j += i) {

            cnt[i] += cnt[j];

        }

    }

    for (int i = ; i < ; i++) {

        for (int j = MAX_N-; j >= ; j--) {

            f[i][j] = newton(cnt[j], i);

            for (int k = j+j; k < MAX_N; k += j)

                sub(f[i][j], f[i][k]);

        }

        if (f[i][] > ) {

            printf("%d\n", i);

            return ;

        }

    }

    puts("-1");

    return ;

}

码农公寓

相关文章