2019面试/笔试题（算法题）总结

喜欢ヅ旅行 2021-12-23 18:45 345阅读 0赞

# 实战链接：[https://www.acwing.com/activity/content/8/][https_www.acwing.com_activity_content_8] #

# Google KickStart 2019 A轮 #

## 1. 训练 ##

题目描述

作为一名学校足球教练，你的任务是挑选一支由P个学生组成的团队代表你的学校。

共有N名学生供你挑选，第 i 名学生的技术等级为SiSi，这是一个正整数，表示他们的技术水平。

在你看来一个合理的团队中的P个球员的技术应该是相当的，这样才能使每个人都融入到队内。

在最开始，你可能无法直接选出一个配置合理的队伍，因此你将为一些学生提供一对一的辅导。

将一名学生的技术等级提高1需要你花费1个小时的时间来进行辅导。

比赛季很快就开始了（事实上，第一场比赛已经开始了！），所以你想知道训练出一个合理的团队，你需要提供的最少训练小时数是多少。

输入格式

第一行包含整数T，表示共有T组测试数据。

每组测试数据的第一行包含两个整数N和P。

第二行包含N个整数SiSi，其中第 i 个整数为第 i 个学生的技术等级。

输出格式

每组数据输出一个结果，每个结果占一行。

结果表示为“Case \#x: y”，其中x为组别编号（从1开始），y为所需的最少训练小时数。

数据范围

1≤T≤1001≤T≤100,  
1≤Si≤100001≤Si≤10000,  
2≤P≤N2≤P≤N,  
2≤N≤1052≤N≤105

输入样例：

3
    4 3
    3 1 9 100
    6 2
    5 5 1 2 3 4
    5 5
    7 7 1 7 7

输出样例：

Case #1: 14
    Case #2: 0
    Case #3: 6

样例解释

在样例＃1中，你可以花费总共6个小时训练第一个学生，8个小时训练第二个学生，使得前三个学生的技能水平同为9。这是你可以花费的最短时间，因此答案是14。

在样例＃2中，你可以选择直接选择前两个学生而无需进行任何指导，因此答案为0。

在样例＃3中，P = N，因此每个学生都将加入您的团队。 你必须花6个小时训练第三个学生，这样所有人的技术等级都为7。 这是你可以花费的最短时间，所以答案是6。

### C++题解： ###

#include <iostream>
    #include <algorithm>
    #include <limits.h>
    
    using namespace std;
    
    const int N = 100010;
    
    int n, p;
    int skill[N], sum[N];
    
    int main()
    {
        int T;
        cin >> T;
        for (int C = 1; C <= T; C ++ )
        {
            cin >> n >> p;
            for (int i = 1; i <= n; i ++ ) cin >> skill[i];
            sort(skill + 1, skill + 1 + n);
            for (int i = 1; i <= n; i ++ ) sum[i] = sum[i - 1] + skill[i];
    
            int res = INT_MAX;
            for (int i = p; i <= n; i ++ )
                res = min(res, p * skill[i] - (sum[i] - sum[i - p]));
    
            printf("Case #%d: %d\n", C, res);
        }
        return 0;
    }

## 2.包裹 ##

恭喜你被聘为著名包裹投递公司的首席决策者（CDM）。

客户喜欢更快的物流，因此你决定在全球范围内降低包裹的运输时间，从而吸引更多客户。

你已经向当局介绍了这个想法，他们已经为你分配了足够的预算来建立一个新的运输处。

我们将世界划分为一个R×C的方格矩阵。

每个方格内或者存在一个运输处，或者没有。

你可以选择一个还未建立运输处的方格，在上面建立新的运输处。

如果某方格包含运输处，则包裹到该方格的运输时间为0。

否则，该方格的运输时间被定义为该方格与包含运输处的任何其他方格之间的最小曼哈顿距离。

总运输时间是所有方格的运输时间的最大值。

在你有权利建立一个新的运输处（最多一个）的情况下，总运输时间最短是多少？

注意：两个方格（r1，c1）和（r2，c2）之间的曼哈顿距离定义为| r1 - r2 | + | c1 - c2 |，其中| \* |运算符表示绝对值。

输入格式

第一行包含整数T，表示共有T组测试数据。

每组测试数据第一行包含两个整数R和C，分别表示矩阵的行数和列数。

接下来R行，每行包含一个长度为C的只包含0或1的字符串，其中0表示没有运输处，1表示有运输处。

输出格式

每组数据输出一个结果，每个结果占一行。

结果表示为“Case \#x: y”，其中x为组别编号（从1开始），y为最小总运输时间。

数据范围

1≤T≤1001≤T≤100,  
1≤R,C≤2501≤R,C≤250,  
数据保证至少存在一个运输处

输入样例：

3
    3 3
    101
    000
    101
    1 2
    11
    5 5
    10001
    00000
    00000
    00000
    10001

输出样例：

Case #1: 1
    Case #2: 0
    Case #3: 2

样例解释

在样例＃1中，通过在没有运输处的五个方格中的任何一个中建立新的运输处，你就可以获得最小总运输时间1。

在样例＃2中，所有方格都已经有一个运输处，因此最小总运输时间为0。请注意，你可以选择不建立新的运输处。

在样例＃3中，要获得最小的总运输时间2，你可以在以下任何方格中建立新的运输处：(2,3),(3,2),(3,3),(3,4),(4,3)。

题解：

#include <cstring>
    #include <iostream>
    #include <algorithm>
    #include <queue>
    #include <limits.h>
    
    using namespace std;
    
    const int N = 255;
    
    int n, m;
    string g[N];
    int dist[N][N];
    
    void bfs(int k)
    {
        queue<pair<int, int>> q;
        memset(dist, -1, sizeof dist);
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                if (g[i][j] == '1')
                {
                    dist[i][j] = 0;
                    q.push({i, j});
                }
    
        int dx[4] = {-1, 0, 1, 0, }, dy[4] = {0, 1, 0, -1};
        while (q.size())
        {
            auto t = q.front();
            q.pop();
            int x = t.first, y = t.second;
            int distance = dist[x][y];
            if (distance == k) continue;
            for (int i = 0; i < 4; i ++ )
            {
                int a = x + dx[i], b = y + dy[i];
                if (a >= 0 && a < n && b >= 0 && b < m && dist[a][b] == -1)
                {
                    dist[a][b] = distance + 1;
                    q.push({a, b});
                }
            }
        }
    }
    
    bool check(int k)
    {
        bfs(k);
    
        int min_sum = INT_MAX, max_sum = INT_MIN;
        int min_sub = INT_MAX, max_sub = INT_MIN;
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                if (dist[i][j] == -1)
                {
                    min_sum = min(min_sum, i + j);
                    max_sum = max(max_sum, i + j);
                    min_sub = min(min_sub, i - j);
                    max_sub = max(max_sub, i - j);
                }
    
        if (min_sum == INT_MAX) return true;
    
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                if (g[i][j] == '0')
                {
                    int sum = max(abs(i + j - min_sum), abs(i + j - max_sum));
                    int sub = max(abs(i - j - min_sub), abs(i - j - max_sub));
                    if (max(sum, sub) <= k) return true;
                }
    
        return false;
    }
    
    int main()
    {
        int T;
        cin >> T;
        for (int C = 1; C <= T; C ++ )
        {
            cin >> n >> m;
            for (int i = 0; i < n; i ++ ) cin >> g[i];
    
            int l = 0, r = n + m;
            while (l < r)
            {
                int mid = l + r >> 1;
                if (check(mid)) r = mid;
                else l = mid + 1;
            }
    
            printf("Case #%d: %d\n", C, r);
        }
    
        return 0;
    }

## 3.抢票 ##

你正在出售电影院前排座位的门票。

前排共有N个座位，从左到右编号为1到N。

短短一个周末的时间，就堆积了关于座位的Q个预订请求！

第 i 个预订要求订下从编号LiLi到RiRi的所有座位。

你现在将每个预订输入系统，一次输入一个。

由于某些预订可能会重叠，因此系统可能无法完全满足每个预订。

当你在系统中输入一个预订时，系统会将该预订所请求的座位里所有还未进行分配的座位分配给该预订。

现在要求每个订单都至少分配k个座位，请问k最大是多少。

输入格式

第一行包含整数T，表示共有T组测试数据。

每组测试数据第一行包含两个整数N和Q。

接下来Q行，每行包含两个整数LiLi和RiRi。

输出格式

每组数据输出一个结果，每个结果占一行。

结果表示为“Case \#x: y”，其中x为组别编号（从1开始），y为k的最大值。

数据范围

1≤T≤1001≤T≤100,  
1≤N≤1061≤N≤106,  
1≤Li≤Ri≤N1≤Li≤Ri≤N,  
1≤Q≤300001≤Q≤30000

输入样例：

3
    5 3
    1 2
    3 4
    2 5
    30 3
    10 11
    10 10
    11 11
    10 4
    1 8
    4 5
    3 6
    2 7

输出样例：

Case #1: 1
    Case #2: 0
    Case #3: 2

样例解释

在样例＃1中，有N = 5个席位和Q = 3个预订。一个可能的顺序是：

在第二次预订中，系统分配其2个座位（3和4）。  
在第一次预订中，系统分配其2个座位（1和2）。  
在第三次预订中，系统分配其1个座位（仅限座位5，因为座位1,2,3和4已经预订）。

每个预订至少分配1个座位，且不存在至少2个座位的分配方式，答案是1。

在样本案例＃2中，有N = 30个席位和Q = 3个预订。无论你如何分配座位，至少有一个预订将没有座位可分。所以答案是0.请注意，可以有座位不属于任何预订！

在样本案例＃3中，有N = 10个席位且Q = 4个预订。一个可能的顺序是：

在第二次预订中，系统分配其2个座位（4和5）。  
在第三次预订中，系统分配其2个座位（3和6，因为4和5已经预订）。请注意，预订的座位不一定彼此相邻。  
在第四次预订中，系统分配其2个座位（2和7）。  
在第一次预订时，系统分配其2个座位（1和8）。

每个预订至少分配2个座位，并且不存在至少3个座位的分配方式，因此答案是2。

