Codeforces Round #519 by Botan Investments翻车记

时间：2023-03-08 18:08:54

　　A：枚举答案即可。注意答案最大可达201，因为这个wa了一发瞬间爆炸。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 110

int n,a[N],mx;

int main()

{

/*#ifndef ONLINE_JUDGE

    freopen("a.in","r",stdin);

    freopen("a.out","w",stdout);

#endif*/

    n=read();

    int tot=;

    for (int i=;i<=n;i++) mx=max(mx,a[i]=read()),tot+=a[i];

    for (int i=mx;i<=;i++)

    {

        int cnt=;

        for (int j=;j<=n;j++) cnt+=i-a[j];

        if (cnt>tot) {cout<<i;return ;}

    }

    return ;

}

　　B：看了半天题。枚举即可。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 1010

int n,a[N],b[N],cnt=,c[N];

int main()

{

/*#ifndef ONLINE_JUDGE

    freopen("a.in","r",stdin);

    freopen("a.out","w",stdout);

#endif*/

    n=read();

    for (int i=;i<=n;i++) a[i]=read();

    for (int k=;k<=n;k++)

    {

        bool flag=;

        for (int i=;i<=k;i++) b[i]=a[i]-a[i-];

        for (int i=k+;i<=n;i++) if (a[i]-a[i-]!=b[(i-)%k+]) {flag=;break;}

        if (flag) c[++cnt]=k;

    }

    cout<<cnt<<endl;

    for (int i=;i<=cnt;i++) cout<<c[i]<<' ';

    return ;

}

　　C：看了半天题。想了半天。每次都在字符的分界处翻转，就可以得到最优解（即a都在前面b都在后面）。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 1010

int n,a[N];

bool flag[N];

char s[N];

int main()

{

/*#ifndef ONLINE_JUDGE

    freopen("a.in","r",stdin);

    freopen("a.out","w",stdout);

#endif*/

    scanf("%s",s+);

    n=strlen(s+);

    for (int i=;i<=n;i++) a[i]=s[i]=='b';

    for (int i=;i<=n;i++)

    {

        int t=i;

        while (t<n&&a[t+]==a[i]) t++;

        if (t<n||a[i]==) reverse(a+i+,a+t+),flag[t]=;

        i=t;

    }

    for (int i=;i<=n;i++) cout<<flag[i]<<' ';

    return ;

}

　　D：看了半天题。暴力匹配，如果失配这些数不可能再被计入答案。这样分成了很多段，将每段答案加起来即可。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 100010

#define M 12

int n,m,a[M][N],p[M][N],q[];

long long ans;

bool check()

{

    for (int i=;i<=m;i++)

    {

        q[i]++;

        if (q[i]>n) return ;

    }

    for (int i=;i<=m;i++)

    if (a[i][q[i]]!=a[i-][q[i-]]) return ;

    return ;

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("a.in","r",stdin);

    freopen("a.out","w",stdout);

#endif

    n=read(),m=read();

    for (int i=;i<=m;i++)

        for (int j=;j<=n;j++)

        a[i][j]=read(),p[i][a[i][j]]=j;

    for (int i=;i<=n;i++)

    {

        int x=i;

        q[]=i;

        for (int j=;j<=m;j++) q[j]=p[j][a[][i]];

        while (x<n&&check()) x++;

        ans+=1ll*(x-i+)*(x-i+)/;

        i=x;

    }

    cout<<ans;

    return ;

}

　　E：看了半天题。看题时间跟想+码的时间差不多了。首先给出的那些边显然可以直接排除。现在要求的是ansi=Σmin(xi+yj,xj+yi)，可以将其变成ansi=Σmin(xi-yi-xj+yj,0)+xj+yi。这样min里面的东西只需要二分查一个前缀和。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 300010

int n,m,t=;

long long ans[N],b[N],pre[N],sum;

struct data{int x,y;

}a[N];

int main()

