BestCoder Round #71 (div.2)-白红宇

BestCoder Round #71 (div.2)

阅读量：6693 次

发布时间：2019-06-25

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

数学 1001

类似斐波那契求和

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             typedef long long ll;const int N = 1e5 + 5;const int MOD = 1e9 + 7;ll run(ll n) { ll a = 1, b = 2, c; ll sum = 3, ret = 2; while (sum < n) { c = a + b; if (sum + c < n) { sum += c; a = b; b = c; ret++; } if (sum + c > n) return ret; if (sum + c == n) return ret + 1; } return ret;}int main(void) { int T; scanf ("%d", &T); while (T--) { ll n; scanf ("%I64d", &n); if (n <= 2) puts ("1"); else { ll ans = run (n); printf ("%I64d\n", ans); } } return 0;}

数学 1002

圆上四个点连线能成圆内一个点，所以答案就是comb (n, 4) + n

#include 
     
      int main(void)  {    int T;  scanf ("%d", &T);    while (T--) {        int n;  scanf ("%d", &n);        if (n < 4)  printf ("%d\n", n);        else    {            unsigned long long ans = 1;            ans = ans * n * (n - 1) / 2 * (n - 2) / 3 * (n - 3) / 4 + n;            printf ("%I64d\n", ans);        }    }    return 0;}

还有自己想出来的结论

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             typedef long long ll;const int N = 1e5 + 5;const int MOD = 1e9 + 7;ll fun(int x) { return 1ll * (1 + x) * x / 2;}int main(void) { int T; scanf ("%d", &T); while (T--) { int n; scanf ("%d", &n); ll ans = n; n -= 3; int t = 1; while (n >= 1) { ans += fun (n) * t; n--; t++; } printf ("%I64d\n", ans); } return 0;}

DP 1004

显然，每个人的策略就是都会拿剩下的数中最大的某几个数

假如我们用f[i]表示当剩下i个数的时候先手得分-后手得分的最小值

那么得到 $f[i]=max\left(a[j+1]-f[j] \right)(1<j\leq i)f[i]=max(a[j+1]−f[j])(1<j≤i)$

但是这样做，是要超时的

我们不妨简单转换一下 f[i]=_max; _max=max(_max,a[i+1]-f[i]);

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             typedef long long ll;const int N = 5e4 + 5;const int MOD = 1e9 + 7;int a[N];long long dp[N];int main(void) { int T; scanf ("%d", &T); while (T--) { int n; scanf ("%d", &n); for (int i=0; i