2013 腾讯马拉松初赛第1场-白红宇

2013 腾讯马拉松初赛第1场

阅读量：6272 次

发布时间：2019-06-22

本文共 1526 字，大约阅读时间需要 5 分钟。

1. 简单模拟题

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

#include 
     
      #include 
      
       #include 
       
        using namespace std;typedef __int64 LL;#define MOD 1000000007int 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

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

#include 
     
      #include 
      
       #include 
       
        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

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

#include 
     
      #include 
      
       #include 
       
        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