~

题意:有 $n$ 个数字，可以把 $n$ 个数字分成若干组，只有连续的数字才能分成一组，并且一组最多 2 个数字，问你所有组的最大值-最小值的差值最小是多少。 发现组的类别一共 2n 种，排序之后枚举最大值，然后指针移动用线段树维护即可。 线段树维护的信息有些不同: $t_{p,x,y}$ 表示 $[l+x, r+y]$ 被覆盖，判断可行的条件是 $t_{1,0,0}$ 是否是 true。 然后发现 $n \times 2$ 大小的 $zkw$ 挂了，原因是可能子树反掉。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576#include <bits/stdc++.h>#ifndef LOCAL#define debug(...) 42#else#define debug(...) cerr << "[" & ...

线性基通常指 $\mathbb{Z}_{2}^{n}$ 下的一组线性无关的向量，而向量用二进制数简易表示。 加法相当于异或运算。 内积，两个数各个位相乘再累加，等价于 $\text{parity(u & v)}$，如果该值为 0，则 $u,v$ 正交。 $\text{span}(A)$ 里的任何一个数字可以被表示出来 $2^{n-|A|}$ 次。 满足分配律，即 $(u + v)·w = u·w+v·w$。 线性基求交的部分内容。（From Sooke。） 高斯消元：针对线性基的高斯消元，目的在于使各个基的最高一位被各自独占，其余位均为 0，可以解决线性基第 $k$ 大等问题，这些位被称为关键位，其余被称为非关键位。 集合幂级数：集合幂级数可以简单理解成 $[x^u]$ 指标为 $u$ 在 $\mathbb{Z}_{2}^{n}$ 下的向量，二进制数的多项式。 对于集合幂级数 $F$，$\hat F = FWT[F]$，对于 $F$ 的 $[x^u]$，若 $u, w$ 正交，则对 $\hat F$ 的 $[x^w]$ 贡献为正，否则为负，系数即为 ...

A.直接写就完了。 12345678910111213141516171819void solve() { int n, a, q; cin >> n >> a >> q; int b=a,mx=a; rp(i,q){ char c; cin>>c; if(c=='-')a--; if(c=='+')a++,b++; cmax(mx,a); } if(mx==n){ cout<<"YES\n"; }else if(b>=n){ cout<<"MAYBE\n"; }else{ cout<<"NO\n"; }} B.考虑至多 $n-1$ 次，然后其实有些操作是不必要的，然后减掉这些不必要的就可以，但是这个实际上就是计算必要的部分。（下图写 ...

A.13/31，17/71，37/73，随便怎么样，我的暴力也过了。 123456789101112131415void solve() { string s; cin >> s; int n=9; rp(i,n)rep(j,i+1,n){ int x=s[i]-'0'; int y=s[j]-'0'; int k=x*10+y; if(isprime(k)){ cout<<k<<"\n"; return; } } cout<<"-1\n";} B.只要找到相同位置的 “01” 就可以了，随便怎么样，我的暴力也过了。 12345678910111213141516171819202122void solve() { string s,t; cin>>s>>t; int ...

The 2nd Universal Cup Stage 1: Qingdao, Sep 2-3, 2023https://contest.ucup.ac/contest/1339 A.有 $m$ 个 perfect 和 $n-m$ 个 nonperfect，分别使得连续段最大或者最小。 连续段最大显然是 $m$ 个 perfect 连在一起。 连续段最小的话可以考虑将把 $m$ 拆成 $n-m+1$ 段（$n-m$ 个可以拆分成 $n-m+1$ 段） 所以答案是 $m$ 和 $\lceil \frac{m}{n-m+1}\rceil$。 B.每个点的代价是离他最近的一个红点祖先的距离，每次询问选出 $k$ 个点，你可以随意改变一个点的颜色，使得 $\max{ cost_{v_i} }$ 最小。 要想要最大值变小，先将 $cost_{v_i}$ 排序，然后可以知道选的点一定在 $lca(v_i….v_k)$ 上。 所以每次的答案就是 $\max{cost{v_{i-1}}, \max{dep_{v_i} … dep_{v_k}} - dep_{lca}}$。 时间复杂度 $O(n \l ...