2025牛客暑期多校訓練營3(FDJAEHB)

題目鏈接：牛客競賽_ACM/NOI/CSP/CCPC/ICPC算法編程高難度練習賽_牛客競賽OJ

F Flower

思路

可知當n<=a時無論怎么操作她都會離開

n%(a+b）是指進行完若干輪之后剩下的不足a+b個，如果是>a的話那么最后一輪必然不在a中，否則就摘掉n%(a+b)朵這樣就使得其位于b中

代碼

#include<bits/stdc++.h>
using namespace std;#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;void solve(){int n,a,b;cin>>n>>a>>b;if(n<=a){cout<<"Sayonara\n";return;}int x=n%(a+b);if(x>a||x==0){cout<<"0\n";return;}cout<<x<<"\n";
}
signed main() {vcoistntcout<<fixed<<setprecision(2);int _=1;cin>>_;while(_--) solve();return 0;
}

D Distant Control

思路

只要有連續a個開機的我們將其設置成a個關機的之后再將這a個連同與其挨著的關機的一個，即將a+1設置成開機的，如此循環就能夠將所有的都設置成開機的

所以結論即為若是有連續不低于a個開機的或者有連續不低于a+1個關機的，就一定能使得所有的都開機

代碼

#include<bits/stdc++.h>
using namespace std;#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;void solve(){int n,a;cin>>n>>a;string s;cin>>s;s=" "+s;int cnt1=0;int cnt0=0;int mx1=0,mx0=0;int ct=0;for(int i=1;i<=n;i++){if(s[i]=='1'){ ct++;cnt1++;cnt0=0;}else{cnt1=0;cnt0++;}mx1=max(mx1,cnt1);mx0=max(mx0,cnt0);}if(mx1>=a||mx0>=a+1){cout<<n<<"\n";}else{cout<<ct<<"\n";}
}
signed main() {vcoistntcout<<fixed<<setprecision(2);int _=1;cin>>_;while(_--) solve();return 0;
}

J Jetton

思路

可以證明若游戲會結束那么輪數不會超過log2(x+y)，直接模擬即可

此外，容易證明游戲能在有限回合內結束，答案為x+y / gcd(x,y) 是 2 的正整數次冪

代碼

#include<bits/stdc++.h>
using namespace std;#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;void solve(){int x,y;cin>>x>>y;int g=__gcd(x,y);int t=(x+y)/g;for(int i=0;i<=32;i++){if(t==(1ll<<i)){cout<<i<<"\n";return;}}cout<<"-1\n";
}
signed main() {vcoistntcout<<fixed<<setprecision(2);int _=1;cin>>_;while(_--) solve();return 0;
}

A Ad-hoc Newbie

思路

賽時沒注意到保證對每個i都有1 ≤ fi ≤ i 這句加重的話導致根本沒有思路，最后還是靠隊友解出來的

我們行和列其實是對稱的所以我們只需要填好一半即可，在構造時我們對于第i列來說我們將后i行添入比i大的數即可

一個可行的構造方法是對于第i行來說 2 3 ... i 0 1這樣保證了此行的mex值為n

當f[i]=x(x<n)時我們只需要將x換成n即可

代碼

#include<bits/stdc++.h>
using namespace std;#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;void solve(){int n;cin>>n;vi f(n+1);for(int i=1;i<=n;i++){cin>>f[i];}vector<vector<int>> ans(n+1,vi(n+1));for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){if(j==i) ans[i][j]=1;else if(j==i-1) ans[i][j]=0;else ans[i][j]=j+1;}}if(f[1]==1) ans[1][1]=0;for(int i=2;i<=n;i++){if(f[i]==i) continue;if(f[i]==1) ans[i][i]=i;else if(f[i]==0) ans[i][i-1]=i;else ans[i][f[i]-1]=i;}for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){ans[i][j]=ans[j][i];}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cout<<ans[i][j]<<" ";}cout<<"\n";}
}
signed main() {vcoistntcout<<fixed<<setprecision(2);int _=1;cin>>_;while(_--) solve();return 0;
}

E Equal

思路

發現當n為奇數時我們總能將所有的a進行乘法來使得所有的a相等，所以n為奇數時輸出yes

偶數時(特判n=2)我們要對其進行質因數分解，如果出現的次數都是偶數次則輸出yes，否則輸出no

代碼

