CodeForces 1009 div2 ABCD

EndlessLethe原创文章,转载请注明: 转载自小楼吹彻玉笙寒

本文链接地址: CodeForces 1009 div2 ABCD

CodeForces 1009 div2 ABCD / Educational Codeforces Round 47 div2 ABCD

A Game Shopping

一眼题,随便以一个文本作为基础,扫描另外一个即可

/**
 * @Date:   16-Jul-2018
 * @Email:  zengsw_study@qq.com
 * @Filename: A.cpp
 * @Last modified time: 17-Jul-2018
 * @Copyright: Copr. 2018 EndlessLethe. All rights reserved.
 * @Description:
 */

#include <stdlib.h>
#include <iostream>
using namespace std;

const int MAXN = 1000;
int a[MAXN], b[MAXN];

int main() {
    int N, M;
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < M; i++) {
        cin >> b[i];
    }
    int j = 0, i = 0;
    for (i = 0; i < M && j < N; i++) {
        while (b[i] < a[j]) {
            j++;
            continue;
        }
        if (j >= N) break;
        j++;
//      cout << j << endl;
    }
    cout << i << endl;
    return 0;
}

B Minimum Ternary String

本来想的是模拟,但2001这种通过单纯贪心模拟是解决不了的,需要关注一下这种交换的特点:
2相当于分隔符,0不可能越过2。但1可以
故1会被提前,而0和2的相对位置不会再变化了

/**
 * @Date:   17-Jul-2018
 * @Email:  zengsw_study@qq.com
 * @Filename: B【第三版】.cpp
 * @Last modified time: 17-Jul-2018
 * @Copyright: Copr. 2018 EndlessLethe. All rights reserved.
 * @Description:
 */

#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;

const int MAXN = 100000+50;
char a[MAXN], b[MAXN];

//2相当于分隔符,0不可能越过2。但1可以
//故1会被提前,之后的0和2不会再变化了
int main() {
    scanf("%s", a);
    int cntOne = 0;
    for (int i = 0; a[i] != '\0'; i++) {
        if (a[i] == '1') {
            cntOne++;
        }
    }
    int j = 0, firstTwo = 0;
    for (firstTwo = 0; a[firstTwo] != '\0' && a[firstTwo] != '2'; firstTwo++) {
        if (a[firstTwo] == '0') b[j++] = '0';
    }
//  cout << cntOne << endl;
    for (int i = 0; i < cntOne; i++) {
        b[j++] = '1';
    }
    for (int i = firstTwo; a[i] != '\0'; i++) {
        if (a[i] != '1') b[j++] = a[i];
    }
    printf("%s\n", b);
    return 0;
}

C Annoying Present

这道题的题面感人,我怀疑是中国人或者毛子出的题。
初始数组是什么也没说清楚(全为0的数组)。“average arithmetic mean”是什么也没说清楚(每一对x, d最大值之和的平均)。

正确的理解是:对于每一对x,d任意选取i,找最大的Smax。再求和取平均。
根据题意有:\(S=max(nx+d\Sigma_j|i-j|)\)
故我们分d<0和d>=0来讨论:对于任意i,\(\Sigma_j|i-j|\) 整个式子的极大极小值在哪里可以取到
显然极大值是在i=1时取到,极小值是在i=n/2时取到,这里要讨论下奇偶
这里给出结论
$$
S_{max} = \left\{ \begin{array}{ll}
nx+d \cdot \frac{N+1}{2} \cdot \frac{N-1}{2} & (d<0)\\
nx+d \cdot \frac{n^2-n}{2} & (d>=0)
\end{array} \right.
$$

公式里的(N+1)/2和(N-1)/2都是向下取整
遍历每一对x,d即可求得

Note:这道题是真·恶心。全部用ll(如果是浮点数double,不是浮点数用ll)。直接用double也会WA

/**
 * @Date:   16-Jul-2018
 * @Email:  zengsw_study@qq.com
 * @Filename: C.cpp
 * @Last modified time: 17-Jul-2018
 * @Copyright: Copr. 2018 EndlessLethe. All rights reserved.
 * @Description:
 */

#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <iomanip>
using namespace std;

typedef long long ll;
#define MAXN 100050
#define EPS 1e-8

ll N, M;
ll getAns(ll x, ll d) {
    ll ans = 0;
    if (d > 0) {
        return N*x+d*(N*N-N)/2;
    }

    else {
        ll l=(1+N)>>1;
        ll num1=l-1,num2=N-l;
        return N*x + d*(N+1)*(N + 1) / 4;
    }
}

int main() {
    cin >> N >> M;
    ll res = 0;
    ll x, d;
    for (int i = 0; i < M; i++) {
        cin >> x >> d;
        res += getAns(x, d);
//      cout << res << endl;
    }
    cout <<  setiosflags(ios::fixed) << setprecision(15) << (double)res / N << endl;
    return 0;
}

D Relatively Prime Graph

  1. 确定存在多少对互质的数
  2. 不断生成
    第一步通过欧拉函数NlogN。第二步暴力
    为了保证所有点联通,还要额外判断一下
/**
 * @Date:   16-Jul-2018
 * @Email:  zengsw_study@qq.com
 * @Filename: D.cpp
 * @Last modified time: 17-Jul-2018
 * @Copyright: Copr. 2018 EndlessLethe. All rights reserved.
 * @Description:
 */

#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;

typedef long long ll;
#define MAXN 100050
ll minDiv[MAXN], phi[MAXN], sum[MAXN];

void genPhi() {
    for (int i = 1; i < MAXN; i++) minDiv[i] = i;
    for (int i = 2; i < MAXN; i++)
        if (minDiv[i] == i)
            for (ll j = (ll)i*i; j < MAXN; j += i)
                minDiv[j] = i;
    phi[1] = 1;
    for (int i = 2; i < MAXN; i++) {
        phi[i] = phi[i / minDiv[i]];
        if ((i / minDiv[i]) % minDiv[i] == 0) phi[i] *= minDiv[i];
        else phi[i] *= minDiv[i] - 1;
    }
}

void getSum() {
    sum[0] = phi[0];
    for (int i = 1; i < MAXN; i++) {
        sum[i] = sum[i-1] + phi[i];
    }
}

ll gcd(ll a,ll b) {
    return b == 0  ? a : gcd(b, a%b);
}

int main() {
    genPhi();
    getSum();
    int N, M;
    cin >> N >> M;
    if (sum[N]-1 < M || M+1 < N) {
        cout << "Impossible" << endl;
        return 0;
    }
    else cout << "Possible" << endl;
//  for (int i = 0; i < 30; i++) cout << sum[i] << endl;
    int cnt = 0;
    for (int i = 1; i < N; i++) {
        if (cnt == M) break;
        for (int j = i+1; j <= N; j++) {
            if (cnt == M) break;
            if (gcd(i, j) == 1) {
                cnt++;
                cout << i << " " << j << endl;
            }
        }
    }
    return 0;
}

参考文献

I. Educational Codeforces Round 47 (Rated for Div. 2) —- C Annoying Present

发表评论

电子邮件地址不会被公开。 必填项已用*标注