Codeforces Edu Round 47 A-E

A. Game Shopping

按照题意模拟既可。

#include <iostream>

#include <cstdio>

using namespace std;

const int N = 1010;

int n, m, c[N], a[N], ans = 0;

int main(){

    scanf("%d%d", &n, &m);

    for(int i = 1; i <= n; i++) scanf("%d", c + i);

    for(int i = 1; i <= m; i++) scanf("%d", a + i);

    for(int i = 1, j = 1; i <= n; i++)

        if(c[i] <= a[j]) ans ++, j++; 

    printf("%d", ans);

    return 0;

}

B. Minimum Ternary String

邻项交换的特性决定了1可以随意活动。
0和2唯独相互遇上不可交换，也就是说0和2的相对位置保持不变。

依据特性，将1尽量靠前放置既可。

#include <iostream>

#include <cstdio>

#include <string>

using namespace std;

string str;

int main(){

    cin >> str;

    int cnt = 0;

    for(int i = 0; i < str.size(); i++)

        if(str[i] == '1') cnt ++ ;

    for(int i = 0; i < str.size(); i++){

        if(str[i] == '1') continue;

        else if(str[i] == '2' && cnt){

            for(int j = 0; j < cnt; j++) printf("1"); cnt = 0;

        }

        printf("%c", str[i]);

    }

    if(cnt)for(int j = 0; j < cnt; j++) printf("1");

    return 0;

}

C. Annoying Present

要使平均值最大，只需让总和最大即可。

$x * d$ 的贡献是定值，只关注 $\sum\limits_{i=1}^n\ d * |i - j|$ 既可。

若 $d > 0$，则令 $\sum\limits_{i=1}^n\ |i - j|$ 最大。显然 $i$ 取 $0$ 或 $n$ 时，值最大。
若 $d < 0$ ，则令 $\sum\limits_{i=1}^n\ |i - j|$ 最小。显然 $i$ 取 n 中位数 $ \lfloor (n + 1) / 2\rfloor$时，值最小。

#include <iostream>

#include <cstdio>

#include <cmath>

using namespace std;

const int N = 100010;

typedef long long LL;

int n, m, x, d;

LL sum = 0, MAX = 0, MIN = 0;

int main(){

    scanf("%d%d", &n, &m);

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

        MAX += abs(i - 1);

        MIN += abs(i - (n + 1) / 2);

    }

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

        int x, d; scanf("%d%d", &x, &d);

        if(d > 0) sum += x * n + d * MAX;

        else sum += x * n + d * MIN;

    }

    printf("%.15f", double(sum) / n);

    return 0;

}

D. Relatively Prime Graph

暴力可行。

任取两个正整数，他们互素的概率为$6/π^2$。参考

维基百科: In a sense that can be made precise, the probability that two randomly chosen integers are coprime is $6/π^2$ (see pi), which is > about 61%. See below.

则我们最多只需筛选 $100000 / 6/π^2 \approx 100000 / 61\% < 200000$ 的数，不会超时。

#include <iostream>

#include <cstdio>

#include <vector>

using namespace std;

const int N = 100010;

int n, m, tot = 0;

int gcd(int a, int b){

    return b ? gcd(b, a % b) : a;

}

vector<int> G[N];

void gcd_prework(){

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

        for(int j = i + 1; j <= n; j++){

            if(gcd(i, j) == 1){

                 ++tot; G[i].push_back(j);

                 if(tot >= m) return;

            }

        }

    }

}

int main(){

    scanf("%d%d", &n, &m);

    if(m < n - 1)

        puts("Impossible");

    else{

        gcd_prework();

        if(tot < m) puts("Impossible");

        else{

            puts("Possible");

            for(int i = 1; i <= n; i++)

                for(int j = 0; j < G[i].size(); j++)

                    printf("%d %d\n", i, G[i][j]);

        }

    }

    return 0;

}

E - Intercity Travelling

退了半天式子自闭了，找规律题，从前一步推向后一步既可。把图画出来可能好理解一点。

#include <iostream>

#include <cstdio>

using namespace std;

typedef long long LL;

const int N = 1000010, Mod = 998244353;

int n, a[N], s, g;

int main(){

    scanf("%d", &n);

    for(int i = 1; i <= n; i++) scanf("%d", a + i);

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

        s = ((LL)s * 2 + a[i] + a[i - 1] + g * 2) % Mod;

        g = ((LL)g * 2 + a[i - 1]) % Mod;

    }

    cout << s;

    return 0;

}

巴特西