AtCoder Beginner Contest 320

Toyota Programming Contest 2023#5（AtCoder Beginner Contest 320）

F - Fuel Round Trip

驾车从坐标 $x_0$ 开到 $x_n$ 再原路返回，车的油箱容量为 $h$，初始油满。在 $x_1\sim x_{n-1}$ 处各有一个加油站，每个加油站最多加油 $f_i$，需要支付 $p_i$，且在来回过程中最多使用一次。求跑完一趟来回的最小花费。

显然比较好的方式是一次性考虑加油站在去回的使用情况，而不是去和回分开来考虑。具体地，设 $dp_{i,j,k}$ 表示去时经过第 $i$ 个加油站油量为 $j$，回时油量为 $k$ ，前 $i$ 个加油站的最小花费。规定在去时已经考虑过在第 $i$ 个加油站加油，在回时尚未考虑。

那么转移就很容易了，我们从 $dp_{0,h,0\sim h}$ 出发，讨论下一个加油站是不用/去时使用/回时使用，进行转移，最后的答案就是 $\underset{j\leq h}\min dp_{n,j,j}$。具体转移可以参考代码：

#include <bits/stdc++.h>
using namespace std;
template<class T> bool ckmin(T& a,const T& b) {return b<a?a=b,1:0;}
const int N=305;
int x[N],p[N],f[N],dp[N][N][N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,h;cin>>n>>h;
    for(int i=1;i<=n;i++) cin>>x[i];
    for(int i=1;i<n;i++) cin>>p[i]>>f[i];
    memset(dp,0x3f,sizeof(dp));
    for(int i=0;i<=h;i++) dp[0][h][i]=0;
    for(int i=0;i<n;i++)
    {
        int d=x[i+1]-x[i];
        for(int j=d;j<=h;j++)
            for(int k=0;k<=h-d;k++)
            { 
                ckmin(dp[i+1][j-d][k+d],dp[i][j][k]);
                ckmin(dp[i+1][min(h,j-d+f[i+1])][k+d],dp[i][j][k]+p[i+1]);
                if(k<h-d) 
                {
                    if(k+d-f[i+1]>=0) 
                        ckmin(dp[i+1][j-d][k+d-f[i+1]],dp[i][j][k]+p[i+1]);
                }
                else
                {
                    for(int kk=max(0,h-f[i+1]);kk<=h;kk++)
                        ckmin(dp[i+1][j-d][kk],dp[i][j][k]+p[i+1]);
                }
            }
    }
    int ans=0x3f3f3f3f;
    for(int i=0;i<=h;i++) ans=min(ans,dp[n][i][i]);
    cout<<(ans==0x3f3f3f3f?-1:ans)<<'\n';
    return 0;
}

G - Slot Strategy 2 (Hard)

有一个 $N$ 个轮子的彩票机，每个轮子长度为 $M$，每一位是数字 $0-9$。轮子每秒滚动一位，每秒可以选择让某个轮子停下不再滚动，轮子定格显示当时的数字，求让所有轮子显示相同数字的最小时间。

考虑判定能否在 $t$ 秒让所有轮子显示相同数字，如果这个问题能够解决，那么原问题可以通过二分处理。

枚举每个数字。构建二分图，左部点为秒数，右部点为轮子。如果某秒数某轮子显示的是对应数字，那么在这两个点之间连一条边。原问题就转化为了最大匹配问题，匹配数为 $N$ 即为合法。

需要注意的是，对于每个轮子，只需要考虑每个数字前 $N$ 次出现就可以了，所以总的边数为 $N^2$，利用 dinic 算法求最大匹配，每次 check 的时间复杂度为 $O(N^3)$。

#include <bits/stdc++.h>
using namespace std;
const int N=105;
const int inf=0x3f3f3f3f;
int n,m;
string s0[N];
int siz[10][N];
vector<int> g[10][N];
int ans=inf;
struct edge
{
    int to,nxt;
    int c;
}e[20*N*N];
int cnt=1,head[5*N*N];
int s,t;
int d[5*N*N],cur[5*N*N];
void add(int u,int v,int c)
{
    e[++cnt]={v,head[u],c};head[u]=cnt;
    e[++cnt]={u,head[v],0};head[v]=cnt;
};
bool bfs()
{
    memset(d,0,sizeof(d));
    queue<int> q;
    d[s]=1;q.push(s);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].to;
            if(d[v]==0&&e[i].c)
            {
                d[v]=d[u]+1;q.push(v);
                if(v==t) return true;
            }
        }
    }
    return false;
}
int dfs(int u,int mf)
{
    if(u==t) return mf;
    int sum=0;
    for(int i=cur[u];i;i=e[i].nxt)
    {
        cur[u]=i;
        int v=e[i].to;
        if(d[v]==d[u]+1&&e[i].c)
        {
            int res=dfs(v,min(mf,e[i].c));
            e[i].c-=res;
            e[i^1].c+=res;
            sum+=res;
            mf-=res;
            if(mf==0) break;
        }
    }
    if(sum==0) d[u]=0;
    return sum;
}
int dinic()
{
    int flow=0;
    while(bfs())
    {
        memcpy(cur,head,sizeof(cur));
        flow+=dfs(s,inf);
    }
    return flow;
}
bool check(int d,int k)
{
    cnt=1;
    memset(head,0,sizeof(head));
    memset(cur,0,sizeof(cur));
    int tot=0;
    map<int,int> mp;
    for(int i=1;i<=n;i++)
    {
        if(mp.find(i)==mp.end()) mp[i]=++tot;
        for(auto j:g[d][i]) 
        {
            if(j>k) continue;
            if(mp.find(j+n+1)==mp.end()) mp[j+n+1]=++tot;
            add(mp[i],mp[j+n+1],1);
        }
    }   
    s=0,t=tot+1;
    for(auto i:mp)
        if(i.first<=n) add(s,i.second,1);
        else add(i.second,t,1);
    return dinic()==n;
}
void solve(int d)
{
    for(int i=1;i<=n;i++)
        if(g[d][i].empty()) return;
    int l=0,r=n*m;
    while(l<r)
    {
        int mid=(l+r)/2;
        if(check(d,mid)) r=mid;
        else l=mid+1;
    }
    if(check(d,l)) ans=min(ans,l);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>s0[i];
    for(int i=1;i<=n;i++)
        for(int j=0;j<m;j++)
            if(siz[s0[i][j]-'0'][i]<n)
            {
                siz[s0[i][j]-'0'][i]++;
                g[s0[i][j]-'0'][i].push_back(j);
            }
    for(int d=0;d<10;d++)
        for(int i=1;i<=n;i++)
        {
            if(siz[d][i]==0||siz[d][i]==n) continue;
            vector<int> tmp;
            for(int j=0;j<n-siz[d][i];j++)
                tmp.push_back(m*(j/siz[d][i]+1)+g[d][i][j%siz[d][i]]);
            for(auto j:tmp) g[d][i].push_back(j);
        }
    for(int d=0;d<10;d++) solve(d);
    cout<<(ans==0x3f3f3f3f?-1:ans)<<'\n';
    return 0;
}