牛客小白月赛48 题解
A
两个正整数 ,。对于任意整数 ,都有 ,不管怎么操作,两个数的 都不会变小。所以只需要判断初始给出的数组是否为孤独的数组,如果是,输出 ,否则输出 。
复杂度为 。
#include <bits/stdc++.h> #define ll long long using namespace std; const int N=1e5+10,mod=1e9+7; ll A[N]; int main() { int n; cin>>n; for (int i=1; i<=n; i++) cin>>A[i]; for (int i=2; i<=n; i++) { if (__gcd(A[i-1],A[i])>1) { cout<<-1; return 0; } } cout<<0; return 0; }
B
技能卡多的一方为 ,技能卡少的一方为 , 拥有比赛胜负的决定权。
会在需要“扭转局势"的情况下发动技能卡,只需要一张卡即可。然后, 每次发动卡, 都发动一张与其抵消,相当于什么都没发生。因此,谁卡多,谁就能必胜。
对于双方技能卡数量一致的情况,可以看作双方都没有卡,因为对于没卡情况下获胜的那一方,每次对方发动技能卡,都会发动一张与其抵消。因此这种情况只需要二分一下可以进行几回合,奇数回合牛妹胜,偶数牛牛胜。
复杂度为 。
#include <bits/stdc++.h> #define ll long long using namespace std; const int N=1e5+10,mod=1e9+7; ll A[N]; int main() { int t; cin>>t; while (t--) { ll n,a,b; cin>>n>>a>>b; if (a>b) cout<<"niuniu\n"; else if (a<b) cout<<"niumei\n"; else { ll L=1,R=1e9,ans=0; while (L<=R) { ll m=L+(R-L+1)/2; if ((1+m)*m/2<=n) ans=m,L=m+1; else R=m-1; } if (ans%2) cout<<"niumei\n"; else cout<<"niuniu\n"; } } return 0; }
C
由于长度是固定的,可以按照左端点从小到大枚举全部牛牛可能选择的区间。
对于两个区间 和 ,只有位置 和 两处不同。对于区间 暴力计算有趣值和权重,然后枚举的时候,可以直接 更新。
有两个坑点分别是:1)可疑区间的右端点范围在 。2)开 。
复杂度为 。
#include <bits/stdc++.h> #define ll long long using namespace std; const int N=1e7+10,mod=1e9+7; ll L[N],R[N]; int add[N],red[N]; int main() { int n,len; cin>>n>>len; for (int i=1; i<=n; i++) { int l,r; cin>>l>>r; add[l]++,red[r]++; L[l]+=i,R[r]+=i; } ll Max_val=0,Max_cnt=0,ans=0,cnt=0,val=0; for (int i=1; i<=len; i++) cnt+=add[i],val+=L[i]; Max_val=val,Max_cnt=cnt,ans=1; for (int i=len+1; i<N; i++) { cnt+=add[i],cnt-=red[i-len]; val+=L[i],val-=R[i-len]; if (cnt>Max_cnt||(cnt==Max_cnt&&val>Max_val)) ans=0,Max_cnt=cnt,Max_val=val; if (cnt==Max_cnt&&val==Max_val) ans++; } cout<<ans; return 0; }
D
用于乘法的元素有 个,加法的有 个。
整个数组 最小的 个元素用于加法,其余用于乘法,用于加法的从大排到小,用于乘法的从小排到大,贪心。证明略。
复杂度为 。
#include <bits/stdc++.h> #define ll long long using namespace std; const int N=3e5+10,mod=1e9+7; ll A[N]; int main() { int n; cin>>n; for (int i=1; i<=n; i++) cin>>A[i]; sort(A+1,A+n+1); int Mul=(n-1)/2,add=n-Mul; ll sum=A[add]; int L=add+1; for (int i=add-1; i>=1; i--) { sum+=A[i]; sum%=mod; if (L<=n) sum*=A[L++]; sum%=mod; } cout<<sum; return 0; }
E
二进制下
和
通过操作得出不同的数的个数一样,归纳起来只有这四种,因为 和 永远也不变,所以最多只是 ,刚好个
可以发现,最多只会通过操作变出 个不同的 ,所以直接暴搜即可。
#include <bits/stdc++.h> #define ll long long #define P pair<ll,ll> using namespace std; const int N=5e5+10,MAXN=5e3+10,mod=998244353,INF=0x3f3f3f3f; P cal1(ll a, ll b) { a=(a|b); if (a>b) swap(a,b); return P(a,b); } P cal2(ll a, ll b) { a=(a&b); if (a>b) swap(a,b); return P(a,b); } P cal3(ll a, ll b) { a=(a^b); if (a>b) swap(a,b); return P(a,b); } void cal(ll a, ll b, ll target) { set<P> S; if (a>b) swap(a,b); S.insert(P(a,b)); queue<P> Q; Q.push(P(a,b)); while (!Q.empty()) { P p=Q.front(); Q.pop(); ll a=p.first,b=p.second; if (!S.count(cal1(a,b))) { S.insert(cal1(a,b)),Q.push(cal1(a,b)); } if (!S.count(cal1(b,a))) { S.insert(cal1(b,a)),Q.push(cal1(b,a)); } if (!S.count(cal2(a,b))) { S.insert(cal2(a,b)),Q.push(cal2(a,b)); } if (!S.count(cal2(b,a))) { S.insert(cal2(b,a)),Q.push(cal2(b,a)); } if (!S.count(cal3(a,b))) { S.insert(cal3(a,b)),Q.push(cal3(a,b)); } if (!S.count(cal3(b,a))) { S.insert(cal3(b,a)),Q.push(cal3(b,a)); } } set<ll> s; for (auto p=S.begin(); p!=S.end(); p++) { s.insert(p->first),s.insert(p->second); } if (s.count(target)) cout<<"YES\n"; else cout<<"NO\n"; } int main() { int t; cin>>t; while (t--) { ll a,b,target; cin>>a>>b>>target; cal(a,b,target); } return 0; }
F
只需要相邻节点不存在相同的质因子即可。枚举范围内质数 ,包含质因子 的节点组成一些联通块,节点的权值为该节点包含因子 的个数。
对于每个联通块,选择一些点标黑,剩余点标白,使得不存在两个相邻白点,并且黑点的权值和最小,经典树形 问题。
复杂度为 。
#include <bits/stdc++.h> #define ll long long using namespace std; const int N=1e5+10,mod=1e9+7; vector<int> G[N]; struct node { int now,cnt; }; vector<node> NODE[N]; int A[N],Max[N],vis[N],cnt[N],col[N],ans[N],dp[N][2]; void dfs(int u) { col[u]=1; dp[u][0]=cnt[u]; dp[u][1]=0; for (int i=0; i<G[u].size(); i++) { int v=G[u][i]; if (!vis[v]) continue; if (col[v]) continue; dfs(v); dp[u][0]+=min(dp[v][0],dp[v][1]); dp[u][1]+=dp[v][0]; } } int main() { for (int i=2; i<N; i++) { if (Max[i]) continue; for (int j=i; j<N; j+=i) Max[j]=i; } int n; cin>>n; for (int i=1; i<=n; i++) { cin>>A[i]; while (A[i]>1) { node res={i,0}; int num=Max[A[i]]; while (A[i]%num==0) A[i]/=num,res.cnt++; NODE[num].push_back(res); } } for (int i=1; i<n; i++) { int u,v; cin>>u>>v; G[u].push_back(v); G[v].push_back(u); } ll res=0; for (int i=1; i<N; i++) { if (Max[i]!=i&&!NODE[i].empty()) exit(-1); if (Max[i]!=i) continue; if (NODE[i].empty()) continue; for (int j=0; j<NODE[i].size(); j++) { int u=NODE[i][j].now; vis[u]=1; cnt[u]=NODE[i][j].cnt; } for (int j=0; j<NODE[i].size(); j++) { int u=NODE[i][j].now; if (!col[u]) { ans[0]=ans[1]=0; dfs(u); res+=min(dp[u][0],dp[u][1]); } } for (int j=0; j<NODE[i].size(); j++) { int u=NODE[i][j].now; col[u]=vis[u]=0; } } cout<<res<<endl; return 0; }