牛客小白月赛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;
} 
海康威视公司福利 1173人发布
投递莉莉丝游戏等公司10个岗位