[Codeforces #494] Tutorial

记录下一开始写错的两道水题

E:

先建出直径，然后在保证直径不变的情况下按照最大度数贪心就好了

注意一下一开始的特判

#include <bits/stdc++.h>

using namespace std;

#define X first

#define Y second

typedef pair<int,int> P;

int n,d,k,tot;vector<P> res;

void print()

{

    puts("YES");

    for(int i=;i<res.size();i++)

        printf("%d %d\n",res[i].X,res[i].Y);

}

void dfs(int u,int v,int dist,int idx)

{

    if(u) res.push_back(P(u,v));

    if(tot==n) print(),exit();

    if(!dist) return;

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

        dfs(v,++tot,dist-,k-);

}

int main()

{

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

    if(n<=d||n>&&k<) return puts("NO");

    for(int i=;i<=d;i++) res.push_back(P(i,i+));

    tot=d+;if(tot==n) return print(),;

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

        if(tot<n&&k>) dfs(,i,min(i-,d-i+),k-);

    puts("NO");

    return ;

}

Problem E

F:

又双叒叕看错题目了，可以缩减多个相同的串……

一开始写的$KMP$，后来发现直接字符串$Hash$就能水过了

注意：此题用$ab$串卡自然溢出，一共只有300个因此单模数就能过

数据开头$dont hash with overflow$好评！

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;

typedef pair<int,int> P;

const int MAXN=;

ull hs[MAXN],MOD=;char s[];

int n,res,tot,len,pre[MAXN];

ull cal_hash()

{

    ull ret=;

    for(int i=;i<strlen(s);i++)

        ret=(ret*+(s[i]-'a'+))%MOD;

    return ret;

}

int main()

{

    scanf("%d",&n);

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

    {

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

        tot+=len;pre[i]=pre[i-]+len;hs[i]=cal_hash();

    }

    tot+=n-;

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

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

        {

            int cnt=;

            for(int k=j+;k+j-i<=n;k++)

            {

                bool f=true;

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

                    if(hs[i+l]!=hs[k+l]) f=false;

                if(f) cnt++,k+=j-i;

            }

            if(cnt>) res=max(res,(pre[j]-pre[i-]-)*cnt);

        }

    printf("%d",tot-res);

    return ;

}

Problem F