include <iostream>
    using namespace std;
    
    define rep(i, a, b) for (int i = (a), i##end = (b); i < i##end; ++i)
    define debug(…) fprintf(stderr, VA_ARGS)
    define mp make_pair
    define x first
    define y second
    define pb push_back
    define SZ(x) (int((x).size()))
    define ALL(x) (x).begin(), (x).end()
    template[HTML_REMOVED] inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
    template[HTML_REMOVED] inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
    template[HTML_REMOVED] inline bool smin(T &a, const T &b) { return a > b ? a = b : a; }
    template[HTML_REMOVED] inline bool smax(T &a, const T &b) { return a < b ? a = b : a; }
    
    typedef long long LL;
    
    const int N = (int) 1e6 + 6, mod = (int) 0;
    int n, q, xl[N], xr[N], mvl[N];
    pair[HTML_REMOVED] sr[N];
    
    int check(int k) {
    for (int j = 0; j < q; j)
    xl[j] = sr[j].first, xr[j] = -sr[j].second, mvl[j] = xl[j];
    for (int j = 0; j < q; j) {
    int l = xl[j], r = xr[j]; 
    int st = mvl[j];
    int allowed_after = r;
    int cnt = 0;
    for (int i = j + 1; i < q; i) {
    if (xr[i] <= r) {
    if (xl[i] <= st) {
    st = max(st, xr[i]); 
    } else {
    cnt += xl[i] - st;
    st = max(st, xr[i]);
    if (cnt >= k) {
    allowed_after = xl[i] - (cnt - k);
    break;
    }
    }
    }
    }
    if (cnt < k) {
    cnt += r - st;
    if (cnt < k) return 0;
    allowed_after = r - (cnt - k);
    }
    for (int i = j + 1; i < q; i) {
    if (xl[i] >= allowed_after) break;
    if (xr[i] > r) {
    mvl[i] = max(mvl[i], r);
    }
    }
    }
    return 1;
    }
    int main() {
    int tc;
    cin >> tc;
    for (int tt = 1; tt <= tc; tt) {
    cout << “Case #” << tt << “: “;
    cin >> n >> q;
    for (int j = 0; j < q; j) {
    cin >> xl[j] >> xr[j], –xl[j];
    sr[j] = mp(xl[j], -xr[j]);
    }
    sort(sr, sr + q);
    int bl = 0, br = n + 1;
    while (bl < br - 1) {
    int bm = bl + br >> 1;
    if (check(bm)) {
    bl = bm;
    } else {
    br = bm;
    }
    }
    cout << bl << ‘\n’;
    
    }
    
     return 0;
    }

# 腾讯2019 暑期实习提前批笔试 #

## 硬币 ##

#include <iostream>
    
    using namespace std;
    
    int main()
    {
        int n, m;
        cin >> n >> m;
        cout << (m + n - 1) / n << endl;
        return 0;
    }

奇妙的数列

#include <iostream>
    
    using namespace std;
    
    int main()
    {
        int n, m;
        cin >> n >> m;
        cout << (m + n - 1) / n << endl;
        return 0;
    }

猜拳游戏

#include <iostream>
    
    using namespace std;
    
    typedef long long LL;
    const int N = 2000010, mod = 1000000007;
    
    int primes[N], cnt;
    int powers[N];
    bool st[N];
    
    void get_primes(int n)
    {
        int s = 0;
        for (int i = 2; i <= n; i ++ )
            if (!st[i])
            {
                primes[cnt ++ ] = i;
                for (int j = i * 2; j <= n; j += i)
                {
                    st[j] = true;
                    s ++ ;
                }
            }
    }
    
    int get(int n, int p)
    {
        int s = 0;
        while (n > 0)
        {
            s += n / p;
            n /= p;
        }
        return s;
    }
    
    int main()
    {
        int n, s;
        cin >> n >> s;
    
        if (s > n) cout << 0 << endl;
        else
        {
            get_primes(n);
    
            for (int i = 0; i < cnt; i ++ )
            {
                int p = primes[i];
                powers[i] += get(n, p) - get(s, p) - get(n - s, p);
            }
    
            int res = 1;
            for (int i = 0; i < cnt; i ++ )
            {
                int p = primes[i];
                while (powers[i] -- ) res = (LL)res * p % mod;
            }
    
            for (int i = 0; i < n - s; i ++ ) res = res * 2 % mod;
    
            cout << res << endl;
        }
    
        return 0;
    }

气球游戏

#include <iostream>
    
    using namespace std;
    
    const int N = 1000010, M = 2010;
    
    int n, m;
    int c[N], s[M];
    
    int main()
    {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i ++ ) scanf("%d", &c[i]);
        int res = n + 1;
    
        int colors = 0;
        for (int i = 1, j = 0; i <= n; i ++ )
        {
            if (c[i] && !s[c[i]]) colors ++ ;
            s[c[i]] ++ ;
    
            if (colors == m)
            {
                while (!c[j] || s[c[j]] > 1)
                {
                    s[c[j]] -- ;
                    j ++ ;
                }
    
                res = min(res, i - j + 1);
            }
        }
    
        if (res > n) res = -1;
        cout << res << endl;
    
        return 0;
    }

# 腾讯笔试题2019 #

小Q购物

#include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 110;
    
    int n, m;
    int c[N];
    
    int main()
    {
        cin >> m >> n;
        for (int i = 0; i < n; i ++ ) cin >> c[i];
    
        sort(c, c + n);
        while (n > 0 && c[n - 1] > m) n -- ;
    
        c[n] = m + 1;
    
        if (c[0] != 1) puts("-1");
        else
        {
            int res = 0;
            for (int i = 0, s = 0; i < n; i ++ )
            {
                int k = (c[i + 1] - 1 - s + c[i] - 1) / c[i];
                res += k;
                s += k * c[i];
            }
    
            cout << res << endl;
        }
    
        return 0;
    }

01串

#include <iostream>
    
    using namespace std;
    
    int main()
    {
        int n;
        string line;
        cin >> n >> line;
        int ones = 0, zeros = 0;
        for (auto c : line)
            if (c == '1') ones ++ ;
            else zeros ++ ;
    
        cout << abs(ones - zeros) << endl;
    
        return 0;
    }

打怪兽

//腾讯第三题标程
    
    #include <cstring>
    #include <iostream>
    
    using namespace std;
    
    typedef long long LL;
    const int N = 55;
    
    int n;
    LL d[N], f[N][N * 2];
    int p[N];
    
    int main()
    {
        cin >> n;
        for (int i = 1; i <= n; i ++ ) cin >> d[i];
        for (int i = 1; i <= n; i ++ ) cin >> p[i];
    
        memset(f, -1, sizeof f);
        f[0][0] = 0;
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n * 2; j ++ )
            {
                if (f[i - 1][j] >= d[i]) f[i][j] = f[i - 1][j];
                if (j >= p[i] && f[i - 1][j - p[i]] != -1) f[i][j] = max(f[i][j], f[i - 1][j - p[i]] + d[i]);
            }
    
        int res = 0;
        for (int i = 1; i <= n * 2; i ++ )
            if (f[n][i] != -1)
            {
                res = i;
                break;
            }
    
        cout << res << endl;
    
        return 0;
    }

邻值查找

//STL set方法：
    #include <iostream>
    #include <algorithm>
    #include <set>
    #include <limits.h>
    
    using namespace std;
    
    typedef long long LL;
    
    int main()
    {
        int n;
        set<pair<int, int>> S;
        S.insert({INT_MIN, 0});
        S.insert({INT_MAX, 0});
        cin >> n;
        for (int i = 1; i <= n; i ++ )
        {
            int v;
            cin >> v;
    
            if (i > 1)
            {
                auto it = S.upper_bound({v, 0});
                auto jt = it;
                jt -- ;
                LL rv = it->first - (LL)v, lv = (LL)v - jt->first;
                if (lv <= rv) cout << lv << ' ' << jt->second << endl;
                else cout << rv << ' ' << it->second << endl;
            }
    
            S.insert({v, i});
        }
    
        return 0;
    }
    //链表法
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    typedef pair<int, int> PII;
    
    const int N = 100010;
    
    int n;
    int p[N], l[N], r[N];
    PII a[N], ans[N];
    
    int main()
    {
        cin >> n;
        for (int i = 1; i <= n; i ++ )
        {
            cin >> a[i].first;
            a[i].second = i;
        }
    
        sort(a + 1, a + 1 + n);
    
        a[0].first = 1e9, a[n + 1].first = -1e9;
        for (int i = 1; i <= n; i ++ )
        {
            l[i] = i - 1, r[i] = i + 1;
            p[a[i].second] = i;
        }
    
        for (int i = n; i > 1; i -- )
        {
            int j = p[i], left = l[j], right = r[j];
            int lv = abs(a[j].first - a[left].first);
            int rv = abs(a[right].first - a[j].first);
            if (lv <= rv) ans[i] = {lv, a[left].second};
            else ans[i] = {rv, a[right].second};
    
            r[left] = right, l[right] = left;
        }
    
        for (int i = 2; i <= n; i ++ )
            cout << ans[i].first << ' ' << ans[i].second << endl;
    
        return 0;
    }

# 今日头条、京东笔试题2019 #

找零

#include <iostream>
    
    using namespace std;
    
    int main()
    {
        int n;
        cin >> n;
        n = 1024 - n;
        int res = 0;
    
        int coins[4] = {64, 16, 4, 1};
        for (int i = 0; i < 4; i ++ )
        {
            res += n / coins[i];
            n %= coins[i];
        }
    
        cout << res << endl;
    
        return 0;
    }

万万没想到之聪明的编辑

#include <iostream>
    
    using namespace std;
    
    const int N = 1000010;
    
    char s[N];
    
    int main()
    {
        int T;
        cin >> T;
        while (T -- )
        {
            cin >> s;
            int k = 0;
            for (int i = 0; s[i]; i ++ )
            {
                s[k ++ ] = s[i];
    
                if (k >= 3 && s[k - 3] == s[k - 2] && s[k - 2] == s[k - 1]) k -- ;
                if (k >= 4 && s[k - 4] == s[k - 3] && s[k - 2] == s[k - 1]) k -- ;
            }
            s[k] = '\0';
            cout << s << endl;
        }
        return 0;
    }

奖品分配

#include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    typedef long long LL;
    typedef pair<int, int> PII;
    
    const int N = 100010;
    
    int n;
    int score[N], bonus[N];
    PII person[N];
    
    int main()
    {
        int T;
        scanf("%d", &T);
        while (T -- )
        {
            scanf("%d", &n);
            for (int i = 0; i < n; i ++ )
            {
                scanf("%d", &score[i]);
                person[i] = {score[i], i};
            }
    
            sort(person, person + n);
    
            for (int i = 0; i < n; i ++ )
            {
                int s = person[i].first, p = person[i].second;
                int left = (p + n - 1) % n, right = (p + 1) % n;
                int lv = 1, rv = 1;
                if (score[left] < s) lv = bonus[left] + 1;
                if (score[right] < s) rv = bonus[right] + 1;
    
                bonus[p] = max(lv, rv);
            }
    
            LL res = 0;
            for (int i = 0; i < n; i ++ ) res += bonus[i];
    
            cout << res << endl;
        }
    
        return 0;
    }

剪绳子

#include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 100010;
    
    int n, m;
    int len[N];
    
    double check(double mid)
    {
        int sum = 0;
        for (int i = 0; i < n; i ++ )
        {
            sum += len[i] / mid;
            if (sum >= m) return true;
        }
        return false;
    }
    
    int main()
    {
        cin >> n >> m;
        for (int i = 0; i < n; i ++ ) cin >> len[i];
    
        double l = 0, r = 1e9;
        while (r - l > 1e-4)
        {
            double mid = (l + r) / 2;
            if (check(mid)) l = mid;
            else r = mid;
        }
    
        printf("%.2lf\n", r);
        return 0;
    }

疏散人群

#include <cstring>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 100010, M = N * 2;
    
    int n;
    int h[N], e[M], ne[M], idx;
    int q[N];
    bool st[N];
    
    void add(int a, int b)
    {
        e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
    }
    
    int bfs(int u)
    {
        int hh = 0, tt = 0;
        q[0] = u;
        st[u] = true;
    
        while (hh <= tt)
        {
            int t = q[hh ++ ];
            for (int i = h[t]; ~i; i = ne[i])
            {
                int j = e[i];
                if (!st[j])
                {
                    q[ ++ tt] = j;
                    st[j] = true;
                }
            }
        }
    
        return tt + 1;
    }
    
    int main()
    {
        scanf("%d", &n);
        memset(h, -1, sizeof h);
        for (int i = 0; i < n - 1; i ++ )
        {
            int a, b;
            scanf("%d%d", &a, &b);
            add(a, b), add(b, a);
        }
    
        int res = 0;
    
        st[1] = true;
        for (int i = h[1]; ~i; i = ne[i]) res = max(res, bfs(e[i]));
    
        printf("%d\n", res);
        return 0;
    }

丢失的序列

#include <cstring>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    typedef long long LL;
    const LL mod = 998244353;
    const int N = 10010, M = 210;
    
    int n;
    int a[N];
    LL f[N][M][3], s1[N], s2[N];
    
    int main()
    {
        cin >> n;
        for (int i = 1; i <= n; i ++ ) cin >> a[i];
    
        for (int i = max(1, a[1]); i <= (a[1] ? a[1] : 200); i ++ )
            for (int j = max(1, a[2]); j <= (a[2] ? a[2] : 200); j ++ )
                if (i == j) f[2][j][1] ++ ;
                else if(i < j) f[2][j][2] ++ ;
    
        for (int j = 1; j <= 200; j ++ )
        {
            s1[j] = s1[j - 1] + f[2][j][0] + f[2][j][1] + f[2][j][2];
            s2[j] = s2[j - 1] + f[2][j][0] + f[2][j][1];
        }
    
        for (int i = 3; i <= n; i ++ )
        {
            for (int j = max(1, a[i]); j <= (a[i] ? a[i] : 200); j ++ )
            {
                f[i][j][1] = (f[i - 1][j][0] + f[i - 1][j][1] + f[i - 1][j][2]) % mod;
                f[i][j][0] = (s2[200] - s2[j]) % mod;
                f[i][j][2] = (s1[j - 1] - s1[0]) % mod;
            }
    
            for (int j = 1; j <= 200; j ++ )
            {
                s1[j] = s1[j - 1] + f[i][j][0] + f[i][j][1] + f[i][j][2];
                s2[j] = s2[j - 1] + f[i][j][0] + f[i][j][1];
            }
        }
    
        LL res = 0;
        for (int i = max(1, a[n]); i <= (a[n] ? a[n] : 200); i ++ ) res += f[n][i][0] + f[n][i][1];
    
        cout << (res % mod + mod) % mod << endl;
    
        return 0;
    }

