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