Codeforces #246(div2)_html/css_WEB-ITnose

A: A. チームの選択

については説明しません。統計だけを説明します。

AC code:

#include<iostream>#include<cstdio>#include<cstring>using namespace std;int cnt[6];int main(){    int n,k,i,x;    while(cin>>n>>k)    {        memset(cnt,0,sizeof(cnt));        for(i=0;i<n;i++)        {            cin>>x;            cnt[5-x]++;        }        int ans=0;        for(i=k;i<=5;i++)        {            ans+=cnt[i];        }        ans/=3;        cout<<ans<<endl;    }    return 0;}/*6 50 0 0 0 0 0*/

B: B. Football Kit

質問が本当にわかりにくいです。 。とにかく、私は長い間読んできました、タイトルは、チャンピオンシップでプレーするnチームがホームゲームとアウェイゲームに分かれて、ホームゲームをプレイするときは色のAを着て、アウェイゲームをプレイするときはB色の服を着ることを意味します。両チームが同じ色の服を着ている場合は、アウェイゲームをプレイします、彼はまだオリジナルのホームコートの服を着ています、それはA服です。 。私は長い間この点を理解できずにいたので、統計を作成する必要があります。

AC コード:

#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int maxn=100005;int x[maxn],y[maxn];int p[maxn];int main(){    int n;    while(cin>>n)    {        memset(p,0,sizeof(p));        for(int i=0;i<n;i++)        {            cin>>x[i]>>y[i];            p[x[i]]++;        }        for(int i=0;i<n;i++)            printf("%d %d\n",n-1+p[y[i]],n-1-p[y[i]]);    }    return 0;}/*31 22 11 3*/

C: C. プライムスワップ

この質問は、n 個の順序のない数字を与えて、それらを並べ替えるようにすることを意味します。ただし、位置 i と j が交換される場合、(j>i の場合) j-i+1 は素数である必要があります。実際、バブリング yy を使用できますが、質問で述べたように、最大​​値は n の 5 倍であることがすぐにわかりました。そこで、それを素数に分割する方法をネットで探し始めました。

ゴールドバッハ予想には 2 つの内容があります:

最初の部分は奇数予想と呼ばれ、
2 番目の部分は偶数予想と呼ばれます。奇数予想は、7 以上の奇数は 3 つの素数の合計であると述べています。
偶数予想とは、4 以上の偶数は 2 つの素数の和でなければならないというものです。

でもメーターをチェックする必要があります。

私のアプローチはこの推測を使用しませんでした。実際には、質問の条件を使用することができます。これらの n 個の数値はたまたま 1 ～ n であるため、毎回最も遠い値を交換し、貪欲なアルゴリズムを使用することができます。通常、この数値を元の位置に戻すには最大 3 ～ 4 回しかかかりません。実際、上記の推測も使用されます。 。

AC コード:

#include<iostream>#include<cstdio>#include<cstring>#include<cmath>using namespace std;const int maxn=100005;int a[maxn],pos[maxn],mark[maxn];int res[5*maxn][2];void sxprime(){    memset(mark, true, sizeof(mark));    mark[0] = mark[1] = false;    for(int i=2; i <= sqrt(maxn-1) ; i++)    {        if(mark[i])        {            for(int j=i*i; j < maxn-1 ; j+=i)                mark[j] = false;        }    }}int main(){    sxprime();    int i,j,n;    while (cin>>n)    {        for (int i=1; i<=n; i++)        {            scanf("%d",&a[i]);            pos[a[i]]=i;        }        int tt=0,p=1;        for (int i=1; i<=n; i++)        {            while (pos[i]!=p)            {                for (j=pos[i]-p+1; j>=2; j--)                    if (mark[j])                    {                        int x=pos[i]+1-j;                        res[tt][0]=x;                        res[tt++][1]=pos[i];                        int l,r,tmp;                        l=x,r=pos[i];                        tmp=a[l];                        a[l]=a[r];                        a[r]=tmp;                        tmp=pos[a[l]];                        pos[a[l]]=pos[a[r]];                        pos[a[r]]=tmp;                        break;                    }            }            p++;        }        printf("%d\n",tt);        for (int i=0; i<tt; i++)            printf("%d %d\n",res[i][0],res[i][1]);    }    return 0;}

