2023.7月初模拟赛总结

前言：
近期（约）3天比了3场模拟赛，都源于USACO。但是这3场我的成绩都很低，赛后一看题解被自己的智商哭死，实在看不下去了，决定要写一篇总结

Day 1

T1

P3132 [USACO16JAN] Angry Cows G

正解

DP，设\(f_i\)为使第\(i\)个干草堆左边的所有干草堆爆炸的最小力度。
考虑转移方程。

找一个\(j\)，满足：

• \(j<i\)
• \(a_i-a_j>f_j+1\)

会有很多个\(j\)，我们需要最后一个，即最靠近\(i\)的那一个。

易得：

其中\(f_1=0\)

类似的，我们可得使右边的爆炸的\(g[]\)的状态转移方程。

最后我们枚举爆炸点，显然：

其中，\(i\)和\(j\)的互相推进用到了贪心策略。

还有一点，因为最优情况爆炸点只可能在整点或两个整点中间，所以为了避免double精度问题，我们可以都乘以一个\(2\)。

代码

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define rp(i, o, p) for (ll i = o; i <= p; ++i)
#define pr(i, o, p) for (ll i = o; i >= p; --i)

const ll MAXN = 5e4 + 5, INF = 0x3f3f3f3f;

ll n;
ll f[MAXN], g[MAXN];
ll a[MAXN];

int main() {
    scanf("%lld", &n);
    rp(i, 1, n) scanf("%lld", &a[i]), a[i] *= 2;
    sort(a + 1, a + n + 1);
    memset(f, 0x3f, sizeof(f));
    memset(g, 0x3f, sizeof(g));
    ll t = 1;
    f[1] = 0;
    rp(i, 2, n) {
        while (t + 1 < i && a[i] - a[t + 1] > f[t + 1] + 2) ++t;
        f[i] = min(a[i] - a[t], f[t + 1] + 2);
    }
    t = n;
    g[n] = 0;
    pr(i, n - 1, 1) {
        while (t - 1 > i && a[t - 1] - a[i] > g[t - 1] + 2) --t;
        g[i] = min(a[t] - a[i], g[t - 1] + 2);
    }
    ll ans = INF;
    for (ll i = 1, j = n; i < j;) {
        ans = min(ans, max((a[j] - a[i]) / 2, max(f[i], g[j]) + 2));
        if (f[i + 1] < g[j - 1])
            ++i;
        else
            --j;
    }
    printf("%.1lf", (double)ans / 2);
    return 0;
}

T2

P3133 [USACO16JAN] Radio Contact G

正解

dp,设\(f_{i,j}\)为在\((i,j)\)时最小代价。对于他们的行动串，分别用两个递推数组储存他们的横坐标与纵坐标。

代码

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define rp(i, o, p) for (ll i = o; i <= p; ++i)
#define pr(i, o, p) for (ll i = o; i >= p; --i)
#define po(x) ((x) * (x))

const ll MAXN = 1e3 + 5;

ll n, m;
ll fx, fy, cx, cy;
ll f[MAXN][MAXN];
ll ax[MAXN], bx[MAXN], ay[MAXN], by[MAXN];

ll d(ll i, ll j) { return po(fx + ax[i] - (cx + bx[j])) + po(fy + ay[i] - (cy + by[j])); }

int main() {
    scanf("%lld%lld", &n, &m);
    scanf("%lld%lld%lld%lld", &fx, &fy, &cx, &cy);
    rp(i, 1, n) {
        char ch;
        cin >> ch;
        ax[i] = ax[i - 1], ay[i] = ay[i - 1];
        if (ch == 'N')
            ay[i]++;
        if (ch == 'S')
            ay[i]--;
        if (ch == 'W')
            ax[i]--;
        if (ch == 'E')
            ax[i]++;
    }
    rp(i, 1, m) {
        char ch;
        cin >> ch;
        bx[i] = bx[i - 1], by[i] = by[i - 1];
        if (ch == 'N')
            by[i]++;
        if (ch == 'S')
            by[i]--;
        if (ch == 'W')
            bx[i]--;
        if (ch == 'E')
            bx[i]++;
    }
    memset(f, 0x3f, sizeof(f));
    f[0][0] = 0;
    rp(i, 0, n) {
        rp(j, 0, m) {
            if (i != 0)
                f[i][j] = min(f[i][j], f[i - 1][j] + d(i, j));
            if (j != 0)
                f[i][j] = min(f[i][j], f[i][j - 1] + d(i, j));
            if (i != 0 && j != 0)
                f[i][j] = min(f[i][j], f[i - 1][j - 1] + d(i, j));
       }
    }

    printf("%lld\n", f[n][m]);
    return 0;
}