# 今日头条笔试题2019 #

变身程序员

#include <iostream>
    #include <sstream>
    #include <algorithm>
    #include <queue>
    #include <cstring>
    
    using namespace std;
    
    typedef pair<int, int> PII;
    
    const int N = 11;
    
    int n, m;
    int g[N][N];
    int d[N][N];
    
    int bfs()
    {
        queue<PII> que;
        memset(d, -1, sizeof d);
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                if (g[i][j] == 2)
                {
                    d[i][j] = 0;
                    que.push({i, j});
                }
    
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
        while (que.size())
        {
            auto t = que.front();
            int x = t.first, y = t.second, dist = d[x][y];
            que.pop();
    
            for (int i = 0; i < 4; i ++ )
            {
                int a = x + dx[i], b = y + dy[i];
                if (a >= 0 && a < n && b >= 0 && b < m && d[a][b] == -1 && g[a][b] == 1)
                {
                    d[a][b] = dist + 1;
                    que.push({a, b});
                }
            }
        }
    
        int res = 0;
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                if (g[i][j] == 1)
                {
                    if (d[i][j] == -1) return -1;
                    res = max(res, d[i][j]);
                }
    
        return res;
    }
    
    int main()
    {
        string line;
        while (getline(cin, line))
        {
            stringstream ssin(line);
            int k = 0, x;
            while (ssin >> x) g[n][k ++ ] = x;
            n ++ ;
            m = k;
        }
    
        cout << bfs() << endl;
    
        return 0;
    }

特征提取

#include <iostream>
    #include <algorithm>
    #include <map>
    #include <cstring>
    
    using namespace std;
    
    typedef pair<int, int> PII;
    
    const int N = 100010;
    
    int main()
    {
        int n;
        cin >> n;
        int res = 0;
        map<PII, int> count, last_time;
        for (int k = 1; k <= n; k ++ )
        {
            int m;
            cin >> m;
            for (int i = 1; i <= m; i ++ )
            {
                PII t;
                cin >> t.first >> t.second;
                if (last_time[t] == k - 1) count[t] ++ ;
                else if (last_time[t] != k) count[t] = 1;
                last_time[t] = k;
    
                res = max(res, count[t]);
            }
        }
    
        cout << res << endl;
        return 0;
    }

机器人跳跃问题

#include <iostream>
    #include <algorithm>
    #include <cstring>
    
    using namespace std;
    
    typedef long long LL;
    
    const int N = 100010;
    
    int n;
    int h[N];
    
    bool check(LL e)
    {
        for (int i = 1; i <= n; i ++ )
        {
            e = e - (h[i] - e);
            if (e >= 1e10) return true;
            if (e < 0) return false;
        }
        return true;
    }
    
    int main()
    {
        cin >> n;
        for (int i = 1; i <= n; i ++ ) cin >> h[i];
    
        LL l = 0, r = 1e10;
    
        while (l < r)
        {
            LL mid = l + r >> 1;
            if (check(mid)) r = mid;
            else l = mid + 1;
        }
    
        cout << r << endl;
    
        return 0;
    }

毕业旅行问题

#include <cstring>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 20, M = 1 << N;
    
    int n;
    int f[M][N];
    int cost[N][N];
    
    int main()
    {
        cin >> n;
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < n; j ++ )
                cin >> cost[i][j];
    
        memset(f, 0x3f, sizeof f);
    
        f[1][0] = 0;
        for (int i = 0; i < 1 << n; i ++ )
            for (int j = 0; j < n; j ++ )
                if (i >> j & 1)
                    for (int k = 0; k < n; k ++ )
                        if (i - (1 << j) >> k & 1)
                            f[i][j] = min(f[i][j], f[i - (1 << j)][k] + cost[k][j]);
    
        int res = 1e9;
        for (int i = 1; i < n; i ++ ) res = min(res, f[(1 << n) - 1][i] + cost[i][0]);
    
        cout << res << endl;
    
        return 0;
    }

过河

#include <iostream>
    #include <algorithm>
    #include <cstring>
    
    using namespace std;
    
    typedef long long LL;
    
    const int N = 100010;
    
    int n;
    int a[N];
    LL f[N];
    
    int main()
    {
        int T;
        cin >> T;
        while (T -- )
        {
            cin >> n;
            for (int i = 1; i <= n; i ++ ) cin >> a[i];
            sort(a + 1, a + 1 + n);
    
            if (n <= 2) cout << a[2] << endl;
            else
            {
                memset(f, 0, sizeof f);
                for (int i = n; i > 3; i -- )
                {
                    f[i] = f[i + 1] + a[i] + a[2];
                    if (i + 2 <= n + 1) f[i] = min(f[i], f[i + 2] + a[i + 1] + 2 * a[3] + a[2]);
                    if (i + 3 <= n + 1) f[i] = min(f[i], f[i + 3] + 2 * a[2] + a[3] + a[4] + a[i + 2] + a[4]);
                }
                cout << a[3] + f[4] << endl;
            }
        }
    
        return 0;
    }

# Google KickStart 2019 B轮 #

## 构建回文 ##

安娜有N个方块排成一排，每一方块都写着一个大写字母(A-Z中的一个)。

这些方块从左到右依次编号为1,2,…,N。

现在，她正在学习回文。

如果一个字符串不论是从左向右看，还是从右向左看，内容都一样，那么这个字符串就是一个回文字符串。

例如，ANNA,RACECAR,AAA和X都是回文字符串，而AB,FROG和YOYO则不是。

鲍勃想要测试一下安娜是否完全理解了回文这一概念，所以向她提出了Q个相关问题。

其中的第i个问题是：安娜能否使用从LiLi号到RiRi号（包括端点方块）的所有方块，经过一系列排列使得它们构成一个回文结构？

如果可以，则回答“是”，如果不可以，则回答“否”。

在每个问题解答完毕之后，安娜都会把方块放回原来的位置。

请你帮助安娜求出，这些问题中有多少个问题可以回答“是”。

输入格式

第一行包含整数T，表示共有T组测试数据。

每组数据第一行包含两个整数N和Q，表示方块数量和问题数量。

第二行包含一个长度为N的由大写字母构成的字符串。

接下来Q行，每行包含两个整数LiLi和RiRi，用来描述一个问题。

输出格式

每组数据输出一个结果，每个结果占一行。

结果表示为“Case \#x: y”，其中x是组别编号（从1开始），y是可以回答“是”的问题数量。

数据范围

1≤T≤1001≤T≤100,  
1≤Li≤Ri≤N1≤Li≤Ri≤N,  
1≤N,Q≤1051≤N,Q≤105

输入样例：

2
    7 5
    ABAACCA
    3 6
    4 4
    2 5
    6 7
    3 7
    3 5
    XYZ
    1 3
    1 3
    1 3
    1 3
    1 3

输出样例：

Case #1: 3
    Case #2: 0

样例解释

在样例＃1中，N = 7且Q = 5。

*  对于第一个问题，安娜需要使用方块AACC，经排列可得到回文结构ACCA（或CAAC）。
 *  对于第二个问题，安娜需要使用方块A，这是回文结构。
 *  对于第三个问题，安娜需要使用方块BAAC，这些方块无法排列得到回文结构。
 *  对于第四个问题，安娜需要使用方块CA，这些方块无法排列得到回文结构。
 *  对于第五个问题，安娜需要使用方块AACCA，经排列可得到回文结构ACACA（或CAAAC）。

总体来看，共有3个问题可以回答“是”，所以答案是3。

在样例＃2中，N = 3且Q = 5。

在这五个问题中，安娜都需要使用方块XYZ来创建回文，显然不可能，所以答案是0。

#include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 100010;
    
    int n, m;
    char str[N];
    int s[26][N];
    
    int main()
    {
        int T;
        cin >> T;
        for (int C = 1; C <= T; C ++ )
        {
            cin >> n >> m;
            scanf("%s", str + 1);
            for (int i = 1; i <= n; i ++ )
                for (int j = 0; j < 26; j ++ )
                    s[j][i] = s[j][i - 1] + (str[i] == j + 'A');
    
            int res = 0;
            for (int i = 0; i < m; i ++ )
            {
                int l, r;
                cin >> l >> r;
                int cnt = 0;
                for (int j = 0; j < 26; j ++ )
                    if (s[j][r] - s[j][l - 1] & 1)
                        cnt ++ ;
                if (cnt <= 1) res ++ ;
            }
    
            printf("Case #%d: %d\n", C, res);
        }
    
        return 0;
    }

## 能量石 ##

岩石怪物杜达生活在魔法森林中，他在午餐时收集了N块能量石准备开吃。

由于他的嘴很小，所以一次只能吃一块能量石。

能量石很硬，吃完需要花不少时间。

吃完第 i 块能量石需要花费的时间为SiSi秒。

杜达靠吃能量石来获取能量。

不同的能量石包含的能量可能不同。

此外，能量石会随着时间流逝逐渐失去能量。

第 i 块能量石最初包含EiEi单位的能量，并且每秒将失去LiLi单位的能量。

当杜达开始吃一块能量石时，他就会立即获得该能量石所含的全部能量（无论实际吃完该石头需要多少时间）。

能量石中包含的能量最多降低至0。

请问杜达吃完所有石头可以获得的最大能量是多少？

输入格式

第一行包含整数T，表示共有T组测试数据。

每组数据第一行包含整数N，表示能量石的数量。

接下来N行，每行包含三个整数Si,Ei,LiSi,Ei,Li。

### 输出格式 ###

每组数据输出一个结果，每个结果占一行。

结果表示为“Case \#x: y”，其中x是组别编号（从1开始），y是可以获得的最大能量值。

数据范围

1≤T≤1001≤T≤100,  
1≤N≤1001≤N≤100,  
1≤Si≤1001≤Si≤100,  
1≤Ei≤1051≤Ei≤105,  
0≤Li≤1050≤Li≤105

输入样例：

3
    4
    20 10 1
    5 30 5
    100 30 1
    5 80 60
    3
    10 4 1000
    10 3 1000
    10 8 1000
    2
    12 300 50
    5 200 0

输出样例：

Case #1: 105
    Case #2: 8
    Case #3: 500

样例解释

在样例＃1中，有N = 4个宝石。杜达可以选择的一个吃石头顺序是：

*  吃第四块石头。这需要5秒，并给他80单位的能量。
 *  吃第二块石头。这需要5秒，并给他5单位的能量（第二块石头开始时具有30单位能量，5秒后失去了25单位的能量）。
 *  吃第三块石头。这需要100秒，并给他20单位的能量（第三块石头开始时具有30单位能量，10秒后失去了10单位的能量）。
 *  吃第一块石头。这需要20秒，并给他0单位的能量（第一块石头以10单位能量开始，110秒后已经失去了所有的能量）。

他一共获得了105单位的能量，这是能获得的最大值，所以答案是105。

在样本案例＃2中，有N = 3个宝石。

无论杜达选择吃哪块石头，剩下的两个石头的能量都会耗光。

所以他应该吃第三块石头，给他提供8单位的能量。

在样本案例＃3中，有N = 2个宝石。杜达可以：

*  吃第一块石头。这需要12秒，并给他300单位的能量。
 *  吃第二块石头。这需要5秒，并给他200单位的能量（第二块石头随着时间的推移不会失去任何能量！）。

