ABC做题记录

黄大师 / 2023-08-31 / 原文

做之前没有想到AT的题还是有一定难度的，加油！

ABC317

E - Avoid Eye Contact

随便bfs一下就好

F - Nim

考虑数位dp，用 $dp[x][r1][r2][r3][d1][d2][d3][z1][z2][z3]$ 记录位数，余数，最高位限制，前导0

用记忆化搜索实现

#include <iostream>
#include <cstring>
#define ll long long
using namespace std;
const int P=998244353;
ll n,a,b,c,top,t[120],k1[110],k2[110],k3[110];
ll dp[120][11][11][11][2][2][2][2][2][2];
ll dfs(int x,int r1,int r2,int r3,int d1,int d2,int d3,int z1,int z2,int z3)
{
    if(x==0) return !r1&&!r2&&!r3&&z1&&z2&&z3;
    if(dp[x][r1][r2][r3][d1][d2][d3][z1][z2][z3]!=-1) return dp[x][r1][r2][r3][d1][d2][d3][z1][z2][z3];
    int l1=d1?t[x]:1,l2=d2?t[x]:1,l3=d3?t[x]:1;ll ans=0;
    if(l2==1&&l3==1) ans=(ans+dfs(x-1,r1,(r2+k2[x-1])%b,(r3+k3[x-1])%c,d1&&(0==l1),d2&&(1==l2),d3&&(1==l3),z1|0,z2|1,z3|1))%P;
    if(l1==1&&l2==1) ans=(ans+dfs(x-1,(r1+k1[x-1])%a,(r2+k2[x-1])%b,r3,d1&&(1==l1),d2&&(1==l2),d3&&(0==l3),z1|1,z2|1,z3|0))%P;
    if(l1==1&&l3==1) ans=(ans+dfs(x-1,(r1+k1[x-1])%a,r2,(r3+k3[x-1])%c,d1&&(1==l1),d2&&(0==l2),d3&&(1==l3),z1|1,z2|0,z3|1))%P;
    ans=(ans+dfs(x-1,r1,r2,r3,d1&&(0==l1),d2&&(0==l2),d3&&(0==l3),z1|0,z2|0,z3|0))%P;
    dp[x][r1][r2][r3][d1][d2][d3][z1][z2][z3]=ans;
    return ans;
}
ll get(ll x){
    while(x){
        t[++top]=x%2;
        x/=2;
    }
    return dfs(top,0,0,0,1,1,1,0,0,0);
}
int main()
{
    memset(dp,-1,sizeof(dp));
    cin>>n>>a>>b>>c;
    k1[0]=1;k2[0]=1;k3[0]=1;
    for(int i=1;i<=70;i++){
        k1[i]=k1[i-1]*2%a;
        k2[i]=k2[i-1]*2%b;
        k3[i]=k3[i-1]*2%c;
    }
    cout<<get(n);
    return 0;
}

View Code

G - Rearranging

由于顺序任意，容易想到建图，将每一行与每一列的每个数字连起来，这样就构成了一个二分图，问题就变成了在这张二分图上恰好找到m个完全匹配，所以考虑Hell定理，每次做完一次匹配就把匹配的边删完，如果找不到完全匹配就输出NO

用dinic解决二分图匹配

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N=20010;
const int M=30010;
const int INF=0x3f3f3f3f;
struct node{
    int v,w,nxt;
}E[M];
int n,m,st,ed,head[N],ans[110][110],lv[N],cur[N],top=-1,tp;
void add(int u,int v,int w){
    E[++top].v=v;
    E[top].w=w;
    E[top].nxt=head[u];
    head[u]=top;
    E[++top].v=u;
    E[top].w=0;
    E[top].nxt=head[v];
    head[v]=top;
}
bool bfs()
{
    memset(lv,-1,sizeof(lv));
    memcpy(cur,head,sizeof(head));
    queue<int> q;q.push(st);
    lv[st]=0;
    while(!q.empty()){
        int now=q.front();
        q.pop();
        for(int i=head[now];i!=-1;i=E[i].nxt){
            int v=E[i].v;
            int w=E[i].w;
            if(w>0&&lv[v]==-1){
                lv[v]=lv[now]+1;
                q.push(v);
            }
        }
    }
    return lv[ed]!=-1;
}
int dfs(int now,int flow)
{
    if(now==ed)
        return flow;
    int res=flow;
    for(int i=cur[now];res&&i!=-1;i=E[i].nxt){
        cur[now]=i;
        int v=E[i].v;
        int w=E[i].w;
        if(w>0&&lv[v]==lv[now]+1){
            int c=dfs(v,min(res,w));
            E[i].w-=c;
            E[i^1].w+=c;
            res-=c;
        }
    }
    return flow-res;
}
int dinic()
{
    int ans=0;
    while(bfs())
        ans+=dfs(st,INF);
    return ans;
}
int main()
{
    memset(head,-1,sizeof(head));
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            int k;cin>>k;
            add(i,k+n,1);
        }
    st=2*n+1,ed=2*n+2;tp=top;
    for(int i=1;i<=n;i++)
        add(st,i,1),add(i+n,ed,1);
    for(int i=1;i<=m;i++){
        if(dinic()!=n){
            cout<<"No";
            return 0;
        }
        for(int j=1;j<=tp;j+=2)
            if(E[j].w==1){
                ans[E[j].v][i]=E[j^1].v-n;
                E[j].w=0;
                E[j^1].w=0;
            }
        for(int j=tp+1;j<=top;j+=2)
            if(E[j].w==0){
                E[j].w=1;
                E[j^1].w=0;
            }
    }
    cout<<"Yes\n";
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            printf("%d ",ans[i][j]);
        printf("\n");
    }
    return 0;
 }