T3

P3134 [USACO16JAN] Lights Out G

正解

按照题意所说，枚举每个点出发的情况。再把路径记录下来，看看这条路径是否唯一。若唯一，则“觉醒”。
我们可以用map储存，路径可以压成string。
其中对于路径储存问题，我们需要知道这条边的长度与这个角的角度。由于这里的角度不是270°就是90°，所以判断旋转方向即可。

代码

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define rp(i, o, p) for (ll i = o; i <= p; ++i)
#define pr(i, o, p) for (ll i = o; i >= p; --i)

const ll MAXN = 200 + 5;

ll n;
struct node {
    ll x, y;
} a[MAXN];
map<string, ll> ma;
ll ans;
ll len[MAXN], dis[MAXN];
string ang[MAXN], ls[MAXN];

bool got(ll i, ll j, ll k) {
    bool op;
    if (a[i].x == a[j].x) {
        if (a[j].y > a[i].y) {
            if (a[k].x > a[j].x)
                op = 1;
            else
                op = 0;
        } else {
            if (a[k].x > a[j].x)
                op = 0;
            else
                op = 1;
        }
    } else {
        if (a[j].x > a[i].x) {
            if (a[k].y > a[j].y)
                op = 0;
            else
                op = 1;
        } else {
            if (a[k].y > a[j].y)
                op = 1;
            else
                op = 0;
        }
    }
    return op;
}

inline string work(ll x) {
    string s;
    ll a[10], hd = 0;
    while (x) {
        a[++hd] = x % 10;
        x /= 10;
    }
    pr(i, hd, 1) s += a[i] + 48;
    return s;
}

int main() {
    scanf("%lld", &n);
    rp(i, 1, n) scanf("%lld%lld", &a[i].x, &a[i].y);
    rp(i, 1, n) {
        ll i0 = i - 1, i1 = i + 1;
        if (i0 < 1)
            i0 = n - i0;
        if (i1 > n)
            i1 = i1 - n;
        ang[i] = got(i0, i, i1) ? "A" : "B";
        len[i] = abs(a[i0].x - a[i].x) + abs(a[i0].y - a[i].y);
    }

    rp(i, 1, n) {
        ls[i] = work(len[i]);
        ll t1 = len[1], t2 = len[2];
        if (i == 1)
            continue;
        rp(j, i + 1, n) t1 += len[j];
        pr(j, i - 1, 2) t2 += len[j + 1];
        dis[i] = min(t1, t2);
    }

    rp(i, 2, n) {
        string s;
        s += ang[i];
        ma[s]++;
        rp(j, i + 1, n) {
            s = s + ls[j] + ang[j];
            ma[s]++;
        }
    }

    rp(i, 2, n) {
        ll now = -1;
        string s;
        s += ang[i];
        if (ma[s] == 1)
            continue;
        ll sum = 0;
        rp(j, i + 1, n) {
            s = s + ls[j] + ang[j];
            sum += len[j];
            if (ma[s] == 1) {
                now = j;
                break;
            }
        }
        if (now == -1)
            ans = max(ans, sum + len[1] - dis[i]);
        else
            ans = max(ans, dis[now] + sum - dis[i]);
    }

    printf("%lld\n", ans);

    return 0;
}

总结

同年级rk12，倒数第一……
其实题都不难，可能是脑子抽了……

Day 2

T1

P8901 [USACO22DEC] Circular Barn S

正解

这是巴什博奕。

上来先筛一遍质数，欧拉筛\(O(n)\)搞定。

经过打表找规律会发现一个房间内只要是对于\(4\)的倍数，则先手必输。（可以证明，但这里不展开了）

对于先手而言，肯定自己占优时希望能快则快、占劣时能拖则拖。
所以我们记录一下轮数（两人都进行一次操作称为一轮）。

如果是\(4\)的倍数，两人最优策略都只能不停出\(2\)，所以我们这一个房间结束时，经历了\(i/4+1\)轮。
如果不是，那先手可以取走一个数使得剩下的数右边为\(4\)的倍数。记录一下\(i \mod 4\)最大数\(i\)。

