省流：\(100+100+100+0\)。
T1
题意：给定长度为 \(n\) 的序列 \(a,b\)，你需要找到一个字典序最大的序列 \(ans\) 使得对于所有的 \(1 \leq i \leq n\)，\(ans_i = ((a_i \oplus ans_{i - 1}) + (b_i \oplus ans_{i - 1})) \% 2^{32}\)，其中 \(ans_0 = ans_n\)。
\(1 \leq n \leq 3 \times 10^5,a_i,b_i \in [0,2^{32})\)。
官方做法：
从低到高枚举 \(ans_n\) 的每一位是什么，check 在这一位下是不是对的，如果对的就继续往下搜。时间复杂度为 \(\Theta(Sn \log V)\)，其中 \(S\) 为合法解的个数。
这就可以通过了， 但是为什么是对的？
考虑 \(a + b\) 的最低位，当给 \(a,b\) 同时异或上某个数的时候，\(a+b\) 的最低位是不会变的，因此每次确定 \(ans_n\) 的最低位然后递推上去就是 \(\Theta(n \log V)\) 的。
我的抽象做法：
可以把 \(ans_n\) 的 \(32\) 位拆成 \(4\) 个 \(8\) 位，对于每 \(8\) 位暴力求出 \(tmp_i\) 表示假设 \(ans_0 = i\) 时 \(ans_q\) 的值。
稍微打表发现，\(tmp_i + tmp_{2^8j} + tmp_{2^{16}k}+tmp_{2^{24}l} = tmp_{i + 2^8j + 2^{16}k + 2^{24}l} + 3 \times tmp_0\)。其中 \(i,j,k,l < 2^8\)，这样我们就能表示出所有的 \(tmp_i\)。如果一个 \(i\) 是合法的，说明 \(tmp_i = i\)，那么把上面的柿子改写一下，即：
- 若 \(i + 2^8j + 2^{16}k + 2^{24}l\) 为合法的 \(ans_0\) 当且仅当 \(tmp_i + tmp_{2^8j} + tmp_{2^{16}k}+tmp_{2^{24}l} = i + 2^8j + 2^{16}k + 2^{24}l + 3 \times tmp_0\)
可以移项，使每个 \(tmp_i\) 变为 \(tmp_i - i\)，那么上面的柿子就变为 \(tmp_i + tmp_{2^8j} + tmp_{2^{16}k}+tmp_{2^{24}l} = 3 \times tmp_0\)。
暴力把第一第二项合并，第三第四项合并，然后在两个合并好的序列上双指针即可。时间复杂度 \(\Theta(n \sqrt[4]{V} + \sqrt{V})\)。
我的做法代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+5;
unsigned ans[N];
pair<int,int> x[N],y[N];
int n,a[N],b[N],tmp[N],sum[N],pos[N],genshin=0,res=114514;
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>n;
for(int i=1; i<=n; i++) cin>>a[i]>>b[i];
for(int i=0; i<256; i++) {
ans[0]=i;
for(int j=1; j<=n; j++) ans[j]=(a[j]^ans[j-1])+(b[j]^ans[j-1]);
tmp[i]=ans[n];
}
for(int i=0; i<256; i++) {
ans[0]=i*256;
for(int j=1; j<=n; j++) ans[j]=(a[j]^ans[j-1])+(b[j]^ans[j-1]);
tmp[i*256]=ans[n];
}
for(int i=0; i<256; i++)
for(int j=0; j<256; j++)
x[i+j*256]=make_pair(tmp[i]+tmp[j*256]-(i+j*256),i+j*256);
for(int i=0; i<256; i++) {
ans[0]=i*65536;
for(int j=1; j<=n; j++) ans[j]=(a[j]^ans[j-1])+(b[j]^ans[j-1]);
tmp[i]=ans[n];
}
for(int i=0; i<256; i++) {
ans[0]=i*16777216;
for(int j=1; j<=n; j++) ans[j]=(a[j]^ans[j-1])+(b[j]^ans[j-1]);
tmp[i*256]=ans[n];
}
for(int i=0; i<256; i++)
for(int j=0; j<256; j++)
y[i+j*256]=make_pair(tmp[i]+tmp[j*256]-(i*65536+j*16777216),i*65536+j*16777216);
swap(x,y);
sort(x,x+65536);sort(y,y+65536);
memset(pos,-1,sizeof(pos));
sum[0]=1,pos[0]=0;
for(int i=1; i<65536; i++) {
if(y[i].first==y[i-1].first) sum[i]=sum[i-1],pos[i]=pos[i-1];
sum[i]++;
if(!~pos[i]||(a[1]^y[i].second)+(b[1]^y[i].second)>(a[1]^y[pos[i]].second)+(b[1]^y[pos[i]].second)) pos[i]=i;
}
int ps=65535;
for(int i=0; i<65536; i++) {
while(ps>=0&&x[i].first+y[ps].first>3*tmp[0]) ps--;
if(ps>=0&&x[i].first+y[ps].first==3*tmp[0]) {
if((a[1]^(x[i].second+y[pos[ps]].second))+(b[1]^(x[i].second+y[pos[ps]].second))>genshin) {
genshin=(a[1]^(x[i].second+y[pos[ps]].second))+(b[1]^(x[i].second+y[pos[ps]].second));
res=x[i].second+y[pos[ps]].second;
}
}
}
ans[0]=res;
for(int i=1; i<=n; i++) ans[i]=(a[i]^ans[i-1])+(b[i]^ans[i-1]);
for(int i=1; i<=n; i++) cout<<ans[i]<<'\n';
return 0;
}
闲话：这题做了2h\oh\oh\oh
T2
原题：CF1967B2。
题意：给定两个整数 \(n,m\)，你需要对满足以下条件的二元组 \((a,b)\) 计数：
- \(1 \leq a \leq n,1 \leq b \leq m\)
- \((a + b) \mid (b \times \gcd(a,b))\)
\(n,m \leq 10^6\)。
数学题。。。
老样子，稍微打表发现，若 \((a + b) \mid \gcd(a,b)^2\)，则 \((a + b) \mid (b \times \gcd(a,b))\)。
所以只需要对满足 \((a + b) \mid \gcd(a,b)^2\) 的在合法范围的 \((a,b)\) 计数就行。
设 \(d = \gcd(a,b)\)，则 \((a + b) \mid d^2\) 等价于 \((\frac{a}{d} + \frac{b}{d}) \mid d\)，所以可以枚举 \(i\) 从 \(1 \to n\)，\(j\) 从 \(1 \to m\)，其中 \(i\) 表示 \(\frac{a}{d}\)，\(b\) 表示 \(\frac{b}{d}\)，由于 \(d\) 是 \(i + j\) 的倍数且 \(i \times d \leq n,j \times d \leq m\)，所以合法的 \(d\) 的个数为 \(\lfloor \frac{\min(\lfloor \frac{n}{i} \rfloor,\lfloor \frac{m}{j} \rfloor)}{i + j} \rfloor\)，发现这个柿子当 \(i > \sqrt n\) 或 \(j > \sqrt m\) 时答案为 \(0\)，所以 \(i\) 只需枚举到 \(\sqrt n\)，\(j\) 只需枚举到 \(\sqrt m\)。时间复杂度忽略求 \(\gcd\) 是 \(\Theta(\sqrt{nm})\)。
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,m;
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>t;
while(t--) {
cin>>n>>m;int ans=0;
for(int i=1; (i-1)*(i-1)<=n; i++) {
for(int j=1; (j-1)*(j-1)<=m; j++) {
if(__gcd(i,j)>1) continue;
ans+=min(n/i,m/j)/(i+j);
}
}
cout<<ans<<'\n';
}
return 0;
}
闲话：这题做了1.5h\oh\oh\oh
T3
题意：给定一个长为 \(n\) 的排列 \(p\)，你需要用最少的操作使得一个形如 \(1,2,3,\cdots,n\) 的排列变为排列 \(p\)，输出操作次数和方案，定义一次操作如下：
选择一个位置 \(1 \leq pos <n\)，把 \([1,pos]\) push到第一个队列，把 \([pos+1,n]\) push到第二个队列，有一个空序列 \(q\)，每次你可以把一个非空队列的队首弹出并放在 \(q\) 的末尾，当两个队列都为空时，让 \(p\) 变成 \(q\)。
多测。\(n \leq 52,\sum n \leq 2 \times 10^5\)。
首先有个比较自然的思路是把 \(p_i\) 变成它的逆排列 \(p'\)，即 \(p'_{p_i} = i\)，这样题意就变为了用最少的操作使得 \(p'\) 变为 \(1,2,3,\cdots,n\) 的排列。
可以先把 \(p'\) 分为若干个连续的上升段，设有 \(cnt\) 个，则把前 \(\frac{cnt}{2}\) 个段扔进第一个队列，剩余扔进第二个。每次让两个队首的段合并放进 \(q\) 的末尾，可以证明一定有一种方法使得合并后的段是上升的，将两个队列队首的段再pop掉。如果第二个队列多了一个段就原封不动的放到 \(q\) 的末尾。这样每次段数会减少一半，可以证明是最少的步数，虽然我不会证。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int t,n,a[N],pos[N];
vector<char> ve[N];
pair<int,int> pr[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>t;
while(t--) {
cin>>n;
for(int i=1; i<=n; i++) cin>>pos[i];
for(int i=1; i<=n; i++) a[pos[i]]=i;
int tot=0,turn=0;
queue<int> q,q1,q2;
while(tot!=1) {
tot=0;turn++;
int cnt=1,lst=1;
for(int i=1; i<=n; i++) {
if(a[i]>a[i-1]) continue;
pr[++tot]=make_pair(lst,i-1);lst=i;
}
pr[++tot]=make_pair(lst,n);
int pos1=1,pos2=tot/2+1;
for(int i=1; i<=tot/2; i++) {
for(int j=pr[pos1].first; j<=pr[pos1].second; j++) q1.push(a[j]);
for(int j=pr[pos2].first; j<=pr[pos2].second; j++) q2.push(a[j]);
while(!q1.empty()&&!q2.empty()) {
if(q1.front()<q2.front()) q.push(q1.front()),q1.pop(),ve[turn].push_back('A');
else q.push(q2.front()),q2.pop(),ve[turn].push_back('B');
}
while(!q1.empty()) q.push(q1.front()),q1.pop(),ve[turn].push_back('A');
while(!q2.empty()) q.push(q2.front()),q2.pop(),ve[turn].push_back('B');
pos1++,pos2++;
}
if(pos2<=tot) for(int j=pr[pos2].first; j<=pr[pos2].second; j++) q.push(a[j]),ve[turn].push_back('B');
for(int i=1; i<=n; i++) a[i]=q.front(),q.pop();
}
turn--;
cout<<turn<<'\n';
for(int i=1; i<=turn; i++) {
for(int j=0; j<ve[i].size(); j++) cout<<ve[i][j];
cout<<'\n';ve[i].clear();
}
ve[turn+1].clear();
}
return 0;
}
闲话：这题只做了40min\kx。好像是某noi模拟t1。
T4
原题：2024年集训队互测Désive。
还不会。代码似乎很难写。
标签：tmp,noip,leq,int,pos,241110,second,ans,模拟 From： https://www.cnblogs.com/System-Error/p/18538156