腾迅马拉松（一）解题报告

腾迅马拉松（一）解题报告

小明系列故事——师兄帮帮忙

题目链接：Click Here~

题目分析：

题目说明给你三个数分别为n,t,k分别表示n个数，t次时间，每次乘以k。且每次的变化规则为：

a[i] = a[i-1]'*K； （a[i-1]'为前一次的数，当i=1时a[1] = a[n]'*K）。题目要求你输出经过t次后的a[1]....a[n].

[Technical Specification]
　　T <= 100
　　1 <= n <= 10 ^ 4
　　0 <= t <= 10 ^ 9　　其中 t = 0 表示初始状态
　　1 <= k <= 10 ^ 9
　　1 <= ai<= 10 ^ 9

由于数字可能会很大，所以只要你输出数字对10^9 + 7取余以后的结果

思路分析：

从题目数据可以看出枚举肯定超时，则我们就要另想他法。有什么办法呢？很显然，题目没经过n次。为一个周期，所以我们只要n这个范围内找就好了。但是，还要用到一个快速冪的方法。一开始我看到模很大，还以为要用到乘法冪，后来发现数据在 long long 范围内，所以就省了一步。还有那个啥的，hdu的输出格式真坑人。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

typedef __int64 LL;
const int N = 1e4 + 5;
const int MOD = 1e9+7;
LL a[N];
//LL MulMod(LL base,LL b)
//{
//    LL res = 0;
//    base %= MOD;
//    while(b)
//    {
//        if(b&1){
//           res += base;
//           if(res > MOD)
//             res -= MOD;
//        }
//        base <<= 1;
//        if(base > MOD) base -= MOD;
//        b >>= 1;
//    }
//    return res;
//}
LL PowMod(LL base,LL n)
{
    LL res = 1;
    base %= MOD;
    while(n)
    {
        if(n&1)
          res = res*base%MOD;
        base = base*base%MOD;
        n >>= 1;
    }
    return res;
}
int main()
{
    int T;
    LL n,k,t;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%I64d%I64d%I64d",&n,&t,&k);
        for(int i = 1;i <= n;++i)
          scanf("%I64d",&a[i]);
        LL res = PowMod(k,t);
        t %= n;
        if(!t){
           printf("%I64d",(a[1]*res)%MOD);
           for(int i = 2;i <= n;++i)
             printf(" %I64d",(a[i]*res)%MOD);
           printf("\n");
           continue;
        }
        printf("%I64d",(a[n-t+1]*res)%MOD);
        for(int i = n-t+2;i <= n;++i){    
           printf(" %I64d",(a[i]*res)%MOD);
        }
        for(int i = 1;i < n-t+1;++i){   
           printf(" %I64d",(a[i]*res)%MOD);
        }
        printf("\n");
    }
    return 0;
}

湫湫系列故事——减肥记II

题目分析：

本题可以是线段树来做。但是好久没敲线段树的代码了，手疏了。下次复习线段树的时候在来不上线段树的代码吧，先看看简单的暴力版吧。

思考：

其实，以前就听学长说过，去大公司面试的时候，面试官会给你一道题目。而且是大家都会做的，但是这时候就看谁会把这道题做的最优了。其实这道题也是，你暴力可以过，但是不是最优的，也肯定不是出题人想要的。

/*
   a > c,b > d
   a > c,b < d
   a < c,b > d
   a < c,b < d
*/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 2e3 + 5;
const int MAX = 5e5 + 5;
int hash[N],a[MAX];
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        int HH,MM,H,M,sum = 0;
        sum = 24*60;
        memset(hash,0,sizeof(hash));
        for(int i = 0;i < n;++i){
           scanf("%d:%d",&HH,&MM);
           scanf("%d:%d",&H,&M);
           HH = HH*60 + MM;             //start time
           H = H*60 + M;             // end time
           for(int i = HH;i < H;++i){
              if(!hash[i]){
                 sum--;
                 hash[i] = 1;
              }
           }
        }
        printf("%d\n",sum);
    }
    return 0;
}

小Q系列故事——为什么时光不能倒流

题目重现：

[Technical Specification]
00<=HH<=11
00<=hh<=99
00<=MM, SS, mm, ss<=59

题目分析：

这道题也是上周我校的比赛题，当时脑残的没看到输出的格式是HH:MM:SS，而HH<=11.所以，必须是结果HH<12，即，要求模12。当时比赛的时候居然没想到，wrong了6次。

思考：

以后，看题一定要认真仔细。看清楚题目的具体要求，这道题不难，但是就是题没看清题目要求。这都是借口！！！！！！！！！！！！以后一定要注意在注意！！！！！！！！！

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int H,HH,MM,M,SS,S;
        scanf("%d:%d:%d",&H,&M,&S);
        scanf("%d:%d:%d",&HH,&MM,&SS);
        H = (H-HH)%24;
        M = M - MM;
        S = S - SS;
        if(S < 0){
           M--;
           S += 60;
           if(M < 0){
              H--;
              M += 60;
           }
           if(H < 0)
              H += 24;
        }else
        {
            if(M < 0){
               H--;
               M += 60;
            }
            if(H < 0)
               H += 24;
        }
        H %= 12;
        printf("%02d:%02d:%02d\n",H,M,S);
    }
    return 0;
}