#include<bits/stdc++.h>
using namespace std;#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;const int N=5e6+10;
const int mod=1e9+7;vector<int> minp,primes;
void sieve(int n){minp.assign(n+1,0);primes.clear();for(int i=2;i<=n;i++){if(minp[i]==0){minp[i]=i;primes.push_back(i);}for(auto p:primes){if(i*p>n){break;}minp[i*p]=p;if(p==minp[i]){break;}}}
}
bool isprime(int n){return minp[n]==n;
}int lcm(int x,int y){return x*y/__gcd(x,y);
}void solve(){int n;cin>>n;vi a(n+1);for(int i=1;i<=n;i++){cin>>a[i];}if(n==2){if(a[1]==a[2]){cout<<"Yes\n";}else{cout<<"No\n";}return;}if(n%2){cout<<"Yes\n";return;}unordered_map<int,int> cnt;auto cal=[&](int tmp){for(int i=0;i<primes.size();i++){while((tmp!=1)&&(tmp%primes[i]==0)){tmp/=primes[i];cnt[primes[i]]++;}if(isprime(tmp)){cnt[tmp]++;break;}if(tmp==1) break;}};for(int i=1;i<=n;i++){cal(a[i]);}for(auto [i,t]:cnt){if(t%2){cout<<"No\n";return;}}cout<<"Yes\n";}
signed main() {vcoistntcout<<fixed<<setprecision(2);sieve(N);int _=1;cin>>_;while(_--) solve();return 0;
}

H Head out to the Target

思路

轉化題意，維護一個可達集合，每個時刻對于目標節點u，選擇集合中距離u最近的節點，往u移動r-l+1步若能到達則輸出此時的時刻，無法到達將r-l+1步走過的點加入到集合里面

找到最近的集合里的點可以用倍增找，加入到集合里面的過程可以暴力

代碼

#include<bits/stdc++.h>
using namespace std;#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;const int N=1e6+10;
const int inf=1e18;
const int mod=998244353;int st[N][35],f[N];
vector<vi> e(N);
int n,k;
bool vis[N]={false};struct node{int u,l,r;
}q[N];
bool cmp(node x,node y){return x.l<y.r;
}void init(){vis[1]=true;vis[0]=true;for(int p=1;(1<<p)<=n;p++){for(int i=1;i<=n;i++){st[i][p]=st[st[i][p-1]][p-1];}}
}pll jamp(int x){int cnt=0;for(int p=30;p>=0;p--){if(!vis[st[x][p]]){x=st[x][p];cnt+=(1<<p);}}return {st[x][0],cnt+1};
}void solve(){cin>>n>>k;for(int i=2;i<=n;i++){cin>>f[i];st[i][0]=f[i];e[f[i]].push_back(i);}init();for(int i=1;i<=k;i++){cin>>q[i].u>>q[i].l>>q[i].r;}sort(q+1,q+1+k,cmp);for(int i=1;i<=k;i++){auto [x,cnt]=jamp(q[i].u);int now=q[i].r-q[i].l+1;if(now>=cnt){cout<<q[i].l+cnt-1<<"\n";return;}int y=q[i].u;int res=cnt-now;while(y!=x){if(res>0) res--;y=f[y];if(res==0) vis[y]=true;}}cout<<"-1\n";
}
signed main() {vcoistntcout<<fixed<<setprecision(2);int _=1;// cin>>_;while(_--) solve();return 0;
}

B Bitwise Puzzle

思路

明顯a，b為0時特判

操作次數不超過64，意味著每次對二進制某一位進行修改平均次數為2，也就是說可以將a或者b某一個改成c，另一個改成0，最后a與b異或一次得到全部相等

注意到我們可以拿b的最高位1來對a進行修改，所以我們在開始時將a與b進行異或，使其最高位1的位置相同，假設用hx表示x的最高位1的位置，此時ha=hb

1.ha>=hc

我們可以用b來不斷修改a，b不斷右移直到a改成c，b變成0，我們進行b=b xor a操作，將b變成a

2.ha<hc

我們依然用b來不斷修改a，此時我們要把a變成c的前綴部分，b變成1，之后將a不斷左移，用1來修改a的最后一位將其變成c，最后將b變成0后與a異或，變成a

可以發現其操作次數是不會超過64的

代碼

#include<bits/stdc++.h>
using namespace std;#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
// #define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;int h(int x){if(x==0) return 0;return 32-__builtin_clz(x);
}
int g(int x,int k){return (x>>(k-1))&1;
}void solve(){int a,b,c;cin>>a>>b>>c;if(a==0&&b==0){if(c>0) cout<<"-1\n";else cout<<"0\n";return;}vi ans;if(h(a)>h(b)){ans.push_back(4);b^=a;}if(h(a)<h(b)){ans.push_back(3);a^=b;}while(h(b)>h(c)){if(g(a,h(b))){ans.push_back(3);a^=b;}ans.push_back(2);b/=2;}if(h(a)<h(b)) ans.push_back(3),a^=b;for(int i=h(a),j=h(c);i>=1;i--,j--){if(g(a,i)!=g(c,j)){ans.push_back(3);a^=b;}ans.push_back(2);b/=2;}ans.pop_back();b=1;for(int i=(h(c)-h(a));i>=1;i--){ans.push_back(1);a*=2;if(g(c,i)){ans.push_back(3);a^=b;}}ans.push_back(2);b/=2;ans.push_back(4);b^=a;// cout<<a<<" "<<b<<" "<<c<<"\n";cout<<ans.size()<<"\n";for(int x:ans){cout<<x<<" ";}cout<<"\n";}
signed main() {vcoistntcout<<fixed<<setprecision(2);int _=1;cin>>_;while(_--) solve();return 0;
}