2020年 CSP-S 第一轮（提高级）

满分 100 分

时长 120 分钟

共 43 题

答题卡已答 0/43

已答正确错误编程题

阅阅读程序（共 18 题，共 0 分）

程序代码请先阅读以下程序

#include <iostream>
using namespace std;

int n;
int d[1000];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> d[i];
    }
    int ans = -1;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (d[i] < d[j])
                ans = max(ans, d[i] + d[j] - (d[i] & d[j]));
    cout << ans;
    return 0;
}

程序代码请先阅读以下程序

#include <iostream>
#include <cstdlib>
using namespace std;

int n;
int d[10000];

int find(int L, int R, int k) {
    int x = rand() % (R - L + 1) + L;
    swap(d[L], d[x]);
    int a = L + 1, b = R;
    while (a < b) {
        while (a < b && d[a] < d[L])
            ++a;
        while (a < b && d[b] >= d[L])
            --b;
        swap(d[a], d[b]);
    }
    if (d[a] < d[L])
        ++a;
    if (a - L == k)
        return d[L];
    if (a - L < k)
        return find(a, R, k - (a - L));
    return find(L + 1, a - 1, k);
}

int main() {
    int k;
    cin >> n;
    cin >> k;
    for (int i = 0; i < n; ++i)
        cin >> d[i];
    cout << find(0, n - 1, k);
    return 0;
}

程序代码请先阅读以下程序

#include <iostream>
#include <queue>
using namespace std;

const int maxl = 2000000000;

class Map {
    struct item {
        string key; int value;
    } d[maxl];
    int cnt;
public:
    int find(string x) {
        for (int i = 0; i < cnt; i++)
            if (d[i].key == x)
                return d[i].value;
        return -1;
    }
    static int end() { return -1; }
    void insert(string k, int v) {
        d[cnt].key = k; d[cnt++].value = v;
    }
} s[2];

class Queue {
    string q[maxl];
    int head, tail;
public:
    void pop() { ++head; }
    string front() { return q[head + 1]; }
    bool empty() { return head == tail; }
    void push(string x) { q[++tail] = x; }
} q[2];

string st0, st1;
int m;

string LtoR(string s, int L, int R) {
    string t = s;
    char tmp = t[L];
    for (int i = L; i < R; ++i)
        t[i] = t[i + 1];
    t[R] = tmp;
    return t;
}

string RtoL(string s, int L, int R) {
    string t = s;
    char tmp = t[R];
    for (int i = R; i > L; --i)
        t[i] = t[i - 1];
    t[L] = tmp;
    return t;
}

bool check(string st, int p, int step) {
    if (s[p].find(st) != s[p].end())
        return false;
    ++step;
    if (s[p ^ 1].find(st) == s[p].end()) {
        s[p].insert(st, step);
        q[p].push(st);
        return false;
    }
    cout << s[p ^ 1].find(st) + step << endl;
    return true;
}

int main() {
    cin >> st0 >> st1;
    int len = st0.length();
    if (len != st1.length()) {
        cout << -1 << endl;
        return 0;
    }
    if (st0 == st1) {
        cout << 0 << endl;
        return 0;
    }
    cin >> m;
    s[0].insert(st0, 0); s[1].insert(st1, 0);
    q[0].push(st0); q[1].push(st1);
    for (int p = 0;
         !(q[0].empty() && q[1].empty());
         p ^= 1) {
        string st = q[p].front(); q[p].pop();
        int step = s[p].find(st);
        if ((p == 0 &&
              (check(LtoR(st, m, len - 1), p, step) ||
               check(RtoL(st, 0, m), p, step)))
                  ||
            (p == 1 &&
              (check(LtoR(st, 0, m), p, step) ||
               check(RtoL(st, m, len - 1), p, step))))
            return 0;
    }
    cout << -1 << endl;
    return 0;
}

完完善程序（共 10 题，共 0 分）

程序代码请先阅读以下程序

#include <cstdio>
using namespace std;

const int maxn = 1005;

int n, B, w[maxn], v[maxn];

int gcd(int u, int v) {
    if (v == 0)
        return u;
    return gcd(v, u % v);
}

void print(int w, int v) {
    int d = gcd(w, v);
    w = w / d;
    v = v / d;
    if (v == 1)
        printf("%d\\n", w);
    else
        printf("%d/%d\\n", w, v);
}

void swap(int &x, int &y) {
    int t = x; x = y; y = t;
}

int main() {
    scanf("%d %d", &n, &B);
    for (int i = 1; i <= n; i ++) {
        scanf("%d%d", &w[i], &v[i]);
    }
    for (int i = 1; i < n; i ++)
        for (int j = 1; j < n; j ++)
            if ( ① ) {
                swap(w[j], w[j + 1]);
                swap(v[j], v[j + 1]);
            }
    int curV, curW;
    if ( ② ) {
        ③
    } else {
        print(B * w[1], v[1]);
        return 0;
    }

    for (int i = 2; i <= n; i ++)
        if (curV + v[i] <= B) {
            curV += v[i];
            curW += w[i];
        } else {
            print( ④ );
            return 0;
        }
    print( ⑤ );
    return 0;
}

程序代码请先阅读以下程序

#include <iostream>

using namespace std;

typedef long long LL;

const int MAXN = 40000, M = 16, B = M >> 1, MS = (1 << B) - 1;
const LL INF = 1000000000000000LL;
LL Max[MS + 4][MS + 4];

int w(int x)
{
    int s = x;
    while (x)
    {
        ①;
        s++;
    }
    return s;
}

void to_max(LL &x, LL y)
{
    if (x < y)
        x = y;
}

int main()
{
    int n;
    LL ans = 0;
    cin >> n;
    for (int x = 0; x <= MS; x++)
        for (int y = 0; y <= MS; y++)
            Max[x][y] = -INF;
    for (int i = 1; i <= n; i++)
    {
        LL a;
        cin >> a;
        int x = ②, y = a & MS;
        LL v = ③;
        for (int z = 0; z <= MS; z++)
            to_max(v, ④);
        for (int z = 0; z <= MS; z++)
            ⑤;
        to_max(ans, v);
    }
    cout << ans << endl;
    return 0;
}

2020年 CSP-S 第一轮（提高级）

选单项选择题（共 15 题，共 0 分）

阅阅读程序（共 18 题，共 0 分）

完完善程序（共 10 题，共 0 分）

考试完成

选 单项选择题（共 15 题，共 0 分）

阅 阅读程序（共 18 题，共 0 分）

完 完善程序（共 10 题，共 0 分）

考试完成

选单项选择题（共 15 题，共 0 分）

阅阅读程序（共 18 题，共 0 分）

完完善程序（共 10 题，共 0 分）