那么怎么知道答案呢？记录先手获胜时最小轮数\(min_1\)与这个房间号\(pos_1\)，后手同理。
然后比较\(min_1\)与\(min_2\)的大小，谁更小，意味着谁更快赢得游戏。
想等的话比较谁的房间号更小。

代码

#include <cstdio>
using namespace std;

#define ll long long
#define rp(i, o, p) for (ll i = o; i <= p; ++i)
#define pr(i, o, p) for (ll i = o; i >= p; --i)

const ll MAXN = 2e5 + 5, MAXM = 5e6 + 5, INF = 0x7f7f7f7f;

ll T, n;
ll a[MAXN], pri[MAXM], pinum;
bool ispr[MAXM];
ll s[4];
ll ans[MAXM];

inline ll read() {
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
    return x * f;
}

inline void write(ll x) {
    if (x < 0) {
        putchar('-'), write(-x);
        return;
    }
    if (x > 9)
        write(x / 10), putchar(x % 10 + 48);
    else
        putchar(x + 48);
}

void getprime(ll n) {
    ans[1] = 1;
    s[1] = 1;
    for (ll i = 2; i <= n; ++i) {
        if (!ispr[i]) {
            pri[++pinum] = i;
            if (i % 4)
                s[i % 4] = i;
        }
        for (ll j = 1; j <= pinum; ++j) {
            if (i * pri[j] > n)
                break;
            ispr[i * pri[j]] = 1;
            if (i % pri[j] == 0)
                break;
        }
        if (i % 4 == 0)
            ans[i] = i / 4 + 1;
        else
            ans[i] = (i - s[i % 4]) / 4 + 1;
    }
}

int main() {
    getprime(MAXM - 5);
    T = read();
    while (T--) {
        n = read();
        ll min1 = INF, pos1, min2 = INF, pos2;
        rp(i, 1, n) {
            a[i] = read();
            if (a[i] % 4 == 0) {
                if (min2 > ans[a[i]]) {
                    min2 = ans[a[i]];
                    pos2 = i;
                }
            } else {
                if (min1 > ans[a[i]]) {
                    min1 = ans[a[i]];
                    pos1 = i;
                }
            }
        }
        if (min1 < min2)
            puts("Farmer John");
        else if (min1 > min2)
            puts("Farmer Nhoj");
        else {
            if (pos1 < pos2)
                puts("Farmer John");
            else
                puts("Farmer Nhoj");
        }
    }
    return 0;
}

T2

P8903 [USACO22DEC] Bribing Friends G

正解

dp，但是需要优化。
\(O(n^3)\)的朴素dp这里不说了，直接说正解。

设\(f_{i,j}\)为遍历了前\(i\)个人，花了\(j\)个雪糕可以得到的最大利润。
设\(g_{i,j}\)为花了\(j\)元的最大利润。

然后我们枚举在哪一个人身上既花雪糕又花钱。
这显然可以证明只会有一个人既花雪糕又花钱，那他前面的就都用雪糕、后面的就都用钱来支付。

代码

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define rp(i, o, p) for (ll i = o; i <= p; ++i)
#define pr(i, o, p) for (ll i = o; i >= p; --i)

const ll MAXN = 2e3 + 5;

ll n, A, B;
ll f[MAXN][MAXN];
ll g[MAXN][MAXN];
struct node {
    ll p, c, x, xc;
    bool operator<(const node &t) const { return x < t.x; }
} a[MAXN];

int main() {
    scanf("%lld%lld%lld", &n, &A, &B);
    rp(i, 1, n) {
        ll x, y, z;
        scanf("%lld%lld%lld", &x, &y, &z);
        a[i] = { x, y, z, y * z };
    }

    sort(a + 1, a + n + 1);

    rp(i, 1, n) {
        rp(j, 0, B) f[i][j] = f[i - 1][j];
        pr(j, B, a[i].xc) f[i][j] = max(f[i][j], f[i - 1][j - a[i].xc] + a[i].p);
    }

    pr(i, n, 1) {
        rp(j, 0, A) g[i][j] = g[i + 1][j];
        pr(j, A, a[i].c) g[i][j] = max(g[i][j], g[i + 1][j - a[i].c] + a[i].p);
    }

    ll ans = 0;
    rp(i, 1, n) {
        ans = max(ans, max(f[i - 1][B] + g[i][A], f[i][B] + g[i + 1][A]));
        for (ll j = 0; j <= min(A, a[i].c); ++j) {
            if (B < (a[i].c - j) * a[i].x)
                continue;
            ans = max(ans, f[i - 1][B - (a[i].c - j) * a[i].x] + g[i + 1][A - j] + a[i].p);
        }
    }

    printf("%lld\n", ans);

    return 0;
}

