2023牛客暑期多校训练营4

H Merge the squares!

题意

给定 $n\times n$ 个 $1\times1$ 的小正方形组成的大正方形，每次合并不超过 $50$ 个小正方形得到一个大正方形。问如何合成能得到 $n\times n$ 的大正方形。

数据范围：$1\leq n\leq 1000$。

题解

为了得到一个 $i\times i$ 的正方形，考虑这样进行合并：分拆成 $j\times j,(i-j)\times j,j\times(i-j),(i-j)\times(i-j)$ 四个部分。也就是两个小正方形和两个相同的矩形。两个小正方形是子问题，可以递归解决，我们考虑处理矩形：有一种比较直觉的策略，即辗转相减。以长为 $a$，宽为 $b$ 的矩形为例，切出一些 $b\times b$ 的小正方形，然后得到一个长为 $b$，宽为 $a\bmod b$ 的小矩形。只要这些总和不超过 $24$（$24\times 2+1+1$），就是一种合法的划分方式。幸运地是，对于每个 $i$ 都能找到一个合法的 $j$。剩下的只是一些模拟工作了。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1005;
int f[N];
vector<array<int,3>> ans;
bool check(int x,int y)
{
    if(!y) return x<=7;
    int cnt=0,tmp;
    while(y)
    {
        cnt+=x/y;
        tmp=x%y,x=y,y=tmp;
    }
    return cnt<=24;
}
void solve1(int x,int y,int a,int b);
void solve2(int x,int y,int a,int b);
void solve(int x,int y,int k)
{
    if(k==1) return;
    ans.push_back({x,y,k});
    if(!f[k]) return;
    solve1(x,y+f[k],f[k],k-f[k]),solve2(x+f[k],y,k-f[k],f[k]);
    solve(x,y,f[k]),solve(x+f[k],y+f[k],k-f[k]);
}
void solve1(int x,int y,int a,int b)
{
    if(a<=1) return;
    for(int i=0;i<=b-a;i+=a) solve(x,y+i,a);
    solve2(x,y+b/a*a,a,b%a);
}
void solve2(int x,int y,int a,int b)
{
    if(b<=1) return;
    for(int i=0;i<=a-b;i+=b) solve(x+i,y,b);
    solve1(x+a/b*b,y,a%b,b);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    for(int i=2;i<=n;i++)
        for(int j=0;j<=i/2;j++)
            if(check(i-j,j))
            {
                f[i]=j;
                break;
            }
    solve(1,1,n);
    reverse(ans.begin(),ans.end());
    cout<<ans.size()<<'\n';
    for(auto i:ans) cout<<i[0]<<' '<<i[1]<<' '<<i[2]<<'\n';
    return 0;
}

I Portal 3

题意

给定 $n$ 个点，点 $i$ 与点 $j$ 的距离为 $d_{i,j}$。现在可以选择两个点 $x,y$ 使得 $d_{x,y}=d_{y,x}=0$。另给定一个序列 $a_1,a_2,\cdots,a_k$，要求从 $a_1$ 出发依次走到每个点，直到最终到达 $a_k$。求最短行走距离。

数据范围：$2\leq n\leq 500,2\leq k\leq 10^6$。

题解

首先Floyd求出两点间的距离 $d_{i,j}$，并且求出在行走序列中每条边 $(i,j)$ 出现的次数 $c(i,j)$。然后，考虑枚举修改的边 $(u,v)$，那么对于每对 $(s,t)$，这次修改的贡献就是 $c_{s,t}\times\max(0,\max(d_{s,t}-d_{s,u}-d_{v,t},d_{s,t}-d_{s,v}-d_{u,t}))$，而后面两项最多只有一项为正，所以可以把贡献拆开算，即 $c_{s,t}\times(\max(0,d_{s,t}-d_{s,u}-d_{v,t})+\max(0,d_{s,t}-d_{s,v}-d_{u,t}))$。考虑计算 $c_{s,t}\times(\max(0,d_{s,t}-d_{s,u}-d_{v,t}))$：我们可以枚举 $s$，然后按 $d_{s,u}$ 对 $u$ 进行排序。然后枚举 $t$ 和 $v$（$v$ 按 $d_{v,t}$ 的顺序枚举），不难发现当 $v$ 变化时，能取到的 $u$ 一定是一段前缀，这就可以用差分维护了。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=505;
int d[N][N],c[N][N];
ll sum,tot[N][N],diff1[N][N],diff2[N][N];
pii tmp[N];
vector<pii> g[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) cin>>d[i][j];
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++) d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
    int lst=0;
    for(int i=1;i<=m;i++)
    {
        int v;cin>>v;
        if(i!=1) c[lst][v]++,sum+=d[lst][v];
        lst=v;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++) 
            g[i].push_back({d[j][i],j});
        sort(g[i].begin(),g[i].end());
    }
    for(int s=1;s<=n;s++)
    {
        memset(diff1,0,sizeof(diff1)),memset(diff2,0,sizeof(diff2));
        for(int u=1;u<=n;u++) tmp[u]={d[s][u],u};
        sort(tmp+1,tmp+n+1);
        for(int t=1;t<=n;t++)
        {
            int j=n;
            for(int i=0;i<n;i++)
            {
                int v=g[t][i].second;
                ll cur=d[s][t]-g[t][i].first;
                while(j>=1&&cur-tmp[j].first<0) j--;
                diff1[1][v]+=c[s][t]*cur,diff1[j+1][v]-=c[s][t]*cur;diff2[1][v]+=c[s][t],diff2[j+1][v]-=c[s][t];
            }
        }
        for(int i=1;i<=n;i++)  
            for(int v=1;v<=n;v++)
            {
                diff1[i][v]+=diff1[i-1][v],diff2[i][v]+=diff2[i-1][v];
                tot[tmp[i].second][v]+=diff1[i][v];
                tot[tmp[i].second][v]-=diff2[i][v]*tmp[i].first;
            }
    }
    ll mx=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) mx=max(mx,tot[i][j]+tot[j][i]);
    cout<<sum-mx<<'\n';
    return 0;
}