AGC001 做题记录

AGC001 做题记录¶

A - BBQ Easy¶

贪心得能取到的最大值为 $L_1+L_3+L_5+\cdots+L_{2N-1}$ ，简单计算并输出即可。

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;
bool cmp(int x,int y){return x<y;}
int main(){
    int n,a[205],ans=0;
    cin>>n;
    rep(i,1,2*n)cin>>a[i];
    sort(a+1,a+2*n+1,cmp);
    for(int i=1;i<=2*n;i+=2){
        ans+=a[i];
    }
    cout<<ans<<endl;
    return 0;
}

B - Mysterious Light¶

很有意思的数学题。首先发现光线在两次反射过后会进入一个边长为 $(x,y)$ $(x>y)$ 的平行四边形，再经过两次反射后 $(x-y,y)$ 。发现这个过程类似欧几里得算法，边长会进行辗转相除，所以我们可以考虑一个类似的递归函数计算答案。

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
ll ans;
inline void dfs(ll x,ll y){
    if(x%y==0){
        ans+=x*2-y;
        return;
    }else{
        ans+=(x-x%y)*2;
        dfs(y,x%y);
    }
}
int main(){
    ll n=read(),x=read();
    ans=n;
    dfs(max(n-x,x),min(n-x,x));
    cout<<ans<<endl;
    return 0;
}

C - Shorten Diameter¶

又一道很不错的思维题。首先观察数据范围，发现时间复杂度大概为 $O(N^2)$ 以下。考虑直径的几何定义（大草），我们枚举这个树的圆心（草*2），画一个半径为 $K/2$ 的圆，并且把圆外的点删掉，判断删掉的点数的最小值。这样的做法是 $O(N^2)$ 的。特别地，当 $K$ 为奇数时我们把一条边当做圆心。

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int N=2e3+5;
vector<int> G[N];
int n,k,ans,tot;
inline void dfs(int u,int fa,int dep){
    ++tot;
    if(dep==0)return;
    for(int v:G[u]){
        if(v==fa)continue;
        dfs(v,u,dep-1);
    }
}
int main(){
    n=read(),k=read();
    rep(i,1,n-1){
        int u=read(),v=read();
        G[u].push_back(v);
        G[v].push_back(u);
    }
    if(k%2==0){
        rep(i,1,n){
            tot=0;dfs(i,0,k/2);
            ans=max(ans,tot);
        }
    }else{
        rep(i,1,n){
            for(int j:G[i]){
                tot=0;
                dfs(i,j,k/2);dfs(j,i,k/2);
                ans=max(ans,tot);
            }
        }
    }
    cout<<n-ans<<endl;
    return 0;
}

D - Arrays and Palindrome¶

很有MO风格的题目。一个 $[l,r]$ 之间的回文条件相当于给出了 $s_l=s_r,s_{l+1}=s_{r-1},\dots$ 总共 $\lfloor \dfrac{a_i}{2}\rfloor$ 个限制。把这些限制看作边，那么仅当所有点在同一个连通块里时每个字符必须相等，这意味着需要至少 $n-1$ 条边。如果 $a_i$ 中有三个奇数，那么会浪费掉 $1.5$ 条边，显然不合法。

下面考虑构造。发现如果 $[1,n-1],[1,n]$ 都是回文串，那么所有元素相同。于是可以把 $a$ 中的奇数放到头或尾，$b$ 数组的头和尾分别 $+1,-1$，其他元素和 $a$ 数组相同。这样类似错位摆放的正确性是显然的。

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int n,m,a[105],b[105],tot,cnt[2];
bool cmp(int x,int y){return x%2>y%2;}
int main(){
    n=read(),m=read();
    rep(i,1,m){
        a[i]=read();
        ++cnt[a[i]&1];
    }
    if(m==1){
        if(a[1]==1)printf("1\n1\n1\n");
        else printf("%d\n%d\n%d %d\n",a[1],2,1,a[1]-1);
        return 0;
    }
    if(cnt[1]>2)return puts("Impossible"),0;
    sort(a+1,a+m+1,cmp);
    printf("%d ",a[1]);
    rep(i,3,m)printf("%d ",a[i]);
    printf("%d\n",a[2]);
    b[++tot]=a[1]+1;
    rep(i,3,m)b[++tot]=a[i];
    if(a[2]>1)b[++tot]=a[2]-1;
    printf("%d\n",tot);
    rep(i,1,tot)printf("%d ",b[i]);
    return 0;
}

E - BBQ Hard¶