所以答案是500。

#include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 110;
    
    int n;
    
    struct Stone
    {
        int s, e, l;
    
        bool operator<(const Stone &W) const
        {
            return s * W.l < W.s * l;
        }
    }stones[N];
    
    int f[N][10010];
    
    int main()
    {
        int T;
        cin >> T;
        for (int C = 1; C <= T; C ++ )
        {
            cin >> n;
            int m = 0;
            for (int i = 1; i <= n; i ++ )
            {
                int s, e, l;
                cin >> s >> e >> l;
                m += s;
                stones[i] = {s, e, l};
            }
    
            sort(stones + 1, stones + 1 + n);
    
            for (int i = 1; i <= n; i ++ )
                for (int j = 0; j <= m; j ++ )
                {
                    f[i][j] = f[i - 1][j];
                    if (j >= stones[i].s)
                        f[i][j] = max(f[i][j], f[i - 1][j - stones[i].s] + max(0, stones[i].e - stones[i].l * (j - stones[i].s)));
                }
    
            int res = 0;
            for (int i = 0; i <= m; i ++ ) res = max(res, f[n][i]);
    
            printf("Case #%d: %d\n", C, res);
        }
    
        return 0;
    }

## 多样性子阵 ##

Vanity的架子上有N个小饰品，从左到右编号为1,2,......,N。

不同的小饰品的类型可能不同，饰品类型用正整数表示。

架子上的第 i 个饰品的类型是AiAi。

今天她要去海外看她的家人，并希望尽可能多地给家人带些小饰品。

然而，由于时间匆忙，Vanity来不及仔细挑选，只能带走连续的一部分小饰品。

具体的说，Vanity选择两个索引l和r，并带走编号为l,l + 1,…,r-1,r的小饰品。

此外，由于税收规则，如果Vanity携带的小饰品中某种类型的小饰品的数量超过了S，则机场安保人员将扣留所有该类型的小饰品。

例如，假设S = 2，并且Vanity带了六个小饰品：一个是类型0，两个是类型1，三个是类型2,她将被允许保留类型0的饰品和类型1的两个小饰品，但是所有类型2的小饰品就会被扣留！

Vanity需要慎重选择l和r，这样她才能为家人带来最多的饰品。

请问，她能带来的最大饰品数量是多少？

输入格式

第一行包含整数T，表示共有T组测试数据。

每组数据第一行包含两个整数N和S，表示小饰品的数量和单个类型小饰品的数量限制。

第二行包含N个整数AiAi，其中第 i 个整数表示第 i 个小饰品的类型。

输出格式

每组数据输出一个结果，每个结果占一行。

结果表示为“Case \#x: y”，其中x是组别编号（从1开始），y是能够带给家人的小饰品的最大数量。

数据范围

1≤T≤1001≤T≤100,  
1≤Ai≤1051≤Ai≤105,  
1≤S≤N1≤S≤N,  
1≤N≤1051≤N≤105

输入样例：

4
    6 2
    1 1 4 1 4 4
    8 1
    1 2 500 3 4 500 6 7
    10 1
    100 200 8 8 8 8 8 300 400 100
    12 2
    40 50 1 1 1 60 70 2 2 2 80 90

输出样例：

Case #1: 4
    Case #2: 6
    Case #3: 4
    Case #4: 6

样例解释

在样例＃1中，Vanity可以选择l = 2，r = 5，这使她将4个小饰品：1,4,1,4带到机场。它们都能通过安检，因此她可以为她的家人带来4件小饰品。

在样例＃2中，Vanity可以选择l = 1，r = 8，这使她将所有8个小饰品带到机场。其中，500型小饰品因为数量超过S = 1而被扣留，因此她可以为她的家人带来6件小饰品。

在样例＃3中，Vanity可以选择l = 1，r = 9，这使她将9个小饰品：100,200,8,8,8,8,8,300,400带到机场。其中8型小饰品因为数量超过S = 1而被扣留，因此她可以为她的家人带来4件小饰品。

在样例＃4中，Vanity可以选择l = 1，r = 12，这使她将所有12个小饰品带到机场。其中1型和2型的小饰品因为数量超过S = 2而被扣留，因此她可以为她的家人带来6件小饰品。

#include <cstring>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    
    using namespace std;
    
    const int N = 100010;
    
    int n, m;
    int types[N], a[N];
    vector<int> all[N + 1];
    
    struct Node
    {
        int l, r;
        int s, ps;
    }tr[N << 2];
    
    void build(int u, int l, int r)
    {
        tr[u].l = l, tr[u].r = r;
        if (l == r)
        {
            tr[u].s = tr[u].ps = a[l];
            return;
        }
        int mid = l + r >> 1, left = u << 1, right = left | 1;
        build(left, l, mid), build(right, mid + 1, r);
        tr[u].s = tr[left].s + tr[right].s;
        tr[u].ps = max(tr[left].ps, tr[left].s + tr[right].ps);
    }
    
    void update(int u, int k, int v)
    {
        if (tr[u].l == tr[u].r)
        {
            a[k] = v;
            tr[u].s = tr[u].ps = v;
            return;
        }
    
        int mid = tr[u].l + tr[u].r >> 1, left = u << 1, right = left | 1;
        if (k <= mid) update(left, k, v);
        else update(right, k, v);
        tr[u].s = tr[left].s + tr[right].s;
        tr[u].ps = max(tr[left].ps, tr[left].s + tr[right].ps);
    }
    
    int main()
    {
        int T;
        cin >> T;
        for (int C = 1; C <= T; C ++ )
        {
            cin >> n >> m;
    
            for (int i = 0; i < N; i ++ ) all[i].clear();
    
            for (int i = 0; i < n; i ++ )
            {
                cin >> types[i];
                all[types[i]].push_back(i);
            }
    
            memset(a, 0, sizeof a);
            for (int i = 0; i < N; i ++ )
            {
                for (int j = 0; j < m && j < all[i].size(); j ++ ) a[all[i][j]] = 1;
                if (all[i].size() >= m + 1) a[all[i][m]] = -m;
            }
    
            build(1, 0, n - 1);
    
            int res = tr[1].ps;
    
            for (int i = 0; i < n; i ++ )
            {
                update(1, i, 0);
                auto indexes = all[types[i]];
                int j = lower_bound(indexes.begin(), indexes.end(), i) - indexes.begin();
                if (j + m < indexes.size()) update(1, indexes[j + m], 1);
                if (j + m + 1 < indexes.size()) update(1, indexes[j + m + 1], -m);
                res = max(res, tr[1].ps);
            }
    
            printf("Case #%d: %d\n", C, res);
        }
    
        return 0;
    }

# 美团笔试题2019 #

## 蛇形矩阵 ##

输入两个整数n和m，输出一个n行m列的矩阵，将数字 1 到 n\*m 按照回字蛇形填充至矩阵中。

具体矩阵形式可参考样例。

输入格式

输入共一行，包含两个整数n和m。

输出格式

输出满足要求的矩阵。

矩阵占n行，每行包含m个空格隔开的整数。

数据范围

1≤n,m≤1001≤n,m≤100

输入样例：

3 3

输出样例：

1 2 3
    8 9 4
    7 6 5

#include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 110;
    
    int res[N][N];
    bool st[N][N];
    
    int main()
    {
        int n, m;
        cin >> n >> m;
    
        int dx[] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
        int x = 0, y = 0, d = 1;
    
        for (int i = 1; i <= n * m; i ++ )
        {
            int a = x + dx[d], b = y + dy[d];
            if (a < 0 || a >= n || b < 0 || b >= m || st[a][b])
            {
                d = (d + 1) % 4;
                a = x + dx[d], b = y + dy[d];
            }
    
            res[x][y] = i;
            st[x][y] = true;
            x = a, y = b;
        }
    
        for (int i = 0; i < n; i ++ )
        {
            for (int j = 0; j < m; j ++ )
            {
                cout << res[i][j] << ' ';
            }
            cout << endl;
        }
    
        return 0;
    }

修改矩阵

#include <cstring>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <unordered_map>
    
    using namespace std;
    
    typedef pair<int, int> PII;
    
    int main()
    {
        int n, m;
        unordered_map<int, int> A, B;
    
        cin >> n >> m;
    
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
            {
                int x;
                cin >> x;
                if (i + j & 1) A[x] ++ ;
                else B[x] ++ ;
            }
    
        vector<PII> as, bs;
        for (auto item : A) as.push_back({item.second, item.first});
        for (auto item : B) bs.push_back({item.second, item.first});
    
        sort(as.begin(), as.end());
        sort(bs.begin(), bs.end());
    
        reverse(as.begin(), as.end());
        reverse(bs.begin(), bs.end());
    
        int res = -1;
        for (int i = 0; i < 2 && i < as.size(); i ++ )
            for (int j = 0; j < 2 && j < bs.size(); j ++ )
                if (as[i].second != bs[j].second) res = max(res, as[i].first + bs[j].first);
                else
                {
                    res = max(res, max(as[i].first, bs[j].first));
                }
    
        if (as.empty()) res = bs[0].first;
        if (bs.empty()) res = as[0].first;
    
        cout << n * m - res << endl;
    
        return 0;
    }

切割树

#include <cstring>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    typedef long long LL;
    
    const int N = 100010, mod = 1e9 + 7;
    
    int n;
    int h[N], e[N], ne[N], idx;
    int color[N];
    int f[N][2];
    int l[N], r[N], q[N];
    
    void add(int a, int b)
    {
        e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
    }
    
    void dfs(int u)
    {
        for (int i = h[u]; ~i; i = ne[i]) dfs(e[i]);
    
        if (color[u] == 0)
        {
            f[u][1] = 1;
            for (int i = h[u]; ~i; i = ne[i])
            {
                int j = e[i];
                f[u][1] = (LL)f[u][1] * (f[j][0] + f[j][1]) % mod;
            }
        }
        else
        {
            f[u][0] = 1;
            for (int i = h[u]; ~i; i = ne[i])
            {
                int j = e[i];
                f[u][0] = (LL)f[u][0] * (f[j][0] + f[j][1]) % mod;
            }
    
            int k = 0;
            for (int i = h[u]; ~i; i = ne[i]) q[ ++ k] = e[i];
    
            l[0] = r[k + 1] = 1;
            for (int i = 1; i <= k; i ++ ) l[i] = (LL)l[i - 1] * (f[q[i]][0] + f[q[i]][1]) % mod;
            for (int i = k; i >= 1; i -- ) r[i] = (LL)r[i + 1] * (f[q[i]][0] + f[q[i]][1]) % mod;
    
            for (int i = 1; i <= k; i ++ )
                f[u][1] = (f[u][1] + (LL)f[q[i]][1] * l[i - 1] % mod * r[i + 1]) % mod;
        }
    }
    
    int main()
    {
        cin >> n;
    
        memset(h, -1, sizeof h);
    
        for (int i = 1; i < n; i ++ )
        {
            int p;
            cin >> p;
            add(p, i);
        }
    
        for (int i = 0; i < n; i ++ ) cin >> color[i];
    
        dfs(0);
    
        cout << f[0][1] << endl;
    
        return 0;
    }

格子染色

#include <iostream>
    #include <algorithm>
    #include <vector>
    
    using namespace std;
    
    typedef long long LL;
    
    const int N = 10010;
    
    struct Segment
    {
        int k;
        int l, r;
    
        bool operator< (const Segment &W)const
        {
            if (k != W.k) return k < W.k;
            if (l != W.l) return l < W.l;
            return r < W.r;
        }
    };
    
    LL merge(vector<Segment> &q)
    {
        vector<Segment> w;
        sort(q.begin(), q.end());
    
        LL res = 0;
        for (int i = 0; i < q.size();)
        {
            int j = i;
            while (j < q.size() && q[j].k == q[i].k) j ++ ;
    
            int l = -2e9, r = l - 1;
            for (int k = i; k < j; k ++ )
                if (r < q[k].l)
                {
                    res += r - l + 1;
                    if (l != -2e9) w.push_back({q[i].k, l, r});
                    l = q[k].l, r = q[k].r;
                }
                else r = max(r, q[k].r);
    
            if (l != -2e9) w.push_back({q[i].k, l, r});
    
            res += r - l + 1;
            i = j;
        }
    
        q = w;
    
        return res;
    }
    
    int main()
    {
        int n;
        cin >> n;
    
        vector<Segment> rows, cols;
    
        while (n -- )
        {
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            if (x1 == x2) cols.push_back({x1, min(y1, y2), max(y1, y2)});
            else rows.push_back({y1, min(x1, x2), max(x1, x2)});
        }
    
        LL res = merge(rows) + merge(cols);
    
        for (auto r : rows)
            for (auto c : cols)
                if (r.k >= c.l && r.k <= c.r && c.k >= r.l && c.k <= r.r)
                    res -- ;
    
        cout << res << endl;
    
        return 0;
    }

