USACO 2021~2022 比赛记录
USACO 2021~2022 比赛记录
前言
USACO 2020~2021 没写过这玩意，当时打到了金组，这个赛季来写一下。
USACO 2021~2022 DEC Gold
T1
不会。
试图搞出 \(T=1\) 但写挂了，最后只过了样例的 \(3/20\) 个点。
等同于啥都没过就不放代码了= =
T2
一开始（题还没读完的时候）莫名其妙有个念头：整体二分。当然这显然在胡扯。但是这个思路至关重要，使得我一上来就去想对于一个新的 \(p_i\) 对每个 \(x+0.5\) 会有什么贡献，直接推出了正解；而不是像我的其他同学一样去想对每个 \(x+0.5\) 分别求答案，最后做不出来。
开了个 Excel 手模样例，发现对于一个新的 \(p_i\)，假设 \(p_1\sim p_{i-1}\) 里询问过的小于 \(p_i\) 的最大的数为 \(pre\)，大于 \(p_i\) 的最小的数为 \(suc\)（即前驱后继），那么 \(pre,p_i,suc\) 会将所有 \(x+0.5\) 分成四段：
- 若 \(x+0.5 < pre\)：根据题意，这次询问会因为可以根据 \(pre\) 的结果推出而被忽略，不会贡献答案。
- 若 \(pre < x+0.5 < p_i\)：这部分的询问结果不能根据已有的结果推出，会进行询问，并贡献一个
HI。 - 若 \(p_i < x+0.5 < suc\)：这部分的询问结果不能根据已有的结果推出，会进行询问，并贡献一个
LO。 - 若 \(suc < x+0.5\)：根据题意，这次询问会因为可以根据 \(suc\) 的结果推出而被忽略，不会贡献答案。
于是问题转化为了设计一个数据结构，使得支持对于一个区间在字符串末尾添加 HI 或 LO，并统计 HILO 个数。显然可以通过打标记的线段树维护。
过了 \(20/20\) 个点。
写得不太好看的赛时 AC 代码：
//By: Luogu@rui_er(122461)
#include
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
#define debug printf("Running %s on line %d...\n",__FUNCTION__,__LINE__)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const int N = 2e5+5;
int n, p[N], pos[N], ps[N];
set sps, sng;
template void chkmin(T& x, T y) {if(x > y) x = y;}
template void chkmax(T& x, T y) {if(x < y) x = y;}
enum Color {
UK = 0, HI, LO
};
struct Node {
int HILO;
Color tag;
};
struct SegTree {
Node t[N<<5];
#define lc(u) (u<<1)
#define rc(u) (u<<1|1)
void pushup(int u) {
t[u].HILO = t[lc(u)].HILO + t[rc(u)].HILO;
}
void pushdown(int u) {
if(t[u].HILO) {
t[lc(u)].HILO += t[u].HILO;
t[rc(u)].HILO += t[u].HILO;
t[u].HILO = 0;
}
if(t[u].tag == UK) return;
if(t[u].tag == HI) {
t[lc(u)].tag = HI;
t[rc(u)].tag = HI;
t[u].tag = UK;
}
else {
if(t[lc(u)].tag == HI) ++t[lc(u)].HILO;
if(t[rc(u)].tag == HI) ++t[rc(u)].HILO;
t[lc(u)].tag = LO;
t[rc(u)].tag = LO;
t[u].tag = UK;
}
}
void modify(int u, int l, int r, int ql, int qr, Color val) {
if(ql <= l && r <= qr) {
if(t[u].tag == HI && val == LO) {
++t[u].HILO;
t[lc(u)].tag = UK;
t[rc(u)].tag = UK;
}
t[u].tag = val;
return;
}
pushdown(u);
int mid = (l + r) >> 1;
if(ql <= mid) modify(lc(u), l, mid, ql, qr, val);
if(qr > mid) modify(rc(u), mid+1, r, ql, qr, val);
// pushup(u);
}
void print(int u, int l, int r) {
if(l == r) {
printf("%d\n", t[u].HILO);
return;
}
pushdown(u);
int mid = (l + r) >> 1;
print(lc(u), l, mid);
print(rc(u), mid+1, r);
}
}sgt;
int main() {
scanf("%d", &n);
rep(i, 1, n) {
scanf("%d", &p[i]);
pos[p[i]] = i;
}
ps[0] = pos[1];
ps[n] = pos[n];
rep(i, 1, n-1) ps[i] = max(pos[i], pos[i+1]);
rep(i, 1, n) {
auto lwit = sng.upper_bound(-p[i]);
auto upit = sps.upper_bound(p[i]);
int lw = lwit == sng.end() ? 0 : -*lwit;
int up = upit == sps.end() ? n : *upit;
// printf("i=%d lw=%d up=%d p=%d\n", i, lw, up, p[i]);
sgt.modify(1, 0, n, lw, p[i]-1, HI);
// printf("GIVEHI [%d, %d]\n", lw, p[i]-1);
sgt.modify(1, 0, n, p[i], up-1, LO);
// printf("GIVELO [%d, %d]\n", p[i], up-1);
sng.insert(-p[i]);
sps.insert(p[i]);
}
sgt.print(1, 0, n);
return 0;
}
T3
乱搞题，没啥技术含量。
首先如果一个手镯被分成了两个部分，即先后存在三束光线，使得这个手镯的状态是有、无、有，那么一定不符合要求。
然后如果两个手镯没有交叉，在任意一束光线处观察，都一定可以通过将每个手镯的两次出现替换为有权值的左、右括号（小括号、中括号、大括号、第四括号……），得到一个合法的括号序列。判掉了在一束光线处有交叉的情况。
还有就是如果两个手镯的位置关系变了，一定被分成了两个部分或有交叉。A 与 B 的位置关系包括：A 在 B 前面、A 在 B 后面、A 包含于 B、A 包含 B。每种情况开个 vector 或类似的东西维护即可。
交上去，发现过了大多数点，但少数点过不去。手模了几组数据，把自己 hack 了。
问题在于漏了一种情况：显然，如果手镯 A 包含于手镯 B，那么当 B 闭合时（即在一束光线中不再出现时），A 一定更早地闭合了，不可能有一束光线没有 B 但有 A，否则此时必然存在交叉。
加上这个判断即可，过了 \(20/20\) 个点。
写得不太好看的赛时 AC 代码：
//By: Luogu@rui_er(122461)
#include
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
#define debug printf("Running %s on line %d...\n",__FUNCTION__,__LINE__)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const int N = 105;
int T, n, m, k[N], buc[N][N], tmp[N], tmpv1[N];
vector a[N];
stack stkv1;
set ins[N], aft[N];
template void chkmin(T& x, T y) {if(x > y) x = y;}
template void chkmax(T& x, T y) {if(x < y) x = y;}
bool verdictBracket(int id) {
rep(i, 1, n) tmpv1[i] = 0;
while(!stkv1.empty()) stkv1.pop();
for(auto i : a[id]) {
if(!tmpv1[i]) {
rep(j, 1, n) {
if(i == j) continue;
if(tmpv1[j] == 1) {
ins[j].insert(i);
if(ins[i].find(j) != ins[i].end()
|| aft[i].find(j) != aft[i].end()
|| aft[j].find(i) != aft[j].end())
return
// printf("VER! @%d.%d.%d\n", id, i, j)&
0;
}
if(tmpv1[j] == 2) {
aft[j].insert(i);
if(ins[i].find(j) != ins[i].end()
|| ins[j].find(i) != ins[j].end()
|| aft[i].find(j) != aft[i].end())
return
// printf("VER? @%d.%d.%d\n", id, i, j)&
0;
}
}
tmpv1[i] = 1;
stkv1.push(i);
}
else if(i == stkv1.top()) {
tmpv1[i] = 2;
stkv1.pop();
}
else return 0;
}
rep(i, 1, n) {
if(!tmpv1[i]) {
for(auto j : ins[i]) {
if(tmpv1[j]) return 0;
}
}
}
return 1;
}
#define give(result) do{puts(result);goto Init;}while(false)
int main() {
for(scanf("%d", &T);T;T--) {
scanf("%d%d", &n, &m);
rep(i, 1, m) {
scanf("%d", &k[i]);
a[i].resize(k[i]);
rep(j, 0, k[i]-1) {
scanf("%d", &a[i][j]);
++buc[i][a[i][j]];
}
}
rep(i, 1, m) {
if(!verdictBracket(i)) give("NO");
rep(j, 1, n) {
if(!tmp[j] && buc[i][j] == 2) ++tmp[j];
else if(tmp[j] == 1 && !buc[i][j]) ++tmp[j];
else if(tmp[j] == 2 && buc[i][j] == 2) ++tmp[j];
// printf("%d%c", tmp[j], " \n"[j==n]);
if(tmp[j] == 3) give("NO");
}
}
per(i, m, 1) if(!verdictBracket(i)) give("NO"); // rejudge it (reverse HACK)
give("YES");
Init:
rep(i, 1, m) {
k[i] = 0;
a[i].clear();
rep(j, 1, n) buc[i][j] = 0;
}
rep(i, 1, n) {
tmp[i] = 0;
ins[i].clear();
aft[i].clear();
}
n = m = 0;
}
return 0;
}
/*
HACKED (Verdict: WRONG_ANSWER)
1
4 2
4 1 2 2 1
2 2 2
Expected: NO
Found: YES
Rejudge: NO (Verdict: OK)
*/
总结
符合预期。还记得 USACO 2020~2021 OPEN Gold 我还啥都不会直接弃了呢。按照总满分为 \(1000\) 分计，大概是得到了 \(716.67\) 分，貌似卡在了晋级/不晋级的中间，只能看人品了。。
upd：貌似上 P 失败了。。