RT. 接下来打算在 11 月份之前刷个 200 题的算法题（包括线上和线下）……然后想着就是开个帖子来整理和记录题解什么的，大概能碰到电脑的话那就每周一篇这样子。

这一阶段的话主要是挑 HDUOJ 的题目来做（因为可以找到详细的题目分类），会从简单的题目开始（比如 A+B Problem），然后辅以一些 Codeforces 的题。之前那个 LeetCode 的记录帖就这么弃坑了（

¹⁄₂₀₀, HDU1003, Max Sum

题意大概是给一个很长的数列，有正有负，然后要求这个数列的子序列的和的最大值。然后范围大概是 1e5 以内。有个比较迷的地方就是不仅要求最大值，而且还要求出取得最大值的时候，子区间的位置。时间 1s, 内存 64M.

第一反应是不是区间 DP 的题啊，然后看了一下数据范围果断把这个白痴的想法扔回肚子里去了。子序列最大值倒是会求啊，但是一开始没有反应过来要怎么统计位置。后来想了一下，开不下二维数组那我开一维的总可以了吧。所以这就是一道最大连续子区间和的动态规划问题了。

设 dp[i] 表示以 a[i] 为区间终点时能取到的和的最大值，然后开两个辅助数组 left[i] 和 right[i] 来表示当取到这个最大值的时候的区间左界和右界分别在哪里，然后最后 for 一遍统计最大值就做完了。需要注意这里一个地方就是数据可正可负，那么考虑一种情况就是假设 dp[i-1] 小于 0 的时候，那么无论 a[i] 是正数还是负数，显然只取 a[i] 的结果会比取 d[i-1] + a[i] 的结果更优，所以遇到这种情况就要重置一下区间的左右界。

还有一个要注意的地方就是输出的格式，当时做的时候各种 PE……

转移方程为 dp[i] = max(dp[i-1] + a[i], a[i]).

Code:

#include <bits/stdc++.h> 
const int INF = 1e9 + 7;
const int MAXN = 1e5 + 10;

int n, sn;
int a[MAXN];
int dp[MAXN];
int left[MAXN], right[MAXN];

void init()
{
  for (int i = 0; i < MAXN; i++)
  {
    dp[i] = -INF;
    left[i] = 0;
    right[i] = 0;
  }
}

int main()
{
  scanf("%d", &n);
  sn = n;
  
  int tmp = 1;
  while (sn--)
  {
    printf("Case %d:\n", tmp++);
    init();
    
    int num;
    scanf("%d", &num);
    for (int i = 0; i < num; i++)
    {
      scanf("%d", &a[i]);
    }
    
    dp[0] = a[0], left[0] = 0, right[0] = 0;
    for (int i = 1; i <= num; i++) 
    {
      // 遇到负数的时候重新计数 
      if (dp[i-1] < 0)
      {
        left[i] = right[i] = i;
        dp[i] = a[i];
        continue;
      }

      dp[i] = dp[i-1] + a[i];
      left[i] = left[i-1];
      right[i] = i;
    }
    
    int maximum = -INF;   // 维护最大值
    int l, r;
    for (int i = 0; i < num; i++) 
    {
      if (dp[i] > maximum)
      {
        maximum = dp[i];
        l = left[i], r = right[i];
      }
    }
    
    printf("%d %d %d\n", maximum, l+1, r+1);
    
    if (tmp-1 != n)
      printf("\n");
  }
  return 0;
}

²⁄₂₀₀, HDU1004, Let the Balloon Raise

题意就是已知有 n 个气球和它们的颜色，然后要问最受欢迎的气球（也就是出现次数最多的颜色种类）是哪个，颜色用字符串表示且长度不超过 15，有多个子任务，且对于每个子任务保证只有一个合法答案。

嘛，简单的字符串计数嘛。这个用什么方法达到都可以的，你开心就好了。在这里我是用一个奇怪的做法，首先用 STL 的 string 保存每个气球的颜色，然后再按字典序用 sort() 排序一下，最后就可以很方便地统计出出现次数最多的那种气球来了。

Code:

#include <bits/stdc++.h> 
using namespace std;
const int MAXN = 1010;
string balloons[MAXN];
int main()
{
  int num;
  int maximum, tmp, handle;
  
  while (scanf("%d", &num) != EOF && num != 0)
  { 
    for (int i = 0; i < num; i++)
    {
      cin >> balloons[i];
    }
    sort(balloons, balloons + num);
    
    maximum = 0, tmp = 0, handle = 0;
    for (int i = 1; i < num; i++)
    {
      if (balloons[i] != balloons[i-1])
      {
        tmp = 1;
      }
      else
      {
        tmp++;
      }
      
      if (tmp > maximum)
      {
        maximum = tmp;
        handle = i;
      }
    }
    cout << balloons[handle]  << endl;
  }
  
  return 0;
}

³⁄₂₀₀, HDU1005, Number Sequence

题意是对于一个函数 f(n), 满足 f(1) = 1, f(2) = 1, f(n) = (A * f(n-1) + B * f(n-2)) % 7, 然后求对于给定的 A, B 和 N, f(N) 的值是多少。1 <= n <= 1e8, 有多个子任务。

看数据范围我想没人敢一个一个算过去吧……而且还有好多个子任务，直接就 T 了。

这题的话一看我就猜到是递推……手推了 7 个之后发现好像没有什么规律……开始怀疑人生.jpg 后来才知道，因为结果要模 7，那么对于 f(n-1) 有 7 种可能的值 (0-6)，对于 f(n-2) 也是有 7 种可能的值，那么 f(n-1) 和 f(n-2) 一共有 7^2=49 种不同的组合可能，也就是最多 49 次就会出现一个循环节……找到循环节，接下来就可以直接算 f(N) 了，然后就做完了。

做的时候不知道为啥各种 RE，把计算输出的那部分改了一下就 AC 了。

#include <bits/stdc++.h> 
int arr[55];
int main()
{
  arr[0] = 1, arr[1] = 1;
  
  int a, b, n;
  int pot = 0;
  while (scanf("%d%d%d", &a, &b, &n) != EOF && n != 0)
  {
    int pot;
    for (int i = 2; i <= 54; i++)
    {
      arr[i] = (a * arr[i-1] + b * arr[i-2]) % 7;
      if (arr[i] == 1 && arr[i-1] == 1)
      {
        pot = i;
        break;
      }
    }
    
    n = n % (pot-1);
    
    if (n == 0)
    {
      printf("%d\n", arr[pot-2]);
    }
    else
    {
      printf("%d\n", arr[n-1]);
    }
  }
  return 0;
}