# 美团、拼多多笔试题2019 #

## 爱健身的小王 ##

#include <iostream>
    
    using namespace std;
    
    int gcd(int a, int b)
    {
        return b ? gcd(b, a % b) : a;
    }
    
    int main()
    {
        int T;
        cin >> T;
        while (T -- )
        {
            int n;
            cin >> n;
            int d = gcd(4 * n, n + 1);
            cout << 4 * n / d + 1 << endl;
        }
    
        return 0;
    }

趣味字母卡片

#include <iostream>
    #include <algorithm>
    #include <unordered_set>
    
    using namespace std;
    
    int main()
    {
        string str;
        cin >> str;
    
        for (auto &c : str) c = tolower(c);
    
        for (char c = 'a'; c <= 'z'; c ++ )
        {
            int k = 0;
            while (k < str.size() && str[k] != c) k ++ ;
    
            unordered_set<char> hash;
            for (int i = k + 1; i < str.size(); i ++ ) hash.insert(str[i]);
    
            bool can = true;
            for (int i = 0; i < k; i ++ )
                if (!hash.count(str[i]))
                {
                    can = false;
                    break;
                }
            if (can)
            {
                cout << c << endl;
                break;
            }
        }
    
        return 0;
    }

避嫌抢劫

#include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    typedef pair<int, int> PII;
    
    const int N = 200010;
    
    int n, d;
    PII banks[N];
    
    int main()
    {
        cin >> n >> d;
        for (int i = 1; i <= n; i ++ ) cin >> banks[i].first >> banks[i].second;
    
        sort(banks + 1, banks + 1 + n);
    
        int res = 0;
        for (int i = 1, j = 0, maxv = -1e9; i <= n; i ++ )
        {
            while (j + 1 < i && banks[i].first - banks[j + 1].first >= d)
            {
                j ++ ;
                maxv = max(maxv, banks[j].second);
            }
    
            res = max(res, banks[i].second + maxv);
        }
    
        cout << res << endl;
    
        return 0;
    }

括号序列

#include <iostream>
    #include <algorithm>
    #include <string.h>
    
    using namespace std;
    
    const int N = 2510, mod = 1e9 + 7;
    
    int n, m;
    char a[N], b[N];
    int as[N], bs[N];
    int f[N][N];
    
    void get_prefix_sum(int sum[], char str[], int k)
    {
        for (int i = 1; i <= k; i ++ )
            if (str[i] == '(')
                sum[i] = sum[i - 1] + 1;
            else
                sum[i] = sum[i - 1] - 1;
    }
    
    int main()
    {
        cin >> a + 1 >> b + 1;
    
        n = strlen(a + 1);
        m = strlen(b + 1);
    
        get_prefix_sum(as, a, n);
        get_prefix_sum(bs, b, m);
    
        if (as[n] + bs[m] != 0) puts("0");
        else
        {
            for (int i = 0; i <= n; i ++ )
                for (int j = 0; j <= m; j ++ )
                    if (!i && !j) f[i][j] = 1;
                    else
                    {
                        if (as[i] + bs[j] >= 0)
                        {
                            if (i) f[i][j] += f[i - 1][j];
                            if (j) f[i][j] += f[i][j - 1];
                            f[i][j] %= mod;
                        }
                    }
    
            cout << f[n][m] << endl;
        }
    
        return 0;
    }

# google kickstart往年题 #

偶数

Supervin有一个独特的计算器。

此计算器由一个显示器，一个加号按钮和一个减号按钮构成。

目前，计算器显示器上显示整数 N。

按加号按钮可将计算器显示屏上显示的当前数字增加1。

同理，按减号按钮可将计算器显示屏上显示的当前数字减1。

计算器不显示任何前导零。

例如，如果计算器显示屏上显示100，则按减号按钮一次将使计算器显示99。

Supervin不喜欢奇数，因为他认为他们是“奇怪的”。

因此，他想通过按动计算器上的按钮来改变显示器上的数字，使得显示数字变为一个全部数位上数字均为偶数的十进制数。

因为计算器比较老旧，按钮并不是很好用，因此Supervin希望尽可能少的按动按钮。

请帮助Supervin确定要使得显示数字各个数位均为偶数，至少需要按动多少次按钮。

输入格式

输入第一行包含整数T，表示共有T组测试数据。

接下来T行，每行包含一个整数N，表示显示器上最初显示的数字。

输出格式

每组测试数据输出一个结果，每个结果占一行。

结果表示为“Case \#x: y”，其中x为组别编号（从1开始），y为该组数据结果（即最少按动次数）。

数据范围

1≤T≤1001≤T≤100,  
1≤N≤10161≤N≤1016

输入样例：

4
    42
    11
    1
    2018

输出样例：

Case #1: 0
    Case #2: 3
    Case #3: 1
    Case #4: 2

样例解释

在样例＃1中，最初显示在计算器上的整数各位均为偶数，因此不需要按下按钮。  
在样例＃2中，最少按动三次减号按钮使计算器显示8。  
在样例＃3中，最少按动减号按钮一次使计算器显示0或按动加号按钮一次使计算器显示2。  
在样例＃4中，最少按动两次加号按钮将使计算器显示2020。

#include <iostream>
    #include <algorithm>
    #include <vector>
    
    using namespace std;
    
    typedef long long LL;
    
    int main()
    {
        int T;
        cin >> T;
    
        for (int C = 1; C <= T; C ++ )
        {
            LL n;
            cin >> n;
            vector<int> nums;
    
            LL x = n;
            while (x) nums.push_back(x % 10), x /= 10;
    
            LL l = 0, r = 0, res = 0;
            for (int i = nums.size() - 1; i >= 0; i -- )
            {
                int u = nums[i];
                if (u % 2 == 0)
                {
                    l = l * 10 + u;
                    r = r * 10 + u;
                }
                else
                {
                    l = l * 10 + u - 1;
                    for (int j = i - 1; j >= 0; j -- ) l = l * 10 + 8;
                    res = n - l;
    
                    if (u != 9)
                    {
                        r = r * 10 + u + 1;
                        for (int j = i - 1; j >= 0; j -- ) r = r * 10 + 0;
                        if (res > r - n) res = r - n;
                    }
    
                    break;
                }
            }
    
            printf("Case #%d: %lld\n", C, res);
        }
    
        return 0;
    }

## 不含九 ##

《不含九》是一款你可以在无聊时尝试的计数游戏。

在这个游戏中，你只能说出合法的数字。

当且仅当满足以下所有条件时，数字才是合法的：

1、它是一个自然数（即在集\{1,2,3 ......\}中）。  
2、它在其十进制表示中的任何数位都不包含数字9。  
3、它不能被9整除。

例如，数字16和17是合法的，数字18,19,17.2和-17不合法。

在游戏的第一个回合中，你需要选择并说出一个合法的数字F。

在接下来的后续会合中，你需要按数字排列顺序依次说出F后面的合法数字。

例如，如果你选择的F=16，则你需要按顺序说出从16开始的合法数字：16,17,20,21…

爱丽丝非常擅长这个游戏，从不可能出错。

她记得她玩的游戏中第一个数字是F，最后一个数字是L，她想知道游戏总共进行了多少轮次（也就是说，求她一共说出了多少个数字）。

输入格式

第一行包含整数T，表示共有T组测试数据。

每组数据占一行，包含两个整数F和L。

输出格式

每组数据输出一个结果，每个结果占一行。

结果表示为“Case \#x: y”，其中x为组别编号（从1开始），y为游戏进行的轮次数。

数据范围

1≤T≤1001≤T≤100,  
1≤F<L≤10181≤F<L≤1018,  
数据保证F和L是合法数字。

输入样例：

2
    16 26
    88 102

输出样例：

Case #1: 9
    Case #2: 4

样例解释

在样例＃1中，游戏进行了9个轮次，Alice所说的数字是：16,17,20,21,22,23,24,25,26。

在样例＃2中，游戏进行了4个轮次，Alice所说的数字是：88,100,101,102。

#include <iostream>
    #include <algorithm>
    #include <vector>
    
    using namespace std;
    
    typedef long long LL;
    
    const int N = 30;
    
    LL f[N][9], g[N];
    
    void init()
    {
        f[0][0] = 1;
    
        for (int i = 0; i + 1 < N; i ++ )
            for (int j = 0; j < 9; j ++ )
                for (int k = 0; k < 9; k ++ )
                    f[i + 1][(j + k) % 9] += f[i][j];
    
        for (int i = 0; i < N; i ++ )
            for (int j = 0; j < 9; j ++ )
                g[i] += f[i][j];
    }
    
    LL work(LL n)
    {
        vector<int> nums;
        while (n) nums.push_back(n % 10), n /= 10;
    
        int s = 0;
        LL res = 0;
        for (int i = nums.size() - 1; i >= 0; i -- )
        {
            int u = nums[i];
    
            for (int j = 0; j < u; j ++ )
            {
                int t = (s + j) % 9;
                res += g[i] - f[i][(9 - t) % 9];
            }
    
            if (u == 9)
            {
                s = -1;
                break;
            }
    
            s += u;
        }
    
        if (s != -1 && s % 9) res ++ ;
    
        return res;
    }
    
    int main()
    {
        int T;
        cin >> T;
    
        init();
    
        for (int C = 1; C <= T; C ++ )
        {
            LL l, r;
            cin >> l >> r;
    
            printf("Case #%d: %lld\n", C, work(r) - work(l - 1));
        }
    
        return 0;
    }

## 行星距离 ##

宇宙中有N个行星，Google的太空部门建设了N个空间通道，你可以通过它们从一个行星到另一个行星。

通道是双向的; 旅行者可以使用两个行星之间的通道从其中任意一个行星行进到另一个行星。

每个空间通道连接两个行星，没有两个空间通道连接同一对行星。

N个行星之间是连通的，你可以通过空间通道从任意一个行星抵达其他任何行星。

在一些通道的连接下，部分星球和这些通道刚好构成了一个环。

谷歌在这个环上的每个星球上都放置了一份礼物。

现在，谷歌想要知道这N个行星中的每个行星与礼物（任意一份）的最小距离是多少。

你的任务是找到并输出每个行星与环上的行星（任意一个均可）之间的距离最小是多少。

现在规定，环上的行星的输出距离均为0。

输入格式

第一行包含整数T，表示共有T组测试数据。

每组测试数据第一行包含整数N。

接下来N行，每行包含两个整数xixi和yiyi，其中第 i 行的整数表示第 i 条通道连接行星xixi和yiyi。

输出格式

每组数据输出一个结果，每个结果占一行。

结果表示为“Case \#x: y”，其中x为组别编号（从1开始），y是N个用空格隔开的整数，其中第i个整数表示第i个行星与环内行星的最小距离。

数据范围

1≤T≤1001≤T≤100,  
1≤xi,yi≤N,xi≤yi1≤xi,yi≤N,xi≤yi,  
对于所有i≠ji≠j,满足(xi,yi)≠(xj,yj)(xi,yi)≠(xj,yj),  
3≤N≤10003≤N≤1000  
数据中只存在一个环。

输入样例：

2
    5
    1 2
    2 3
    3 4
    2 4
    5 3
    3
    1 2
    3 2
    1 3

输出样例：

Case #1: 1 0 0 0 1
    Case #2: 0 0 0

