河南萌新联赛2024第（一）场：河南农业大学

C-有大家喜欢的零食吗_河南萌新联赛2024第（一）场：河南农业大学 (nowcoder.com)

思路:匈牙利算法的板子题. 二部图

int n;
vector<int> vct[505];
int match[505],vis[505];
bool dfs(int s){for(auto v:vct[s]){if(vis[v]) continue;vis[v]=1;if(!match[v]||dfs(match[v])){   女生没有伴侣,或者其伴侣可以选择其他女生match[v]=s;    糖果v被s孩子选了return 1;}}return 0;
}
有大家喜欢的零食吗
https://ac.nowcoder.com/acm/contest/86639/C
void solve(){               C   匈牙利🇭🇺--求最大匹配cin>>n;for(int i=1;i<=n;i++){int k; cin>>k;for(int j=1;j<=k;j++){      孩子选糖果int x; cin>>x;vct[i].emplace_back(x);}}int ans=0;for(int i=1;i<=n;i++){if(dfs(i)) ans++;for(int j=1;j<=n;j++) vis[j]=0; init}if(ans==n) cout<<"Yes";else cout<<"No"<<endl<<n-ans;
}

B-爱探险的朵拉_河南萌新联赛2024第（一）场：河南农业大学 (nowcoder.com)

思路:拓扑脱点之后，处理每一个环，环里的每一个点的可达大小都可以处理出来，并且同一个环中的点的可达大小都是一样的。处理完之后，再dfs处理环外的点，环外的点只要遇到!dis[x]==1的点就可以停止了.

int n;
int to[100005];     定义:to[i]为i点的下一个点
int du[100005];
int dis[100005];   定义:dis[i]为从i点走可以到达最多的点个数.
int d0=0,start;
对于每一个点,其出度只能是0/1. 但是入度可能大于1
拓扑之后脱点之后，如果构成环的话,环中的点出入度都为1.  画图可以知道双环是不存在的，因为不可能存在点的出度大于1
可以先拓扑脱点，先处理环中的距离。再处理其他环外的点.
///细节写拉了一点..wa了三发
void dfs0(int cur,int d){if(to[cur]==start) {d0=d;dis[cur]=d0;            少了这个...return;}dfs0(to[cur],d+1);dis[cur]=d0;
}
void dfs(int cur){if(dis[to[cur]]!=1){dis[cur]+=dis[to[cur]];return;}if(to[cur]!=cur) {dfs(to[cur]);dis[cur]+=dis[to[cur]];}
}
爱探险的朵拉
https://ac.nowcoder.com/acm/contest/86639/B
void solve(){                 B 拓扑脱点cin>>n;for(int i=1;i<=n;i++){cin>>to[i];if(to[i]!=i) du[i]++,du[to[i]]++;dis[i]=1;}queue<int> que;for(int i=1;i<=n;i++) if(du[i]==1) que.emplace(i);while(que.size()){int cur=que.front();que.pop();int nex=to[cur];du[cur]--,du[nex]--;if(du[nex]==1) que.emplace(nex);}for(int i=1;i<=n;i++) {if(du[i]==2&&dis[i]==1) {  这里重复跑了,得加条件dis[i]==1...一开始还加错了..写了dis[i]==0start=i;dfs0(i,1);}}int ans=1;for(int i=1;i<=n;i++) {if(dis[i]==1) dfs(i);ans=max(ans,dis[i]);}cout<<ans;
}

D-小蓝的二进制询问_河南萌新联赛2024第（一）场：河南农业大学 (nowcoder.com)

思路:思维.考虑每一位二进制位的贡献。算出1到R的贡献减去1到L-1的贡献，就是L到R的贡献.

简单枚举一下1到15的二进制可以发现，第0位是每2次出现一个1，第1位是每4次出现2个1，第3位是每8次出现4个1...计算即可，注意处理余数.

const int mod=998244353;
int count(int x){int res=0,a=2;x++;while(a/2<=x){(res+=(x/a)*(a/2))%=mod;if(x%a!=0) (res+=max(0ll,x%a-(a/2)))%=mod;        和0取maxa*=2;}return res;
}
小蓝的二进制询问
https://ac.nowcoder.com/acm/contest/86639/D
void solve(){       D   考虑每一位--差点没想到.int q; cin>>q;int l,r;while(q--){cin>>l>>r;cout<<(count(r)-count(l-1)+mod)%mod<<endl;}
}

G-旅途的终点_河南萌新联赛2024第（一）场：河南农业大学 (nowcoder.com)

思路:非常好想的二分答案，check也容易写。把前x个放入优先队列，贪心对顶k个施展魔法。

之后判断剩下的sum即可.

int n,m,k;
int arr[200005];
bool check(int x){int m0=m,k0=k;priority_queue<int> pq;for(int i=1;i<=x;i++) pq.emplace(arr[i]);   wa了一发，写成i<=n了..should be i<=xwhile(k0--&&pq.size()) pq.pop();while(pq.size()){m0-=pq.top();pq.pop();if(m0<=0) return false;}return true;
}
旅途的终点
https://ac.nowcoder.com/acm/contest/86639/G
void solve(){           G  二分答案cin>>n>>m>>k;for(int i=1;i<=n;i++) cin>>arr[i];int l=1,r=n,ans=0;while(l<=r){int mid=(l+r)>>1;if(check(mid)){ans=mid;l=mid+1;}else r=mid-1;}cout<<ans;
}

I-除法移位_河南萌新联赛2024第（一）场：河南农业大学 (nowcoder.com)

思路:糖完了。一开始居然还想着去模拟枚举一下。这是不可能的1e5个1e9相乘...实际上就是

分子/分母。。想要该值最大，尽量让最大那个值当分子即可。。然后注意要倒着找。。

int fz,fm=1;            想要fz/fm最大，那么fz肯定取能取到的最大那个数字
int ans=0;
int arr[200005];
除法移位
https://ac.nowcoder.com/acm/contest/86639/I
void solve(){           I    糖完了int n,k; cin>>n>>k;for(int i=1;i<=n;i++) cin>>arr[i];int maxn=arr[1];int idx=n,cnt=1;   倒着的...while(cnt<=k&&idx>=2){if(arr[idx]>maxn){maxn=arr[idx];ans=cnt;}idx--,cnt++;}cout<<ans;
}

F-两难抉择新编_河南萌新联赛2024第（一）场：河南农业大学 (nowcoder.com)

思路:也是糖题。简单算一下暴力枚举会枚举2.4e6次，那就直接枚举即可.

int n;
int arr[200005];
难抉择新编
https://ac.nowcoder.com/acm/contest/86639/F
void solve(){           F  一开始想复杂了,以为要拆位。。直接枚举即可.
//    int sum=0;
//    int n=200005;
//    for(int i=1;i<=200005;i++) sum+=n/i;
//    cout<<sum;        sum大概2.4e6  那么可以直接枚举cin>>n;int sum=0;for(int i=1;i<=n;i++){cin>>arr[i];sum^=arr[i];}int ans=sum;for(int i=1;i<=n;i++){int d=n/i;sum^=arr[i];for(int j=1;j<=d;j++){ans=max(ans,sum^(arr[i]+j));ans=max(ans,sum^(arr[i]*j));}sum^=arr[i];}先不考虑maxadd==0的情况,即sum的二进制全为1，的确不必理会. n=1,x=5-->ans=6cout<<ans;
}