挂了不少，还行Rank
A. Alice 和璀璨花
签。
一眼最长上升子序列，昨天在 AT 专题里刚见过，不过赛时没想到离散化之后树状数组，所以打的动态开点，结果细节挂了 30pts。
和最长上升子序列思路基本一致，直接区间查询 \([1,a_i-1]\) 的最大值，然后在 \(a_i\times b_{f_i}\) 插入 \(f_i\) 即可，时间空间都是 \(\mathcal{O(n\log n)}\) 的。
常数略大，稍微卡卡就过去了。几个卡常 trick：动态开点加取地址符会快很多；没事把函数都加上 inline；剪枝尽量；快读 + printf + puts；空间开够；不要 #define int long long ！
点击查看代码
// ubsan: undefined
// accoders
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
typedef long long ll;
using namespace std;
#define lx ll
inline lx qr()
{
char ch = getchar(); lx x = 0, f = 1;
for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
return x * f;
}
#undef lx
#define qr qr()
#define pll pair<ll, ll>
#define fi first
#define se second
#define M_P(x, y) make_pair(x, y)
const int Ratio = 0;
const int N = 1e6 + 5;
int n, b[N], f[N], ans, cnt = 1;
ll a[N], maxx, MA;
int t[N * 20], son[N * 20][2];
namespace Wisadel
{
#define ls son[rt][0]
#define rs son[rt][1]
#define mid ((l + r) >> 1)
inline void Wpushup(int rt)
{
t[rt] = max(t[ls], t[rs]);
}
inline void Wadd(int &rt, ll l, ll r, ll x, int k)
{
if(!rt)rt=++cnt;
if(l == r){t[rt] = max(t[rt], k); return ;}// !
if(x <= mid)
{
Wadd(ls, l, mid, x, k);
}
else
{
Wadd(rs, mid + 1, r, x, k);
}
Wpushup(rt);
}
inline int Wq(int rt, ll l, ll r, ll x, ll y)
{
if(!rt) return 0;
if(x <= l && r <= y) return t[rt];
int ans = 0;
if(x <= mid) ans = Wq(ls, l, mid, x, y);
if(y > mid) ans = max(ans, Wq(rs, mid + 1, r, x, y));
return ans;
}
short main()
{
freopen("alice.in", "r", stdin), freopen("alice.out", "w", stdout);
n = qr;
fo(i, 1, n) a[i] = qr, MA = max(MA, a[i]);
fo(i, 1, n) b[i] = qr, maxx = max(maxx, MA * b[i]);
int rot = 1;
fo(i, 1, n)
{
f[i] = Wq(1, 1, maxx, 1, a[i] - 1) + 1;
Wadd(rot, 1, maxx, 1ll * a[i] * b[f[i]], f[i]);
ans = max(ans, f[i]);
}
printf("%d\n", ans);
return Ratio;
}
}
signed main(){return Wisadel::main();}
B. Bob 与幸运日
解同余方程 + 分讨，挺 ex 的。
暴力直接跑，不过要注意 \(a,b=w\) 的情况，直接开局取模即可，挂了 10pts。
正解仙姑，估计需要复习板子。
C. Charlie 的运输网
有点复杂的树上问题。
暴力就是每次 \(\mathcal{O(n)}\) 跑一遍图，如果跑到了已经跑过的点就看是否符合 \(dis_v\equiv dis_u+1\pmod 2\)，不符合直接 return 即可，复杂度 \(\mathcal{O(nq)}\)，有 25pts。
正解仙姑。
D. David 与和谐号
迭代加深搜索。
首先一个上界 \(2n-2\) 是通过对 \(2\) ~ \(n\) 做了共 \(n-1\) 次先换到 1 再换到本身位置的操作得来的。然后因为步数少，可以用迭代加深搜索做。所谓迭代加深搜索，其实就是规定了搜索的深度不超过某个钦定的值，相当于做了很大的剪枝。这样还不足以通过本题。我们发现每次翻转只会改变一对相邻数对，因此对于每个状态求出值不连续的相邻数对的数量，剩余步数一定大于这个值，然后就能过了。稍微卡卡常能跑的飞快。
点击查看代码（41ms）
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
typedef long long ll;
using namespace std;
#define lx ll
inline lx qr()
{
char ch = getchar(); lx x = 0, f = 1;
for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
return x * f;
}
#undef lx
#define qr qr()
#define pll pair<ll, ll>
#define fi first
#define se second
#define M_P(x, y) make_pair(x, y)
const int Ratio = 0;
const int N = 30 + 5;
int n, ans;
int a[N];
namespace Wisadel
{
inline int Wq()
{
int res = 0;
fo(i, 1, n) res += (abs(a[i] - a[i + 1]) != 1);
return res;
}
inline bool Wdo(int res)
{
int zc = Wq();
if(res + zc > ans) return 0;
if(res == ans) return !zc;
fo(i, 2, n)
{
reverse(a + 1, a + 1 + i);
if(Wdo(res + 1)) return 1;
reverse(a + 1, a + 1 + i);
}
return 0;
}
short main()
{
freopen("david.in", "r", stdin), freopen("david.out", "w", stdout);
int T = qr;
while(T--)
{
n = qr, ans = 0;
fo(i, 1, n) a[i] = qr;
a[n + 1] = n + 1;
while(!Wdo(0)) ans++;
printf("%d\n", ans);
}
return Ratio;
}
}
signed main(){return Wisadel::main();}
末
CSP 前最后一场模拟赛，紧张是肯定的，有些地方明显失常了。
T1 想剪枝想假了，发现赛时的做法会漏掉某个区间内的值，其实还是没手动算最坏的时空复杂度，每次最多加 \(\log n\) 个点，所以单点修改到底就行。T2 忘了怎么解同余方程（其实就没想到要解），暴力还挂了。T3 T4 感觉暴力也没打完，还能拿更多的分。但其实加上 T1 T2 挂的就能 Rank1 了，有点可惜。好在不是正式比赛，一切都还有机会。
考前心态最重要，没准这挂的 40pts 就在之后的某次更重要的比赛上复活了。
加油，我的第一次，也是最后一次。
完结撒花~
