是金子总会发光的！
2026.11.03
#15297. 最大匹配对
很好的贪心，首先数列顺序没有用，考虑从小到大排序，然后不难看出，最优秀的匹配方式是首尾相匹配。
只考虑前 \(k\) 个数，如果前 \(k\) 个数可以匹配上，就看看 \(k + 1\) 个数能不能匹配，
如果匹配不上，看看 \(k - 1\) 个数能不能匹配上，这样一定是不劣的，如果 \(k\) 个数不能按这样优秀的操作匹配，至少有一个匹配是不合法的，不如减少一个数，完全匹配数至多减少 \(1\) ，且更容易匹配。
然后把所以匹配方法算出匹配数和匹配最大值，对每次询问做二分即可。
#include
using namespace std;
int rd() {int x = 0, w = 1;char ch = 0;while (ch < '0' || ch > '9') {if (ch == '-') w = -1;ch = getchar();}while (ch >= '0' && ch <= '9') {x = x * 10 + (ch - '0');ch = getchar();}return x * w;
}
void wt(int x) {static int sta[35];int f = 1;if(x < 0) f = -1,x *= f;int top = 0;do {sta[top++] = x % 10, x /= 10;} while (x);if(f == -1) putchar('-');while (top) putchar(sta[--top] + 48);
}
const int N = 1e4+5;
int n,q,a[N],k,lstans;
pair m[N];
int p[N],z[N];void solve() {n = rd(),q = rd(),lstans = 0;for(int i = 1;i<=n;i++) a[i] = rd();sort(a + 1,a + n + 1);for(int i = 1;i<=n;i++) {int mx = 0;for(int j = 1;j <= i / 2;j++) {int o = i - j + 1;mx = max(mx,a[o] + a[j]);}m[i] = {mx,i / 2};}sort(m + 1,m + n + 1);for(int i = 1;i<=n;i++) m[i].second = max(m[i].second,m[i - 1].second);for(int i = 1;i<=n;i++) p[i] = m[i].first,z[i] = m[i].second;while(q--) {int k = rd() ^ lstans;int o = upper_bound(p + 1,p + n + 1,k) - p - 1;wt(z[o]),putchar('\n');lstans = z[o]; }
}signed main() {int t = rd();while(t--) solve();return 0;
}
Nucleic Acid Test
先跑一个 \(floyd\)，对黑点单独建图，做最小生成树，这就是最优旅游路线，对于白点，找到最近的黑点，跑来回最优，找到这些的操作的最大值，除以时间，得到答案。
小心时间为 \(0\) 的情况， 万恶的 \(corner\ case\)
#include
using namespace std;#define int long long
const int MAXN=600;
int n,m,k,T;
vector > e,e2;
bool b[MAXN];
vector > g[MAXN];int dis[MAXN];
bool vis[MAXN];
void dij() {priority_queue,vector >,greater > > pq;pq.push({0,0});for(int i=1;i<=n;i++) dis[i]=1e18;dis[0]=0;while(!pq.empty()) {auto [d,p]=pq.top();pq.pop();if(vis[p]) continue;vis[p]=true;for(auto [to,w]:g[p]) {if(dis[p]+w x,array y) {return x[2]>n>>m>>k>>T;if(T==0) {cout<<-1<>u>>v>>w;g[u].push_back({v,w});g[v].push_back({u,w});f[u][v] = w;f[v][u] = w;dsu.merge(u,v);}for(int i=1;i<=k;i++) {int t;cin>>t;b[t]=true;}floyd();for(int i=1;i<=n;i++) {for(int j=i+1;j<=n;j++) {if(b[i]&&b[j])e2.push_back({i,j,f[i][j]});}}bool flag=false;for(int i=1;i<=n;i++)if(dsu.siz[i]==n)flag=true;if(!flag) {cout<<-1<D. RReeppeettiittiioonn
%%% \(steveyang\) %%%
非常优质的根号分治，Yang 太强了。
当进制 \(> \sqrt{n}\) 时，只有 \(2\) 位数，可以解方程 \(\overline{kk} \rightarrow kd + k = n\)
反解出 \(d = \frac{n}{k} - 1\)，对于进制 \(< \sqrt{n}\) 的暴力求最大值，然后求最大值的约数个数。
#include
using namespace std;#define int long long
const int N=1e6+5;vector pri;
bool not_prime[N];
int d[N], num[N];void pre(int n) {d[1] = 1;for (int i = 2; i <= n; ++i) {if (!not_prime[i]) {pri.push_back(i);d[i] = 2;num[i] = 1;}for (int pri_j : pri) {if (i * pri_j > n) break;not_prime[i * pri_j] = true;if (i % pri_j == 0) {num[i * pri_j] = num[i] + 1;d[i * pri_j] = d[i] / num[i * pri_j] * (num[i * pri_j] + 1);break;}num[i * pri_j] = 1;d[i * pri_j] = d[i] * 2;}}
}int check(int x, int k) {int last=-1;int cnt=0;int g=0;while(x) {int t=x%k;x/=k;if(t==last) {cnt++;} else {if(cnt)g=gcd(g,cnt);last=t;cnt=1;}}g=gcd(g,cnt);return g;
}void solve() {int n;cin>>n;if(n<3) {cout<<0<=1) ans++;cout<>t;pre(1e6);while(t--) solve();return 0;
}//helloworld
The 2026 ICPC Asia Chengdu Regional Contest
M. 最少纪录
对于一个值，其为前缀最大值，就把其标记，考虑如何最小化标记。
因为是前缀最大值，所以考虑倒序扫（可以取消正序扫的后效性），考虑单调栈，能压住后面的值肯定优先压住后面，但是不要压得太狠，能刚好压上就刚好压上。
这样如果前面有一个有机会压上的也能发挥作用。
#include
using namespace std;
#define int long long
int rd() {int x = 0, w = 1;char ch = 0;while (ch < '0' || ch > '9') {if (ch == '-') w = -1;ch = getchar();}while (ch >= '0' && ch <= '9') {x = x * 10 + (ch - '0');ch = getchar();}return x * w;
}
void wt(int x) {static int sta[35];int f = 1;if(x < 0) f = -1,x *= f;int top = 0;do {sta[top++] = x % 10, x /= 10;} while (x);if(f == -1) putchar('-');while (top) putchar(sta[--top] + 48);
}
const int inf = 1e18;
void solve(){int n = rd();vector > a(n + 1);for(int i = 1;i<=n;i++) {auto &[l,r] = a[i];l = rd(),r = rd();}stack > s;s.push(a[n]);for(int i = n - 1;i >= 1;i--) {auto [l,r] = a[i];int mx = l;while(!s.empty() && r >= s.top()[0]) mx = max(mx,s.top()[0]),s.pop();s.push({mx,r});}wt(s.size());putchar('\n');
}signed main() {int t = rd();while(t--) solve();return 0;
}
H. 隐藏的顺序
考虑用询问在序列里面抠出一条不降的序列，操作 \(n - 1\) 次，如果能直接把整个序列抠出来，直接输出。
另外一部分考虑用双端队列维护，还是抠出一条不降的序列，而那些剩下的只能是 \(0\)，所以换方向 push 进去，操作 \(k - 1\) 次，\(k\) 为另外一部分的大小。
现在，审视现在的局面：一个序列是 \(0,\ldots,0,1,\ldots,1,2,\ldots,2\)，另外一个序列是 \(0,\ldots,0,1,\ldots,1\)
显然找到第一个序列的 \(0,1\) 交接处插入就可以在规定操作数完成了。
考虑对第一个序列反向询问，得到交接处。
但是遇到第一个序列是 \(1,1,1,2,2,2\) 怎么办，会和 \(0,0,0,1,1,1\) 搞混的。
这个时候，发现对于 \(1,1,1,2,2,2\) 的最小值为 \(1\)，第二个序列是 \(0,0,0,1,1,1\)，最小值是 \(0\)，\(1 > 0\) 通过询问可以分开和第一个序列是 \(0,0,0,1,1,1\) 的情况。
对于第一个序列是 \(1,1,1,2,2,2\) 和 \(2,2,2\)，都可以直接在最前面接上 \(0,0,0,1,1,1\)。
注意,这里需要特判 \(n = 2\) 的情形，这时这个特判方法会多一个操作，我使用 unordered_map 规避掉无需询问已知答案的操作。
根据刚才的操作，第一个序列的最大值显然是严格大于第二个序列内的所有值的，那么如果没有交接点肯定要放到第一个序列最后一个数前面，所以没有必要询问最后一个数和前面的数是否形成交接点对，如果没发现交接点对，就放在这里。
这样就可以在 \(2n - 3\) 次操作内完美通过。
赛时过 \(H\) 的队伍怎么这么少，这个交互显然很可做啊？
不要严格跟榜啊！
#include
using namespace std;
const int N = 1005;
bool ask(int i,int j) {cout<<"? "<>f;return f;
}
int p[N];
void answer(int n) {cout<<"! ";for(int i = 1;i<=n;i++) cout<o[3];struct queue{int q[N + N + N];int l = N,r = N;bool empty() {return l >= r;}void init() {l = r = N;}void push_back(int k) {q[r] = k;r++;}void push_front(int k) {l--;q[l] = k;}void pop_back() {if(empty()) return;r--;}void pop_front(){if(empty()) return;l++;}int get(int start) {for(int i = r - 1,cnt = 1;i >= l;i--,cnt++) p[start + cnt] = q[i];return start + r - l;}
}q2;void solve() {int n;cin>>n;unordered_map m;//part 1o[0].clear();o[1].clear();int mx = 1;bool flag = false;for(int i = 2;i<=n;i++) {m[mx * 505 + i] = ask(mx,i);if(!m[mx * 505 + i]) {o[0].push_back(mx);mx = i;}else o[1].push_back(i),flag = true;}o[0].push_back(mx);if(!flag) {cout<<"! ";for(int i = 0;i= q2.l;i--) o[1][cnt++] = q2.q[i];vector c(3);cnt = 0;if(!m.count(o[0][0] * 505 + o[1][0])) m[o[0][0] * 505 + o[1][0]] = ask(o[0][0],o[1][0]);flag = m[o[0][0] * 505 + o[1][0]];if(flag) {for(int i = 0;i= 1;i--) {if(!m.count(o[0][i] * 505 + o[0][i - 1])) m[o[0][i] * 505 + o[0][i - 1]] = ask(o[0][i],o[0][i - 1]);if(m[o[0][i] * 505 + o[0][i - 1]]) c[++cnt] = i;}if(cnt == 0) c[++cnt] = o[0].size() - 1;int i = 0;while(i < c[cnt]) {p[++top] = o[0][i];i++;}for(int j = 0;j>T;while(T--) solve();return 0;
}