Atcoder Tenka1 Programmer Contest 2019

C

签到题，f[i][0/1]表示以i结尾最后一个为白/黑的最小值，转移显然。

#include<bits/stdc++.h>

using namespace std;

const int N=2e5+;

int n,f[N][];

char s[N];

int main()

{

    scanf("%d",&n);

    scanf("%s",s+);

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

    if(s[i]=='.')

    {

        f[i][]=f[i-][];

        f[i][]=min(f[i-][],f[i-][])+;

    }

    else{

        f[i][]=f[i-][]+;

        f[i][]=min(f[i-][],f[i-][]);

    }

    printf("%d\n",min(f[n][],f[n][]));

}

D

方案数=总方案数-不能拼成三角形的方案数。不能拼成三角形，即最长边大于等于边总和的一半。于是可以f[i]表示以i为最长边能组成三角形的方案数，g[i]表示凑成长度为i的边方案。f[0]=2^n，g[0]=1，然后每次转移f除以2即可。注意讨论最长边为总和一半的情况（没讨论WA了一发）。

#include<bits/stdc++.h>

using namespace std;

const int N=,mod=,inv2=,inv3=;

int n,ans,sum,lim,pw2[N],pw3[N],a[N],f[N*N],g[N*N];

int main()

{

    scanf("%d",&n);

    ans=f[]=g[]=;

    for(int i=;i<=n;i++)f[]=2ll*f[]%mod;

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

    {

        ans=3ll*ans%mod;

        scanf("%d",&a[i]);

        sum+=a[i];

        for(int j=sum;j>=a[i];j--)

        f[j]=(f[j]+1ll*f[j-a[i]]*inv2)%mod,g[j]=(g[j]+g[j-a[i]])%mod;

    }

    lim=(sum+)/;

    for(int i=lim;i<=sum;i++)ans=(ans-3ll*f[i]%mod+mod)%mod;

    if(sum%==)ans=(ans+3ll*g[lim])%mod;

    printf("%d\n",ans);

}

E

很容易发现答案只有2种：1、所有系数的gcd的质因数。2、1~n以内符合条件的数（具体证明是看官方题解的）。第一种无脑枚举，第二种直接O(n^2)暴力即可。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=2e5+;

int n,m,a[N],h[N];

set<int>ans;

void check(int p)

{

    for(int i=;i<p-;i++)h[i]=;

    for(int i=,x;i<=n;i++)x=i%(p-),h[x]=(h[x]+a[i])%p;

    for(int i=;i<p-;i++)if(h[i])return;

    ans.insert(p);

}

int main()

{

    scanf("%d",&n);

    for(int i=n;i>=;i--)scanf("%d",&a[i]),m=__gcd(m,abs(a[i]));

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

    if(m%i==)

    {

        ans.insert(i);

        while(m%i==)m/=i;

    }

    if(m!=)ans.insert(m);

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

    if(a[]%i==)

    {

        int flag=;

        for(int j=;j*j<=i;j++)if(i%j==){flag=;break;}

        if(flag)check(i);

    }

    for(auto x:ans)printf("%d\n",x);

}

F

咕

rank=105，rating+=108，因为原本rating过低。