Hdu-6253 2017CCPC-Final K.Knightmare 规律

题面

题意:给你一个无限大的棋盘,一个象棋中的马,问你这个马,飞n步后,可能的位置有多少种?

题解:看到题,就想先打表试试,于是先写个暴力(枚举每个位置,是马就飞周围8个格子,注意不要在同个循环里把格子的标记涂成相同的数字)

然后打出来是9 41 109 205 325 473 649 853

对于这种增长不快的,我一般是先直接两项相减

得到 32 68 96 120 148 176 204

这时就看到,这个数列的增长越来越有趣? 后面都加的是?

于是对于n>=5,我们有 f[n]=f[n-1]+120+(n-5)*28 = f[n-1]+28*n-20

这种递推式很明显的解法 f[n] = f[n-1]+28*n-20

f[n-1]= f[n-2]+28*(n-1)-20

f[5]=f[4]+28*(5)-20

左右相加,再抵消.

f[n]=28*(n+n-1+...+5)-20*(n-5+1)=f[4]+28*(n+5)*(n-4)/2-20*(n-4)=(14*(n+5)-20)*(n-4)+205 = (14*n+50)*(n-4)+205

 #include<bits/stdc++.h>

 using namespace std;

 typedef unsigned long long ll;

 int main()

 {

     int caseCnt;

     scanf("%d",&caseCnt);

     for(int t=;t<=caseCnt;++t) {

         ll n;

         scanf("%llu",&n);

         ll ans;

         if(n==) ans=;

         else if(n==) ans=;

         else if(n==) ans=;

         else if(n==) ans=;

         else if(n==) ans=;

         else {

             ans=(*n+)*(n-)+;

         }

         printf("Case #%d: %llu\n",t,ans);

     }

     return ;

 }

巴特西

Hdu-6253 2017CCPC-Final K.Knightmare 规律

最新文章

热门文章