模拟赛题目复盘

· · 个人记录

难度: CSPS - NOIP

Day11

估分 100 + 15 + 26 + 0 = 141，结果 C 挂没了。

T1.P11989 弱化

::::info[Description]

有 n 个任务，所有任务有总限时 T。

每个任务有完成限时 s_i，重量 h_i，分数 p_i。

每一时刻，你可以选择一个任务 i 使得 h_i = max(h_i - 1, 0)

最小化 \sum h_i\cdot p_i。

:::: 按照 $s$ 从大到小排序，增量构造。每次加入新任务时，若时间不够，则进行反悔贪心，换掉 $p$ 更大的任务以最小化分数。 ::::success[代码] ```cpp #include <bits/stdc++.h> #define pb push_back #define pii pair<int, int> #define int long long using namespace std; #ifdef ONLINE_JUDGE #define debug(...) 0 #else #define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr) #endif // you need fread or not? /* I had an idea of greedy with backtracking, seems to be 100pts hope it can pass the problem */ const int maxn = 2e5 + 10; int n, m; struct node { int s, h, p; bool operator < (const node &o) const { return s < o.s; } } a[maxn]; struct edge { int h, p; bool operator < (const edge &o) const { return p > o.p; } }; priority_queue<edge> q; signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // freopen("eata6.in", "r", stdin); cin >> n >> m; for (int i = 1; i <= n; ++i) cin >> a[i].s >> a[i].h >> a[i].p; sort(a + 1, a + n + 1); int tot = 0, ans = 0; for (int i = 1; i <= n; ++i) { int c = tot + a[i].h - a[i].s; if (c <= 0) { tot += a[i].h; q.push({a[i].h, a[i].p}); } else { if (q.size() && a[i].p > q.top().p) { while (q.size() && a[i].p > q.top().p && c > 0) { int hh = q.top().h, pp = q.top().p; q.pop(); if (hh > 0) { if (c <= hh) { hh -= c; ans += c * pp; c = 0; } else { c -= hh; ans += hh * pp; hh = 0; } } if (hh == 0) continue; q.push({hh, pp}); } ans += c * a[i].p; } else { ans += c * a[i].p; } tot = a[i].s; q.push({a[i].h - c, a[i].p}); } } cout << (ans == 0 ? 1 : 0) << ' ' << ans << '\n'; cout << flush; return 0; } ``` :::: T2 P11770 长为 $n$ 的序列，第一个数为 $1$。 对于第 $i$ 个数，当前只为 $v$, 给所有编号 $i$ 的整数倍（不含 $i$ ）的数从大到小更新取最大值 $v + 1, v + 2, ...

求序列的总和。

solution

首先一个数字最终的值一定是由它的因数推出来的。

设 p_i 是 i 的一个因子，容易得到 x 要小，则 p_i 为 i 的最大质因子最合适。

x=\dfrac{i}{p_i} f_i=f_x+1-p_i+\dfrac{n}{x}

用 i 枚举 x，以保证时间复杂度。

找到 f_{i\times j} 被统计当且仅当 i\times j 可以推（除）几次最大质因子得到 i，也就是满足 i 的最大质因子小于等于 j 的最小质因子，这样每次推的都是 j 的质因子。

所以我们计算 \dfrac{n}{x} , 对 x 调和级数。

::::info[代码]

#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>

#define int long long

using namespace std;

#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif

// you need fread or not?

const int maxn = 2e6 + 10;

int n, tot;
int p[maxn], mx[maxn], mn[maxn], ans[maxn];
bool vis[maxn];

void init() {
    mx[1] = mn[1] = vis[1] = 1;
    for (int i = 1; i < maxn; ++i) 
        ans[i] = 1;

    for (int i = 2; i < maxn; ++i) {
        if (!vis[i]) 
            p[++tot] = mx[i] = mn[i] = i;
        for (int j = 1; j <= tot && i * p[j] < maxn; ++j) {
            vis[i * p[j]] = 1, mx[i * p[j]] = mx[i], mn[i * p[j]] = p[j];
            if (i % p[j] == 0)
                break;
        }
    }
    for (int i = 2; i < maxn; ++i) {
        ans[i] += 1 - mx[i];
        for (int j = 2; i * j < maxn; ++j)
            if (mx[i] <= mn[j])
                ans[i * j] += 1 - mx[i];
    }
    for (int i = 1, o = 0; i < maxn; ++i, o = 0) {
        for (int j = 2; i * j < maxn; ++j) {
            ans[i * j] += o;
            if (mx[i] <= mn[j])
                ans[i * j] += j, o++;
        }
    }

    for (int i = 1; i < maxn; ++i)
        ans[i] += ans[i - 1];
}

void solve() {
    cin >> n;
    cout << ans[n] << '\n';
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    int t;
    cin >> t;
    while (t--)
        solve();
    cout << flush;
    return 0;
}

:::: Day10

Score

估 100 20 0 20

实 100 20 0 0

T1 abc166f 弱化

初始时 ABC 都有初值。

