T1 点分树
很简单的思路，暴力跳父亲，就是去除当前数最后一个 \(1\) 再计算当前子树的答案，记得减去已经算过的子树的答案
#include<bits/stdc++.h>
#define N 10000010
#define mod 998244353
#define int long long
using namespace std;
int n,q,ans,fac[N],inv[N];
vector<int>g;
inline int ksm(int x,int y){
int res = 1;
while(y){
if(y&1) res = res*x%mod;
x = x*x%mod;
y>>=1;
}
return res;
}
inline int C(int x,int y){
if(x<y||x<0||y<0) return 0;
return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
bool cmp(int x,int y){
return x>y;
}
inline void jump(int d){
if(g.size())ans = C(g[(int)g.size()-1],d)%mod;
else ans = C(n,d)%mod;
for(int i = 1;g.size();i++){
if(g.size()>1) ans = (ans+C(g[(int)g.size()-2],d-i))%mod;
else ans = (ans+C(n,d-i))%mod;
ans = (ans-C(g[(int)g.size()-1],d-i-1)+mod)%mod;
g.pop_back();
}
}
signed main(){
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>q;
fac[0] = 1;
for(int i = 1;i<N;i++)
fac[i] = fac[i-1]*i%mod;
inv[N-1] = ksm(fac[N-1],mod-2);
for(int i = N-2;i>=0;i--)
inv[i] = inv[i+1]*(i+1)%mod;
for(int i = 1;i<=q;i++){
g.clear();ans = 0;
int k,d;cin>>k;
for(int j = 1;j<=k;j++){
int x;cin>>x;
g.push_back(x);
}
sort(g.begin(),g.end(),cmp);
cin>>d;
jump(d);
cout<<ans<<"\n";
}
return 0;
}
T2 塔
只有最下面 $\sqrt k $ 行会放二技能，可以自己算一下，上面的只会放一技能
考虑 \(dp\) ，设 \(f_{i,j}\) 表示从左到右的第 \(i\) 条斜线，在第 \(j\) 行放二技能的最小代价
对于每一条斜线，枚举放二技能位置，斜线外的点都用一技能解决
对于转移， \((a,b)\) 放二技能同时相当于在 \((a+1,b)\) 放置了二技能，因此 \(f_{i,j}\) 可以从 \(f_{i-1,j+1}\) 转移
此时在斜线 \(i-1\) 的 \(j\) 行放二技能不消耗代价，因此要减去
同时 \(f_{i,j}\) 可以从 \(f_{i-1,*}\) 转移 \(*\)作为通配符应该没人不知道吧
只记录下 \(\min\limits_{j = 1}^{i-1} f_{i-1,j}\) 再加上滚动数组即可
时间复杂度 \(\mathcal O(n\sqrt k)\)
#include<bits/stdc++.h>
#define N 100010
#define inf 0x3f3f3f3f
using namespace std;
int n,m,k,f[N][2],g[N];
vector<int>v[N];
int main(){
freopen("tower.in","r",stdin);
freopen("tower.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>k;
for(int i = 1;i<=k;i++){
int x,y;cin>>x>>y;
v[y].push_back(n-x+1);
}
while(g[m]<=k*3){
m++;
g[m] = m*(m+1)/2+2;
}
for(int i = 1;i<=m;i++)
f[i][0] = inf;
for(int i = 1;i<=n;i++){
sort(v[i].begin(),v[i].end());
int p = (i&1),mn = f[m][p] = inf;
int x = 0;
for(int j = 1;j<=m;j++){
while((x<v[i].size())&&(v[i][x]<j)) x++;
f[j-1][p] = f[j][p^1]+((int)v[i].size()-x)*3;
}
x = 0;
for(int j = 0;j<m;j++){
while((x<v[i].size())&&(v[i][x]<=j)) x++;
mn = min(mn,f[j][p^1]);
f[j][p] = min(f[j][p],mn+g[j]+((int)v[i].size()-x)*3);
}
}
cout<<min(f[0][n&1],f[1][n&1]);
return 0;
}
T3 排序
考虑增量构造，即按某种顺序，每次将 \(n\) 归位，并递归到规模为 \(n-1\) 的子问题
直接做能得到一个 \(O(n\log n)\) 的做法，但并不够优秀
我们将一次操作考虑成一个置换，则我们只需构造一个置换序列 \(\{p_i\}\)，使得 \(p_k \circ p_{k-1} \circ \cdots \circ p_1 \circ a = e\)。这等价于构造 \(p_1^{-1}\circ p_2^{-1} \circ \cdots \circ p_k^{-1}=a\)，即使得 \(p_1^{-1}\circ p_2^{-1} \circ \cdots \circ p_k^{-1}\circ a^{-1}=e\)
看不懂是啥？题解写的我也不懂，不过你可以去oi-wiki上了解
还有一点，\(a^{-1} \circ a = e\)
因此我们不妨考虑对原排列的逆排列排序，且只能使用原操作的逆操作，最后将操作序列倒序输出即可
现在考虑如何将 \(i\) 移到 \(n\)。观察到若 \(2i\le n\)，则使用操作 \((1,2i)\) 可以使得 \(i\) 移到 \(2i\)
而否则我们使用操作 \((2i-n+1,n)\)，可以直接令 \(i\) 移动到 \(n\)
注意到这样一次过程需要 \(\log n-\log i+1\) 次操作，而这是均摊 \(O(1)\) 的
为了使排列随机，在一开始的时候随机操作若干次，打乱排列即可
#include<bits/stdc++.h>
using namespace std;
int n,a[3010],b[3010];
vector<pair<int,int> >v;
void work(int l,int r){
if(l>=r)return;
static int c[3010];
int p=l;
for(int i=l+1;i<=r;i+=2)c[i]=b[p++];
for(int i=l;i<=r;i+=2)c[i]=b[p++];
for(int i=l;i<=r;i++)b[i]=c[i];
v.emplace_back(l,r);
}
mt19937 rnd(17680321);
bool solve(){
v.clear();
for(int j=1;j<=n;j++)b[j]=a[j];
for(int i=1;i<=rnd()%20;i++){
int l=rnd()%n+1,r=rnd()%n+1;
if(l>r)swap(l,r);
work(l,r);
}
for(int i=n;i;i--){
int j=find(b+1,b+i+1,i)-b;
while((j<<1)<=i)work(1,j<<=1);
work((j<<1)-i+1,i);
}
return v.size()<=6000;
}
int main(){
freopen("sort.in","r",stdin);
freopen("sort.out","w",stdout);
scanf("%d",&n);
for(int i=1,x;i<=n;i++)scanf("%d",&x),a[x]=i;
while(!solve());
printf("%d\n",v.size());
while(!v.empty())printf("%d %d\n",v.back().first,v.back().second),v.pop_back();
return 0;
}