1.D-小蓝的二进制询问
原题链接：
https://ac.nowcoder.com/acm/contest/86639/D
我们列举一些二进制数，发现在第一位永远是0 1的循环，第二位是0 0 1 1的循环。。。第n位也是如此，所以可以得出每位上的循环节是2k ,且前一半的数都是0。每次在计算某数时的1的总个数可以计算他是循环节的几倍，乘以循环节的一半，再加上余数减去前面的0个数后的数，所得即所求。
查看代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 4e5 + 7;
const int mod = 998244353;
int f(int x, int k)
{
int y = 1ll << (k );//这里一定要把1强制类型转换，不然会有误差
int ok = y / 2;
x++;//加上0这个数，方便算倍数
int res=x/y*ok;
int yu = x % y;
yu -= ok;
if (yu > 0)
res += yu;
return res;
}
void solve()
{
int l, r;
cin >> l >> r;
int ans = 0;
for (int i = 62; i >= 1; i--)
{//枚举每个数位
int p = (f(r, i) % mod - f(l - 1, i) % mod + mod) % mod;
ans = (ans + p) % mod;
}
cout << ans << endl;
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t--)
solve();
return 0;
}2.C-有大家喜欢的零食么
原题链接：
https://ac.nowcoder.com/acm/contest/86639/C
在此推荐一个大佬博客：https://blog.csdn.net/u011815404/article/details/84260940
二分图最大匹配匈牙利算法模板题
查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
vector<int> G[10001];
int sign[100000],jie[100000];
bool dfs(int x)
{
for(int i=0;i<G[x].size();i++)
{
int f=G[x][i];
if(!sign[f])
{
sign[f]=1;
if(jie[f]==0||dfs(jie[f]))
{
jie[f]=x;
return true;
}
}
}
return false;
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
int t;
cin>>t;
while(t--)
{
int x;
cin>>x;
G[i].push_back(x);
}
}
int ans=0;
for(int i=1;i<=n;i++)
{
memset(sign,0,sizeof sign);
if(dfs(i))ans++;
}
if(ans==n)cout<<"Yes";
else
{
cout<<"No"<<endl;
cout<<n-ans;
}
return 0;
}