526互联

AtCoder Grand Contest 023

发布时间 2023-09-27 19:06:23作者: Zhou_JK

A - Zero-Sum Ranges

令 \(s_n=\sum\limits_{i=1}^n a_i\)，相当于找满足 \(l\le r,s_r-s_{l-1}\) 的点对 \((l,r)\) 的个数，直接搞就完事了。

#include<iostream>
#include<cstdio>
#include<unordered_map>
using namespace std;
const int N=200005;
int n;
int a[N];
long long sum[N];
unordered_map<long long,int>pre;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        sum[i]=sum[i-1]+a[i];
    long long ans=0;
    pre[0]++;
    for(int i=1;i<=n;i++)
        ans+=pre[sum[i]],pre[sum[i]]++;
    printf("%lld",ans);
    return 0;
}

B - Find Symmetries

对于一条斜率为 \(-1\) 的斜线上的点是等价的，枚举这条直线，暴力判断是否合法即可。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=305;
int n;
char s[N+N][N+N];
int solve(int sx,int sy)
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(s[sx+i-1][sy+j-1]!=s[sx+j-1][sy+i-1]) return 0;
    if(sx==1) return n-sy+1;
    else return n-sx+1;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%s",s[i]+1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            s[i+n][j]=s[i][j+n]=s[i+n][j+n]=s[i][j];
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        int j=1;
        ans+=solve(i,j);
    }
    for(int j=2;j<=n;j++)
    {
        int i=1;
        ans+=solve(i,j);
    }
    printf("%d",ans);
    return 0;
}

C - Painting Machines

考虑计算恰好在第 \(i\) 步停止的方案数。

可以发现，最后两个机器之间间隔为 \(1\) 或 \(0\)。总共 \(i\) 个机器，头尾机器的位置已经确定，总共 \(i-1\) 个空，放入 \(n-1-i\) 个空，方案数为 \(C_{i-1}^{n-i-1}\)。

\(k\) 个机器可以随便排列，后面 \(n-1-k\) 个机器也可以随便排列，所以还要乘上 \(k!(n-1-k)!\)。

但是你发现这有可能将 \(1\sim i-1\) 步停止的方案也算进去，减掉就好了。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1000005;
const int MOD=1000000007;
int n;
int ksm(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1) res=1LL*res*a%MOD;
        a=1LL*a*a%MOD,b>>=1;
    }
    return res;
}
int fac[N],inv[N];
void init(int n=1000000)
{
    fac[0]=1;
    for(int i=1;i<=n;i++)
        fac[i]=1LL*fac[i-1]*i%MOD;
    inv[n]=ksm(fac[n],MOD-2);
    for(int i=n;i>=1;i--)
        inv[i-1]=1LL*inv[i]*i%MOD;
    return;
}
int C(int n,int m)
{
    if(m>n) return 0;
    else return 1LL*fac[n]*inv[m]%MOD*inv[n-m]%MOD;
}
int f[N];
int main()
{
    init();
    scanf("%d",&n);
    for(int i=1;i<=n-1;i++)
        f[i]=1LL*C(i-1,n-i-1)*fac[i]%MOD*fac[n-i-1]%MOD;
    for(int i=n-1;i>=1;i--)
        f[i]=(1LL*f[i]-f[i-1]+MOD)%MOD;
    int ans=0;
    for(int i=1;i<=n-1;i++)
        ans=(ans+1LL*f[i]*i)%MOD;
    printf("%d",ans);
    return 0;
}

D - Go Home

最后肯定是到 \(1\) 或 \(n\)，肯定是先走到人数多的那边，少的一方肯定是要帮着多的一方尽快到达家然后他们再回家。

我们可以看做是少的一方的人变成了多的一方的人，就可以变成一个子问题，递归解决即可。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=100005;
int n,s;
int x[N];
long long p[N];
long long solve(int l,int r,int t)
{
    if(s<=x[l]) return (long long)x[r]-s+abs((long long)x[t]-x[r]);
    if(s>=x[r]) return (long long)s-x[l]+abs((long long)x[t]-x[l]);
    if(p[l]>=p[r])
    {
        p[l]+=p[r];
        return solve(l,r-1,l)+(t==r?x[r]-x[l]:0);
    }
    else
    {
        p[r]+=p[l];
        return solve(l+1,r,r)+(t==l?x[r]-x[l]:0);
    }
}
int main()
{
    scanf("%d%d",&n,&s);
    for(int i=1;i<=n;i++)
        scanf("%d%lld",&x[i],&p[i]);
    if(s<=x[1]) printf("%lld",(long long)x[n]-s);
    else if(s>=x[n]) printf("%lld",(long long)s-x[1]);
    else if(p[1]<p[n]) printf("%lld",solve(1,n,1));
    else printf("%lld",solve(1,n,n));
    return 0;
}

