tips:今天全过了

-二分图最大匹配

|1.A

二分图最大匹配模板

|1.B

如果map[i][j]为0，连接i→j
然后二分图最大匹配

|1.C

同B，后二分图最大匹配

|1.D

像国际象棋棋盘一样黑白染色
黑格向白格连日字边，用总点数减去最大匹配

|1.E

同D但是不需要染色，每个点往其他R*C的点连边，用总点数减去最大匹配

-欧拉路

|2.F

模板题

void dfs(int t){
    for(int j=l[t];j<v[t].size();j=max(j+1,l[t])){
        GP i=v[t][j];
        id=abs(i.second);
        if(x[id]) continue;
        x[id]=1;l[t]=j+1;dfs(i.first);
        ans[++c]=i.second;
    }
}

|2.G

同F，由第一个字母向最后一个字母连边，查看有没有欧拉路径

|2.H

名副其实的水题，只需要判入度出度，孤立点，连通块即可

int dfs(int t,int st){
    if(!v[t].size()) return 0;
    int ans=(d[t]&1);x[t]=1;
    for(auto i:v[t]){
        if(x[i]) continue;
        ans+=dfs(i,st); 
    }
    if(t==st) return max(1,ans/2);
    else return ans;
}

2-SAT

|3.K

先讲K，因为是模板

for(int i=1;i<=m;i++){
    char str[105];char qx,qy;
    int qa,qb,qc,qd;
    cin>>str;
    sscanf(str,"%c%d",&qx,&qa);qb=!!(qx-&#039;m&#039;);
    cin>>str;
    sscanf(str,"%c%d",&qy,&qc);qd=!!(qy-&#039;m&#039;);
    if(qb&&qd)
        {ae(qa*2,qc*2-1);ae(qc*2,qa*2-1);}
    if(!qb&&qd)
        {ae(qa*2-1,qc*2-1);ae(qc*2,qa*2);}
    if(qb&&!qd) 
        {ae(qa*2,qc*2);ae(qc*2-1,qa*2-1);}
    if(!qb&&!qd) 
        {ae(qa*2-1,qc*2);ae(qc*2-1,qa*2);}
}
for(int i=1;i<=2*n;i++)
    if(!dfn[i])
        tarj(i);
d1=0;
for(int i=1;i<=n;i++)
    if(col[i*2-1]==col[i*2])
        {d1=1;break;}
if(d1){cout<<"BAD\n";continue;}
cout<<"GOOD\n";

|3.I

建边有区别

qb=1-qb;qd=1-qd;
if(qb&&qd)
    {ae(qa*2,qc*2-1);ae(qc*2,qa*2-1);}
if(!qb&&qd)
    {ae(qa*2-1,qc*2-1);ae(qc*2,qa*2);}
if(qb&&!qd) 
    {ae(qa*2,qc*2);ae(qc*2-1,qa*2-1);}
if(!qb&&!qd) 
    {ae(qa*2-1,qc*2);ae(qc*2-1,qa*2);}

|3.J

估计是全场最难
二分答案，每次验证一次2-SAT

if(qd[i]==1){
    ae(qa[i]*2,qc[i]*2);
    ae(qa[i]*2-1,qc[i]*2-1);
    ae(qc[i]*2,qa[i]*2);
    ae(qc[i]*2-1,qa[i]*2-1);
}else if(qd[i]==0){
    ae(qa[i]*2-1,qc[i]*2);
    ae(qc[i]*2-1,qa[i]*2);
}else if(qd[i]==2){
    ae(qa[i]*2,qc[i]*2-1);
    ae(qc[i]*2,qa[i]*2-1);
}

int ll=0,rr=mm;
while(ll<rr){
    int mid=(ll+rr+1)/2;
    if(bcheck(mid)){
        ll=mid;
    }else{rr=mid-1;}
}
cout<<ll<<&#039;\n&#039;;