一. 选择题 30 道

瞎蒙，花了 30 分钟。。。

二. 问答题 1 道

衡量两个向量的相似性的方法及计算方式

三. 系统设计题 1 道

设计一个能准确预估搜索广告点击率的系统

四. 编程题 2 道

1. 最长回文 01 子串 100% AC

题目：给定一个只有 0、1 组成的字符串，返回最长的回文 01 子串（回文串，且同时包含 0、1 两种字符的子串）

示例：

输入：111010010100
输出：8
解释：中间的 10100101

中心扩展法：只是对每个回文串需要判断是否同时包含 0、1 两种字符

#include <iostream>
#include <string>
using namespace std;
int main()
{
    string str;
    cin >> str;
    int len = str.size();
    int result = 0;
    int mid1 = 0;
    int mid2 = 0;
    while(mid1 < len && mid2 < len)
    {
        int left = mid1;
        int right = mid2;
        bool flag0 = false;
        bool flag1 = false;
        while(left >= 0 && right < len && str[left] == str[right])
        {
            if(str[left] == '0')
                flag0 = true;
            if(str[left] == '1')
                flag1 = true;
            --left;
            ++right;
        }
        int len = right - left - 1;
        if(flag0 == true && flag1 == true && len > result)
            result = len;
        if(mid1 == mid2)
            ++mid2;
        else
            ++mid1;
    }
    cout << result << endl;
    return 0;
}

2. 礼物组合数 100% AC

题目：有 a、b 两种礼物，组合打包售卖，有两种组合方式

1. x 件 a + y 件 b
2. x 件 b + y 件 a

希望组合数越多越好，求最多多少个组合？

示例：

输入：a = 10, b = 12, x = 2, y = 5
输出：3

输入：a = 1, b = 1, x = 2, y = 2
输出：0

输入：a = 7, b = 8, x = 1, y = 2
输出：5

解法：

1. 开始试了下特殊情形，直接 cout << ((a + b) / (x + y)) << endl; 竟然过了 55%
2. 然后用二维 dp 做，只能过 27%，提示 RunTime Error，应该超时了？
   1. 动态规划数组 dp：dp[i][j] 代表当前剩余 i 个 a，j 个 b 的最大组合数
   2. 状态转移方程：dp[i][j] = max(dp[i - x][j - y] + 1, dp[i - y][j-x] + 1)，当然下标差值都要大于等于 0，否则就为 0
   3. 初始化：全部初始化为 0
      1. dp[i][0] = 0
      2. dp[0][j] = 0 ```cpp

         include

         include

         using namespace std;

int main() { int a, b, x, y; cin >> a >> b >> x >> y;

vector<vector<int>> dp(a + 1, vector<int>(b + 1, 0));
for(int i = 1; i <= a; ++i)
{
    for(int j = 1; j <= b; ++j)
    {
        int val1 = (i - x >= 0 && j- y >= 0) ? dp[i - x][j - y] + 1 : 0;
        int val2 = (i - y >= 0 && j- x >= 0) ? dp[i - y][j - x] + 1 : 0;
        dp[i][j] = max(val1, val2);
    }
}
cout << dp[a][b] << endl;
return 0;

}

3. 直接模拟（贪心），过了 100%。。。
- 每次 a、b 两者中较大的减去 x、y 中较大的，a、b 两者中较小的减去 x、y 中较小的
```cpp
#include <iostream>
#include <vector>
using namespace std;
int main()
{
    int a, b, x, y;
    cin >> a >> b >> x >> y;
    if(x == y)
        cout << min(a / x, b / y) << endl;
    else
    {
        int large = max(x, y);
        int small = min(x, y);
        int cnt = 0;
        while(true)
        {
            int numL = max(a, b);
            int numS = min(a, b);
            if(numL < large || numS < small)
                break;
            else
            {
                numL -= large;
                numS -= small;
                a = numL;
                b = numS;
                ++cnt;
            }
        }
        cout << cnt << endl;
    }
    return 0;
}