{

#ifndef ONLINE_JUDGE

    freopen("a.in","r",stdin);

    freopen("a.out","w",stdout);

#endif

    n=read(),m=read();

    for (int i=;i<=n;i++) sum+=a[i].x=read(),a[i].y=read(),b[i]=a[i].y-a[i].x;

    sort(b+,b+n+);

    for (int i=;i<=n;i++) pre[i]=pre[i-]+b[i];

    for (int i=;i<=m;i++)

    {

        int x=read(),y=read();

        ans[x]-=min(a[x].x+a[y].y,a[x].y+a[y].x),ans[y]-=min(a[x].x+a[y].y,a[x].y+a[y].x);

    }

    /*for (int i=1;i<=n;i++)

        for (int j=1;j<=n;j++)

        if (i!=j) ans[i]+=min(a[i].x-a[i].y+b[j],0)+a[i].y+a[j].x;*/

    for (int i=;i<=n;i++)

    {

        ans[i]+=sum-a[i].x+1ll*a[i].y*(n-);

        int l=,r=n,t=;

        while (l<=r)

        {

            int mid=l+r>>;

            if (b[mid]+a[i].x-a[i].y<) t=mid,l=mid+;

            else r=mid-;

        }

        ans[i]+=pre[t]+1ll*t*(a[i].x-a[i].y);

    }

    for (int i=;i<=n;i++) printf("%I64d ",ans[i]);

    return ;

}

close

　　F：做法似乎很多。比赛时只想到设f[i]为gcd=i时最少选多少元素，考虑通过与i的gcd数量是i的因子个数来优化，预处理可以向哪转移。这一部分看起来可以瞎优化到不错的效率，然而又wa又T最后弃疗了。

　　题解给的是状压dp，没有太懂（upd：好像也是算方案数）。似乎也有不少随机化做法。

　　感觉最妙的做法还是这样：强化这个题，求选k个数时的方案数。这显然可以莫比乌斯反演，预处理每个数在a中有多少个是其倍数即可，这可以利用调和级数做到log。显然最终答案若存在一定不超过7，于是复杂度O(n+vlogv)。这应该是保证正确性（取模后变成0什么的就算了吧）的最优做法了。把一个判定性问题转化为数数题居然能够简化问题非常有意思。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 300010

#define P 1000000007

int n,a[N],mobius[N],prime[N],tot[N],cnt;

int fac[N],inv[N];

bool flag[N];

int C(int n,int m)

{

    if (m>n) return ;

    return 1ll*fac[n]*inv[m]%P*inv[n-m]%P;

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("f.in","r",stdin);

    freopen("f.out","w",stdout);

#endif

    n=read();

    for (int i=;i<=n;i++) a[read()]++;

    flag[]=;mobius[]=;

    for (int i=;i<=N-;i++)

    {

        if (!flag[i]) prime[++cnt]=i,mobius[i]=-;

        for (int j=;j<=cnt&&prime[j]*i<=N-;j++)

        {

            flag[prime[j]*i]=;

            if (i%prime[j]==) break;

            else mobius[prime[j]*i]=-mobius[i];

        }

    }

    fac[]=;for (int i=;i<=N-;i++) fac[i]=1ll*fac[i-]*i%P;

    inv[]=inv[]=;for (int i=;i<=N-;i++) inv[i]=P-1ll*(P/i)*inv[P%i]%P;

    for (int i=;i<=N-;i++) inv[i]=1ll*inv[i-]*inv[i]%P;

    for (int i=;i<=N-;i++)

        for (int j=i;j<=N-;j+=i)

        tot[i]+=a[j];

    for (int k=;k<=;k++)

    {

        int ans=;

        for (int i=;i<=N-;i++)

        ans=((ans+mobius[i]*C(tot[i],k))%P+P)%P;

        if (ans) {cout<<k;return ;}

    }

    cout<<-;

    return ;

}

　　这场阅读量实在太大，读题感觉花了快有30min。A wa一发掉了至少30名非常惨了。

　　result：rank 417 rating -6

　　

相关文章