[Atcoder Regular Contest 060] Tutorial

Link:

C:

由于难以维护和更新平均数的值：

$Average->Sum/Num$

这样我们只要用$dp[i][j][sum]$维护前$i$个数中取$j$个，且和为$sum$的个数

最后统计$dp[n][k][k*a]$即可

这样就得到了$O(n^4)$的解法

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN=;

int n,a,sum,dat[MAXN];

ll dp[MAXN][MAXN][MAXN*MAXN],res=;

int main()

{

    scanf("%d%d",&n,&a);

    for(int i=;i<=n;i++) scanf("%d",&dat[i]);

    dp[][][dat[]]=;sum=dat[]+dat[];

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

    for(int i=;i<=n;i++,sum+=dat[i])

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

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

            {

                dp[i][j][k]=dp[i-][j][k];

                if(k>=dat[i]) dp[i][j][k]+=dp[i-][j-][k-dat[i]];

            }

    for(int i=;i<=n;i++) res+=dp[n][i][i*a];

    printf("%lld",res);

    return ;

}

O(n^4)

不过真的需要同时记录个数与和吗？

如果将$dat[i]->a-dat[i]$，只要维护最终和为0的情况即可

于是将复杂度降到了$O(n^3)$

#include <bits/stdc++.h>

using namespace std;

const int MAXN=,ZERO=;

typedef long long ll;

int n,a,x,cur;

ll dp[][*ZERO];

int main()

{

    scanf("%d%d",&n,&a);

    dp[cur^][ZERO]=;

    for (int i=;i<=n;i++,cur^=)

    {

        scanf("%d",&x);x-=a;

        for (int j=MAXN;j+MAXN<*ZERO;j++)

            dp[cur][j]=dp[cur^][j]+dp[cur^][j-x];

    }

    printf ("%lld\n",dp[cur^][ZERO]-);

}

O(n^3)

D:

遇到多次取模问题时，有以下对数据的典型分类：

1、$base\le sqrt(n)$，此时直接枚举即可

2、$base>sqrt(n)$，此时由$n=p*base+q$和$p+q=s$可得$n-s=p(base-1)$

从小到大枚举$n-s$的所有约数算出$base$再验证

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll n,s,sq;

bool check(ll b)

{

    ll ret=,t=n;

    for(;t;t/=b) ret+=t%b;

    return (ret==s);

}

ll solve()

{

    if(s==n) return n+; //s=1时不特殊处理

    if(s>n) return -;

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

        if(check(i)) return i;

    for(int i=sq;i;i--)  //注意枚举顺序

        if((n-s)%i==&&check((n-s)/i+)) return ((n-s)/i+);

    return -;

}

int main()

{

    scanf("%lld%lld",&n,&s);sq=sqrt(n);

    printf("%lld",solve());

    return ;

}

Problem D

很多题目都是暴力枚举$k\le sqrt(n)$，对$k>sqrt(n)$进行分块等处理来保证$O(nlog(n))$的复杂度

E:

比较明显的序列上倍增裸题

记录每个点能达到的最大距离再倍增即可

可以用假设法证明$dist(i,j)=dist(j,i)$

#include <bits/stdc++.h>

using namespace std;

const int MAXN=1e5+;

int n,l,q,a,b,dat[MAXN],nxt[MAXN][];

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++) scanf("%d",&dat[i]);

    scanf("%d",&l);

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

        nxt[i][]=upper_bound(dat+,dat+n+,dat[i]+l)-dat-;

    for(int i=n;i;i--)

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

            nxt[i][j]=nxt[nxt[i][j-]][j-];

    scanf("%d",&q);

    while(q--)

    {

        scanf("%d%d",&a,&b);

        if(a>b) swap(a,b);

        int res=;

        for(int i=;i>=;i--)

            if(nxt[a][i]&&nxt[a][i]<b) a=nxt[a][i],res+=(<<i);

        printf("%d\n",res+);

    }

    return ;

}

Problem E

F:

首先要在对小数据尝试后得到结论：

分成的组数只可能为$1 / 2 / len(s)(当每个字符都相同时)$

接下来只要判断任意一个$s$的前缀/后缀是否有循环节即可

%陈主力的代码后找到了最简易的判断方式：$KMP$算法中的$nxt$数组！

由画图可知：一个字符串最长相同的前/后缀有重叠部分且剩余部分为$len$的约数则其有循环节

因此$pos\% (pos-nxt[pos])==0$时则$pos$为有循环节的前缀/后缀

正反求一次$nxt$数组枚举每一个分割点判断就好啦

#include <bits/stdc++.h>

using namespace std;

const int MAXN=5e5+;

char s[MAXN];

int len,res=,nxt1[MAXN],nxt2[MAXN];

void cal_nxt(int* nxt)

{

    int k=;

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

    {

        while(k&&s[k+]!=s[i]) k=nxt[k];

        if(s[k+]==s[i]) k++;nxt[i]=k;

    }

}

bool check(int* nxt,int pos)

{

    if(!nxt[pos]) return false;

    return (pos%(pos-nxt[pos])==);

}

int main()

{

    scanf("%s",s+);len=strlen(s+);

    cal_nxt(nxt1);

    if(!check(nxt1,len)) printf("1\n1");

    else if(nxt1[len]==len-)  printf("%d\n1",len);

    else

    {

        reverse(s+,s+len+);

        cal_nxt(nxt2);

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

            res+=(!check(nxt1,i))&(!check(nxt2,len-i));

        printf("2\n%d",res);

    }

    return ;

}

Problem F

Review:

感觉$Atcoder$里的题目对推断能力要求比较高

还是要多尝试小数据，大胆猜结论再证明

巴特西

[Atcoder Regular Contest 060] Tutorial

Link:

C:

D:

E:

F:

Review:

最新文章

热门文章