阅读量:0
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]==0 start=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取max a*=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<=x while(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=6 cout<<ans; }