2025牛客暑期多校训练营2（部分补题）

题目链接：牛客竞赛_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ

B Bitwise Perfect

思路

考虑到由 $2^{x}+2^{y}==>2^{x\bigoplus y}$ ，那么只有 $x\bigoplus y$ 变小的时候对答案的贡献才能够减少，从二进制的角度考虑什么时候变小，只有min(x,y)中的最高位1异或之后变成0那么就一定变小，否则一定变大

代码

#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;int cal(int x){int mx=0;for(int i=0;i<=63;i++){if((1ll<<i)<=x){mx=i;}else{break;}}return mx;
}void f(int x,vi& cnt){for(int i=0;i<63;i++){if((x>>i)&1){cnt[i]++;}}
}void solve(){int n;cin>>n;vi a(n+10);vi ct(65,0);vi cnt(65,0);for(int i=1;i<=n;i++){cin>>a[i];f(a[i],cnt);}for(int i=1;i<=n;i++){if(cnt[cal(a[i])]>1){cout<<"NO\n";return;}}cout<<"YES\n";
}
signed main() {vcoistntcout<<fixed<<setprecision(2);int _=1;cin>>_;while(_--) solve();return 0;
}

F Field of Fire

思路

由01组成的环形数组，模拟一遍过程得知

我们把所有连续0的长度统计出来，我们要选择最大的一段将一段给用火烧掉，其余的全部火势正常蔓延，T秒后统计答案

那么最长的一段对答案的贡献为max(0,len-T-1)，其余的为max(0,len-2*T)

代码

#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,t;cin>>n>>t;string s;cin>>s;s=" "+s;vi v;int mx=0;int i=1;while(s[i]!='1'){i++;}int pre=i-1;while(i<=n){int ti=i+1;while(ti<=n&&s[ti]!='1'){ti++;}if(ti!=n+1){v.push_back(ti-i-1);mx=max(mx,ti-i-1);}i=ti;}int xi=n;int suf=0;while(s[xi]!='1'){suf++;xi--;}mx=max(mx,suf+pre);v.push_back(suf+pre);sort(v.begin(),v.end(),greater<int>());int ans=0;if(mx<=t+1){cout<<0<<"\n";return;}else{ans+=(mx-t-1);}for(int i=1;i<v.size();i++){if(v[i]>=2*t){ans+=v[i]-2*t;}else{break;}}cout<<ans<<"\n";}
signed main() {vcoistntcout<<fixed<<setprecision(2);int _=1;cin>>_;while(_--) solve();return 0;
}

I Identical Somehow

思路

我们可以发现当x与y都不是1，我们令k=1，那么一定是相等的

如果x与y中有一个为1，那么就无法构造输出-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 x,y;cin>>x>>y;if(min(x,y)==1){cout<<"-1"<<"\n";return;}cout<<"1\n";
}
signed main() {vcoistntcout<<fixed<<setprecision(2);int _=1;cin>>_;while(_--) solve();return 0;
}

A Another Day of Sun

思路

我们可以将开头加入0，那么根据题意我们要找的便是01串出现的次数和

我们考虑每个01串对于整体的贡献，我们用cnt表示-1出现的次数

考虑进-1，有以下四种情况可以产生贡献：

{0 1} : $2^{cnt}$

{0 -1}: $2^{cnt-1}$

{-1 1}: $2^{cnt-1}$