样例解释

在样例＃1中，行星2,3,4之间存在一个环。因此，行星2,3和4与环的距离为0。行星1和2之间存在通道，行星5和3之间存在通道。 因此，行星1和5与环的距离均为1。

在样例＃2中，所有行星都是环的一部分。 因此，他们与环的距离都是0。

include <bits/stdc++.h>
    using namespace std;
    
    const int N = 1010, M = N * 2;
    
    int n;
    int h[N], e[M], ne[M], idx;
    bool st[N];
    int d[N];
    
    vector[HTML_REMOVED] cirs;
    stack[HTML_REMOVED] path;
    
    void add(int a, int b)
    {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
    }
    
    bool dfs_cir(int u, int p)
    {
    st[u] = true;
    path.push(u);
    
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
    
        if (j != p)
        {
            if (st[j])
            {
                // 找出环上的所有点
    
                while (path.top() != j)
                {
                    cirs.push_back(path.top());
                    path.pop();
                }
    
                cirs.push_back(j);
    
                return true;
            }
    
            if (dfs_cir(j, u)) return true;
        }
    }
    
    path.pop();
    
    return false;
    }
    
    void dfs_dep(int u, int depth)
    {
    st[u] = true;
    d[u] = depth;
    
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
            dfs_dep(j, depth + 1);
    }
    }
    
    int main()
    {
    int T;
    cin >> T;
    
    for (int C = 1; C <= T; C ++ )
    {
        cin >> n;
    
        memset(h, -1, sizeof h);
        idx = 0;
        memset(st, 0, sizeof st);
        cirs.clear();
        path = stack<int>();
    
        for (int i = 0; i < n; i ++ )
        {
            int a, b;
            cin >> a >> b;
            add(a, b);
            add(b, a);
        }
    
        dfs_cir(1, -1);
    
        memset(st, 0, sizeof st);
    
        for (auto c : cirs) st[c] = true;
        for (auto c : cirs) dfs_dep(c, 0);
    
        printf("Case #%d:", C);
        for (int i = 1; i <= n; i ++ ) printf(" %d", d[i]);
        puts("");
    }
    
    return 0;
    }

# Google KickStart 2019 C轮 #

摆动行走

班尼刚买了一台新的可编程机器人。

为了测试他的编码技能，他将机器人放置在了一个R行（从北到南编号为1到R）C列（从西到东编号为1到C）的矩形网格中，其中位于第r行第c列的方格的坐标表示为(r, c)。

最初,机器人位于方格(SR,SCSR,SC)处。

班尼将给机器人下达N条指令,每条指令是N，S，E，W中的一条，分别指示机器人向北，向南，向东或向西移动一个方格。

如果机器人移动到之前到过的方格，则机器人将继续沿同一方向移动，直到它到达之前未曾进入过的方格为止。

班尼永远都不会给机器人下达使其移出网格范围的指令。

现在请你帮助班尼计算一下，N次指令过后，他的机器人位于哪个方格内？

输入格式

第一行包含整数T，表示共有T组测试数据。

每组数据第一行包含5个整数N,R,C,SR,SCN,R,C,SR,SC。

第二行包含一个N个字符的字符串表示N条指令，字符串中的字符一定是N，S，E，W中的一种。

输出格式

每组数据输出一个结果，每个结果占一行。

结果表示为“Case \#x: r c”，其中x是组别编号（从1开始），(r, c)为最终所在位置的方格坐标。

数据范围

1≤T≤101≤T≤10,  
1≤R,C,N≤5∗1041≤R,C,N≤5∗104,  
1≤SR≤R1≤SR≤R,  
1≤SC≤C1≤SC≤C,

输入样例：

3
    5 3 6 2 3
    EEWNS
    4 3 3 1 1
    SESE
    11 5 8 3 4
    NEESSWWNESE

输出样例：

Case #1: 3 2
    Case #2: 3 3
    Case #3: 3 7

样例解释：

下面给出了三个样例的矩形网格以及机器人行进图，其中黄色方格为机器人起始位置，绿色方格为机器人终止位置。

样例\#1：

![111.png][]

样例\#2：

![222.png][]

样例\#3：

![333.png][]

#include <iostream>
    #include <algorithm>
    #include <set>
    
    using namespace std;
    
    typedef pair<int, int> PII;
    
    const int N = 50010, INF = 1e9;
    
    int n, R, C;
    char ops[N];
    
    set<PII> row[N], col[N];
    
    void insert(set<PII> &segs, int x)
    {
        auto i = segs.lower_bound({x, x});
        auto j = i -- ;
    
        bool left = i->second == x - 1;
        bool right = j->first == x + 1;
    
        if (left && right)
        {
            segs.insert({i->first, j->second});
            segs.erase(i);
            segs.erase(j);
        }
        else if (left)
        {
            segs.insert({i->first, x});
            segs.erase(i);
        }
        else if (right)
        {
            segs.insert({x, j->second});
            segs.erase(j);
        }
        else segs.insert({x, x});
    }
    
    int move(set<PII> &segs, int x, int dir)
    {
        auto i = segs.lower_bound({x, x});
    
        if (dir < 0) // 往左走
        {
            i -- ;
            if (i->second == x - 1) return i->first - 1;
            return x - 1;
        }
        else // 往右走
        {
            if (i->first == x + 1) return i->second + 1;
            return x + 1;
        }
    
        return - 1; // 正常情况下不会执行到这里
    }
    
    int main()
    {
        int T;
        scanf("%d", &T);
        for (int cases = 1; cases <= T; cases ++ )
        {
            int x, y;
            scanf("%d%d%d%d%d", &n, &R, &C, &x, &y);
            scanf("%s", ops);
    
            // 初始化维护区间的数据结构
            for (int i = 1; i <= R; i ++ )
            {
                row[i].clear();
                row[i].insert({-INF, -INF});
                row[i].insert({INF, INF});
            }
            for (int i = 1; i <= C; i ++ )
            {
                col[i].clear();
                col[i].insert({-INF, -INF});
                col[i].insert({INF, INF});
            }
    
            for (int i = 0; i < n; i ++ )
            {
                char c = ops[i];
                int dx, dy;
    
                if (c == 'N')
                {
                    dy = y;
                    dx = move(col[y], x, -1);
                }
                else if (c == 'S')
                {
                    dy = y;
                    dx = move(col[y], x, 1);
                }
                else if (c == 'W')
                {
                    dx = x;
                    dy = move(row[x], y, -1);
                }
                else
                {
                    dx = x;
                    dy = move(row[x], y, 1);
                }
    
                insert(row[x], y), insert(col[y], x);
    
                x = dx, y = dy;
            }
    
            printf("Case #%d: %d %d\n", cases, x, y);
        }
    
        return 0;
    }

电路板

Arsh从事回收旧电路板的工作，他最近发现了一个R行C列的矩形方格电路板。

电路板上的每个方格区域都具有一定的厚度（以毫米为单位）。

其中第r行第c列的电路板方格厚度记为Vr,cVr,c。

如果说一个电路板，满足在它的每一行中，最厚的方格区域的厚度与最薄的方格区域的厚度之间的厚度差均不大于K，则我们认为这块电路板是好电路板。

由于这个电路板整体可能不是一个好电路板，所以Arsh想从中找到一个好的子电路板。

通过从原始板上选择一个轴对齐的子矩形，并将子矩形内的电路板方格区域全部取出，就可以获得一块子电路板。

请你帮帮Arsh，找到原始板中最大的好子电路板，并求出该子电路板所占的方格区域数量。

输入格式

第一行包含整数T，表示共有T组测试数据。

每组数据第一行包含三个整数R,C,K。

接下来R行，每行包含C个整数，其中第r行第c个整数表示Vr,cVr,c,即电路板中第r行第c列方格区域的厚度。

输出格式

每组数据输出一个结果，每个结果占一行。

结果表示为“Case \#x: y”，其中x是组别编号（从1开始），y为最大好子电路板包含的方格区域数量。

数据范围

1≤T≤101≤T≤10,  
1≤R,C≤3001≤R,C≤300,  
0≤Vi,j≤10000≤Vi,j≤1000,  
0≤K≤10000≤K≤1000

输入样例1：

3
    1 4 0
    3 1 3 3
    2 3 0
    4 4 5
    7 6 6
    4 5 0
    2 2 4 4 20
    8 3 3 3 12
    6 6 3 3 3
    1 6 8 6 4

输出样例1：

Case #1: 2
    Case #2: 2
    Case #3: 6

输入样例2：

3
    1 4 2
    3 1 3 3
    3 3 2
    0 5 0
    8 12 3
    7 10 1
    4 4 8
    20 10 20 10
    10 4 5 20
    20 5 4 10
    10 20 10 20

输出样例2：

Case #1: 4
    Case #2: 3
    Case #3: 4

样例解释

两个案例，每个情况对应的电路板如下所示，其中具有最大数量的方格区域的好子电路板以绿色标出。

![QQ截图20190527024400.png][QQ_20190527024400.png]

#include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 310;
    
    int n, m, k;
    int a[N][N];
    int minv[N][N], maxv[N][N];
    
    int main()
    {
        int T;
        scanf("%d", &T);
        for (int C = 1; C <= T; C ++ )
        {
            scanf("%d%d%d", &n, &m, &k);
    
            for (int i = 1; i <= n; i ++ )
                for (int j = 1; j <= m; j ++ )
                {
                    scanf("%d", &a[i][j]);
                    minv[i][j] = maxv[i][j] = a[i][j];
                }
    
            int res = n;
            for (int len = 2; len <= m; len ++ ) // 枚举子矩阵宽度
                for (int i = 1; i + len - 1 <= m; i ++ ) // 枚举子矩阵左端点
                    for (int j = 1, s = 0; j <= n; j ++ ) // 枚举列
                    {
                        int &mn = minv[j][i], &mx = maxv[j][i];
                        mn = min(mn, a[j][i + len - 1]);
                        mx = max(mx, a[j][i + len - 1]);
    
                        if (mx - mn <= k)
                        {
                            s ++ ;
                            res = max(res, s * len);
                        }
                        else s = 0;
                    }
            printf("Case #%d: %d\n", C, res);
        }
    
        return 0;
    }

## 看狗 ##

Bundle是一名动物研究员，她需要去观察k条小狗。

她住在一个水平的街道上，街道可以看做一个数轴。

她的家可以被认为是在数轴的原点上。

街道上共有N条狗，其中第 i 条狗的位置在距离她家右侧PiPi米处，不同的狗可能处在同一位置。

每条狗都有着它的颜色，第 i 条狗的颜色用正整数AiAi表示。

当Bundle在家中的时候，她可以改变所穿衬衫的颜色。

这非常的重要，因为只有Bundle和一条狗位于同一位置并且她的衬衫的颜色与小狗的颜色相同时，小狗才会让她进行观察。

Bundle在街道上每向左或向右移动一米，就需要花费一秒钟的时间。

观察小狗和换衣服的时间忽略不计。

请问，她成功观察完k条小狗所花费的时间，最少是多少？

注意，她在观察完k条小狗后，不必回到家中。

输入格式

第一行包含整数T，表示共有T组测试数据。

每组数据第一行包含整数N和K。

第二行包含N个整数，其中第 i 个整数为PiPi，表示第 i 条狗的位置。

第三行包含N个整数，其中第 i 个整数为AiAi，表示第 i 条狗的颜色。

输出格式

每组数据输出一个结果，每个结果占一行。

结果表示为“Case \#x: y”，其中x是组别编号（从1开始），y为观察小狗所花的最短时间。

数据范围

1≤T≤101≤T≤10,  
1≤K≤N1≤K≤N,  
1≤Ai≤10001≤Ai≤1000,  
1≤Pi≤1051≤Pi≤105,  
1≤N≤10001≤N≤1000

输入样例：

3
    4 3
    1 2 4 9
    3 3 2 3
    4 3
    1 2 3 4
    1 8 1 8
    6 6
    4 3 3 1 3 10000
    1 2 8 9 5 7

输出样例：

Case #1: 8
    Case #2: 6
    Case #3: 10028

