Codeforces #246(div2)_html/css_WEB-ITnose

A: A. Choosing Teams

. I won’t introduce the topic, just statistics.

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

True question Very difficult to understand. . Anyway, I have been reading for a long time. The title means that there are n teams playing in a championship, divided into home and away games. Each team wears color A when playing home games and wears color B clothes when playing away games. If the two teams have the same color clothes, then play away games. He still wears his original home court clothes, which is A clothes, hey. . I have been stuck in understanding this place for a long time, and I just need to make some statistics.

AC code:

#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. Prime Swaps

The question means that you are given n unordered numbers and asked to sort them. But there is one thing. If the positions i and j are exchanged, (if j>i) j-i 1 needs to be a prime number. In fact, you can use bubbling yy, but it soon proved that it doesn't work. As mentioned in the question, the maximum is five times n. Then I started looking online for how to divide it into prime numbers.

Goldbach's conjecture has two contents:

The first part is called the odd number conjecture,
The second part is called the even number conjecture. The odd number conjecture states that any odd number greater than or equal to 7 is the sum of three prime numbers.
The even number conjecture is that an even number greater than or equal to 4 must be the sum of two prime numbers.

But a meter is required.

My approach did not use this conjecture. In fact, we can use the conditions of the question. There are n numbers. These n numbers happen to be 1~n, so we can directly locate them. Then we can exchange the furthest one each time and use the greedy algorithm. Generally, it only takes up to three or four times to change this number to its original position. In fact, the above conjecture is also used. .

AC code:

#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. Prefixes and Suffixes

D.

1 second

memory limit per test 256 megabytes

input standard input

output standard output

You have a string s?=?s1s2...s|s|, where |s| is the length of string s, and si its i-th character .

Let's introduce several definitions:

A substring s[i..j] (1?≤?i?≤?j?≤?|s|) of string s is string sisi ? ?1...sj.

The prefix of string s of length l (1?≤?l?≤?|s|) is string s[1..l].

The suffix of string s of length l (1?≤?l?≤?|s|) is string s[|s|?-?l? ?1..|s|].

Your task is, for any prefix of string s which matches a suffix of string s, print the number of times it occurs in string s as a substring.

Input

The single line contains a sequence of characters s1s2...s|s| (1?≤?|s|?≤?105) ? string s. The string only consists of uppercase English letters.

Output

In the first line, print integer k (0?≤?k?≤?|s|) ? the number of prefixes that match a suffix of string s. Next print k lines, in each line print two integers li ci. Numbers li ci mean that the prefix of the length li matches the suffix of length li and occurs in string s as a substring citimes. Print pairs li ci in the order of increasing li.

Sample test(s)

input

ABACABA

output

31 43 27 1

input

AAA

output

31 32 23 1

It means that you can first find the prefix equal to the suffix, and then find the number of such strings in the original string. .

开始在用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*/