T3

P8904 [USACO22DEC] Mountains G

正解

暴力膜你模拟。
我们每个山峰都建一个set，记录他右边能看到的山有哪些。

在修改一座山\(x\)的数据后，判断山\(x\)会不会挡住山\(i\)本来能看见的一些山。若挡住，则将山\(x\)右边的山从\(s_i\)中删掉。
对于山\(x\)本身，重构就好了。

能互相看到的山的对数在这个过程中也可以统计出来。

代码

#include <cstdio>
#include <set>
using namespace std;

#define ll long long
#define rp(i, o, p) for (ll i = o; i <= p; ++i)
#define pr(i, o, p) for (ll i = o; i >= p; --i)
#define ins insert
#define era erase
#define upp upper_bound
#define low lower_bound

const ll MAXN = 2e3 + 5;

ll n, ans;
ll a[MAXN];
set<ll> s[MAXN];

double gotk(ll i, ll j) { return 1.0 * (a[j] - a[i]) / (j - i); }

int main() {
    scanf("%lld", &n);
    rp(i, 1, n) scanf("%lld", &a[i]);
    rp(i, 1, n) {
        s[i].ins(0), s[i].ins(n + 1);
        double k = -1e9;
        rp(j, i + 1, n) {
            if (gotk(i, j) >= k) {
                k = gotk(i, j);
                s[i].ins(j);
                ++ans;
            }
        }
    }

    ll Q;
    scanf("%lld", &Q);
    while (Q--) {
        ll ix, h;
        scanf("%lld%lld", &ix, &h);
        a[ix] += h;
        rp(i, 1, ix - 1) {
            auto it = s[i].low(ix);
            it--;
            ll y = *it;
            if (y && gotk(i, y) > gotk(i, ix))
                continue;
            if (s[i].find(ix) == s[i].end())
                s[i].ins(ix), ++ans;
            for (y = *s[i].upp(ix); y <= n; y = *(s[i].upp(y))) {
                if (gotk(i, y) >= gotk(i, ix))
                    break;
                s[i].era(y), --ans;
            }
        }
        ans -= s[ix].size() - 2;
        s[ix].ins(0), s[ix].ins(n + 1);
        double k = -1e9;
        rp(i, ix + 1, n) {
            if (gotk(ix, i) >= k) {
                k = gotk(ix, i);
                s[ix].ins(i);
                ++ans;
            }
        }
        printf("%lld\n", ans);
    }

    return 0;
}

总结

同级rk5，但是大家都没打好，太难了，没有人A。

可能是我这次比较走运。

Day 3

补题去了。
顺便一提，一道绿题做了一天……

其实还是很简单的，但是我的脑细胞却死了不少。。

罪魁祸首：

Day 4

T1

P3090 [USACO13NOV] Empty Stalls G

正解

签到题，但是我没做出来。

赛后看了题解，只要扫一遍就好了，注意要再扫一轮，以免一些特殊情况。

代码

#include <set>
#include <cstdio>
using namespace std;

#define int long long
#define rp(i, o, p) for (int i = o; i <= p; ++i)
#define pr(i, o, p) for (int i = o; i >= p; --i)

const int MAXN = 3e6 + 5, MAXK = 1e4 + 5;

int n, k;
int num[MAXN];

signed main() {
    scanf("%lld%lld", &n, &k);
    rp(i, 1, k) {
        int x, y, a, b;
        scanf("%lld%lld%lld%lld", &x, &y, &a, &b);
        rp(j, 1, y) {
            int t = a * j % n + b % n;
            t %= n;
            num[t] += x;
        }
    }
    rp(i, 0, n - 1) {
        if (num[i]) {
            num[(i + 1) % n] += num[i] - 1;
            num[i] = 1;
        }
    }
    if (num[0])
        for (int i = 0; i < n; ++i) {
            if (num[i]) {
                num[(i + 1) % n] += num[i] - 1;
                num[i] = 1;
            }
        }
    rp(i, 0, n - 1) if (!num[i]) {
        printf("%lld\n", i);
        break;
    }

    return 0;
}

T2

P3088 [USACO13NOV] Crowded Cows S

正解

又是签到题，可是我又傻了。

