codeforces round# 177 div2

这真是一场神奇的比赛，比赛中各种猜想各种对，但我都无法证明，无语了，正式比赛中要能有这状态那我不无敌了？不废话了,上题解吧。

http://codeforces.com/contest/289/problem/A

A:水题吧，求出每个区间中所包含的数的个数，求和后，看和k的倍数差多少即可。

#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
#define maxn 100010
using namespace std;

int main()
{
    //freopen("dd.txt","r",stdin);
    int n,k,l,r,sum=0;
    scanf("%d%d",&n,&k);
    while(n--)
    {
        scanf("%d%d",&l,&r);
        sum+=r-l+1;
    }
    sum%=k;
    printf("%d\n",(k-sum)%k);
    return 0;
}
           

http://codeforces.com/contest/289/problem/B

B:如果矩阵中有两个数的差不是d的倍数则无解，否则，我们假设要把所有的数变成a[1][1]，每个矩阵需要多少步，（这里的步数是指增加的次数，如果要减少的话则为负数）比如说矩阵是

 8   4

12 14

d为2.则a[1][1]需要0步，a[1][2]需要2步,a[2][1]需要-2步，a[2][2]需要-3步。

假设我们得到每个矩阵中的步数依次为b1 b2 b3.......bn*m，则我们及时要求一个j，使得|b1-bj|+|b2-bj|......+|bn*m-bj|最小，事实上bj是数列b的中位数时，得到的和最小（显然吧。。。）。

#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
#define maxn 110
using namespace std;
int bo[maxn][maxn];
int a[10010];
int init(int n,int m,int d)
{
    int i,j,num=1,tmp=bo[1][1];
    a[1]=0;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(i==1&&j==1)
            continue;
            int tt=bo[i][j]-tmp;
            //printf("%d\n",tt);
            if(tt%d)
            return 0;
            tt/=d;
            a[++num]=tt;
        }
    }
    return 1;
}
int main()
{
    freopen("dd.txt","r",stdin);
    int n,m,d,num=0,i,j;
    scanf("%d%d%d",&n,&m,&d);
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        scanf("%d",&bo[i][j]);
    }
    if(init(n,m,d))
    {
        sort(a+1,a+n*m+1);
        int ans=0,tmp=a[(1+n*m)/2];
        for(i=1;i<=n*m;i++)
        {
            ans+=abs(a[i]-tmp);
        }
        printf("%d\n",ans);
    }
    else
    printf("-1\n");

    return 0;
}
           

http://codeforces.com/contest/289/problem/C

 C：  贪心即可，首先若k>n或者k==1且n>1时无解。k==n,我们依次输出abcde.....即可，若k<n，则前n-k个字母一定是abababab...类型的串，我们在最后k个字符中构造满足条件1的解，若第n-k个字符为b，则我最后k个字符为abcde...即可，否则，最后k个字符为bacde....即可。

#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
#define maxn 100010
using namespace std;

int main()
{
   //freopen("dd.txt","r",stdin);
   int n,k;
   scanf("%d%d",&n,&k);
   if(k==1)
   {
       if(n==1)
       printf("a\n");
       else
       printf("-1\n");
   }
   else if(k>n)
   printf("-1\n");
   else if(k==n)
   {
       for(int i=1;i<=n;i++)
       printf("%c",'a'+i-1);
       printf("\n");
   }
   else
   {
       int i;
       for(i=1;i<=n-k;i++)
       {
           if(i%2)
           printf("a");
           else
           printf("b");
       }
       if((n-k)%2)
       {
           printf("ba");
       }
       else
       printf("ab");
       for(i=1;i<=k-2;i++)
       printf("%c",'b'+i);
       printf("\n");

   }
    return 0;
}
           

http://codeforces.com/contest/289/problem/D

D:有公式，对于 n,k，答案为 (k^(k-1))*((n-k)^(n-k))  注意这里的^表示乘方运算。

什么，你问我为什么？。。。。。。这是个谜。。。。。。

随便YY的一个公式，竟然过了。。。其实我就是根据前两个样例推的公式啊。。。伤不起。。。大牛勿喷啊。。。

#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
#define ll long long
#define mod 1000000007
using namespace std;
ll pow[1010][2];
void init()
{
    ll i,j;
    pow[0][0]=pow[0][1]=1;
    for(i=1;i<=1000;i++)
    {
        ll tmp=1;
        for(j=1;j<i;j++)
        {
            tmp=(tmp*i)%mod;
        }
        pow[i][0]=tmp;
        pow[i][1]=(tmp*i)%mod;
    }
}
int main()
{
    //freopen("dd.txt","r",stdin);
    ll n,k;
    init();
    scanf("%I64d%I64d",&n,&k);
    printf("%I64d\n",(pow[n-k][1]*pow[k][0])%mod);
    return 0;
}
           

http://codeforces.com/contest/289/problem/E

E:这道题再次证明了我YY的功力，实在没头绪，YY了一个贪心算法，竟然又过了。。。神RP啊，昨天要是做比赛就好了。。。。

由于我没办法证明算法的正确性，而且算法也不是很好描述，所以先放在这里，等到我能够证明了的时候再来补。。。，如果有哪位大牛知道证明，欢迎来讨论！！谢谢！！

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#define ll long long
#define maxn 1000010
using namespace std;
int getlen(int x)
{
    int num=0;
    while(x)
    {
        num++;
        x/=2;
    }
    return num;
}
int vis[maxn];
ll ans=0;
int main()
{
    //freopen("dd.txt","r",stdin);
    int n;
    scanf("%d",&n);
    int len=getlen(n),i;
    int limit=(1<<len)-1;
    memset(vis,0,sizeof(vis));
    for(i=n;i>=0;i--)
    {
        if(vis[i])
        continue;
        int t=limit-i;
        for(int j=len;j>=1;j--)
        {
            if(t<=n&&!vis[t])
            {
                ans+=(t^i);
                vis[i]=t;
                vis[t]=i;
                if(t!=i)
                ans+=(t^i);
                break;
            }
            if((1<<(j-1))&t)
            {
                t-=(1<<(j-1));
            }
        }
    }
    printf("%I64d\n",ans);
    for(i=0;i<=n;i++)
    printf("%d ",vis[i]);
    printf("\n");
    return 0;
}