第十一届北京邮电大学程序设计竞赛

第十一届北京邮电大学程序设计竞赛 - 热身赛 (1)

注册新账号即可参加比赛(已被延长为3W分钟)

A.预处理筛出2^15以内的质数然后枚举计数即可

#include <cstdio>

int p[60000], v[60000];

int main() {
    for(int i = 2;i <= 50000;i ++) {
        if(!v[i]) p[++ p[0]] = i;
        for(int j = 1;j <= p[0] && 1ll * i * p[j] <= 50000;j ++) {
             v[i * p[j]] = 1;
             if(i % p[j] == 0) break;
        }
    }
    int n, m;
    while(scanf("%d", &n), n) {
        m = 0;
        for(int i = 2;i + i <= n;i ++)
            if(!v[i] && ! v[n - i])
                m ++;
        printf("%d
", m);
    }
    return 0;
}

B.一个比较典型的背包问题

f[i]表示组成 i 元的方案数

然后分别用面值1 4 9 ... 289的coin更新17次就好了

#include <cstdio>

typedef long long ll;

const ll Mod = 1000000009;

int s[18];

ll f[2222];

int main() {
    f[0] = 1;
    for(int i = 1;i <= 17;i ++)
        s[i] = i * i;
    for(int j = 1;j <= 17;j ++)
        for(int i = s[j];i <= 2000;i ++)
            f[i] = (f[i] + f[i - s[j]]) % Mod;
    int t, n;
    scanf("%d", &t);
    while(t --) {
        scanf("%d", &n);
        printf("%lld
", f[n]);
    }
    return 0;
}

C.注意到题目描述最后一句

little Ding is concerned about the answer of every user's new friends

when that user is the only one who adds new friends

所以并不是并查集

直接枚举就好了，注意到为了防止一个人与自己建立新边并计入答案

我们一开始就设置好 i 和 i 自己是朋友即可

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>

using namespace std;

vector <int> e[1010];

int t, m, n, p, f[1010];

int main() {
    cin >> t;
    while(t --) {
        cin >> n >> m;
        for(int i = 1;i <= n;i ++)
            f[i] = 0, e[i].clear();
        for(int u, v, i = 1;i <= m;i ++) {
            scanf("%d %d", &u, &v);
            e[u].push_back(v);
            e[v].push_back(u);
        }
        for(int i = 1;i <= n;i ++) {
            p = 0, f[i] = i;
            for(int j = 0;j < e[i].size();j ++)
                f[e[i][j]] = i;
            for(int j = 0;j < e[i].size();j ++)
                for(int u = e[i][j], k = 0;k < e[u].size();k ++)
                    if(f[e[u][k]] != i) f[e[u][k]] = i, p ++;
            printf("%d
", p);
        }
    }
    return 0;
}

D.last[i]表示当 i 是选中的区间的最右端时，最左端可以在last[i] + 1的位置

pre[i]表示 ai 上一次出现的位置，初始化均为0

显然就有 last[i] = max(pre[j])， 1 <= j <= i

ans = max(i - last[i]). 1 <= i <= n

所以从左向右O(n)扫一遍即可

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

int t, n, l, a, m, p[100010];

int main() {
    cin >> t;
    while(t --) {
        m = 1, l = 0;
        cin >> n;
        memset(p, 0, sizeof p);
        for(int i = 1;i <= n;i ++) {
            scanf("%d", &a);
            if(p[a]) l = max(l, p[a]);
            p[a] = i, m = max(m, i - l);
        }
        cout << m << endl;
    }
    return 0;
} 

G.看样例xjb猜一下

分子是lcm，分母是gcd

然后就过了...

正确性简单证明:

要求n个分数的lcm

那么我们...嗨呀好麻烦自己脑补吧233

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

vector <ll> a, b;

ll gcd(ll x, ll y) {
    return y ? gcd(y, x % y) : x;
}

int main() {
    int n;
    ll x, y, X, Y;
    while(~scanf("%d", &n)) {
        a.clear(), b.clear();
        while(n --) {
            scanf("%lld %lld", &x, &y);
            a.push_back(x);
            b.push_back(y);
        }
        X = a[0], Y = b[0];
        for(int i = 1;i < a.size();i ++)
            X = X / gcd(X, a[i]) * a[i], Y = gcd(Y, b[i]);
        printf("%lld %lld
", X, Y);
    }
    return 0;
}