A.Searching for Soulmates
题意：a经过+1,*2,/2三种操作变成b的最小次数
1.a一定是按照 /2(+1)/2(+1)......（+1+1+1...)*2(+1)*2(+1) 这种操作顺序变成b
证明：首先令a小于b，并且只经过+1与*2变成b，最少步数的构造方法是令c=a*2^k且c<b,将得到的(b-c)二进制分解，对于其二进制每一位都可以插入到相应的乘法位置中，用一步完成，故这样为最小步数
为了保证有这种方案并且可行，我们枚举要经过的乘法的轮数，也就是说能够得到一个res，令res经过*2(+1)*2(+1)...（每次中间只加一个1）这样的操作后变成b，统计答案时候这部分的贡献为乘法的轮数+加法的轮数（也就是二进制1的个数）
只有res比a小的时候，a才能到达res
a到达res的最小方法：能/2一直/2，否则+1后/2直到<=res,在加上两数之差
#include<bits/stdc++.h>
#define int long long
using namespace std;
int t;
int popcnt(int x);
signed main(){
scanf("%d",&t);
while(t--){
int a,b;
cin>>a>>b;
int ans=1000;
for(int mul=0;(b>>mul)>0;mul++){//乘法轮数
int res=b>>mul;
int now=a;
int cnt=0;
while(now>res){
if(now&1){
cnt++,now++;
}
cnt++,now>>=1;
}
cnt+=(res-now);//a->res
cnt+=mul+popcnt(b&((1ll<<mul)-1));res->b
ans=min(ans,cnt);
}
cout<<ans<<endl;
}
return 0;
}
int popcnt(int x){
int ans=0;
while(x) ans+=(x&1),x>>=1;
return ans;
}C.Cereal 2
二分图匹配，将奶牛与可以吃的麦片连边，跑最大匹配，难点在于输出方案，提供两种解法
1.匈牙利
考虑匈牙利算法的过程：按顺序访问边，若这条边的终点已经使用，回溯看能否使这条边的起点连接其他点
相当于模拟了送麦片的过程，先选第一喜欢的麦片，若被其他奶牛选走，看看其他奶牛能否腾出这个麦片，否则选第二个麦片
显然，最后得到的解一定可行，输出时先输出得到第一喜欢的麦片的奶牛，然后记录哪些麦片已经失去，再输出得到第二喜欢麦片的奶牛并且其第一喜欢的麦片已经被送走，最后输出没得到麦片的奶牛
#include<bits/stdc++.h>
#define inf 200604300
using namespace std;
vector<int>tu[300110];
int match[300100];
int v[1400010],vsz;
int d[300110],las[300110];
int a,b,fir[300110],sec[300110],jl[300110],gs;
bool vis[100100],hv[300100];
bool er[300110];
vector<int>hh[300110];
bool dfs(int x);
int main(){
scanf("%d%d",&a,&b);
for(int i=1;i<=a;i++){
scanf("%d%d",&fir[i],&sec[i]);
hh[fir[i]].push_back(i);//第一喜欢麦片是fir[i]的奶牛集合
tu[i].push_back(fir[i]),tu[i].push_back(sec[i]);
}
int gs=0;
for(int i=1;i<=a;i++){
memset(vis,0,sizeof(vis)),gs+=dfs(i);
}
queue<int>q;
printf("%d\n",a-gs);
for(int i=1;i<=b;i++){
if(fir[match[i]]==i){
hv[match[i]]=true;
printf("%d\n",match[i]);
q.push(i);
}
if(sec[match[i]]==i){
er[match[i]]=true;//记录得到第二喜欢的
hv[match[i]]=true;
}
}//输出得到第一喜欢的
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=0;i<hh[x].size();i++){
int p=hh[x][i];
if(er[p]){
printf("%d\n",p);
er[p]=false;
q.push(sec[p]);
}
}
}
for(int i=1;i<=a;i++){
if(!hv[i]) printf("%d\n",i);
}
return 0;
}
bool dfs(int x){
for(int i=0;i<tu[x].size();i++){
int p=tu[x][i];
if(!vis[p]){
vis[p]=true;
if(!match[p]||dfs(match[p])){
match[p]=x;
return true;
}
}
}
return false;
}但是毕竟匈牙利算法最坏n^2,dinic做二分图问题复杂度是严格??的，考虑dinic
不能直接dinic最大流，因为会破坏有第一喜欢的先拿第一喜欢的这个条件
但是可以将每条边加一个权值，第一喜欢的是2，第二喜欢的是1，跑最大费用最大流，这样保证能匹配的最喜欢的一定那最喜欢的
并且可以让这道题多一个限制条件：使最多奶牛拿到最喜欢的麦片
#include<bits/stdc++.h>
#define inf 200604300
using namespace std;
struct node{
int p,vid,w;
};
vector<node>tu[300110];
int v[1400010],vsz;
int dis[300110],las[300110];
int a,b,fir[300110],sec[300110],jl[300110],gs;
int p_beg,p_end;
bool vis[300110],in[300100],ty[300100];
bool er[300110];
vector<int>hh[300110];
void add(int x,int y,int V,int W);
bool get_dis();
int dinic(int x,int flow);
int main(){
scanf("%d%d",&a,&b);
p_beg=0,p_end=a+b+1;
for(int i=1;i<=a;i++){
scanf("%d%d",&fir[i],&sec[i]);
hh[fir[i]].push_back(i);
add(i,a+fir[i],1,2),add(i,a+sec[i],1,1);
add(p_beg,i,1,0);
}
for(int i=1;i<=b;i++) add(i+a,p_end,1,0);
int flow=0;
while(get_dis()){
int now=dinic(p_beg,inf);
while(now) flow+=now,now=dinic(p_beg,inf);
}
printf("%d\n",a-flow);
queue<int>q;
for(int x=1;x<=a;x++){
for(int i=0;i<tu[x].size();i++){
int p=tu[x][i].p,vid=tu[x][i].vid;
if(p>a&&p<=a+b){
if(!v[vid]){
vis[x]=true;
p-=a;
if(fir[x]==p) printf("%d\n",x),q.push(fir[x]);
if(sec[x]==p) er[x]=true;
break;
}
}
}
}
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=0;i<hh[x].size();i++){
int p=hh[x][i];
if(er[p]){
printf("%d\n",p);
er[p]=false;
q.push(sec[p]);
}
}
}
for(int i=1;i<=a;i++){
if(!vis[i]) printf("%d\n",i);
}
return 0;
}
void add(int x,int y,int V,int W){
tu[x].push_back({y,vsz,W}),v[vsz]=V,vsz++;
tu[y].push_back({x,vsz,-W}),v[vsz]=0,vsz++;
}
bool get_dis(){
for(int i=p_beg;i<=p_end;i++) ty[i]=in[i]=las[i]=0,dis[i]=-0x3f3f3f3f;
queue<int>q;
q.push(p_beg);dis[p_beg]=0;
while(!q.empty()){
int x=q.front();
in[x]=false;
q.pop();
for(int i=0;i<tu[x].size();i++){
int p=tu[x][i].p,vid=tu[x][i].vid,w=tu[x][i].w;
if(!v[vid]) continue;
if(dis[p]<dis[x]+w){
dis[p]=dis[x]+w;
if(!in[p]) q.push(p),in[p]=true;
}
}
}
return dis[p_end]>-inf/10;
}
int dinic(int x,int flow){
if(x==p_end) return flow;
int res=flow;
ty[x]=true;
for(int i=0;i<tu[x].size();i++){
las[x]=i;
int p=tu[x][i].p,vid=tu[x][i].vid,w=tu[x][i].w;
if(!v[vid]||dis[p]!=dis[x]+w||ty[p]) continue;
int now=dinic(p,min(res,v[vid]));
v[vid]-=now,v[vid^1]+=now;
res-=now;
if(!res) break;
}
return flow-res;
}