{-1 -1}: $2^{cnt-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=5e5+10;
const int inf=1e18;
const int mod=998244353;vi pw(N);
void init(){pw[0]=1;for(int i=1;i<N;i++){pw[i]=(pw[i-1]*2)%mod;}
}void solve(){int n;cin>>n;vi a(2);int cnt=0;for(int i=1;i<=n;i++){int x;cin>>x;if(x==-1) cnt++;a.push_back(x);}n=n+1;int ans=0;for(int i=1;i<n;i++){if(a[i]==0&&a[i+1]==1) ans=(ans+pw[cnt])%mod;if(a[i]==0&&a[i+1]==-1) ans=(ans+pw[cnt-1])%mod;if(a[i]==-1&&a[i+1]==1) ans=(ans+pw[cnt-1])%mod;if(a[i]==-1&&a[i+1]==-1) ans=(ans+pw[cnt-2])%mod;}cout<<ans<<"\n";
}
signed main() {vcoistntcout<<fixed<<setprecision(2);int _=1;init();cin>>_;while(_--) solve();return 0;
}

L Love Wins All

思路

我们可以考虑将排列转化成图，然后发现最后一定是由多个环组成的

发现如果存在奇数环那么只能是2个，否则只能为0，因为根据题意我们要选择两人禁婚，要么在没有奇数环的情况下在偶数环中选择两个，否则有奇数环的时候只能每个奇数环各选一个

在有奇数环的情况下：

我们在两个奇数环各选一个奇数环剩下的人只能有一种匹配情况，其余偶数环每个有2种匹配可能(要注意n=2的情况下匹配情况只有1种)

没有奇数环的情况下：

我们可能选择任意偶数环中的两个，其余每个环为2种可能(要注意n=2的情况下匹配情况只有1种)，对于一个偶数环来说选择两个的情况为 $\frac{n^{2}}{4}$ 种，(n/2)*(n/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=5e5+10;
const int inf=1e18;
const int mod=998244353;int ksm(int a,int b){int ans=1;while(b){if(b&1){ans=(ans*a)%mod;}a=((a%mod)*(a%mod))%mod;b>>=1;}return ans;
}struct DSU {                //并查集应用模板vector<int>p,siz;       //p表示祖先，siz表示这个组合有多少个DSU(int n):p(n),siz(n,1) {      //初始化iota(p.begin(),p.end(),0);  //p[i]=i}int find(int x) {while(x!=p[x]) x=p[x]=p[p[x]];return x;}bool same(int x,int y) {return find(x)==find(y);}bool merge(int x, int y) {x=find(x),y=find(y);if (x==y) return false;siz[x]+=siz[y],p[y]=x;return true;}int size(int x) {return siz[find(x)];}
};void solve(){int n;cin>>n;vi a(n+10);DSU dsu(n+10);for(int i=1;i<=n;i++){cin>>a[i];dsu.merge(i,a[i]);}map<int,bool> mp;vi v;int cnt=0;int c2=0;for(int i=1;i<=n;i++){if(!mp[dsu.find(i)]){mp[dsu.find(i)]=true;int x=dsu.size(i);v.push_back(x);if(x==2) c2++;if(x%2) cnt++;}}if(cnt!=2&&cnt!=0){cout<<0<<"\n";return;}int ct=v.size();int ans=0;if(cnt==2){ans=1;int d=ksm(2,ct-c2-2);for(auto x:v){if(x%2){ans=(ans*x)%mod;}}ans=(ans*d)%mod;}else{ans=0;for(auto x:v){if(x==2){ans=(ans+(x*x/4)*ksm(2,ct-c2))%mod;}else{ans=(ans+(x*x/4)*ksm(2,ct-1-c2))%mod;}}}cout<<ans<<"\n";
}
signed main() {vcoistntcout<<fixed<<setprecision(2);int _=1;cin>>_;while(_--) solve();return 0;
}

G Geometry Friend

思路

如果点在多边形的内部，我们找到距离最远的一个或多个点，以其为直径转一个完整的圆，最大的夹角即为答案；

如果点在多边形的外部，我们发现距离最近的点有且仅有一个点，我们需要转一个圆，答案为2*pi

代码

#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;const long double pi=acosl(-1);
struct node{int x,y;
};node dir(node a,node b){return {b.x-a.x,b.y-a.y};
}
int cross(node a,node b){return a.x*b.y-a.y*b.x;
}void solve(){int n,x,y;cin>>n>>x>>y;vector<node> p(n+1);for(int i=1;i<=n;i++){cin>>p[i].x>>p[i].y;}bool f=true;    //判断(x,y)在多边形内部还是外部for(int i=1;i<=n;i++){if(cross( dir(p[i],p[(i%n)+1]), dir(p[i],{x,y}) )<0){f=false;break;}}if(!f){cout<<2*pi<<"\n";}else{auto dis=[&](node no)->int{return (no.x-x)*(no.x-x)+(no.y-y)*(no.y-y);};int mx=0;for(int i=1;i<=n;i++) mx=max(mx,dis(p[i]));vector<long double> v;for(int i=1;i<=n;i++){if(mx==dis(p[i])){v.push_back(atan2(p[i].x-x,p[i].y-y));}}sort(v.begin(),v.end());long double res=0.0;for(int i=0;i<v.size()-1;i++){res=max(res,v[i+1]-v[i]);}res=max(res,v[0]-v.back()+2*pi);cout<<res<<"\n";}}
signed main() {vcoistntcout<<fixed<<setprecision(15);int _=1;cin>>_;while(_--) solve();return 0;
}

H Highway Upgrade

思路

最终答案肯定是我们只对某一条边进行缩减，然后求得的最短路

正向和反向分别跑最短路算法，用d1[i]表示从节点1到节点i的最短距离，用dn[i]表示从节点i到节点n的最短距离

对于边 $(u_i,v_i)$ 若对其进行k次缩减，那答案便为 $d1[u_i]+dn[v_i]+t_i-w_i*k$ ，发现只有k是未知的，这是一条直线，我们可以将所有边形成的直线统计，每次询问k找最小

然后我们可以将其维护成下凸包，因其满足一个类似与开口向上的二次函数，可以用二分来找最小值

代码

#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,m;cin>>n>>m;vector< vector<array<int,3>> > e(n+10);vector< vector<array<int,3>> > g(n+10);vi us(m+1),vs(m+1),ts(m+1),ws(m+1);for(int i=1;i<=m;i++){int u,v,t,w;cin>>u>>v>>t>>w;us[i]=u;vs[i]=v;ts[i]=t;ws[i]=w;e[u].push_back({v,t,w});g[v].push_back({u,t,w});}//跑最短路vi d1(n+10,inf);vi dn(n+10,inf);auto dij=[&](int s,vi& dis,vector<vector<array<int,3>>> &edg)->void{vector<bool> vis(n+10,false);priority_queue<pll,vector<pll>,greater<pll>> pq;pq.push({0,s});dis[s]=0;while(!pq.empty()){auto [t,u]=pq.top();pq.pop();if(vis[u]) continue;vis[u]=true;for(auto& tmp:edg[u]){int v=tmp[0];int w=tmp[1];if(dis[v]>t+w){dis[v]=t+w;pq.push({dis[v],v});}}}};dij(1,d1,e); //从1出发到节点x的最短距离dij(n,dn,g); //从n出发到节点x的最短距离//将所有直线统计first表示斜率，second表示截距vector<pll> lines;for(int i=1;i<=m;i++){lines.push_back({-ws[i],d1[us[i]]+dn[vs[i]]+ts[i]});}sort(lines.rbegin(),lines.rend()); //斜率绝对值从小到大//下凸包vector<pll> h;  //记录凸点h.push_back({0,d1[n]});for(auto [k,y]:lines){while(h.size()>1){      //利用叉积保持凸包auto [k1,y1]=h[h.size()-2];auto [k2,y2]=h[h.size()-1];if((__int128)1*(y1-y2)*(k2-k)<=(__int128)1*(y2-y)*(k1-k2)) h.pop_back();else break;}h.push_back({k,y});}//二分查找最低点int siz=h.size();auto f=[&](int i,int t)->int{if(i<0||i>=siz) return inf;return t*h[i].first+h[i].second;};int q;cin>>q;while(q--){int k;cin>>k;int l=0,r=siz-2;while(l<=r){int mid=(l+r)>>1;if(f(mid,k)>=f(mid+1,k)) l=mid+1;else r=mid-1;}cout<<f(l,k)<<"\n";}}
signed main() {vcoistntcout<<fixed<<setprecision(2);int _=1;cin>>_;while(_--) solve();return 0;
}

D Donkey Thinks...

思路

此题赛时出挺少的，但补题的时候发现思路倒是挺清晰的，就是卡的很极限。。。

形式化题目我们要求 $\sum h_i-(V-\sum s_i)*\sum d_i$ ，看数据发现V是很小的，那么我们不妨枚举V，也就是将 $\sum s_i=S$ 变成一个常数， $x=V-S$

然后每个物品的价值变成 $h_i-x*d_i$ ，跑一遍恰好装满背包的背包dp

发现这样是过不了的因为时间复杂度太高了

我们考虑优化，对于体积为i的物品我们只需要枚举前 $\left \lfloor \frac{S}{i} \right \rfloor$ 个价值最大的，这里要用到nth_element库函数(精华所在)

代码

#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,v;cin>>n>>v;vi h(n+1),s(n+1),d(n+1);for(int i=1;i<=n;i++){cin>>h[i]>>s[i]>>d[i];}int ans=0;for(int S=1;S<=v;S++){int x=v-S;vector<vi> va(S+1);for(int i=1;i<=n;i++){if(s[i]<=S){va[s[i]].emplace_back(x*d[i]-h[i]);}}vi dp(S+1,-inf);dp[0]=0;for(int i=1;i<=S;i++){int k=min(S/i,(int)va[i].size());nth_element(va[i].begin(), va[i].begin() + k - 1, va[i].end());for(int idx=0;idx<k;idx++){for(int cur=S;cur>=i;cur--){dp[cur]=max(dp[cur],dp[cur-i]-va[i][idx]);}}}ans=max(ans,dp[S]);}cout<<ans<<"\n";
}
signed main() {vcoistntcout<<fixed<<setprecision(2);int _=1;cin>>_;while(_--) solve();return 0;
}