首页 > 其他分享 >AtCoder Grand Contest 023

AtCoder Grand Contest 023

时间：2023-09-27 19:15:08浏览次数：35  
标签：AtCoder return Contest int res long 023 include MOD

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;
}

标签：AtCoder,return,Contest,int,res,long,023,include,MOD
From： https://www.cnblogs.com/zhou-jk/p/17733476.html

相关文章

  • AtCoder Grand Contest 024
    A-Fairness每次操作后\(a_i-b_i=b_{i-1}-a_{i-1}\)，对\(k\)的奇偶性讨论一下即可。#include<iostream>#include<cstdio>usingnamespacestd;inta,b,c;longlongk;intmain(){scanf("%d%d%d%lld",&a,&b,&c,&k);if(k%2==0)......
  • AtCoder Grand Contest 021
    A-DigitSum2要么是\(n\)要么是\(n\)的第一位后面加上若干个\(9\)。#include<iostream>#include<cstdio>#include<cmath>usingnamespacestd;longlongn;intcalc(longlongx){if(x==0)return0;intsum=0;while(x)sum+=x......
  • AtCoder Regular Contest 102
    C-TriangularRelationship枚举\(a\bmodk\)的值，\(b\bmodk,c\bmodk\)的值也就确定了，算下贡献就好了。#include<iostream>#include<cstdio>usingnamespacestd;intn,k;intmain(){ scanf("%d%d",&n,&k); longlongans=0; for(inta=0;......
  • ACL Contest 1
    A-ReachableTowns现把城市按照\(x_i\)排序将第一维去掉。对于每个联通块，将单调栈将每个联通块中\(y_i\)最小的那个存下来。每次新加入一个点\(i\)相当于前面的\(\lty_i\)的位置合并成一个联通块。具体地，将单调栈中所有\(\lty_i\)的点弹出，并查集合并一下，加入弹出......
  • AtCoder Regular Contest 103
    C-////如果奇数和偶数出现的颜色的最大值相同一边取最大值和一边取次大值，否则两边都选最大值即可。#include<iostream>#include<cstdio>#include<algorithm>usingnamespacestd;constintN=100005;intn,m;intv[N];intc[N];intmain(){ scanf("%d",&n); for(in......
  • DISCO Presents Discovery Channel Code Contest 2020 Qual
    A-DDCCFinals直接模拟即可。#include<iostream>#include<cstdio>usingnamespacestd;intx,y;intmain(){ scanf("%d%d",&x,&y); intans=0; if(x==1)ans+=30; elseif(x==2)ans+=20; elseif(x==3)ans+=10; if(y==1)ans+=30; ......
  • 2023-2024-1 20231402 《计算机基础与程序设计》第1周学习总结
    2023-2024-120231402《计算机基础与程序设计》第1周学习总结作业信息班级2023-2024-1-计算机基础与程序设计作业要求2023-2024-1计算机基础与程序设计第1周作业作业目标浏览教材并提出问题作业正文https://www.cnblogs.com/lsh0815/p/17731540.html教材学习中提出的问......
  • diverta 2019 Programming Contest
    A-ConsecutiveIntegers答案为\(n-k+1\)。#include<iostream>#include<cstdio>usingnamespacestd;intn,k;intmain(){ scanf("%d%d",&n,&k); printf("%d",n-k+1); return0;}B-RGBBoxes枚举\(r,g\)，判断一下对应的......
  • 2023 Bonree ONE 秋季产品发布会：亮点抢先看！
    ......
  • 2023年9月中旬大模型新动向集锦
    2023年9月中旬大模型新动向集锦2023.9.20版权声明：本文为博主chszs的原创文章，未经博主允许不得转载。1、微软发布13亿参数小模型phi-1.5微软研究院于2023年9月11日发布了名为phi-1.5的全新预训练语言模型，共有13亿个参数，适用于QA问答、聊天格式和代码等等场景。phi-1.5采用来......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99