退役人大闹某机房,被创飞学弟显神通

· · 生活·游记

却说退役选手 foglake 过了一轮,进了二轮,不思去机房刷题,却在教室摸鱼,玩物丧志,莫过如此,正是:

再看考试当天,进入考场 foglake 不思回忆模版,思索晚饭内容。到了时间,密码不发,遂大骂西西弗草台班子。

:::align{center} 折戟省选不努力,天天摸鱼盼奇迹。

命运不爱懒惰者,到时考差怨谁人?

终于拿到题目,发现可用单调队列,于是 1A。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 10;
long long e[maxn], sum, m;
int n, p = 1, ans = 1;
int main() {
    freopen("crystal.in", "r", stdin);
    freopen("crystal.out", "w", stdout); 
    scanf("%d%lld", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%lld", e + i);
    sort(e + 1, e + 1 + n);
    for (int i = 2; i <= n; i++) {
        sum += e[i - 1];
        while (e[i] * (i - p) - sum > m) sum -= e[p++];
        ans = max(ans, i - p + 1);
    }
    printf("%d\n", ans);
    return 0;
}

:::align{center} 一眼秒切狂欢喜,全靠队列在硬撑。

自古选手被单调,常使英雄泪满襟!

再看 T2,发现可将地铁抽象为点,大喜,对每个先跑 Dijkstra,O(nmlogm) 一代代码横空出世。

蠢脑算错复杂度以为能过,超时于最后大样例,遂怀疑 CY 老年机性能,终于发现自己算错了。

然后就是重构,debug……

于是终于想到 Floyd,历经三小时 AC。

#include <bits/stdc++.h>
#define PII pair<int,int>
using namespace std;
const int maxn = 5e5 + 1000, maxq = 1e5 + 10;
vector <PII> e[maxn];
PII que[maxq];
long long dis[maxn], d[510][510], w[maxn];
bool vis[maxn];
int n, m, k, Q;
int main() {
    freopen("subway.in", "r", stdin);
    freopen("subway.out", "w", stdout);
    int c, D;
    scanf("%d%d%d%d%d", &c, &n, &m, &D, &Q);
    for (int i = 1; i <= m; i++) scanf("%lld", w + i);
    for (int i = 1; i <= n; i++) {
        int k;
        scanf("%d", &k);
        for (int j = 1; j <= k; j++) {
            int a, t;
            scanf("%d%d", &a, &t);
            e[m + i].push_back({a, t});
            e[a].push_back({m + i, t});
        }
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) if (i != j) d[i][j] = 1e18;
    for (int i = 1; i <= m; i++)
        for (auto j : e[i])
            for (auto k : e[i])
                d[j.first - m][k.first - m] = min(d[j.first - m][k.first - m], 1ll * j.second + k.second);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= n; k++)
                d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
    for (int i = 1; i <= Q; i++) {
        long long ans = 1e18;
        int s, t;
        scanf("%d%d", &s, &t);
        for (auto j : e[s])
            for (auto k : e[t])
                ans = min(ans, d[j.first - m][k.first - m] + j.second + k.second + w[s] + w[t]);
        printf("%lld\n", ans);
    }
    return 0;
}

:::align{center} 花了很久切 debug,气的脸颊红充血。

自己码力差一截,哭天喊地无人应!

发现 T3 O(n^2),结果用了 memset,跪了。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 10;
long long loc[maxn], cnt[maxn], dis[maxn], sum[maxn];
int l[maxn];
int main() {
    freopen("migrate.in", "r", stdin);
    freopen("migrate.out", "w", stdout);
    int c, T;
    scanf("%d%d", &c, &T);
    while (T--) {
        int n;
        long long d, ans = 0;
        scanf("%d%lld", &n, &d);
        for (int i = 1; i <= n; i++) scanf("%lld", loc + i);
        if (c == 11 || c == 12) {
            long long D = loc[2] - loc[1];
            long long k = d / D;
            if (k < 2) puts("0");
            else {
                if (n < 2 * k) puts("0");
                else printf("%lld\n", 1ll * n - 2 * k + 1); 
            }
        } else {
            int p = 1;
            for (int i = 1; i <= n; i++) {
                while (loc[i] - loc[p] > d) p++;
                l[i] = p;
            }
            for (int i = 1; i <= n; i++) {
                memset(sum, 0, sizeof sum);
                cnt[i] = 1, sum[i] = 1;
                for (int j = i + 1; j <= n; j++) {
                    if (l[j] == j) break;
                    dis[j] = dis[max(l[j], i)] + 1;
                    if (dis[j] > dis[j - 1]) {
                        for (int k = j - 1; dis[k] == dis[j - 1] && k >= i; k--)
                            sum[k] = sum[k + 1] + cnt[k];                   
                    }
                    cnt[j] = sum[max(l[j], i)];
                    if (cnt[j] == 2) ans++;
                }
            }
            printf("%lld\n", ans);          
        }
    }
    return 0;
}

:::align{center} 骗分 40 本窃喜,不想清空出问题。

不假思索 memset,被卡 O(n^3) 空悲切。

T4 看了 20 分钟才看懂,没时间敲暴力了。

:::align{center} 前不见 AC,后不见暴力。

念 OI 之悠悠,独挂分而泪下!

最后 100 + 100 + 32 + 0 = 232。被卡 7 勾了(还好已经有一个了)。

结果横向对比种子选手,是最低的,哈哈。