Codeforces#246(div2)_html/css_WEB-ITnose

.题目就不介绍了，直接统计即可。

AC代码：

#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<  <br>  <br>  <p></p>  <p>B：B. Football Kit</p>  <p>题目真的好难懂。。反正我读了很久很久，题目意思是说有n支队伍打锦标赛，分主场客场，每支队伍打主场穿颜色A，打客场穿颜色B的衣服，如果两支队伍颜色衣服一样，那么打客场的还是穿原本自己主场的衣服，就是A衣服，哎。。就这个地方理解坑了许久，，只需要统计一下即可。</p>  <p><br> </p>  <p>AC代码：</p>  <p></p>  <pre name="code" class="sycode layui-box layui-code-view layui-code-notepad"><ol class="layui-code-ol"><li>#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*="" <="" script=""></n;i++)></n;i++)></cstring></cstdio></iostream></li></ol></pre>  <br>  <br>  <p></p>  <p>C：C. Prime Swaps</p>  <p>题目意思是给你n个无序的数字，让你排序。不过有一点如果i和j这个位置，交换，（如果j>i）需要j-i+1为素数。其实可以用冒泡yy一下，不过很快就证明不行，题目上面说了，最大是五倍的n。然后就开始网上找怎么分成素数。</p>  <p>哥德巴赫猜想有两个内容：</p>  <p>第一部分叫做奇数的猜想，<br> 第二部分叫做偶数的猜想。奇数的猜想指出，任何一个大于等于7的奇数都是三个素数的和。<br> 偶数的猜想是说，大于等于4的偶数一定是两个素数的和。<br> </p>  <p>不过需要打表。</p>  <p>我的做法没有用到这个猜想。其实可以利用题目的条件，有n个数，这n个数字刚好是1~n，所以可以直接定位，然后我们可以每次交换最远的，利用的贪心的算法。一般只需要最多三四次就可以把这个数字换到原位，实际上也利用到了上面的猜想。。</p>  <p><br> </p>  <p>AC代码：</p>  <p></p>  <pre name="code" class="sycode layui-box layui-code-view layui-code-notepad"><ol class="layui-code-ol"><li>#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;}<="" script=""></tt;></cmath></cstring></cstdio></iostream></li></ol></pre>  <br>  <br>  <p></p>  <p>D：D. Prefixes and Suffixes</p>  <p></p>  <p class="sycode">   </p><p class="sycode">    </p><p class="sycode">     </p><p class="sycode">      </p><p class="sycode">       </p><p class="sycode">        </p><p class="sycode">         D. Prefixes and Suffixes        </p>        <p class="sycode">         </p><p class="sycode">          time limit per test         </p> 1 second        <p></p>        <p class="sycode">         </p><p class="sycode">          memory limit per test         </p> 256 megabytes        <p></p>        <p class="sycode">         </p><p class="sycode">          input         </p> standard input        <p></p>        <p class="sycode">         </p><p class="sycode">          output         </p> standard output        <p></p>       <p></p>       <p class="sycode">        </p><p> You have a string s?=?s1s2...s|s|, where |s| is the length of string s, and si its i-th character.</p>        <p> Let's introduce several definitions:</p>        <li> A substring s[i..j] (1?≤?i?≤?j?≤?|s|) of string s is string sisi?+?1...sj.</li>        <li> The prefix of string s of length l (1?≤?l?≤?|s|) is string s[1..l].</li>        <li> The suffix of string s of length l (1?≤?l?≤?|s|) is string s[|s|?-?l?+?1..|s|].</li>        <p> 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.</p>       <p></p>       <p class="sycode">        </p><p class="sycode">         Input        </p>        <p> The single line contains a sequence of characters s1s2...s|s| (1?≤?|s|?≤?105) ? string s. The string only consists of uppercase English letters.</p>       <p></p>       <p class="sycode">        </p><p class="sycode">         Output        </p>        <p> 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.</p>       <p></p>       <p class="sycode">        </p><p class="sycode">         Sample test(s)        </p>        <p class="sycode">         </p><p class="sycode">          </p><p class="sycode">           input          </p>          <pre style="代码" class="precsshei layui-box layui-code-view layui-code-notepad"><ol class="layui-code-ol"><li>ABACABA</li></ol></pre>         <p></p>         <p class="sycode">          </p><p class="sycode">           output          </p>          <pre style="代码" class="precsshei layui-box layui-code-view layui-code-notepad"><ol class="layui-code-ol"><li>31 43 27 1</li></ol></pre>         <p></p>         <p class="sycode">          </p><p class="sycode">           input          </p>          <pre style="代码" class="precsshei layui-box layui-code-view layui-code-notepad"><ol class="layui-code-ol"><li>AAA</li></ol></pre>         <p></p>         <p class="sycode">          </p><p class="sycode">           output          </p>          <pre style="代码" class="precsshei layui-box layui-code-view layui-code-notepad"><ol class="layui-code-ol"><li>31 32 23 1</li></ol></pre>          <p class="sycode">           <br>          </p>         <p></p>        <p></p>       <p></p>      <p></p>     <p></p>    <p></p>   <p></p>  <p></p>  <br>  <p></p>  <p>意思就是让你求首先前缀等于后缀，然后求原串中有多少个这样的串的个数。</p>  <p></p>  <p>开始在用manacher想，但是无果，于是想kmp，然后就开始写了，getnext，然后统计个数，但是当时脑筋犯迷糊，不知道怎么统计前缀等于后缀，实际上自己和自己匹配就可以了。。YY的能力越来越差了。</p>  <p>然后在KMP中统计前缀出现的个数，然后再往前递推，因为如果next[k]!=0，那么说明k这一点记录的cnt会包含cnt[next[k]]的，然后就可以递推了。详见代码。</p>  <p><br> </p>  <p>AC代码：</p>  <p></p>  <pre name="code" class="sycode layui-box layui-code-view layui-code-notepad"><ol class="layui-code-ol"><li>#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])" if(p[i]="=p[j])" next[i+1]="j+1;" else="" }}void="" kmp(){="" memset(cnt,0,sizeof(cnt));="" int="" i,j="0;" for(i="0;i<len;i++)" j++;="" cnt[j]++;="" }="" 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*/</len;i++)></cstdio></string></cstring></iostream></li></ol></pre>                    </n;i++)></cstring></cstdio></iostream>