E - Inversions

考虑按照 \(a_i\) 从小到大填数，令 \(b_i\) 表示 \(a_i\) 的排名，那么总方案数为

\[\prod\limits_{i=1}^n(a_i-b_i+1) \]

记为 \(S\)。

考虑一个点对 \((i,j)\) 的贡献，令 \(c_i\) 表示 \(a_i\) 从小到大排序后第 \(i\) 个位置原来在哪里，则 \((i,j)\) 的贡献为：

如果 \(j\le i,a_j\le a_i\)，这和将 \(a_i\) 改为 \(a_j\) 的方案数是相同的，那么就可以用 \(a_i=a_j\) 的方案数除以 \(2\) 来计算贡献：

\[\frac{S}{2}\cdot\frac{a_j-b_j}{a_i-b_i+1}\cdot\left(\prod\limits_{k=b_j+1}^{b_i-1}\frac{a_{c_k}-k}{a_{c_k}-k+1}\right) \]

如果 \(j\gt i,a_j\le a_i\)，我们可以求 \(j\le i,a_j\le a_i\) 时的方案数，用总方案数减去它：

\[S-\frac{S}{2}\cdot\frac{a_j-b_j}{a_i-b_i+1}\cdot\left(\prod\limits_{k=b_j+1}^{b_i-1}\frac{a_{c_k}-k}{a_{c_k}-k+1}\right) \]

这个东西 \(a_j-b_j\) 和 \(a_{c_k}-k\) 可能为 \(0\)，直接前缀和可能不太好搞。

考虑维护两个式子中相同的那个部分，按照 \(a_i\) 从小到大扫，每次相当于全局乘上 \(\frac{a_i-b_i}{a_i-b_i+1}\)，将 \(i\) 位置修改为 \(a_i-b_i\)，然后区间求和，线段树维护即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<unordered_map>
#include<algorithm>
using namespace std;
const int N=200005;
const int MOD=1000000007;
int n;
int a[N],b[N],c[N];
int ksm(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1) res=1LL*res*a%MOD;
        a=1LL*a*a%MOD,b>>=1;
    }
    return res;
}
int getinv(int x)
{
    return ksm(x,MOD-2);
}
struct BIT
{
    int C[N];
    BIT()
    {
        memset(C,0,sizeof(C));
        return;
    }
    int lowbit(int x)
    {
        return x&-x;
    }
    void add(int x,int y)
    {
        for(int i=x;i<=n;i+=lowbit(i))
            C[i]=(C[i]+y)%MOD;
        return;
    }
    int getsum(int x)
    {
        int res=0;
        for(int i=x;i>0;i-=lowbit(i))
            res=(res+C[i])%MOD;
        return res;
    }
    int query(int l,int r)
    {
        return (getsum(r)-getsum(l-1)+MOD)%MOD;
    }
}TC;
struct Segment_Tree
{
    struct Node
    {
        int l,r;
        int sum,tag;
    }tree[N<<2];
    void push_up(int i)
    {
        tree[i].sum=(tree[i*2].sum+tree[i*2+1].sum)%MOD;
        return;
    }
    void mul(int i,int v)
    {
        tree[i].sum=1LL*tree[i].sum*v%MOD;
        tree[i].tag=1LL*tree[i].tag*v%MOD;
        return;
    }
    void push_down(int i)
    {
        if(tree[i].tag==1) return;
        mul(i*2,tree[i].tag);
        mul(i*2+1,tree[i].tag);
        tree[i].tag=1;
        return;
    }
    void build(int i,int l,int r)
    {
        tree[i].l=l,tree[i].r=r;
        tree[i].tag=1;
        if(l==r)
        {
            tree[i].sum=0;
            return;
        }
        int mid=(l+r)/2;
        build(i*2,l,mid);
        build(i*2+1,mid+1,r);
        push_up(i);
        return;
    }
    void modifyadd(int i,int u,int v)
    {
        if(tree[i].l==tree[i].r)
        {
            tree[i].sum=(tree[i].sum+v)%MOD;
            return;
        }
        push_down(i);
        if(u<=tree[i*2].r) modifyadd(i*2,u,v);
        else modifyadd(i*2+1,u,v);
        push_up(i);
        return;
    }
    void modifymul(int i,int l,int r,int v)
    {
        if(l<=tree[i].l&&tree[i].r<=r) return mul(i,v);
        push_down(i);
        if(l<=tree[i*2].r) modifymul(i*2,l,r,v);
        if(r>=tree[i*2+1].l) modifymul(i*2+1,l,r,v);
        push_up(i);
        return;
    }
    int query(int i,int l,int r)
    {
        if(l>r) return 0;
        if(l<=tree[i].l&&tree[i].r<=r) return tree[i].sum;
        push_down(i);
        int res=0;
        if(l<=tree[i*2].r) res=(res+query(i*2,l,r))%MOD;
        if(r>=tree[i*2+1].l) res=(res+query(i*2+1,l,r))%MOD;
        return res;
    }
}T;

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        c[i]=i;
    sort(c+1,c+n+1,[=](const int &x,const int &y){return a[x]<a[y];});
    for(int i=1;i<=n;i++)
        b[c[i]]=i;
    for(int i=1;i<=n;i++)
        if(a[i]<b[i])
        {
            printf("0");
            return 0;
        }
    int sum=1;
    for(int i=1;i<=n;i++)
        sum=1LL*sum*(a[i]-b[i]+1)%MOD;
    T.build(1,1,n);
    int ans=0;
    int inv2=getinv(2);
    for(int k=1;k<=n;k++)
    {
        ans=(ans+1LL*T.query(1,1,c[k]-1)*getinv(a[c[k]]-b[c[k]]+1)%MOD*sum%MOD*inv2)%MOD;
        ans=(ans+1LL*TC.query(c[k]+1,n)*sum)%MOD;
        ans=(ans-1LL*T.query(1,c[k]+1,n)*getinv(a[c[k]]-b[c[k]]+1)%MOD*sum%MOD*inv2%MOD+MOD)%MOD;
        TC.add(c[k],1);
        T.modifymul(1,1,n,1LL*(a[c[k]]-b[c[k]])*getinv(a[c[k]]-b[c[k]]+1)%MOD);
        T.modifyadd(1,c[k],a[c[k]]-b[c[k]]);
    }
    printf("%d",ans);
    return 0;
}

