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