退役人大闹某机房,被创飞学弟显神通
却说退役选手 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,
蠢脑算错复杂度以为能过,超时于最后大样例,遂怀疑 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
#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,被卡 |
|---|
T4 看了 20 分钟才看懂,没时间敲暴力了。
:::align{center} 前不见 AC,后不见暴力。
| 念 OI 之悠悠,独挂分而泪下! |
|---|
最后 100 + 100 + 32 + 0 = 232。被卡 7 勾了(还好已经有一个了)。
结果横向对比种子选手,是最低的,哈哈。