F - 01 on Tree

把一个节点看作一个遍历的序列，初始时为 \(v_i\)，每次将一个点合并到它的父亲上，表示选了父亲之后马上就选它，一直这样操作直到剩下根节点。可以发现这样操作方案可以和所有遍历方案一一对应。

考虑合并两个节点，不妨设第一个节点有 \(a_1\) 个 \(1\)，\(b_1\) 个 \(1\)，第二个节点有 \(a_1\) 个 \(1\)，\(b_1\) 个 \(0\)。第一个放在第二个前的贡献为 \(b_1a_2\)；反之贡献为 \(b_2a_1\)。

假如第一个放在第二个前面更优，即 \(b_1a_2\le b_2a_1\Leftrightarrow \frac{a_1}{b_1}\ge \frac{a_2}{b_2}\)。

每次找到最大的 \(\frac{a_i}{b_i}\)，合并到父亲，用 std::set 维护一下就好了。

#include<iostream>
#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;
const int N=200005;
int n;
int fa[N];
int v[N];
struct Node
{
    int a,b;
    bool operator < (const Node &rhs)const
    {
        return (long long)a*rhs.b>(long long)b*rhs.a;
    }
}c[N];
multiset<pair<Node,int>>S;
int f[N];
int getf(int v)
{
    if(v==f[v]) return v;
    else return f[v]=getf(f[v]);
}
int nxt[N];
int main()
{
    scanf("%d",&n);
    for(int i=2;i<=n;i++)
        scanf("%d",&fa[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&v[i]);
    for(int i=1;i<=n;i++)
        if(v[i]==0) c[i].a++;
        else c[i].b++;
    for(int i=1;i<=n;i++)
        f[i]=i;
    for(int i=2;i<=n;i++)
        S.insert({c[i],i});
    long long ans=0;
    while(!S.empty())
    {
        auto [p,v]=*S.begin();
        S.erase(S.begin());
        int u=getf(fa[v]);
        f[v]=f[fa[v]];
        if(u!=1) S.erase(S.find({c[u],u}));
        ans+=(long long)c[u].b*c[v].a;
        c[u].a+=c[v].a,c[u].b+=c[v].b;
        if(u!=1) S.insert({c[u],u});
    }
    printf("%lld",ans);
    return 0;
}