对一个字符串，可以选择给其中一个字符 $+ 1$，给另一个 $-1$。 求能否保证，每次操作完一个字符串后，ABC 的值都不能为负数。 solution 简单题，直接 $dfs$，复杂度保证在 $O(n)$。 当然也可以思考神秘结论。 ::::info[代码] ```cpp #include <bits/stdc++.h> #define pb push_back #define pii pair<int, int> // #define int long long using namespace std; #ifdef ONLINE_JUDGE #define debug(...) 0 #else #define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr) #endif // you need fread or not? const int maxn = 1e5 + 10; int n, g[maxn]; char f[maxn]; int A, B, C; void dfs(int a, int b, int c, int s) { if (s == n + 1) { cout << "Yes\n"; exit(0); } if (g[s] == 1) { if (a > 0) { f[s] = 'B'; dfs(a - 1, b + 1, c, s + 1); } if (b > 0) { f[s] = 'A'; dfs(a + 1, b - 1, c, s + 1); } } else if (g[s] == 2) { if (a > 0) { f[s] = 'C'; dfs(a - 1, b, c + 1, s + 1); } if (c > 0) { f[s] = 'A'; dfs(a + 1, b, c - 1, s + 1); } } else { if (b > 0) { f[s] = 'C'; dfs(a, b - 1, c + 1, s + 1); } if (c > 0) { f[s] = 'B'; dfs(a, b + 1, c - 1, s + 1); } } } signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // freopen("D1.in", "r", stdin); // freopen("D1.ans", "w", stdout); cin >> n >> A >> B >> C; string t; for (int i = 1; i <= n; ++i) cin >> t, g[i] = (t == "AB" ? 1 : (t == "AC" ? 2 : 3)); dfs(A, B, C, 1); cout << "No\n"; cout << flush; return 0; } ``` :::: Day9 - Score 估 100 10 0 20 实 100 10 0 0 T1 cf1967b2 给定 $n,m$，求满足 $a+b|b\times \gcd(a,b)$ 的 $1\le a \le n,1 \le b \le m$ 的整数对 $(a,b)$ 的个数。 solution $\text{let}~d = \gcd(a,b) \text{let}x = \dfrac{a}{d} \text{let}y = \dfrac{b}{d}

则式字变为 x+y|y\times d

\gcd(x+y,y)=\gcd(x,y)=1

式子变为 x+y|d

设 d=k(x+y)

则 a=d\times x=k(x^2+y)

b=d\times y=k(x+y^2)

推出 x\le \sqrt n

y\le \sqrt m

直接枚举 x,y 时间复杂度 O(\sqrt {nm})

::::info[代码]

#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>

// #define int long long

using namespace std;

#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif

// you need fread or not?

int n, m, ans, sn, sm, a, b;

void solve() {
    cin >> n >> m;
    ans = 0;
    sn = sqrt(n), sm = sqrt(m);
    for (int i = 1; i <= sn; ++i) {
        for (int j = 1; j <= sm; ++j) {
            if (__gcd(i, j) != 1) 
                continue; 
            a = (i + j) * i, b = (i + j) * j;
            if (a > n || b > m) 
                continue;
            ans += min(n / a, m / b); 
        }
    }
    cout << ans << '\n';
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while (t--)
        solve(); 
    cout << flush;
    return 0;
}

::::

T2 arc104c

满足 1.$a_i<b_i

2.所有 a 和 b 组成 2n 的排列

3.若两线段有交集，则它们长度一样。

先给出所有 a_i 和 b_i，有些端点遗漏为 -1（可自行填数），有些可能有误。判断能否存在构造满足条件。

solution

首先特判，ababa..

考虑合法方案的形态，线段必然没有包含关系，考虑每个独立的段，发现必定形如:

前半部分是左端点，后半部分是右端点。

我们需要知道是否有合法方案，考虑可行性 dp。

设 f_i 表示 f_i 是否可行，转移时容易的:f_i←f_j 且 chk(j+1,i)，其中 chk(l,r) 表示 [l,r] 是否能成为合法段。 考虑怎么计算 chk(l,r)，维护每个线段的起点和终点，判断是否有矛盾即可。

::::info[代码]

#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>

// #define int long long

using namespace std;

#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif

// you need fread or not?

const int maxn = 5e2 + 10;

int n;
int A[maxn], B[maxn], f[maxn], c[maxn], d[maxn];

bool cc() {
    for (int i = 1; i <= n; ++i)
        if (c[i] > 1) 
            return 0;
    return 1;
}

bool ck(int l, int r) {
    for (int i = l + 1; i <= r; ++i) {
        if (f[i] < 0 && A[-f[i]] != -1 && A[-f[i]] < l) 
            return 0;
        if (f[i] > 0 && B[f[i]] != -1 && B[f[i]] > r)
            return 0;
    }
    int len = (r - l + 1) >> 1;
    for (int i = l, j = l + len; i <= l + len - 1; ++i, ++j) {
        if (f[i] < 0 && f[j] > 0) 
            return 0;
        if (f[i] && B[f[i]] != -1 && B[f[i]] != j) 
            return 0;
        if (f[i] && f[j] && f[i] + f[j])
            return 0;
    }
    return 1;
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n * 2; ++i)
        c[i] = d[i] = f[i] = 0;
    for (int i = 1; i <= n; ++i) 
        cin >> A[i] >> B[i];
    for (int i = 1, a, b; i <= n; ++i) {
        a = A[i], b = B[i];
        if (b > 0 && a > b) {
            cout << "0\n";
            return;
        }
        if (a > 0) 
            c[a]++, f[a] = i;
        if (b > 0)
            c[b]++, f[b] = -i;
    }
    n <<= 1;
    if (!cc()) {
        cout << "0\n";
        return;
    }
    d[0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = (i & 1); j < i; j += 2) 
            d[i] = (d[i] | (d[j] && ck(j + 1, i)));
    }
    cout << d[n] << '\n';
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while (t--) 
        solve();
    cout << flush;
    return 0;
}

::::