样例解释

在样例\#1中，共有4条狗，Bundle需要观察其中3条，一种可行方案如下：

*  穿上3号颜色的衬衫。
 *  向右移动一米，观察小狗。
 *  向右移动一米，观察小狗。
 *  向左移动两米回家，并换上2号颜色的衬衫。
 *  向右移动四米，观察小狗。

总共花费8秒。

在样例\#2中，共有4条狗，Bundle需要观察其中3条，一种可行方案如下：

*  穿上1号颜色的衬衫。
 *  向右移动一米，观察小狗。
 *  向左移动一米回家，并换上2号衬衫。
 *  向右移动两米，观察小狗。
 *  向右移动两米，观察小狗。

总共花费6秒。

#include <cstring>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    
    using namespace std;
    
    const int N = 1010;
    
    int n, m;
    int pos[N], color[N];
    int f[N][N], g[N][N];
    vector<int> dog[N];
    
    int main()
    {
        int T;
        scanf("%d", &T);
        for (int C = 1; C <= T; C ++ )
        {
            scanf("%d%d", &n, &m);
            for (int i = 0; i < n; i ++ ) scanf("%d", &pos[i]);
            for (int i = 0; i < n; i ++ ) scanf("%d", &color[i]);
    
            for (int i = 1; i <= 1000; i ++ ) dog[i].clear();
    
            for (int i = 0; i < n; i ++ ) dog[color[i]].push_back(pos[i]);
    
            for (int i = 1; i <= 1000; i ++ ) sort(dog[i].begin(), dog[i].end());
    
            memset(f, 0x3f, sizeof f);
            memset(g, 0x3f, sizeof g);
            f[0][0] = g[1001][0] = 0;
            for (int i = 1; i <= 1000; i ++ )
                for (int j = 0; j <= m; j ++ )
                {
                    f[i][j] = f[i - 1][j];
                    for (int k = 0; k < dog[i].size() && k + 1 <= j; k ++ )
                        f[i][j] = min(f[i][j], f[i - 1][j - k - 1] + dog[i][k] * 2);
                }
    
            for (int i = 1000; i; i -- )
                for (int j = 0; j <= m; j ++ )
                {
                    g[i][j] = g[i + 1][j];
                    for (int k = 0; k < dog[i].size() && k + 1 <= j; k ++ )
                        g[i][j] = min(g[i][j], g[i + 1][j - k - 1] + dog[i][k] * 2);
                }
    
            int ans = 1e9;
            for (int i = 1; i <= 1000; i ++ )
                for (int j = 0; j < dog[i].size(); j ++ )
                    for (int k = 0; k + j + 1 <= m; k ++ )
                        ans = min(ans, f[i - 1][k] + dog[i][j] + g[i + 1][m - k - j - 1]);
    
            printf("Case #%d: %d\n", C, ans);
        }
    
        return 0;
    }

# 今日头条笔试题2019 #

## 立方体塔 ##

小方有w个白色立方体和b个黑色立方体，现在小方想把它们堆成一个立方体塔。

一座高度为h的立方体塔，最底层有h个立方体，每往上一层，所需立方体减一，直到最高层只需要一个立方体。

为了让这座塔看起来美观，小方希望，每一层都只能用一种颜色的立方体。

小方希望把这座塔叠的尽可能高，因此他想知道塔的最大高度是多少，以及这个高度的立方体塔能有几种。

两种立方体塔，当且仅当至少有一层的颜色是不同的，则被认为是不同的。

输入格式

共一行，包含两个整数w和b。

输出格式

共一行，包含两个整数h和c，分别表示最高塔的高度以及此高度塔的种类数。

因为种类数可能较多，请将c对109+7取模后的值输出。

数据范围

0≤w,b≤1050≤w,b≤105

输入样例：

1 1

输出样例：

1 2

#include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 100010, mod = 1e9 + 7;
    
    int f[N];
    
    int main()
    {
        int n, m;
        scanf("%d%d", &n, &m);
    
        int h = 1;
        while (h * (h + 1) / 2 <= n + m) h ++ ;
        h -- ;
    
        f[0] = 1;
        for (int i = 1; i <= h; i ++ )
            for (int j = n; j >= i; j -- )
                f[j] = (f[j] + f[j - i]) % mod;
    
        int res = 0;
        for (int i = 0; i <= n; i ++ )
            if (h * (h + 1) / 2 - i <= m)
                res = (res + f[i]) % mod;
    
        printf("%d %d\n", h, res);
    
        return 0;
    }

变量名拆分

有一天，小赵正在愉快的敲代码，小钱说：“小赵，你这个变量的名字取的可读性不行啊，我都不知道哪里到哪里代表什么意思。”

小赵不服气的说：“那你给我一组变量名，我保证我的变量名可以拆开，并且拆开的每一个变量名都在你这组变量名中出现”。

现在小钱提供了一组不含重复变量名的列表，你能判断小赵的变量名是否能够拆分为多个小钱提供的变量名吗，能则输出True，不能则输出False。

说明：可以重复使用小钱提供的变量名，输入变量名长度均不超过10000，变量名个数不超过10000，所有变量名总字符长度不超过106106。

输入格式

第一行输入待拆分的变量名，第二行输入多个变量名，用空格隔开。

输出格式

根据能不能拆分输出True或False。

输入样例：

thisisadog
    this thisis is a dog

输出样例：

True

#include <iostream>
    #include <algorithm>
    #include <string.h>
    #include <unordered_set>
    
    using namespace std;
    
    typedef unsigned long long ULL;
    
    const int N = 10010, P = 131;
    
    bool f[N];
    ULL h[N], p[N];
    char str[N], word[N];
    
    ULL get(int l, int r)
    {
        return h[r] - h[l - 1] * p[r - l + 1];
    }
    
    int main()
    {
        scanf("%s", str + 1);
        int n = strlen(str + 1);
    
        p[0] = 1;
        for (int i = 1; i <= n; i ++ )
        {
            h[i] = h[i - 1] * P + str[i];
            p[i] = p[i - 1] * P;
        }
    
        unordered_set<ULL> S;
        while (scanf("%s", word) != -1)
        {
            ULL t = 0;
            for (int i = 0; word[i]; i ++ ) t = t * P + word[i];
            S.insert(t);
        }
    
        f[0] = true;
        for (int i = 1; i <= n; i ++ )
            for (int j = i; j; j -- )
                if (f[j - 1] && S.count(get(j, i)))
                {
                    f[i] = true;
                    break;
                }
    
        if (f[n]) puts("True");
        else puts("False");
    
        return 0;
    }

## 宝石迷阵 ##

#include <cstring>
    #include <iostream>
    #include <algorithm>
    #include <unordered_map>
    
    using namespace std;
    
    typedef unsigned long long ULL;
    
    const int N = 20010, M = N * 2, P = 131;
    
    int n, m;
    int v[N];
    int h[N], e[M], ne[M], ch[M], idx;
    int ans[N];
    
    void add(int a, int b, int c)
    {
        e[idx] = b, ch[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
    }
    
    unordered_map<ULL, int> dfs(int u, int father)
    {
        unordered_map<ULL, int> heap;
        heap[0] = v[u];
    
        for (int i = h[u]; ~i; i = ne[i])
        {
            int j = e[i];
            if (j != father)
            {
                auto S = dfs(j, u);
    
                for (auto item : S) heap[item.first * P + ch[i]] += item.second;
            }
        }
    
        for (auto item : heap) ans[u] = max(ans[u], item.second);
    
        return heap;
    }
    
    int main()
    {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i ++ ) scanf("%d", &v[i]);
    
        memset(h, -1, sizeof h);
        for (int i = 0; i < n - 1; i ++ )
        {
            int a, b;
            char c[2];
            scanf("%d%d%s", &a, &b, c);
            add(a, b, *c), add(b, a, *c);
        }
    
        dfs(1, -1);
    
        while (m -- )
        {
            int x;
            scanf("%d", &x);
            printf("%d\n", ans[x]);
        }
    
        return 0;
    }

# 今日头条笔试题2019 #

## 国庆旅行 ##

小明国庆节来北京玩，北京有N个景点，第 i 个景点的评分用a\[i\]表示，两个景点i, j之间的距离为j - i(j > i)。

小明一天只能游玩两个景点，我们认为总评分是两个景点的评分之和减去两个景点之间的距离，即为a\[i\]+a\[j\]+i-j。

那么小明选择哪两个景点才会总评分最大呢？

输入格式

第一行包含整数N。

第二行分别输入N个景点的评分。

输出格式

输出最大评分

数据范围

2≤N≤1052≤N≤105,  
1≤a\[i\]≤10001≤a\[i\]≤1000

输入样例：

5
    11 6 5 18 12

输出样例：

#include <cstring>
    #include <iostream>
    #include <algorithm>
    #include <queue>
    
    using namespace std;
    
    const int N = 100010;
    
    int n;
    int a[N];
    
    int main()
    {
        scanf("%d", &n);
    
        for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    
        int res = 0, maxs = a[0];
    
        for (int i = 1; i < n; i ++ )
        {
            res = max(res, maxs + a[i] - i);
            maxs = max(maxs, a[i] + i);
        }
    
        printf("%d\n", res);
    
        return 0;
    }

##  二维数组区块计数 ##

输入一个只包含0和1的二维数组，上下左右和对角相邻的1组成一个区块，0不形成区块，求数组中的区块个数。

输入格式

第一行输入两个正整数N和M，N表示数组行数，M表示数组列数。

接下来N行，每行表示数组对应的一行，每行包含M个整数，整数之间用空格隔开。

输出格式

输出一个整数，表示数组中区块的个数。

数据范围

0≤N,M,N∗M≤1060≤N,M,N∗M≤106

输入样例：

3 3
    0 1 0
    1 0 0
    1 0 1

输出样例：

样例解释

数组右下角的1单独构成一个区块，其他的3个1对角或上下相邻，构成另一个区块。

//宽度优先遍历 flood-fill
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    using namespace std;
    
    typedef pair<int, int> PII;
    
    const int N = 1000010;
    
    int n, m;
    int g[N];
    PII q[N];
    
    
    void bfs(int sx, int sy)
    {
        int hh = 0, tt = 0;
        q[0] = {sx, sy};
        g[sx * m + sy] = 0;
    
        while (hh <= tt)
        {
            auto t = q[hh ++ ];
    
            int x = t.first, y = t.second;
            for (int i = -1; i <= 1; i ++ )
                for (int j = -1; j <= 1; j ++ )
                {
                    int a = x + i, b = y + j;
                    if (a >= 0 && a < n && b >= 0 && b < m && g[a * m + b])
                    {
                        g[a * m + b] = 0;
                        q[ ++ tt] = {a, b};
                    }
                }
        }
    }
    
    
    int main()
    {
        scanf("%d%d", &n, &m);
        for (int i = 0, k = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ , k ++ )
                scanf("%d", &g[k]);
    
        int res = 0;
        for (int i = 0, k = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++, k ++ )
                if (g[k])
                {
                    bfs(i, j);
                    res ++ ;
                }
    
        printf("%d\n", res);
    
        return 0;
    }
    //深度优先遍历 flood-fill
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    typedef pair<int, int> PII;
    
    const int N = 1000010;
    
    int n, m;
    int g[N];
    
    void dfs(int x, int y)
    {
        g[x * m + y] = 0;
    
        for (int i = -1; i <= 1; i ++ )
            for (int j = -1; j <= 1; j ++ )
            {
                int a = x + i, b = y + j;
                if (a >= 0 && a < n && b >= 0 && b < m && g[a * m + b])
                    dfs(a, b);
            }
    }
    
    
    int main()
    {
        scanf("%d%d", &n, &m);
    
        for (int i = 0, k = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ , k ++ )
                scanf("%d", &g[k]);
    
        int res = 0;
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                if (g[i * m + j])
                {
                    res ++ ;
                    dfs(i, j);
                }
    
        printf("%d\n", res);
    
        return 0;
    }

## 字符串展开 ##

小赵和小钱在练字，小钱对小赵说：你知道吗，我练习的字是有蕴含的。

