【比賽記錄】2025CSP+NOIP 沖刺模擬賽合集Ⅱ
2025CSP-S模擬賽65（HZOJ 2025多校沖刺CSP模擬賽7）
| A | B | C | D | Sum | Rank |
|---|---|---|---|---|---|
| 100 | 40 | 15 | - | 155 | 7/12 |
HZOJ 上也有這場比賽，但我沒看見。放過去大概是個 14/24 左右吧。
A. gcd&xor (gcdxor)
首先打表，發現對于所有合法的 \((x,y)\)，都滿足 \(y-x|x\)。于是有 \(O(n\log^2n)\) 的做法，枚舉 \(y-x\)，再枚舉 \(x\)，暴力判斷合不合法。\(10^7\) 跑不過去，但 \(10^5\) 能跑過。考慮以 \(10^5\) 分塊，將每個塊前綴的答案打表出來，然后再用上面那個做法處理散塊即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define gcd __gcd
using namespace std;
namespace asbt{
const int B=1e5;
const ll pre[]={0,173407,347890,522448,696846,871744,1046284,1220431,1395236,1570280,1745100,1919875,2093695,2267837,2442059,2617018,2791283,2966683,3141146,3315871,3490365,3666781,3839968,4013813,4188010,4362066,4536292,4710801,4884960,5060158,5234883,5408205,5583629,5758317,5933666,6107019,6282382,6458098,6631521,6804281,6980543,7155409,7332425,7505250,7678957,7852680,8026427,8200183,8374902,8548938,8723182,8897288,9071582,9246092,9420147,9594727,9768429,9942808,10117875,10291162,10467026,10640553,10813783,10989926,11164092,11338740,11513448,11687394,11863511,12037297,12210785,12385489,12560986,12736987,12911711,13084959,13258776,13431315,13604565,13779830,13956088,14130677,14305355,14480650,14657932,14830769,15004603,15178361,15352044,15525831,15699840,15873481,16047556,16221400,16395321,16570018,16744419,16919172,17092225,17266746,17440305};
int n;
int main(){
freopen("gcdxor.in","r",stdin);
freopen("gcdxor.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
int id=n/B;
ll ans=pre[id];
// cout<<ans<<'\n';
// cout<<n/B;
for(int i=1;i<=n;i++){
// cout<<i<<' '<<(id*B+i)/i*i-i<<'\n';
for(int j=max((id*B+i)/i*i-i,i);j+i<=n;j+=i){
if((j^(i+j))==gcd(j,i+j)){
// cout<<j<<' '<<i+j<<'\n';
ans++;
}
}
}
cout<<ans;
return 0;
}
}
int main(){return asbt::main();}
B. 異或樹 (xortree)
因為樹始終是完全二叉樹，所以除了葉子節點之外的店的子樹異或和是不會改變的。用維護每種葉子節點的數量，修改時維護答案即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=1e4+5,mod=998244353;
int m,kk,ans[maxn],a[maxn],b[maxn];
int main(){
freopen("xortree.in","r",stdin);
freopen("xortree.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>kk>>m;
ans[kk]=1,a[kk]=1;
while(m--){
int opt,x;
cin>>opt>>x;
if(opt==1){
for(int i=0;i<1<<13;i++){
b[i]=0;
}
for(int i=0;i<1<<13;i++){
(ans[i]+=mod-a[i])%=mod;
(ans[i^x]+=a[i])%=mod;
(b[i]+=a[i])%=mod;
(b[i^x]+=a[i])%=mod;
}
for(int i=0;i<1<<13;i++){
a[i]=b[i];
(ans[i]+=a[i])%=mod;
}
}else{
cout<<ans[x]<<'\n';
}
}
return 0;
}
}
int main(){return asbt::main();}
C. 符文石 (stone)
我們需要點 \(u\) 能走到的所有權值，考慮在拓撲過程中用 set 直接維護。但顯然這樣時間復雜度爆炸，考慮哪些數是沒用的。由于 \(a\operatorname{bitand}b\le\min(a,b)\)，所以 \(u\) 的 set 中 \(\le ans_u\) 的數直接扔掉?？紤]大于 \(ans_u\) 的數，考慮它們于 \(ans_u\) 不同的最高位，顯然 \(ans_u\) 這一位為 \(0\) 而這個數這一位為 \(1\)。而如果還有另一個數這一位也為 \(1\)，那么 \(ans_u\) 就不是最大的按位與值了。所以大于 \(ans_u\) 的數最多有 \(O(\log V)\) 個。暴力合并即可。時間復雜度 \(O(m\log^2V)\)。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
const int maxn=5e5+5;
int n,m,a[maxn],d[maxn],ans[maxn];
vector<int> e[maxn];
queue<int> q;
struct opt{
il bool operator()(const int &x,const int &y)const{
return a[x]<a[y];
}
};
set<int,opt> st[maxn];
int main(){
freopen("stone.in","r",stdin);
freopen("stone.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
st[i].insert(i);
}
for(int i=1,u,v;i<=m;i++){
cin>>u>>v;
d[u]++,e[v].pb(u);
}
for(int i=1;i<=n;i++){
ans[i]=-1;
if(d[i]==0){
q.push(i);
}
}
while(q.size()){
int u=q.front();
q.pop();
// cout<<u<<' '<<ans[u]<<'\n';
for(int v:e[u]){
if(--d[v]==0){
q.push(v);
}
ans[v]=max(ans[v],ans[u]);
for(int x:st[u]){
for(int y:st[v]){
if(x==y){
continue;
}
ans[v]=max(ans[v],a[x]&a[y]);
}
}
for(int x:st[u]){
if(a[x]>=ans[v]){
st[v].insert(x);
}
}
if(a[*st[v].rbegin()]<=ans[v]){
st[v].clear();
continue;
}
for(auto it=st[v].begin();it!=st[v].end();it++){
if(a[*it]>ans[v]){
st[v].erase(st[v].begin(),it);
break;
}
}
}
}
for(int i=1;i<=n;i++){
cout<<ans[i]<<' ';
}
return 0;
}
}
signed main(){return asbt::main();}
D. 彩色括號 (witch)
2025CSP-S模擬賽66（HZOJ CSP-S模擬37）
| A | B | C | D | Sum | Rank |
|---|---|---|---|---|---|
| 20 | 0 | 70 | 20 | 110 | 5/8(23/33) |
A. 回文
構成回文串的必然是 \(a\) 和 \(b\) 上分別兩段連續的區間。設 \(f_{i,j,l,r}\) 表示 \(a(i\dots j)\) 和 \(b(l\dots r)\) 能否構成回文串。轉移考慮 \(a\) 和 \(b\) 分別提供左/右端點即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
int T,n,m;
bool f[55][55][55][55];
string a,b;
int main(){
freopen("string.in","r",stdin);
freopen("string.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>T;
while(T--){
cin>>a>>b;
n=a.size(),m=b.size();
a=" "+a,b=" "+b;
memset(f,0,sizeof(f));
for(int i=1;i<=n+1;i++){
for(int j=1;j<=m+1;j++){
f[i][i][j][j-1]=f[i][i-1][j][j]=f[i][i-1][j][j-1]=1;
}
}
for(int la=0;la<=n;la++){
for(int i=1,j=la;j<=n;i++,j++){
for(int lb=0;lb<=m;lb++){
for(int l=1,r=lb;r<=m;l++,r++){
if(la&&lb){
f[i][j][l][r]|=f[i+1][j][l][r-1]&&a[i]==b[r];
f[i][j][l][r]|=f[i][j-1][l+1][r]&&a[j]==b[l];
}
if(la>=2){
f[i][j][l][r]|=f[i+1][j-1][l][r]&&a[i]==a[j];
}
if(lb>=2){
f[i][j][l][r]|=f[i][j][l+1][r-1]&&b[l]==b[r];
}
}
}
}
}
// cout<<f[2][1][2][1]<<' '<<f[2][1][1][2]<<' '<<f[1][2][2][1]<<' '<<f[1][2][1][2]<<'\n';
int ans=0;
for(int i=1;i<=n;i++){
for(int j=i-1;j<=n;j++){
for(int l=1;l<=m;l++){
for(int r=l-1;r<=m;r++){
if(f[i][j][l][r]){
ans=max(ans,j-i+1+r-l+1);
}
}
}
}
}
cout<<ans<<'\n';
}
return 0;
}
}
int main(){return asbt::main();}
B. 數排列
其實是簡單 DP。設 \(f_{i,j}\) 表示 \(i\) 在 \(1\) 到 \(i\) 中排第 \(j\) 個，前綴和優化即可。
還可以考慮求逆置換，就和 AT_dp_t 一樣了。實際上二者的轉移方程就是完全一樣的。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=2e3+5,mod=1e9+7;
il int pls(int x,int y){
return x+y<mod?x+y:x+y-mod;
}
il void add(int &x,int y){
x=pls(x,y);
}
il int mns(int x,int y){
return x<y?x-y+mod:x-y;
}
il void sub(int &x,int y){
x=mns(x,y);
}
int n,f[maxn][maxn],g[maxn][maxn],s[maxn];
int main(){
freopen("perm.in","r",stdin);
freopen("perm.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1;i<n;i++){
cin>>s[i];
}
f[1][1]=g[1][1]=1;
for(int i=2;i<=n;i++){
for(int j=1;j<=i;j++){
if(s[i-1]==1){
f[i][j]=g[i-1][j-1];
}else{
f[i][j]=mns(g[i-1][i-1],g[i-1][j-1]);
}
g[i][j]=pls(g[i][j-1],f[i][j]);
}
}
cout<<g[n][n];
return 0;
}
}
int main(){return asbt::main();}
C. 樹上的背包
首先有 \(O(n^2)\) 做法：預處理出每個點的背包數組，\(O(1)\) 回答。時間極不平衡，考慮根號分治。預處理 \(1\) 到 \(\sqrt{n}\) 的背包，詢問時將下面的 \(\frac{\log n}{2}\) 個點是否選擇暴力枚舉出來即可。時間復雜度 \(O((L+Q)\sqrt{n})\)。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define lowbit(x) (x&-x)
using namespace std;
namespace asbt{
const int maxn=1e5+5,B=1<<8;
int n,m,f[B+5][maxn],a[maxn],b[maxn],sa[maxn],sb[maxn],Log[maxn];
il void dfs(int u,int fa){
if(u>B){
return ;
}
memcpy(f[u],f[fa],100001<<3);
for(int i=100000;i>=b[u];i--){
f[u][i]=max(f[u][i],f[u][i-b[u]]+a[u]);
}
dfs(u<<1,u),dfs(u<<1|1,u);
}
int main(){
freopen("knapsack.in","r",stdin);
freopen("knapsack.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
}
dfs(1,0);
for(int i=2;i<=n;i++){
Log[i]=Log[i>>1]+1;
}
cin>>m;
while(m--){
int u,x;
cin>>u>>x;
int p[10],cnt=0,ans=0;
while(u>B){
p[++cnt]=u,u>>=1;
}
// cout<<u<<'\n';
for(int S=0;S<1<<cnt;S++){
if(S){
int x=lowbit(S);
// cout<<p[Log[x]+1]<<'\n';
sa[S]=sa[S^x]+a[p[Log[x]+1]];
sb[S]=sb[S^x]+b[p[Log[x]+1]];
}
if(sb[S]<=x){
ans=max(ans,f[u][x-sb[S]]+sa[S]);
}
}
cout<<ans<<'\n';
}
return 0;
}
}
signed main(){return asbt::main();}
D. 開會
2025CSP-S模擬賽67（HZOJ CSP-S模擬39）
| A | B | C | D | Sum | Rank |
|---|---|---|---|---|---|
| 100 | 40 | 36 | 100(0) | 280(176) | 8/22(21/32) |
HZOJ 啥時候把 T4 文件名改了？暈??
校內 OJT2 評測咋這么慢？暈暈????破案了原來我 T2 寫假了????
A. 最小生成樹（tree）
考慮 kruskal 的過程，將每條邊按邊權排序，每次將區間 \([l,r]\) 內還沒合并的合并起來即可。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=1e5+5;
int n,m,fa[maxn];
struct edge{
int l,r,w;
il bool operator<(const edge &x)const{
return w<x.w;
}
}e[maxn];
il int find(int x){
return x!=fa[x]?fa[x]=find(fa[x]):x;
}
int main(){
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
fa[i]=i;
}
for(int i=1;i<=m;i++){
cin>>e[i].l>>e[i].r>>e[i].w;
}
sort(e+1,e+m+1);
int ans=0;
for(int i=1;i<=m;i++){
for(int j=find(e[i].l);j<e[i].r;j=find(j)){
ans+=e[i].w,fa[j]=find(j+1);
}
}
cout<<(find(1)!=n?-1:ans);
return 0;
}
}
signed main(){return asbt::main();}
B. 最短路（roads）
考場做法
每個點的最短路對后面的松弛操作不一定最優，需要考慮從哪一條邊過來。所以對邊設點跑 dijkstra 即可。
但實際上這樣做是錯的，因為如果一個點有大量的入邊和出邊，邊和邊之間的新邊會達到 \(O(m^2)\) 級別，時間就炸了。
正解
由于與從哪一條邊過來有關，所以我們在 dijkstra 過程中同時記錄距離 \(dis\) 和最后一條邊 \(a\)。對于兩條入邊 \(a_x\) 和 \(a_y\)，如果 \(a_x<a_y\)，則對于 \(\ge a_y\) 的出邊，二者得到的邊權是相同的。于是對于同一個點，如果是第一次從堆頂彈出就將所有出邊都松弛，否則假設上一次的入邊是 \(a_p\)，這一次入邊是 \(a_q\)，將 \(a_q<a\le a_p\) 的出邊全都松弛即可。每條邊最多被松弛兩次，時間復雜度線性對數。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define pb push_back
#define pii pair<int,int>
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace asbt{
const int maxn=1e5+5,inf=1e18;
int n,m,enm,hd[maxn],ans[maxn],a[maxn];
vector<pair<int,pii>> e[maxn];
priority_queue<pair<int,pii>> q;
int main(){
freopen("roads.in","r",stdin);
freopen("roads.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1,u,v,a,b;i<=m;i++){
cin>>u>>v>>a>>b;
e[u].pb(mp(v,mp(a,b)));
}
for(int i=1;i<=n;i++){
sort(e[i].begin(),e[i].end(),[](auto x,auto y){return x.sec.fir>y.sec.fir;});
}
memset(ans,0x3f,sizeof(ans));
memset(a,-1,sizeof(a));
q.push(mp(0,mp(1,inf)));
while(q.size()){
int dis=-q.top().fir,u=q.top().sec.fir,x=q.top().sec.sec;
q.pop();
ans[u]=min(ans[u],dis);
// cout<<u<<' '<<x<<'\n';
if(a[u]==-1){
for(auto i:e[u]){
int v=i.fir,a=i.sec.fir,b=i.sec.sec;
int w=x<a?a-b:a;
int tmp=dis+w;
q.push(mp(-tmp,mp(v,a)));
}
a[u]=0;
}else{
for(int &i=a[u];i<e[u].size()&&e[u][i].sec.fir>x;i++){
int v=e[u][i].fir,a=e[u][i].sec.fir,b=e[u][i].sec.sec;
int w=x<a?a-b:a;
int tmp=dis+w;
q.push(mp(-tmp,mp(v,a)));
}
}
}
for(int i=1;i<=n;i++){
cout<<(ans[i]>=inf?-1:ans[i])<<' ';
}
return 0;
}
}
signed main(){return asbt::main();}
C. 計算任務（mission）
我們將每個任務的 \(y\) 拆成 \(k\) 個 \(\lceil\frac{y}{k}\rceil\)，如果 \(k\) 臺計算機都沒有計算到 \(\lceil\frac{y}{k}\rceil\)，那么這個任務必然沒有完成。用數據結構維護每臺計算機當前需要完成的任務和每個任務分到的時間。
如果對于計算機 \(x\)，有一個任務在此計算機上的運行時間超過了 \(\lceil\frac{y}{k}\rceil\)，那么我們將 \(k\) 臺計算機上這個任務的運行時間都取出來。如果運行時間夠了那么直接輸出，否則將剩余需要的時間再拆成 \(k\) 份插進去。
數據結構需要支持插入、刪除、取出最小值，使用 set 即可。
考慮時間復雜度，每個任務取出時 \(y\) 至少減少三分之一，于是總時間為 \(O(m\log_{\frac{3}{2}}V\log m)\)。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define pii pair<int,int>
#define mp make_pair
#define fir first
#define sec second
using namespace std;
namespace asbt{
const int maxn=2e5+5;
int n,m,cnt,a[maxn],b[maxn][5],c[maxn][5],d[maxn],tag[maxn],p[maxn],q[maxn];
set<pii> st[maxn];
int main(){
freopen("mission.in","r",stdin);
freopen("mission.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
int ans=0;
while(m--){
int opt;
cin>>opt;
if(opt==1){
int y,k;
cin>>y>>k;
y^=ans;
a[++cnt]=k,d[cnt]=y;
y=(y+k-1)/k;
for(int i=1,x;i<=k;i++){
cin>>x;
x^=ans;
b[cnt][i]=x,c[cnt][i]=y+tag[x];
st[x].insert(mp(c[cnt][i],cnt));
}
}else{
int x,y;
cin>>x>>y;
x^=ans,y^=ans;
ans=0;
tag[x]+=y;
int tot=0;
for(auto i=st[x].begin();i!=st[x].end()&&i->fir<=tag[x];i++){
p[++tot]=i->sec;
}
for(int i=1;i<=tot;i++){
int sum=0,zong=d[p[i]];
for(int j=1;j<=a[p[i]];j++){
sum+=tag[b[p[i]][j]];
zong+=c[p[i]][j]-(d[p[i]]+a[p[i]]-1)/a[p[i]];
st[b[p[i]][j]].erase(mp(c[p[i]][j],p[i]));
}
// cout<<p[i]<<' '<<sum<<' '<<zong<<'\n';
if(sum<zong){
int y=zong-sum;
d[p[i]]=y;
y=(y+a[p[i]]-1)/a[p[i]];
for(int j=1;j<=a[p[i]];j++){
c[p[i]][j]=y+tag[b[p[i]][j]];
st[b[p[i]][j]].insert(mp(c[p[i]][j],p[i]));
}
}else{
q[++ans]=p[i];
}
}
sort(q+1,q+ans+1);
cout<<ans<<' ';
for(int i=1;i<=ans;i++){
cout<<q[i]<<' ';
}
cout<<'\n';
}
}
return 0;
}
}
signed main(){return asbt::main();}
D. 樹上純樹（tree）
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
const int maxn=1e5+5,inf=1e18;
int n,a[maxn],b[maxn],tot,rt[maxn],ls[maxn],rs[maxn],f[maxn];
vector<int> e[maxn];
struct line{
int k,b;
il int calc(int x){
return k*x+b;
}
}tr[maxn];
il void insert(int &id,int l,int r,int x){
if(!id){
id=x;
ls[id]=rs[id]=0;
return ;
}
int mid=(l+r)>>1;
if(tr[id].calc(mid)>tr[x].calc(mid)){
swap(tr[id],tr[x]);
}
int lo=tr[id].calc(l),ro=tr[id].calc(r);
int ln=tr[x].calc(l),rn=tr[x].calc(r);
if(lo>ln){
insert(ls[id],l,mid,x);
}else if(ro>rn){
insert(rs[id],mid+1,r,x);
}
}
il int merge(int p,int q,int l,int r){
if(!p||!q){
return p|q;
}
int mid=(l+r)>>1;
ls[p]=merge(ls[p],ls[q],l,mid);
rs[p]=merge(rs[p],rs[q],mid+1,r);
insert(p,l,r,q);
return p;
}
il int query(int id,int l,int r,int x){
if(!id){
return inf;
}
int mid=(l+r)>>1;
if(x<=mid){
return min(tr[id].calc(x),query(ls[id],l,mid,x));
}else{
return min(tr[id].calc(x),query(rs[id],mid+1,r,x));
}
}
il void dfs(int u,int fa){
for(int v:e[u]){
if(v==fa){
continue;
}
dfs(v,u);
rt[u]=merge(rt[u],rt[v],-1e5,1e5);
}
if(rt[u]){
f[u]=query(rt[u],-1e5,1e5,a[u]);
}
tr[++tot]={b[u],f[u]};
insert(rt[u],-1e5,1e5,tot);
}
int main(){
// system("fc 3.out my.out");
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
cin>>b[i];
}
for(int i=1,u,v;i<n;i++){
cin>>u>>v;
e[u].pb(v),e[v].pb(u);
}
dfs(1,0);
for(int i=1;i<=n;i++){
cout<<f[i]<<' ';
}
return 0;
}
}
signed main(){return asbt::main();}
HZOJ CSP-S模擬40
| A | B | C | D | Sum | Rank |
|---|---|---|---|---|---|
| 80 | 20 | - | 0 | 100 | 5/35 |
A. 公約數神廟
考慮 \(a_y\) 的所有質因子 \(p_k\)，記 \(f_{i,j}\) 表示 \(i\) 能走到的最近的含有質因子 \(j\) 的位置，則如果 \(\exist p_k,f_{x,p_k}\le y\) 則答案為 Shi。而 \(f_{i,j}\) 的遞推也是簡單的，因為最多只有 \(4\) 個質因子，所以倒著計算，維護 \(b_k\) 表示當前最小的含有 \(k\) 的位置即可。然后進行一些特判就好了。時間復雜度 \(O(\frac{V}{\ln V}(n+m))\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
const int maxn=1e5+5;
int n,m,a[maxn],f[maxn][205],b[205],c[maxn];
vector<int> prm;
il bool isp(int x){
for(int i=2;i<=x/i;i++){
if(x%i==0){
return 0;
}
}
return 1;
}
int main(){
freopen("gcd.in","r",stdin);
freopen("gcd.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
c[i]=c[i-1]+(a[i]>1);
}
for(int i=2;i<=1e3;i++){
if(isp(i)){
prm.pb(i);
}
}
memset(f,0x3f,sizeof(f));
for(int i=0;i<prm.size();i++){
b[i]=n+1;
}
for(int i=n;i;i--){
if(!a[i]){
for(int j=0;j<prm.size();j++){
b[j]=f[i][j]=i;
}
continue;
}
for(int j=0;j<prm.size();j++){
if(a[i]%prm[j]==0){
for(int k=0;k<prm.size();k++){
f[i][k]=min(f[i][k],f[b[j]][k]);
}
b[j]=f[i][j]=i;
}
}
}
while(m--){
int l,r;
cin>>l>>r;
if(l==r){
cout<<"Shi\n";
}else if(a[l]==1||a[r]==1){
cout<<"Fou\n";
}else if(!a[l]||!a[r]){
cout<<(c[r]-c[l-1]?"Shi":"Fou")<<'\n';
}else{
for(int j=0;j<prm.size();j++){
if(a[r]%prm[j]==0&&f[l][j]<=r){
cout<<"Shi\n";
goto togo;
}
}
cout<<"Fou\n";
togo:;
}
}
return 0;
}
}
int main(){return asbt::main();}
B. 棧法師
掛 80pts，賽后調 2h。死因：頑固不化地認為 \(a_i\le n\)。
首先經過手玩可以發現，\(k\) 最多為 \(2\)。那么我們首先考慮 \(k=2\) 是否確有解。構造很簡單：先把所有的數全都壓到一棧內，然后對于當前的最小值，找到在棧內最靠上的位置，將其上的全都壓入二棧，然后 pop，直到當前最小值 pop 完了，再把一棧里剩下的全都壓到二棧里，再在二棧里找下一個最小值。每次需要往二棧里壓多少用樹狀數組維護一下即可。
考慮判斷 \(k\) 能否等于 \(1\)，我們只要用一個棧模擬一下即可，如果能跑出來那就 \(k=1\)，否則 \(k=2\)。
模擬的過程：首先找到當前的最小值 \(x\)，如果棧內沒有 \(x\) 那就把下一個數壓棧，否則就在棧頂等于 \(x\) 時不停的 pop，直到棧頂不等于 \(x\)，此時如果棧內還有 \(x\) 那么就做不下去了，返回 \(k=2\)，否則就再去找下一個最小值。
再次強調：a 的上限為 1e5！！！
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
const int maxn=1e5+5;
int T,n,a[maxn],ins[maxn],tong[maxn];
int s1[maxn];
vector<int> pos[maxn];
il bool check(){
for(int i=1;i<=n;i++){
tong[a[i]]++;
}
int t1=0,x=0,y=n;
while(1){
while(1){
while(x<=1e5&&!tong[x]){
x++;
}
if(!ins[x]){
break;
}
while(t1&&s1[t1]==x){
t1--,ins[x]--,tong[x]--;
}
if(ins[x]){
return 0;
}
}
if(y){
s1[++t1]=a[y],ins[a[y--]]++;
}else{
break;
}
}
return 1;
}
il void print1(){
cout<<1<<'\n'<<2*n<<'\n';
for(int i=1;i<=n;i++){
tong[a[i]]++;
}
int t1=0,x=0,y=n;
while(1){
while(1){
while(x<=1e5&&!tong[x]){
x++;
}
if(!ins[x]){
break;
}
while(t1&&s1[t1]==x){
t1--,ins[x]--,tong[x]--;
cout<<2<<' '<<1<<'\n';
}
}
if(y){
cout<<1<<' '<<1<<' '<<1<<'\n';
s1[++t1]=a[y],ins[a[y--]]++;
}else{
break;
}
}
}
struct{
int opt,i,j,c;
}ans[maxn*5];
struct{
#define lowbit(x) (x&-x)
int tr[maxn];
il void add(int p,int v){
for(;p<=1e5;p+=lowbit(p)){
tr[p]+=v;
}
}
il int query(int p){
int r=0;
for(;p;p-=lowbit(p)){
r+=tr[p];
}
return r;
}
#undef lowbit
}F;
il void print2(){
set<int> S;
for(int i=1;i<=n;i++){
S.insert(a[i]);
pos[a[i]].pb(i);
F.add(i,1);
}
int cnt=0,p=1;
ans[++cnt]={1,1,0,n};
for(int x:S){
if(p==1){
for(int i=0;i<pos[x].size();i++){
int num=0;
if(!i){
num=F.query(pos[x][i]-1);
}else{
num=F.query(pos[x][i]-1)-F.query(pos[x][i-1]);
}
if(num){
ans[++cnt]={3,1,2,num};
}
ans[++cnt]={2,1,0,0};
F.add(pos[x][i],-1);
}
int num=F.query(1e5)-F.query(pos[x].back());
if(num){
ans[++cnt]={3,1,2,num};
}
}else{
for(int i=pos[x].size()-1;~i;i--){
int num=0;
if(i==pos[x].size()-1){
num=F.query(1e5)-F.query(pos[x][i]);
}else{
num=F.query(pos[x][i+1])-F.query(pos[x][i]);
}
if(num){
ans[++cnt]={3,2,1,num};
}
ans[++cnt]={2,2,0,0};
F.add(pos[x][i],-1);
}
int num=F.query(pos[x][0]);
if(num){
ans[++cnt]={3,2,1,num};
}
}
p=3-p;
}
cout<<2<<'\n'<<cnt<<'\n';
for(int i=1;i<=cnt;i++){
switch(ans[i].opt){
case 1:{
cout<<ans[i].opt<<' '<<ans[i].i<<' '<<ans[i].c<<'\n';
break;
}
case 2:{
cout<<ans[i].opt<<' '<<ans[i].i<<'\n';
break;
}
default:{
cout<<ans[i].opt<<' '<<ans[i].i<<' '<<ans[i].j<<' '<<ans[i].c<<'\n';
break;
}
}
}
for(int i=1;i<=n;i++){
pos[a[i]].clear();
}
}
int main(){
freopen("sort.in","r",stdin);
freopen("sort.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>T;
while(T--){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
if(check()){
print1();
}else{
print2();
}
for(int i=1;i<=n;i++){
tong[a[i]]=ins[a[i]]=0;
}
}
return 0;
}
}
int main(){return asbt::main();}
C. 城堡考古
板+屎。
顯然的狀壓 DP，矩陣快速冪優化。狀態數是 \(O(2^m)\) 的，難以通過。打表發現有用的狀態頂多有 \(20\) 個，于是把它們的轉移矩陣打出來即可。然后 \(L,R\) 很大，需要高精。
打表 Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
int m,cnt,vis[79],bas[79][79];
FILE *out;
il void dfs2(int,int,int);
il void dfs1(int S){
if(vis[S]){
return ;
}
vis[S]=++cnt;
dfs2(S,1,0);
}
il void dfs2(int S,int x,int T){
if(x>m){
dfs1(T);
bas[vis[S]][vis[T]]=1;
cout<<" bas["<<vis[S]<<"]["<<vis[T]<<"]=1;\n";
fprintf(out,"%d %d\n",S,T);
return ;
}
if(S>>(x-1)&1){
dfs2(S,x+1,T);
}else if(x==m||(S>>x&1)){
dfs2(S,x+1,T|1<<(x-1));
}else{
dfs2(S,x+1,T|1<<(x-1));
dfs2(S,x+2,T);
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
out=fopen("C.txt","w");
for(m=1;m<=6;m++){
cout<<"if(m=="<<m<<"){\n";
fprintf(out,"%d\n",m);
memset(vis,0,sizeof(vis));
memset(bas,0,sizeof(bas));
cnt=0,dfs1(0);
for(int i=1;i<=cnt;i++){
if(bas[i][1]){
cout<<" bas["<<i<<"]["<<cnt+1<<"]=1;\n";
}
}
cout<<" bas["<<cnt+1<<"]["<<cnt+1<<"]=1;\n";
cout<<" n="<<cnt+1<<";\n}\n";
}
return 0;
}
}
int main(){return asbt::main();}
AC Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=1e4+5,mod=998244353;
int m,n,a[maxn],b[maxn],c[maxn];
string L,R;
struct juz{
int a[23][23];
juz(){
memset(a,0,sizeof(a));
}
il int*operator[](int x){
return a[x];
}
il juz operator*(juz b)const{
juz c;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int k=1;k<=n;k++){
c[i][j]=(c[i][j]+a[i][k]*1ll*b[k][j])%mod;
}
}
}
return c;
}
}bas;
il int solve(string s,bool flag){
int la=s.size();
for(int i=1;i<=la;i++){
a[i]=s[la-i]^48;
}
if(flag){
a[1]--;
for(int i=1;i<=la;i++){
if(a[i]<0){
a[i]+=10,a[i+1]--;
}
}
while(la&&!a[la]){
la--;
}
}
// cout<<flag<<' '<<la<<'\n';
// for(int i=1;i<=la;i++){
// cout<<a[i]<<' ';
// }
// cout<<'\n';
int lb=0;
while(la){
b[++lb]=a[1]&1;
int lc=la;
for(int i=la;i;i--){
c[i]=a[i]>>1;
a[i-1]+=(a[i]&1)*10;
}
while(lc&&!c[lc]){
lc--;
}
la=lc;
for(int i=1;i<=la;i++){
a[i]=c[i];
}
}
juz x=bas,res;
for(int i=1;i<=n;i++){
res[i][i]=1;
}
for(int i=1;i<=lb;i++){
if(b[i]){
res=res*x;
}
x=x*x;
}
juz dp;
dp[1][1]=dp[1][n]=1;
return (dp*res)[1][n];
}
int main(){
freopen("decoration.in","r",stdin);
freopen("decoration.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>L>>R>>m;
if(m==1){
bas[2][1]=1;
bas[1][2]=1;
bas[2][3]=1;
bas[3][3]=1;
n=3;
}
if(m==2){
bas[2][1]=1;
bas[1][2]=1;
bas[1][1]=1;
bas[1][3]=1;
bas[2][3]=1;
bas[3][3]=1;
n=3;
}
if(m==3){
bas[2][1]=1;
bas[1][2]=1;
bas[4][3]=1;
bas[3][4]=1;
bas[3][1]=1;
bas[1][3]=1;
bas[6][5]=1;
bas[5][6]=1;
bas[5][1]=1;
bas[1][5]=1;
bas[2][7]=1;
bas[3][7]=1;
bas[5][7]=1;
bas[7][7]=1;
n=7;
}
if(m==4){
bas[2][1]=1;
bas[1][2]=1;
bas[4][3]=1;
bas[4][1]=1;
bas[3][4]=1;
bas[3][1]=1;
bas[1][3]=1;
bas[6][5]=1;
bas[5][6]=1;
bas[5][1]=1;
bas[1][5]=1;
bas[1][4]=1;
bas[1][1]=1;
bas[1][7]=1;
bas[2][7]=1;
bas[3][7]=1;
bas[4][7]=1;
bas[5][7]=1;
bas[7][7]=1;
n=7;
}
if(m==5){
bas[2][1]=1;
bas[1][2]=1;
bas[4][3]=1;
bas[6][5]=1;
bas[5][6]=1;
bas[8][7]=1;
bas[8][1]=1;
bas[7][8]=1;
bas[7][5]=1;
bas[5][7]=1;
bas[10][9]=1;
bas[9][10]=1;
bas[9][5]=1;
bas[5][9]=1;
bas[5][4]=1;
bas[5][1]=1;
bas[4][5]=1;
bas[12][11]=1;
bas[11][12]=1;
bas[14][13]=1;
bas[14][1]=1;
bas[13][14]=1;
bas[13][11]=1;
bas[16][15]=1;
bas[15][16]=1;
bas[15][13]=1;
bas[18][17]=1;
bas[17][18]=1;
bas[17][15]=1;
bas[15][17]=1;
bas[20][19]=1;
bas[20][1]=1;
bas[19][20]=1;
bas[19][15]=1;
bas[15][19]=1;
bas[15][1]=1;
bas[13][15]=1;
bas[11][13]=1;
bas[11][4]=1;
bas[11][1]=1;
bas[4][11]=1;
bas[3][4]=1;
bas[3][1]=1;
bas[1][3]=1;
bas[1][20]=1;
bas[1][8]=1;
bas[1][5]=1;
bas[1][14]=1;
bas[1][11]=1;
bas[1][15]=1;
bas[2][21]=1;
bas[3][21]=1;
bas[5][21]=1;
bas[8][21]=1;
bas[11][21]=1;
bas[14][21]=1;
bas[15][21]=1;
bas[20][21]=1;
bas[21][21]=1;
n=21;
}
if(m==6){
bas[2][1]=1;
bas[1][2]=1;
bas[4][3]=1;
bas[6][5]=1;
bas[6][1]=1;
bas[5][6]=1;
bas[8][7]=1;
bas[8][1]=1;
bas[7][8]=1;
bas[7][5]=1;
bas[7][4]=1;
bas[7][1]=1;
bas[5][7]=1;
bas[10][9]=1;
bas[9][10]=1;
bas[9][5]=1;
bas[12][11]=1;
bas[12][1]=1;
bas[11][12]=1;
bas[14][13]=1;
bas[13][14]=1;
bas[16][15]=1;
bas[16][1]=1;
bas[15][16]=1;
bas[18][17]=1;
bas[17][18]=1;
bas[17][15]=1;
bas[17][4]=1;
bas[17][1]=1;
bas[15][17]=1;
bas[15][13]=1;
bas[13][15]=1;
bas[20][19]=1;
bas[19][20]=1;
bas[19][13]=1;
bas[13][19]=1;
bas[13][11]=1;
bas[13][1]=1;
bas[11][13]=1;
bas[11][9]=1;
bas[9][11]=1;
bas[9][1]=1;
bas[5][9]=1;
bas[5][4]=1;
bas[5][1]=1;
bas[4][5]=1;
bas[4][17]=1;
bas[4][7]=1;
bas[4][1]=1;
bas[3][4]=1;
bas[3][1]=1;
bas[1][3]=1;
bas[1][12]=1;
bas[1][8]=1;
bas[1][5]=1;
bas[1][16]=1;
bas[1][17]=1;
bas[1][13]=1;
bas[1][6]=1;
bas[1][7]=1;
bas[1][9]=1;
bas[1][4]=1;
bas[1][1]=1;
bas[1][21]=1;
bas[2][21]=1;
bas[3][21]=1;
bas[4][21]=1;
bas[5][21]=1;
bas[6][21]=1;
bas[7][21]=1;
bas[8][21]=1;
bas[9][21]=1;
bas[12][21]=1;
bas[13][21]=1;
bas[16][21]=1;
bas[17][21]=1;
bas[21][21]=1;
n=21;
}
cout<<(solve(R,0)-solve(L,1)+mod)%mod;
return 0;
}
}
int main(){return asbt::main();}
D. 生命之樹
記離 \(u\) 最近的染色點為 \(u\) 的配對點，有一個重要的觀察：對于 \(u\) 的子樹，最多只有一個配對點在 \(u\) 的子樹外。因為如果有多個，則必然可以選擇離 \(u\) 最近的那一個。于是有 DP：設 \(f_{u,i}\) 表示 \(u\) 的配對點是 \(i\)，\(u\) 子樹內的最小花費，\(g_u=\min f_{u,i}\)?？紤]每個兒子 \(v\) 的配對點，則有轉移：
\[f_{u,i}=c_i+\sum_v\min\{g_v,f_{v,i}-c_i\}
\]
時間復雜度 \(O(n^2)\)。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define fir first
#define sec second
using namespace std;
namespace asbt{
const int maxn=1e3+5,inf=1e18;
int T,n,a[maxn],b[maxn],dis[maxn][maxn];
int f[maxn][maxn],g[maxn];
vector<pii> e[maxn];
il void dfs1(int u,int fa,int *dis){
for(pii i:e[u]){
int v=i.fir,w=i.sec;
if(v==fa){
continue;
}
dis[v]=dis[u]+w;
dfs1(v,u,dis);
}
}
il void dfs2(int u,int fa){
for(int i=1;i<=n;i++){
if(dis[u][i]<=b[u]){
f[u][i]=a[i];
}else{
f[u][i]=inf;
}
}
for(pii i:e[u]){
int v=i.fir;
if(v==fa){
continue;
}
dfs2(v,u);
for(int j=1;j<=n;j++){
if(dis[u][j]<=b[u]){
f[u][j]+=min(f[v][j]-a[j],g[v]);
}
}
}
g[u]=inf;
for(int i=1;i<=n;i++){
g[u]=min(g[u],f[u][i]);
}
}
int main(){
freopen("dagger.in","r",stdin);
freopen("dagger.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>T;
while(T--){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
cin>>b[i];
}
for(int i=1,u,v,w;i<n;i++){
cin>>u>>v>>w;
e[u].pb(mp(v,w));
e[v].pb(mp(u,w));
}
for(int i=1;i<=n;i++){
dis[i][i]=0;
dfs1(i,0,dis[i]);
}
dfs2(1,0);
cout<<g[1]<<'\n';
for(int i=1;i<=n;i++){
e[i].clear();
}
}
return 0;
}
}
signed main(){return asbt::main();}
2025CSP-S模擬賽69（HZOJ CSP-S模擬41）
| A | B | C | D | Sum | Rank |
|---|---|---|---|---|---|
| 60 | 20 | 60 | 10 | 150 | 6/12(21/33) |
A. 數軸取物(axis)
顯然有 \(O(n^2m)\) 的DP：設 \(f_{i,j}\) 表示用了前 \(i\) 個包，走到了第 \(j\) 個物品的最大價值。預處理一下每個區間的背包數組即可。
由于背包容量遞增，而最壞情況每個背包裝一個物品，因此只考慮后 \(n\) 個背包即可，時間復雜度 \(O(n^3)\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=1e5+5;
int n,m,a[205],b[205],c[maxn],dp[205][205][205],f[maxn][205];
int main(){
freopen("axis.in","r",stdin);
freopen("axis.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
}
for(int i=1;i<=m;i++){
cin>>c[i];
}
for(int l=1;l<=n;l++){
for(int r=l;r<=n;r++){
for(int i=0;i<=200;i++){
dp[l][r][i]=dp[l][r-1][i];
}
for(int i=200;i>=a[r];i--){
dp[l][r][i]=max(dp[l][r][i],dp[l][r][i-a[r]]+b[r]);
}
}
}
// for(int l=1;l<=n;l++){
// for(int r=l;r<=n;r++){
// for(int i=0;i<=10;i++){
// cout<<dp[l][r][i]<<' ';
// }
// cout<<'\n';
// }
// cout<<'\n';
// }
for(int i=max(m-n,0)+1;i<=m;i++){
for(int j=0;j<=n;j++){
for(int k=0;k<=j;k++){
f[i][j]=max(f[i][j],f[i-1][k]+dp[k+1][j][c[i]]);
}
}
}
cout<<f[m][n];
return 0;
}
}
int main(){return asbt::main();}
B. 排列變環(circle)
首先如果 \(k\le0\)，考慮 \(\max\{w_i\}\) 若 \(<k\)，那么無解，否則全都成自環即可，答案為 \(0\)。
然后只考慮 \(k>0\) 的情況即可。顯然是一個大環和若干自環的形式。
先考慮如果 \(w\) 全為正，那么我們顯然要選擇的是連續的一段區間 \([l,r]\)，并且排成 \(\{l+1,l+2,\dots,r-1,r,l\}\) 的順序，逆序對數為 \(r-l\)，如果再交換則逆序對數必然增加。
那么如果 \(w\) 中有負數，對于區間 \([l,r]\) 我們可能會舍去其中的一些負數。發現被舍去的點貢獻為 \(2\) 而環上的點貢獻為 \(1\)，于是我們考慮固定右端點 \(r\)，用兩個優先隊列維護被舍棄的負數和在環上的負數，\(l\) 左移時嘗試刪去一個較小的負數，再加上若干個較大的負數即可。時間復雜度 \(O(n^2\log n)\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=1e3+5,inf=1e9;
int n,m,a[maxn];
int main(){
freopen("circle.in","r",stdin);
freopen("circle.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
if(m<=0){
for(int i=1;i<=n;i++){
if(a[i]>=m){
cout<<0;
return 0;
}
}
cout<<-1;
return 0;
}
int ans=inf;
for(int r=1;r<=n;r++){
int l=r+1,sum=0;
while(l>1&&sum<m){
l--;
if(a[l]>0){
sum+=a[l];
}
}
if(sum<m){
continue;
}
// cout<<r<<' '<<l<<'\n';
priority_queue<int,vector<int>,greater<int>> q1;
priority_queue<int> q2;
for(int i=l;i<=r;i++){
if(a[i]<=0){
q1.push(a[i]),sum+=a[i];
}
}
while(l>=1){
// cout<<l<<'\n';
while(sum<m){
q2.push(q1.top()),sum-=q1.top(),q1.pop();
}
while(q2.size()&&sum+q2.top()>=m){
q1.push(q2.top()),sum+=q2.top(),q2.pop();
}
if(sum>=m){
ans=min(ans,(int)(r-l+q2.size()));
}
sum+=a[--l];
if(a[l]<=0){
q1.push(a[l]);
}
}
}
cout<<(ans==inf?-1:ans);
return 0;
}
}
int main(){return asbt::main();}
C. 理想路徑(path)
對每個 \(t\) 建出能走到它的所有點構成的反圖，然后對于圖上任何一個點 \(s\) 就可以直接貪心了。因為下一步走哪個點是確定的，因此倍增即可。時間復雜度 \(O(nm+n^2\log n+q\log n)\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
const int maxn=2e3+5,inf=1e9;
int n,m,q,T,f[maxn][maxn][13];
bool vis[maxn];
vector<int> e1[maxn],e2[maxn];
il int kth(auto f,int u,int k){
int d=0;
while(k){
if(k&1){
u=f[u][d];
}
d++,k>>=1;
}
return u;
}
il int len(auto f,int u,int v){
int r=0;
for(int i=11;~i;i--){
if(f[u][i]!=v){
u=f[u][i],r+=1<<i;
}
}
return r+1;
}
int main(){
freopen("path.in","r",stdin);
freopen("path.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m>>q>>T;
for(int i=1,u,v;i<=m;i++){
cin>>u>>v;
e1[u].pb(v),e2[v].pb(u);
}
for(int t=1;t<=n;t++){
for(int i=1;i<=n;i++){
vis[i]=0;
}
queue<int> q;
vis[t]=1,q.push(t);
while(q.size()){
int u=q.front();
q.pop();
for(int v:e2[u]){
if(!vis[v]){
vis[v]=1,q.push(v);
}
}
}
for(int i=1;i<=n;i++){
if(vis[i]){
if(i==t){
f[t][i][0]=t;
}else{
int &u=f[t][i][0]=inf;
for(int v:e1[i]){
if(vis[v]){
u=min(u,v);
}
}
}
}
}
for(int j=1;j<=11;j++){
for(int i=1;i<=n;i++){
if(vis[i]){
f[t][i][j]=f[t][f[t][i][j-1]][j-1];
}
}
}
}
// for(int i=1;i<=n;i++){
// cout<<i<<":\n";
// for(int j=1;j<=n;j++){
// cout<<j<<": ";
// for(int k=0;k<=11;k++){
// cout<<f[i][j][k]<<' ';
// }
// cout<<'\n';
// }
// }
int ans=1;
while(q--){
int u,v,k;
cin>>u>>v>>k;
if(T){
u=(u^ans)%n+1,v=(v^ans)%n+1,k=(k^ans)%n+1;
}
// cout<<kth(f[v],u,n)<<' '<<len(f[v],u,v)<<'\n';
if(!f[v][u][0]||kth(f[v],u,n)!=v||len(f[v],u,v)<k-1){
cout<<-1<<'\n';
ans=1;
}else{
ans=kth(f[v],u,k-1);
cout<<ans<<'\n';
}
}
return 0;
}
}
int main(){return asbt::main();}
浙公網安備 33010602011771號