还是因为不够强吧?
开考看了所有题,感觉应该是正常的升序难度就开做 T1 了,写完 T1 加造了大样例和多测的时间是 45 分钟。T2 的 k=2n-2 部分分很好想,只需钦定一个空位,剩下的队列强制每个最多放两个数,利用空位消除即可。这个部分分很有启发性,k=2n-1 的情况考虑规约到 k=2n-2 的情况,在准备加入第 2n-1 个颜色的时候往后面扫,分情况讨论把扫到的一串一并处理,就能回到至多有 2n-2 个颜色的情况。
写了 1h 发现代码挺难实现的,而且有个地方应该按某个东西出现次数的奇偶性进行讨论而不是按是否出现进行讨论,要改的话就得重构一片代码。这个时候已经有点慌了,去上了厕所冷静一下,回来认真想了想 T3 和 T4。T4 大概率只能拿暴力分,T3 并没有看出是什么东西,感觉不可做。于是就回到了 T2 重构了一下代码,继续各种改 bug 和完善没考虑到的情况。考场上的时间过得飞快,又写了 1h 多终于跑出方案了,赶紧写 checker 检验(话说不发 checker 真的是****)。写完 checker 又调了一会才改对,甚至发现有个地方写反了。。
考场上随着 T2 沉没的时间越来越多,就越来越慌张。到写 checker 的时候我已经知道很可能会挂掉了。就算我过了场上下发的样例最后还是大概率会挂掉,而策略的选择又导致我最后只剩下 40 分钟的时间来写后两题。自然写不出什么像样的部分分,最后甚至 T3 的暴力都写错了没有时间调。
出考场感觉灵魂飘走了,想说话又说不出。听大家讨论好像 T3 其实不是很难,至少缩边双之后 O(n^2) 的 DP 不难,可是我并没有看出边双啊。。然后就发现会 T3 的一车,会 T2 的少,哈哈,那我 T2 挂了不就真的没了。后来洛谷和 infoj 都挂成了 30 分,好些思路正确的人也说因为细节地方根本考虑不到而挂了。要是最后甚至只有二等奖退役,那我真的不知道说什么好(笑)(哭)(zgs 一语成谶)。
有很多抱怨的地方:四个半小时四道题的赛制不够好(还是觉得 2 天 6 道题有足够的时间实现代码才能发挥出水平),没有实时测评极其不合理(高一某巨 T1 多测没清空答案自闭了),大样例故意造水可笑的 yyloi。
强又是什么?是精细实现 T2 不挂分的码力吗?是一眼识别出 T3 做法稳健通过的实力吗?是合理放弃题目的良好考场策略吗?我不知道,我只知道我退役了,再没有时间和机会思考这些问题。
初三的时候学的东西很少但拿到了省内不错的名次,感觉有机会把竞赛搬上正轨的时候是那么自信和开心。如果我告诉那时的自己最后的故事是这样,他会觉得很可笑吧。
来石室的一年干了很多蠢事,可能我从小就是个毛病挺多的人,感谢父母、老师和同学的忍耐与支持。
请不要为前路而担心!竞赛已经让你死过一次,且问有什么样的事情能突破这道屏障呢?
(T2 详细题解有空我会发到博客上,附上考场代码,此题承载了我所有的遗憾)
#include <bits/stdc++.h>
using namespace std;
void debug_out() { cerr << '\n'; }
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << ' ' << H, debug_out(T...); }
#ifdef HRJ
#define debug(...) cerr << '[' << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif
const int MM = 2e6 + 5;
int n, m, K, a[MM], pos[605], tpos[605];
int op;
string ans;
inline void add(int x) {
++op, ans += "1 " + to_string(x) + '\n';
}
inline void add(int x, int y) {
++op, ans += "2 " + to_string(x) + ' ' + to_string(y) + '\n';
// debug("2 " + to_string(x) + ' ' + to_string(y) + '\n');
}
int sp;
set<int> has;
struct stk {
int id;
deque<int> q; // assert q.size() <= 2
void pop_front() {
pos[q.front()] = 0;
q.pop_front();
has.insert(id);
if(int(q.size()) < 2 && id != sp) has.insert(id); // don't touch sp!!!
}
void pop_back() {
pos[q.back()] = 0;
q.pop_back();
if(int(q.size()) < 2 && id != sp) has.insert(id);
}
void push(int x) {
q.push_back(x);
pos[x] = id;
if(int(q.size()) >= 2 && id != sp) has.erase(id);
}
} q[305];
void Main() {
cin >> n >> m >> K;
op = 0, sp = n;
ans.clear();
has.clear();
for(int i = 1; i <= n; i++) q[i].q.clear(), q[i].id = i;
for(int i = 1; i < n; i++) has.insert(i);
for(int i = 1; i <= m; i++) cin >> a[i];
for(int i = 1; i <= K; i++) pos[i] = 0, tpos[i] = 0;
for(int i = 1; i <= m; i++) {
if(pos[a[i]]) {
if(q[pos[a[i]]].q.front() == a[i]) {
add(sp), add(sp, pos[a[i]]);
q[pos[a[i]]].pop_front();
} else {
add(pos[a[i]]);
q[pos[a[i]]].pop_back();
}
} else {
if(has.empty()) {
for(int j = i + 1; j <= m; j++) {
if(a[j] == a[i]) {
for(int k = i; k <= j; k++) tpos[a[k]] = pos[a[k]];
add(sp);
for(int k = i + 1; k < j; k++) {
add(tpos[a[k]]);
if(q[tpos[a[k]]].q.back() == a[k]) q[tpos[a[k]]].pop_back();
else q[tpos[a[k]]].push(a[k]);
}
add(sp);
i = j;
break;
} else if(q[pos[a[j]]].q.front() == a[j]) { // a[j] ÊÇÕ»µ×
for(int k = i; k <= j; k++) tpos[a[k]] = pos[a[k]];
int same = 0;
for(int k = i + 1; k < j; k++)
if(tpos[a[k]] == tpos[a[j]]) ++same;
if(same % 2 == 1) {
assert(q[sp].q.empty());
add(sp);
q[sp].push(a[i]);
for(int k = i + 1; k < j; k++) {
add(tpos[a[k]]);
if(q[tpos[a[k]]].q.back() == a[k]) q[tpos[a[k]]].pop_back();
else q[tpos[a[k]]].push(a[k]);
}
has.insert(sp);
sp = tpos[a[j]];
q[tpos[a[j]]].pop_back();
has.erase(sp);
assert(q[sp].q.empty());
} else {
assert(q[sp].q.empty());
add(tpos[a[j]]);
int cc = 0;
for(int k = i + 1; k < j; k++) {
if(tpos[a[k]] == tpos[a[j]]) {
++cc;
add(sp);
if(!q[sp].q.empty()) q[sp].pop_back();
else q[sp].push(a[k]);
} else {
add(tpos[a[k]]);
if(q[tpos[a[k]]].q.back() == a[k]) q[tpos[a[k]]].pop_back();
else q[tpos[a[k]]].push(a[k]);
}
}
assert(q[sp].q.empty());
add(sp), add(sp, tpos[a[j]]);
q[tpos[a[j]]].pop_front();
q[tpos[a[j]]].push(a[i]);
}
i = j;
break;
}
}
} else {
assert(has.size() >= 1);
add(*has.begin());
q[*has.begin()].push(a[i]);
}
}
}
cout << op << '\n' << ans;
}
int main() {
freopen("meow.in", "r", stdin);
freopen("meow.out", "w", stdout);
ios::sync_with_stdio(false);
int T;
for(cin >> T; T; T--) Main();
return 0;
}
标签:AFO,代码,T2,T3,考场,checker,2n
From: https://www.cnblogs.com/huaruoji/p/16929011.html