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;
}