2013 腾讯马拉松初赛 第1场

1. 简单模拟题

2. 快速幂，加上一点数组的处理。。  其实也是很简单的，但是我交了好几次才过...

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

typedef __int64 LL;
#define MOD 1000000007
int n,t,k;

LL g[100100];

LL fuc()
{
    if(t==0) return 1;
    LL sum=k;
    LL s=1;
    while(t!=1)
    {
        if(t%2==0)
        {
            sum=(sum*sum)%MOD;
            t/=2;
        }
        else
        {
            s=(s*sum)%MOD;
            sum=(sum*sum)%MOD;
            t/=2;
        }
    }
    sum=(sum*s)%MOD;
    return sum;
}
LL save[100100];

int main()
{
    int t1;
    scanf("%d",&t1);
    while(t1--)
    {
        scanf("%d%d%d",&n,&t,&k);
        for(int i=1;i<=n;i++)
            scanf("%I64d",&g[i]);
        int tt=t%n;
        LL key=fuc();
        int cnt=0;
        for(int i=n-tt+1;i<=n;i++)
        {
            save[cnt++]=((LL)g[i]*key)%MOD;
        }
        for(int i=1;i<=n-tt;i++)
            save[cnt++]=((LL)g[i]*key)%MOD;

        for(int i=0;i<cnt-1;i++)
            printf("%I64d ",save[i]);
        printf("%I64d",save[cnt-1]);
        printf("\n");
    }
    return 0;
}

 4. dp题，和背包很类似， 不过这个是从1-m   每次用1-n 来更新...

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

typedef __int64 LL;
LL dp[100100];
LL gx[110],gy[110];

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        memset(dp,0,sizeof(dp));
        int m;
        for(int i=0;i<n;i++)
        {
            scanf("%I64d%I64d",&gx[i],&gy[i]);
        }
        scanf("%d",&m);
        for(int i=0;i<=m;i++)
        {
            int w,c;
            LL tmp=dp[i];
            for(int j=0;j<n;j++)
            {
                LL w=gx[j];
                LL c=gy[j];
                if(i<c) continue;
                tmp=max(tmp,dp[i-c]+w);
            }
            dp[i]=tmp;
        }
        printf("%I64d\n",dp[m]);
    }
    return 0;
}

5. 暴力都能过的题， 可以用线段树优化...

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;


int g[100100];

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        memset(g,0,sizeof(g));
        int f,e;
        int x,y;
        for(int i=0;i<n;i++)
        {
            scanf("%d:%d",&x,&y);
            f=x*60+y;
            scanf("%d:%d",&x,&y);
            e=x*60+y;
            for(int i=f;i<e;i++)
                g[i]=1;
        }
        int sum=0;
        for(int i=0;i<1500;i++)
        {
            if(g[i]==1) sum++; 
        }
        printf("%d\n",1440-sum);
    }

    return 0;
}