小赵不服气了，凭什么你的就有蕴含呢？

小钱说，你所看到的并不是我真正练习的字，你需要将我现在写下的字符串里面“%”和“\#”之间的字重复符号前的那么多倍，才能看到我真正写的是什么。

你能帮帮小赵吗？

说明：可能存在嵌套的情况，如“3%g2%n\#\#”，返回“gnngnngnn”，输入输出的字符串长度都不超过10000。

输入字符串保证合法，且输出的字符串中只包含大小写英文字母。

输入格式

一行带数字和嵌套括号的字符串。

输出格式

展开的字符串。

输入样例：

3%acm#2%acm#

输出样例：

acmacmacmacmacm

#include <cstring>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    string str;
    
    string dfs(int &u)
    {
        string res;
        while (u < str.size())
        {
            char c = str[u];
            if (c == '#') return res;
            if (c >= '0' && c <= '9')
            {
                int k = 0;
                while (str[u] != '%')
                {
                    k = k * 10 + str[u] - '0';
                    u ++ ;
                }
                u ++ ;
                string single = dfs(u);
                while (k -- ) res += single;
            }
            else res += c;
    
            u ++ ;
        }
    
        return res;
    }
    
    int main()
    {
        cin >> str;
    
        int u = 0;
        cout << dfs(u) << endl;
    
        return 0;
    }

# PayPal笔试题2019 #

## 幸存者游戏 ##

有nn个同学围成一圈，其idid依次为11~nn（nn号挨着11号）。

现在从11号开始报数，第一回合报到mm的人就出局，第二回合从出局的下一个人开始报数，报到m2m2的同学出局。

以此类推，直到最后一个回合报到mn−1mn−1的人出局，剩下最后一个同学。

输出这个同学的编号。

输入格式

共一行，包含两个整数n和m。

输出格式

输出最后剩下的同学的编号。

数据范围

n≤15,m≤5n≤15,m≤5

输入样例：

5 2

输出样例：

#include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 16;
    
    bool st[N];
    
    int main()
    {
        int n, m;
        cin >> n >> m;
    
        int p = 1;
        for (int i = 1, r = n; i <= n; i ++, r -- )
        {
            int k = 1;
            for (int j = 1; j <= i; j ++ ) k = k * m % r;
            if (k == 0) k = r;
            while (true)
            {
                if (!st[p])
                {
                    k -- ;
                    if (!k)
                    {
                        st[p] = true;
                        break;
                    }
                }
                p ++ ;
                if (p > n) p = 1;
            }
        }
    
        cout << p << endl;
        return 0;
    }

##  数字对生成树 ##

根据输入生成一棵树，并打印该树。

输入为N行数字对序列（例如：N = 2，数字对序列为(1, 2)，(2, 3)），其中数字代表该树的节点，左边数字代表的节点是右边数字代表的节点的父节点。

请根据输入的数字对序列生成一棵树，并根据广度优先的顺序打印该树。

注意，存在输入无法生成树的情况，例如(1, 2)，(1, 3)，(2, 4)，(3, 4)，根据该序列生成的图中，2节点和3节点同时为4节点的父节点，所以根据定义该图不是树。

如遇无法生成树的情况，请输出字符串”Not a tree”。

广度优先遍历树，并打印输出时，同一层级的节点根据输入时节点出现的顺序打印输出。

输入格式

第一行包含整数N。

接下来N行，每行包含两个不同的正整数，表示一个数字对，两数之间用英文逗号分隔，例如：1,2。

没有默认的输入顺序，第一行可能不是根节点，最后一行可能不是叶子节点。

可能有完全重复的行。

输出格式

输出共一行，如果可以生成树，请根据广度优先顺序，输出每个节点对应的数字，并用英文逗号隔开，同一层级的节点根据输入顺序输出。

如果无法生成树，请输出字符串”Not a tree”。

数据范围

1≤N≤100001≤N≤10000  
整数对中的正整数均小于2的31次方。

输入样例1：

5
    1,2
    1,3
    2,4
    2,5
    3,6

输出样例1：

1,2,3,4,5,6

输入样例2：

4
    1,2
    1,3
    2,4
    3,4

输出样例2：

Not a tree

输入样例3:

5
    3,6
    2,4
    1,3
    2,5
    1,2

输出样例3：

1,3,2,6,4,5

#include <iostream>
    #include <algorithm>
    #include <map>
    #include <vector>
    #include <queue>
    
    using namespace std;
    
    map<int, vector<int>> h; // 存储整个图，例如h[5]存储 以5为起点的所有边
    map<int, int> timestamp, dist;
    map<int, bool> has_father;
    map<pair<int, int>, bool> edges;
    
    
    vector<int> bfs(int root)
    {
        queue<int> q;
        q.push(root);
        dist[root] = 0;
        vector<int> nodes;
    
        while (q.size())
        {
            auto t = q.front();
            q.pop();
    
            nodes.push_back(t);
    
            for (auto ver : h[t])
            {
                if (dist.count(ver)) return vector<int>();
                dist[ver] = dist[t] + 1;
                q.push(ver);
            }
        }
    
        vector<vector<int>> ans;
        for (auto ver : nodes) ans.push_back({dist[ver], timestamp[ver], ver});
    
        sort(ans.begin(), ans.end());
    
        nodes.clear();
        for (auto t : ans) nodes.push_back(t[2]);
    
        return nodes;
    }
    
    
    int main()
    {
        int n;
        cin >> n;
    
        int tm = 0;
        while (n -- )
        {
            int a, b;
            scanf("%d,%d", &a, &b);
    
            if (edges[{a, b}]) continue;
            edges[{a, b}] = true;
    
            if (timestamp.count(a) == 0) timestamp[a] = tm ++ ;
            if (timestamp.count(b) == 0) timestamp[b] = tm ++ ;
    
            has_father[b] = true;
            h[a].push_back(b);
        }
    
        int root = -1;
        for (auto x : timestamp)
        {
            int p = x.first;
            if (!has_father[p])
            {
                root = p;
                break;
            }
        }
    
        if (!root) puts("Not a tree");
        else
        {
            auto res = bfs(root);
    
            if (res.size() < timestamp.size()) puts("Not a tree");
            else
            {
                cout << res[0];
                for (int i = 1; i < res.size(); i ++ ) cout << ',' << res[i];
                cout << endl;
            }
        }
    
        return 0;
    }

##  整理书架 ##

图书管理员小P每天要整理书架，一个书架有N排，每一排书架上能摆放k本书，每本书上都有索引的数字编号，例如1,5,7等等。

小P喜欢从数字编号排列最整齐的书架开始整理，因为这样的话这排书架上的书就不用整理，按照整齐程度整理，最后整理最不整齐的那排书架。

那么能否请机智的你帮助小P找出整理书架的顺序呢？

整齐程度的定义：每排书架中书的编号存在的逆序对越少，这排书架就越整齐，一排书架中若书的编号完全升序即为最整洁。

逆序对的定义：在一个数组A中，在i < j的情况下，有A\[i\] > A\[j\]，则(i,j)就称为数组A中的一个逆序对。

输入格式

第一行输入N，表示书架排数。

第二行输入k，表示每排书架上书的数量。

之后的N\*k的数组表示每本书的数字编号。

输出格式

输出按照整齐程度，对各排书架重新排序后得到的新N\*k的数组。

输出共一行，具体形式参考输出样例。

注意，逆序数相同则按书架原有顺序整理。

数据范围

1≤N,k≤2001≤N,k≤200,  
1≤数字编号≤100001≤数字编号≤10000

输入样例：

4
    8
    0 1 2 3 4 5 6 7
    11 6 5 7 3 2 2 0
    2 3 6 1 9 3 5 4
    0 2 4 5 3 10 6 7

输出样例：

[[0, 1, 2, 3, 4, 5, 6, 7], [0, 2, 4, 5, 3, 10, 6, 7], [2, 3, 6, 1, 9, 3, 5, 4], [11, 6, 5, 7, 3, 2, 2, 0]]

#include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 210;
    
    int n, m;
    int a[N][N], cnt[N];
    int index[N];
    
    
    bool cmp(int a, int b)
    {
        return cnt[a] < cnt[b];
    }
    
    
    int main()
    {
        cin >> n >> m;
        for (int i = 0; i < n; i ++ )
        {
            for (int j = 0; j < m; j ++ ) cin >> a[i][j];
            for (int j = 0; j < m; j ++ )
                for (int k = j + 1; k < m; k ++ )
                    if (a[i][j] > a[i][k])
                        cnt[i] ++ ;
    
            index[i] = i;
        }
    
        stable_sort(index, index + n, cmp);
    
        cout << '[';
        for (int i = 0; i < n; i ++ )
        {
            cout << '[';
            for (int j = 0; j < m; j ++ )
            {
                cout << a[index[i]][j];
                if (j != m - 1) cout << ", ";
            }
            cout << ']';
            if (i != n - 1) cout << ", ";
        }
        cout << ']';
    
        return 0;
    }

## 飞机最低可俯冲高度 ##

近日，埃航空难的新闻牵动了无数人的心。

据悉，空难很可能是由于波音737MAX飞机的失速保护系统错误触发所致。

在飞机进行高空飞行时，驾驶辅助系统如果检测到飞机失速，无法维持足够的飞行升力，会压低机头进行俯冲，以重新获得速度，进而获取足够的飞行升力，维持飞行高度。

但是在飞机进行低空飞行时，触发俯冲机制极有可能在飞机还未获得足够飞行速度并上升之前已经撞击地面。

鉴于半年内的两起事故，波音公司决定在低于一定高度时屏蔽自动俯冲机制，现提供K架飞机用于测试最低可俯冲高度，设定需要测试的海拔范围为1~H（单位米）（注意：测试高度只从整数中选取），请问最不理想情况下，至少需要多少次才能求出飞机的最低可俯冲高度？

输入格式

输入为整数K, H，用空格分隔。

K代表用于测试的飞机数量，H代表需要测试的高度范围为1~H米（包含H）。

输出格式

输出整数N，代表最坏情况下需要测试的次数。

数据范围

1≤K≤201≤K≤20  
1≤H≤10001≤H≤1000

输入样例1：

1 1000

输出样例1：

1000

输入样例2:

15 1000

输出样例2：

样例解释

在样例\#1中，只有一架飞机用来测试的情况下，从最高高度1000米，逐次减1m进行测试，直到飞机坠毁。

在样例\#2中，飞机数量足够多，每次均使用二分法进行测试。

说明

1-H为低空飞行高度范围，所有大于H的高度都不属于低空飞行，不会在俯冲过程中撞击地面，不需要进行测试。

如果飞机俯冲测试过程中撞击地面坠毁，可以推断本次测试高度低于飞机实际最低可俯冲高度，可测试飞机数量减1。

如果飞机俯冲测试过程中撞击地面前顺利拉升，可以推断本次测试高度高于或等于飞机最低可俯冲高度，本次试验所用飞机可继续用来测试。

#include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 1010, M = 21;
    
    int n, m;
    int f[N][M];
    
    int main()
    {
        cin >> m >> n;
    
        for (int i = 1; i <= n; i ++ ) f[i][1] = i;
        for (int i = 1; i <= m; i ++ ) f[1][i] = 1;
    
        for (int i = 2; i <= n; i ++ )
            for (int j = 2; j <= m; j ++ )
            {
                f[i][j] = f[i][j - 1];
                for (int k = 1; k <= i; k ++ )
                    f[i][j] = min(f[i][j], 1 + max(f[k - 1][j - 1], f[i - k][j]));
            }
    
        cout << f[n][m] << endl;
    
        return 0;
    }

# #

[https_www.acwing.com_activity_content_8]: https://www.acwing.com/activity/content/8/
[111.png]: /images/20211223/07c22839510b4637b35ba2b293f9dd87.png
[222.png]: /images/20211223/b835ad56c2f24fb68f9c891d3d44e88c.png
[333.png]: /images/20211223/f747b763e97543fcb8559b965bac27dd.png
[QQ_20190527024400.png]: /images/20211223/2adcd68b24a947589c7e4fbec17c3394.png