Day 29 - 结营测试

So_noSlack 的博客 / 2024-08-05 / 原文

Problems.pdf

A

#include<iostream>
using namespace std;
#define MAXN 100005

long long read() {
    long long x = 0, f = 1;
    char c = getchar();
    while(c < 48 || c > 57) { if(c == 45) f = -1; c = getchar(); }
    while(c >= 48 && c <= 57) { x = (x << 3) + (x << 1) + (c - 48); c = getchar(); }
    return x * f;
}

long long n, m, a[MAXN], b[MAXN], tp = 0;
bool mp[MAXN];

int main() {
    freopen("seq.in", "r", stdin);
    freopen("seq.out", "w", stdout);

    n = read(); m = read();
    for(int i = 1; i <= m; i ++) a[i] = read(), mp[a[i]] = true;
    for(int i = 1; i <= n; i ++) if(!mp[i]) b[++ tp] = i;
    long long l = 1, r = 1;
    for(int i = 1; i <= n; i ++) 
        if(l > m) cout << b[r ++] << "\n";
        else if(r > tp) cout << a[l ++] << "\n";
        else if(a[l] > b[r]) cout << b[r ++] << "\n";
        else cout << a[l ++] << "\n";
    return 0;
}

B

#include<iostream>
using namespace std;
#define MAXN 1000005

long long read() {
    long long x = 0, f = 1;
    char c = getchar();
    while(c < 48 || c > 57) { if(c == 45) f = -1; c = getchar(); }
    while(c >= 48 && c <= 57) { x = (x << 3) + (x << 1) + (c - 48); c = getchar(); }
    return x * f;
}

long long n, l, p = 0, ans = 0;
char c[MAXN], b[MAXN];

int main() {
    freopen("bracket.in", "r", stdin);
    freopen("bracket.out", "w", stdout);

    n = read(); l = read(); cin >> c + 1;
    for(int i = 1; i <= n; i ++) {
        if(!p) 
            if(c[i] == ')') { ans ++, b[++ p] = c[i] = '('; continue; }
            else { b[++ p] = c[i]; continue; }
        if(p == l && c[i] == '(') c[i] = ')', p --, ans ++;
        else if(b[p] == '(' && c[i] == ')') p --;
        else b[++ p] = c[i];
    }
    cout << ans << "\n";
    return 0;
}

C

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define MAXN 10005

long long read() {
    long long x = 0, f = 1;
    char c = getchar();
    while(c < 48 || c > 57) { if(c == 45) f = -1; c = getchar(); }
    while(c >= 48 && c <= 57) { x = (x << 3) + (x << 1) + (c - 48); c = getchar(); }
    return x * f;
}

long long n, T, b[MAXN], ans = 0, res = 0x3f3f3f3f3f3f3f3f;
struct node { long long t, p; } a[MAXN];
bool vis[MAXN];

void f(long long p) {
    do {
        long long tp = 0;
        for(int i = 1; i <= p; i ++) tp += a[b[i]].t + (i - 1) * a[b[i]].p;
        res = min(res, tp);
    } while(next_permutation(b + 1, b + p + 1));
    return;
}

void dfs(long long x, long long p) {
    if(x > n) {
        res = 0x3f3f3f3f3f3f3f3f; f(p);
        if(res <= T) ans = max(ans, p);
        return;
    }
    dfs(x + 1, p); b[p + 1] = x;
    dfs(x + 1, p + 1); return;
}

void dfs2(long long x, long long p) {
    if(p > T) return;
    else ans = max(ans, x);
    for(int i = 1; i <= n; i ++) {
        if(vis[i]) continue;
        vis[i] = true;
        dfs2(x + 1, p + a[i].t + x * a[i].p);
        vis[i] = false;
    }
    return;
}

int main() {
    freopen("work.in", "r", stdin);
    freopen("work.out", "w", stdout);

    n = read(); T = read();
    for(int i = 1; i <= n; i ++) a[i].t = read();
    for(int i = 1; i <= n; i ++) a[i].p = read();
    if(n <= 10) {
        dfs(1, 0);
        cout << ans << "\n";
        return 0;
    }
    dfs2(0, 0);
    cout << ans << "\n";
    return 0;
}

D

#include<iostream>
using namespace std;

long long read() {
    long long x = 0, f = 1;
    char c = getchar();
    while(c < 48 || c > 57) { if(c == 45) f = -1; c = getchar(); }
    while(c >= 48 && c <= 57) { x = (x << 3) + (x << 1) + (c - 48); c = getchar(); }
    return x * f;
}

int main() {
    freopen("clique.in", "r", stdin);
    freopen("clique.out", "w", stdout);
    
    cout << "0\n";
    return 0;
}

$08:00$ 拿到题目，居然有 $\text{pdf}$ 还断网，这次好玩。

$08:02$ 看完 $\text{A}$ 题，发现又是一眼题？

$08:06$ 光速打完 $\text{A}$ 题，简单过了一下大样例。

$08:20$ 写了对拍，暴力居然比正解还难写。

$08:25$ 就这吧，不管 $\text{A}$ 了，开 $\text{B}$ 去了。

$08:30$ 好的，$\text{B}$ 题还是有点思维的，先想想。

$08:34$ 不是很会啊，怎么办，手模了几个样例，没找到思路。

$08:47$ 好的！找到思路了，类似贪心思想每次直到必须修改的时候我们才修改。

$09:01$ 写出来了，大样例也过了，于是赶紧写对拍，因为我当时不确定这个做法对不对。

$09:32$ 发现今天的比赛怎么暴力都比正解难写？？我想怎么计算深度想了好久。

$09:33$ 好的写完造数据的程序就开拍了，感觉没什么问题，不过因为暴力的时间复杂度是 $O(n2^n)$，所以只能拍 $1 \le n \le 10$ 的数据。

$09:40$ 看了看 $\text{C}$ 题，咋感觉这题这么像 $\text{DP}$ 的板子呢？但是又有点不一样。