感觉可以拿一些神秘东西来摘录（
内心不堪的记忆快将悲伤穿透
无法释怀的怨恨都因为那家伙
才留存于心
你们怎么会明白呢
真正受伤的孤独
现在就把束缚挣脱
— Ado，逆光
还不是很能挣脱束缚，因此划掉最后一句。
题目越来越离离原上谱，再加上是一堆新题目，因此题单里没有更新。
[A]
考 hash 还搁着卡 unordered_map，有点左右脑互搏。
然后纯让考生调整 hash_table 的数组大小，小了 TLE，大了 RE。
最终试出来大小在 1.5 \times 10^7 左右，有点反人类。
#include
using namespace std;
const int N = 5005;
typedef long long LL;
const LL mod = 14000029, delta = 2e9;
LL T[mod];
int read()
{
int x = 0, f = 1;
char ch = getchar();
while (ch '9')
{
if (ch == '-')f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = (x << 3) + (x << 1) + (ch ^ '0');
ch = getchar();
}
return x * f;
}
int n, res;
LL w[N];
LL HASH(LL x)
{
LL t = x % mod;
while (T[t] && T[t] != x)t = (t + 1) % mod;
return t;
}
int main()
{
freopen("good.in", "r", stdin);
freopen("good.out", "w", stdout);
n = read();
for (int i = 1; i <= n; i ++)
{
w[i] = read();
for (int j = 1; j < i; j ++)
{
if (T[HASH(w[i] - w[j] + delta)] == (w[i] - w[j] + delta))
{
res ++;
break;
}
}
for (int j = 1; j <= i; j ++)T[HASH(w[i] + w[j] + delta)] = (w[i] + w[j] + delta);
}
printf("%d", res);
return 0;
}
[B]
考场上二分写挂了没调出来，事实上连二分都不需要。
首先容易知道先对 k 区间做一个区间合并，合并完成后之多 2000 个区间。
考虑 DP，设 f_{i, j} 表示 S 的第 i 段， T 的第 j 个字符开始向后匹配最多匹配多少个。
转移好写，不放了。主要还要考虑可能前面也有可能匹配上，因此再向前暴力跑就行。
时间复杂度不会算 O(k \log k + nm) 主要瓶颈在 k 个区间的排序处理。
#include
using namespace std;
const int N = 2005;
typedef pair PII;
#define l first
#define r second
vector seg, res;
int n, m, k;
char s[N], t[N];
int cntS[N][26];
int f[N][N], cnt[26];
int main()
{
freopen("lcs.in", "r", stdin);
freopen("lcs.out", "w", stdout);
scanf("%s%s%d", t + 1, s + 1, &k);
m = strlen(t + 1);
n = strlen(s + 1);
for (int i = 1; i <= n; i ++)
{
cntS[i][s[i] - 'a'] ++;
for (int j = 0; j < 26; j ++)cntS[i][j] += cntS[i - 1][j];
}
while (k --)
{
int l, r;
scanf("%d%d", &l, &r);
l ++, r ++;
seg.push_back({l, r});
}
sort(seg.begin(), seg.end());
res.push_back({0, 0});
int st = -2e9, ed = 0;
for (auto i : seg)
{
if (ed < i.l)
{
if(st != -2e9)res.push_back({st, ed});
for (int j = ed + 1; j <= i.l - 1; j ++)res.push_back({j, j});
st = i.l, ed = i.r;
}
else ed = max(ed, i.r);
}
if (st != -2e9)res.push_back({st, ed});
if (ed + 1 <= n)
{
for (int j = ed + 1; j <= n; j ++)res.push_back({j, j});
}
int ans = 0;
for (int i = res.size() - 1; i; i --)
{
int L = res[i].l, R = res[i].r;
for (int j = m; j; j --)
{
memset(cnt, 0, sizeof cnt);
int flag = 0;
for (int k = j; k < j + (R - L + 1) && k = 1; k --)
{
if (cnt[t[k] - 'a'] == cntS[RP][t[k] - 'a'] - cntS[LP - 1][t[k] - 'a'])break;
cnt[t[k] - 'a'] ++;
flag ++;
}
ans = max(ans, f[i][j] + flag);
}
}
printf("%d", ans);
return 0;
}
[C]
感觉有点人类智慧，但是用的都是基础算法。
暴力做不太可行，因此考虑求 LCA 的时候能不能加速。
答案是显然的，对于 $a_x > by时，我们就是要找x’ < x且a{x’} < b_y的最大的x’$。
因此直接一个二分 + ST表 送走，时间复杂度这回真不太会算，因为最差情况下仍然有可能跳 O(n) 次，但是考虑到 数据随机生成， 跳的次数一定不会太多，因此能过。
#include
using namespace std;
#define x first
#define y second
typedef pair PII;
typedef long long LL;
const int N = 1e5 + 5;
int n, m, cnt, Log[N];
int f[N][25], g[N][25];
int queryF(int l, int r)
{
int k = Log[r - l + 1];
return min(f[l][k], f[r - (1 << k) + 1][k]);
}
int queryG(int l, int r)
{
int k = Log[r - l + 1];
return min(g[l][k], g[r - (1 <= '0' && ch <= '9')
{
x = (x << 3) + (x 1;
if (queryF(mid, u.x - 1) 1;
if (queryG(mid, u.y - 1) < f[u.x][0])l = mid;
else r = mid - 1;
}
u.y = l;
}
}
PII LCA(PII u, PII v)
{
PII lastu = {1, 1}, lastv = {1, 1};
while (u != v)
{
if (u.x + u.y < v.x + v.y)
{
swap(u, v);
swap(lastu, lastv);
}
lastu = u;
jump(u);
if (lastu.x == u.x && u.x == v.x && u.y <= v.y && v.y <= lastu.y)return v;
if (lastu.y == u.y && u.y == v.y && u.x <= v.x && v.x <= lastu.x)return v;
if (lastv.x == u.x && u.x == v.x && v.y <= u.y && u.y <= lastv.y)return u;
if (lastv.y == u.y && u.y == v.y && v.x <= u.x && u.x 1] + 1;
f[i][0] = read();
}
for (int i = 1; i <= n; i ++)g[i][0] = read();
for(int j = 1; j <= Log[n]; j ++)
{
for(int i = 1; i + (1 << j) - 1 <= n; i ++)
{
f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
g[i][j] = min(g[i][j - 1], g[i + (1 << (j - 1))][j - 1]);
}
}
m = read();
while (m --)
{
PII a, b;
a.x = read(), a.y = read(), b.x = read(), b.y = read();
PII lca = LCA(a, b);
printf("%d\n", a.x + a.y + b.x + b.y - 2 * (lca.x + lca.y));
}
return 0;
}
[D]
首先我们需要会 FWT。
（提一嘴，FFT 都是 10 级考点了您这直接演都不演了）
然后会了之后，我们猜左右两边具有独立性，也就是你从左边选一个合法子集，和从右边选一个合法子集，拼在一起一定合法。
这个东西不是很会证，但是从边上去考虑应该还是比较能看出来的。
以上纯口胡，代码还没打，让我打完再来。
调不动了，获得了 72pts.
#include
using namespace std;
const int N = 25, M = (1 << 20) + 5, K = (1 <= '0' && ch <= '9')
{
x = (x << 3) + (x << 1) + (ch ^ '0');
ch = getchar();
}
return x * f;
}
void mul()
{
for (int i = 0; i < K; i ++)a[i] = (a[i] * b[i]) % mod;
}
void XOR(LL *f, LL op)
{
for(int i = 1; i < K; i <<= 1)
{
for(int p = i << 1, j = 0; j < K; j += p)
{
for(int k = 0; k > 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
x = (x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF);
return x;
}
void dfs1(int u, int S, int w, int cnt)
{
if (u == n)
{
a[w] ++;
return;
}
dfs1(u + 1, S, w, cnt);
if (cnt + 1 <= popcount(S | f[u]))dfs1(u + 1, S | f[u], w ^ w1[u], cnt + 1);
}
void dfs2(int u, int S, int w, int cnt)
{
if (u == m)
{
b[w] ++;
return;
}
dfs2(u + 1, S, w, cnt);
if (cnt + 1 <= popcount(S | g[u]))dfs2(u + 1, S | g[u], w ^ w2[u], cnt + 1);
}
int main()
{
freopen("bip.in", "r", stdin);
freopen("bip.out", "w", stdout);
int ID = read(), e, q;
n = read(), m = read(), e = read(), q = read();
for (int i = 0; i < n; i ++)w1[i] = read();
for (int i = 0; i < m; i ++)w2[i] = read();
while (e --)
{
int x, y;
scanf("%d%d", &x, &y);
x --, y --;
f[x] |= (1 << y);
g[y] |= (1 << x);
}
dfs1(0, 0, 0, 0);
dfs2(0, 0, 0, 0);
XOR(a, 1), XOR(b, 1), mul(), XOR(a, inv);
while (q --)
{
int x = read();
printf("%lld\n", a[x]);
}
return 0;
}