的暴力计算不是我们想要的。看到形如 $\binom{x+y}{x}$ 的形式的数求和，想到经典的格路计数问题。这等价于从 $(0,0)$ 走到 $(x,y)$ 的方案数。于是这变成了求 $(0,0)$ 到所有 $(a_i+a_j,b_i+b_j)$ 的路径数之和。可以通过减少终点数来优化，平移路径到 $(-a_i,-b_i)\rightarrow(a_j,b_j)$ 。可以用简单的dp计算，最后去掉 $i=j$ 时的答案即可。

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int N=2e5+5,S=2e3+5,P=1e9+7,inv2=5e8+4;
ll fpow(ll x,ll y){
    ll res=1;
    while(y){
        if(y&1)res=res*x%P;
        y>>=1;x=x*x%P;
    }
    return res;
}
int fac[8050],ifac[8050];
ll C(int n,int m){return 1ll*fac[n]*ifac[m]%P*ifac[n-m]%P;}
int n,a[N],b[N],dp[4050][4050];
ll ans;
int main(){
    n=read();
    rep(i,1,n){
        a[i]=read(),b[i]=read();
        ++dp[S-a[i]][S-b[i]];
    }
    fac[0]=1;
    rep(i,1,8000)fac[i]=1ll*fac[i-1]*i%P;
    ifac[8000]=fpow(fac[8000],P-2);
    per(i,7999,0)ifac[i]=1ll*ifac[i+1]*(i+1)%P;
    rep(i,1,S<<1)rep(j,1,S<<1){
        dp[i][j]=(dp[i][j]+(dp[i-1][j]+dp[i][j-1])%P)%P;
    }
    rep(i,1,n){
        ans=(ans+dp[S+a[i]][S+b[i]])%P;
        ans=(ans-C(2*a[i]+2*b[i],2*a[i]))%P;
    }
    ans=(ans+P)%P*inv2%P;
    cout<<ans<<endl;
    return 0;
}

F - Wide Swap¶

$i,j$ 两个位置能交换的条件为 $|i-j|\ge K$ 且 $|P_i-P_j|= 1$ ，这个条件太玄妙了，考虑构造排列 $Q$ 满足 $Q_{P_i}=i$ ，那么对于 $Q$ ，$|Q_i-Q_j|\ge K$ 且 $|i-j|=1$ 即 $i,j$ 相邻时，我们可以交换。而求出字典序最小的 $P$ 也就等价于优先考虑 $1$ 在 $Q$ 上的下标最靠前，然后考虑 $2$ 的下标，以此类推。

于是我们发现对于所有在 $Q$ 中差值小于 $K$ 的数对 $(u,v)$ ，它们无法交换，也就是相对位置被固定了。对于这样的数对 $(u,v)$ ，我们把在 $Q$ 中出现较前的数向出现较后的数连一条有向边，不难发现这样建图会构成一张 $DAG$ 。 $Q$ 可以转换成任意一个满足该图拓扑序的序列。

注意到 $Q$ 的要求并不是简单的字典序最小，因此直接建图后贪心取最小值是错误的，正确的做法类似 [HNOI2015]菜肴制作，应当建反图后求反图中字典序最大的排列。最后还有一个问题，如果我们对所有 $|u-v|< K$ 都连边，边数是 $O(NK)$ 的，所以不能显式建图。

首先把 $Q$ 上建反图换到原序列上，类似的，即对所有点 $i$ 连上 $\{j||i-j|<K,P_j<P_i\}$ ，若点 $i$ 入度为 $0$ ，可以发现在区间 $(i-K,i+K)$ 上 $P_i$ 最大。用大根堆维护入度为 $0$ 的点集，线段树维护区间最值，当删除点 $i$ 时，判断 $(i-K,i),(i,i+K)$ 两个区间的最大值中是否有入度变为 $0$ 。

时间复杂度：$O(N\log N)$ 。

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define li (i<<1)
#define ri (i<<1|1)
#define mid (l+r>>1)
#define ls li,l,mid
#define rs ri,mid+1,r
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int N=5e5+5,inf=0x3f3f3f3f,M=2e6+5;
int n,k,P[N],Ans[N],mx[M];
void upd(int i){mx[i]=P[mx[li]]>P[mx[ri]]?mx[li]:mx[ri];}
void Build(int i,int l,int r){
    if(l==r)return mx[i]=l,void();
    Build(ls),Build(rs);upd(i);
}
void del(int i,int l,int r,int p){
    if(l==r)return mx[i]=0,void();
    p<=mid?del(ls,p):del(rs,p);upd(i);
}
int Q(int i,int l,int r,int a,int b){
    if(r<a||b<l)return 0;
    if(a<=l&&r<=b)return mx[i];
    int v1=Q(ls,a,b),v2=Q(rs,a,b);
    return P[v1]>P[v2]?v1:v2;
}
bool vis[N];
priority_queue<int> pq;
inline void check(int id){
    if(vis[id])return;
    if(Q(1,1,n,id-k+1,id+k-1)==id){
        pq.push(id);vis[id]=1;
    }
}
int main(){
    n=read(),k=read();
    rep(i,1,n)P[i]=read();
    P[0]=-inf;
    Build(1,1,n);
    rep(i,1,n)check(i);
    for(int i=n;i>=1;i--){
        int u=pq.top();pq.pop();
        Ans[u]=i;del(1,1,n,u);
        int pos;
        if((pos=Q(1,1,n,u-k+1,u-1)))check(pos);
        if((pos=Q(1,1,n,u+1,u+k-1)))check(pos);
    }
    rep(i,1,n)printf("%d\n",Ans[i]);
    return 0;
}

AGC001 做题记录