D: D. プレフィックスとサフィックス

D. プレフィックスとサフィックス

テストごとの制限時間

1 秒

テストごとのメモリ制限

256 メガバイト

入力

標準入力

出力

標準出力

文字列 s?=?s1s2...s|s| があります。ここで、|s| は文字列 s の長さ、si はその i 番目の文字です。

いくつかの定義を紹介しましょう:

文字列の部分文字列 s[i..j] (1?≤?i?≤?j?≤?|s|) s は文字列 sisi?+?1...sj.

長さ l (1?≤?l?≤?|s|) の文字列 s の接頭辞は文字列 s[1..l].

接尾辞長さ l (1?≤?l?≤?|s|) の文字列 s は、文字列 s[|s|?-?l?+?1..|s|] です。

あなたのタスクは、任意のプレフィックスに対してです。文字列 s のサフィックスに一致する文字列 s を部分文字列として出力します。

入力

単一行には、一連の文字 s1s2...s|s| が含まれます。 ?≤?|s|?≤?105) ? 文字列 s。文字列は大文字の英字のみで構成されます。

出力

最初の行に、整数 k (0?≤?k?≤?|s) を出力します。 |) ? 文字列 s の接尾辞に一致する接頭辞の数。次に k 行を出力し、各行に 2 つの整数 li ci を出力します。数値 li ci は、長さ li の接尾辞が文字列内に出現することを意味します。 s を部分文字列 citimes として、li の増加順にペア li ci を出力します。

サンプルテスト

入力

ABACABA

出力

31 43 27 1

入力

AAA

出力

31 32 23 1

は、まずサフィックスと等しいプレフィックスを見つけてから、元の文字列内でそのような文字列の数を見つけることができることを意味します。

开始在用manacher想，但是无果，于是想kmp，然后就开始写了，getnext，然后统计个数，但是当时脑筋犯迷糊，不知道怎么统计前缀等于后缀，实际上自己和自己匹配就可以了。。YY的能力越来越差了。

然后在KMP中统计前缀出现的个数，然后再往前递推，因为如果next[k]!=0，那么说明k这一点记录的cnt会包含cnt[next[k]]的，然后就可以递推了。详见代码。

AC代码：

#include<iostream>#include<cstring>#include<string>#include<cstdio>using namespace std;const int maxn=100005;char p[maxn];int cnt[maxn],len,t;int next[maxn],ans[maxn][2];void getnext(){     int i,j;     next[0]=0,next[1]=0;     for(i=1;i<len;i++)     {          j=next[i];          while(j&&p[i]!=p[j])               j=next[j];          if(p[i]==p[j])               next[i+1]=j+1;          else               next[i+1]=0;     }}void KMP(){    memset(cnt,0,sizeof(cnt));    int i,j=0;    for(i=0;i<len;i++)    {        while(j&&p[i]!=p[j])            j=next[j];        if(p[i]==p[j])        {            j++;            cnt[j]++;        }    }    int k=j;    for(k=len;k>=1;k--)  //往前递推，长度长的可能会包含长度短的.        if(next[k])            cnt[next[k]]+=cnt[k];    j=next[j];    t=0;    ans[t][0]=len;    ans[t++][1]=1;    while(j)    {        ans[t][0]=j;        ans[t++][1]=cnt[j];        j=next[j];    }}int main(){    int i;    while(cin>>p)    {        len=strlen(p);        getnext();        KMP();        printf("%d\n",t);        for(i=t-1;i>=0;i--)            printf("%d %d\n",ans[i][0],ans[i][1]);    }    return 0;}/*ABACABAAAAAAAAAAAAAAAAAXAAAAAAAAAAAAAAAAAAAAAAA*/