单调队列维护最大值，然后判断即可。
注意正反都做一遍，可以做到\(O(n)\)。

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

#define int long long
#define rp(i, o, p) for (int i = o; i <= p; ++i)
#define pr(i, o, p) for (int i = o; i >= p; --i)

const int MAXN = 1e5 + 5;

int n, d;
struct node {
    int x, h;
    bool operator<(const node &t) const { return x < t.x; }
} a[MAXN], q[MAXN];
bool l[MAXN], r[MAXN];

signed main() {
    scanf("%lld%lld", &n, &d);
    rp(i, 1, n) scanf("%lld%lld", &a[i].x, &a[i].h);
    sort(a + 1, a + n + 1);

    int lf = 1, rg = 0;
    rp(i, 1, n) {
        while (lf <= rg && q[rg].h < a[i].h) --rg;
        q[++rg] = a[i];
        while (lf <= rg && q[lf].x < a[i].x - d) ++lf;
        if (q[lf].h >= a[i].h * 2)
            l[i] = 1;
    }
    memset(q, 0, sizeof(q));
    lf = 1, rg = 0;
    pr(i, n, 1) {
        while (lf <= rg && q[rg].h < a[i].h) --rg;
        q[++rg] = a[i];
        while (lf <= rg && q[lf].x > a[i].x + d) ++lf;
        if (q[lf].h >= a[i].h * 2)
            r[i] = 1;
    }

    int ans = 0;
    rp(i, 1, n) if (l[i] && r[i])++ ans;
    printf("%lld\n", ans);

    return 0;
}

T3

P3089 [USACO13NOV] Pogo-Cow S

正解

dp，容易想到设\(f_{i,j}\)为第\(i\)点，从第\(j\)点跳过来的最大分值。

可得

但是会爆。
若\(i\to i-1\)
得

结合一下，得

好像没\(k\)什么事了。

我们思考一下，如果固定\(j\)点，\(i\)点与\(k\)点的变换类似于共同进行，所以我们可以在同一个循环中搞定。

时间复杂度\(O(n^2)\)。

代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e3 + 5;

int n;
struct node {
    int x, p;
    bool operator<(const node &t) const { return x < t.x; }
} a[MAXN];
int ans;
int f[MAXN][MAXN];

signed main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d%d", &a[i].x, &a[i].p);
    sort(a + 1, a + n + 1);

    for (int j = 1; j <= n; ++j) {
        f[j][j] = a[j].p;
        int k = j + 1;
        for (int i = j + 1; i <= n; ++i) {
            f[i][j] = f[i - 1][j] - a[i - 1].p;
            while (k > 1 && a[j].x - a[k - 1].x <= a[i].x - a[j].x) f[i][j] = max(f[i][j], f[j][--k]);
            f[i][j] += a[i].p;
            ans = max(ans, f[i][j]);
        }
        ans = max(ans, f[j][j]);
    }

    for (int j = n; j >= 1; --j) {
        f[j][j] = a[j].p;
        int k = j - 1;
        for (int i = j - 1; i >= 1; --i) {
            f[i][j] = f[i + 1][j] - a[i + 1].p;
            while (k < n && a[k + 1].x - a[j].x <= a[j].x - a[i].x) f[i][j] = max(f[i][j], f[j][++k]);
            f[i][j] += a[i].p;
            ans = max(f[i][j], ans);
        }
        ans = max(ans, f[j][j]);
    }

    printf("%d\n", ans);

    return 0;
}

总结

同级倒数第一，有两个人AK……

总总结

“开动脑筋。”这是教练常说的话。

确实，这个暑假如果不改变不勤思考的习惯，只会被淘汰。

本栏目推荐文章
• 2023年度总结
• CSP-J/S 2023 游记
• Ubuntu下运行LVGL模拟器
• Libevent [补档-2023-08-29]
• 本地套接字 [补档-2023-07-24]
• UDP通信 [补档-2023-07-22]
• 多路io复用Select [补档-2023-07-16]
• 多路io复用pool [补档-2023-07-19]
• 多路io复用epoll [补档-2023-07-20]
• socket编程 [补档-2023-07-10]

模拟赛 2023.7 2023模拟赛2023.7 2023 2023.7 2023.7 2023 professional community windows 2023.7 opendiary 2023.7 2023 模拟赛2023 模拟赛2023.11日志2023 模拟赛 题解2023 模拟赛2023.12日志2023 模拟赛2023.8日志2023