A.Left-handers, Right-handers and Ambidexters—数学+签到

题意：一个运动队里有 l 个人只能用左手训练，有 r 个人只能用右手训练，还有 a 个人左右手都可以训练。现在教练决定组建一支队伍，但是要保证队伍的能用左手训练和能用右手训练的人数对半分，请确定队伍的最大人数

思路：首先 l 个只能用左手训练和 r 个只能用右手训练的人是确定的，然后用 a 人去填充少的一方，如果不能填充到双方相等那么就是少的一方的人数*2，否则的话就用剩余 a 对半分给两方

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int l, r, a;
    while (cin >> l >> r >> a) {
        if (l < r) swap(l, r);  //让少的一方是 l
        if (a <= (l - r))
            cout << 2 * (r + a) << endl;
        else
            cout << (l + (a - (l - r)) / 2) * 2 << endl;
    }
    // system("pause");
    return 0;
}

B.Intercepted Message—贪心+双指针

题意：给出 n 和 m 长度的两个数组，把这两个数组都分成若干段连续的区间，两个数组的区间数量相同且各区间的元素之和相同，题目保证两个数组的全部元素之和相等，问最多能分出多少段区间

题意：既然想要区间段数最多那么我们肯定是能用最少的元素凑出相等的区间就算一次，又因为区间内元素是连续的并且每个元素都必须属于一段区间所以我们就用两个指针分别遍历两个数组统计经过的元素之和：

  • 当两指针遍历的元素和相等时说明我们找到了一段区间，那么答案+1，两个指针的和设置为 0 用来找新的一段区间
  • 当两指针遍历的元素和不等式说明我们还要用后面的元素继续凑相等的区间，哪个指针统计的元素和小就让它加上后面的元素

因为题目保证的条件最终两个指针肯定会到达各自数组的末尾元素的位置结束上述操作，所以我们不用担心凑不出来区间、指针未遍历完数组或者数组越界访问的问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+100;
#define int ll

int a[maxn], b[maxn];

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, m;
    while (cin >> n >> m) {
        for (int i = 1; i <= n; ++i)
            cin >> a[i];
        for (int i = 1; i <= m; ++i)
            cin >> b[i];
        int x = 1, y = 1;
        int cnt = 0;
        while (x <= n || y <= m) {
            if (a[x] == b[y]) {
                ++cnt;
                ++x, ++y;
                continue;
            }
            if (a[x] < b[y]) {
                ++x;
                a[x] += a[x - 1];
            } else {
                ++y;
                b[y] += b[y - 1];
            }
        }
        cout << cnt << endl;
    }
    // system("pause");
    return 0;
}

C.Zebras—贪心+构造+思维

题意：如果一个串满足两端为 0，中间有 0 对、一对或者多对 10 就就成为 zebras 串（0 是特殊的 zebras 串），现在给出一个由 0 和 1 组成的长串，请问在每个元素都用的情况下可以最多形成多少个 zebras 串，如果能用所有的元素形成多的 zebras 串输出形成的串的最大数量以及每个串拥有的元素的下标，否则输出 -1

思路：为了尽可能多的构造出 zebras 串肯定每个 0 尽可能多的和 1 配对：

  • 对于每个 0 我们先用他们去填充前面需要用 0 作为末尾的串来构造一个 zebras 串，如果是多余出来的 0 那么我们就让它作为一个新的 zebras 串的开头
  • 如果是 1 那么我们就贪心的将他们放在前面构造出来以 0 结尾的 zebras 串末尾这样相当于 1010101 穿插，这样每个 0 解决了 2 个 1 的配对问题，然后该串末尾的 1 等待后面的 0 来补全。如果前面没有 0 结尾的串来放就输出 -1
  • 如果最终 0 补全了前面所有的 1 结尾的串，剩余的 0 就可以单独作为一个 zebras 串，如果并未补全那么也输出 -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 100;

char s[maxn];
vector<int> ans[maxn];	//记录构成每个串的元素的下标

void solve() {
    int n = strlen(s + 1);
    int p = 0, cnt = 0;
    if (s[1] == '1' || s[n] == '1') {
        puts("-1");
        return;
    }
    for (int i = 1; i <= n; ++i) {
        if (s[i] == '0') {
            ans[++p].push_back(i);  //尝试作为一个新串的开头或者填充前面的有1结尾的串
            cnt = max(cnt, p);		//记录开到的最大的zebras串
        } else {  //贪心的填在前面生成0开头子串的后面
            if (p == 0) {  //前面没有可以放的串了
                puts("-1");
                return;
            }
            ans[p].push_back(i);
            --p;	//下次再需要放1就是更前面的串了
        }
    }
    if (p < cnt) {  //最终p没回来那么说明没有将前面的1结尾的串补完
        puts("-1");
        return;
    }
    cout << cnt << endl;	//反之这说明补全了且形成的zebras串数量最多
    for (int i = 1; i <= cnt; ++i) {
        cout << ans[i].size();
        for (auto e : ans[i])
            cout << ' ' << e;
        cout << endl;
    }
}

signed main() {
    while (~scanf("%s", s + 1)) {
        solve();
    }
    // system("pause");
    return 0;
}

D.A Leapfrog in the Array—规律+模拟

题意：给出一个序列，从 1 到 n，每个数之间刚开始都有一个缝隙，现在每次将最后一个元素填入最后的空缺中直至整个序列不再存在缝隙，现在问你对于最终的序列第 x 位置上的值是多少，总共有 q 次询问

思路： 参考博客 因为序列最大有 1e18 那么大，询问次数也很多而时间只有 2000 ms，所以无疑又是打表找规律的题：

1： 1
2： 1 2
3： 1 3 2
4： 1 3 2 4
5： 1 5 2 4 3
6： 1 4 2 6 3 5
7： 1 6 2 5 3 7 4
8： 1 5 2 7 3 6 4 8
9： 1 9 2 6 3 8 4 7 5
10： 1 6 2 10 3 7 4 9 5 8
11： 1 9 2 7 3 11 4 8 5 10 6
12： 1 7 2 10 3 8 4 12 5 9 6 11
13： 1 12 2 8 3 11 4 9 5 13 6 10 7

  • 首先不难发现对于序列奇数项上的数前后没有发生变化就是 (idx+1)/2

  • 对于序列偶数项上的数通过表（n 为 1~13 时的最终序列）中可以找到规律：每一行的数实际上和上一行都有着一定的关系：例如这里第 13 行的第 10 位就是第 12 行的第 8 位 +1 得来的，而第 12 行的第八为是由第 11 行的第 6 位 +1 得来的：

    (13,10)←(12,8)←(11,6)←(10,4)+1←(9,2)+1←(8,0)+1(8,8)+1←(7,6)+1←(6,4)+1←(5,2)+1←(4,4)+1←(3,2)+1←(2,2)+1←(1,1)+1←(10,4)+1←(9,2)+1←(8,0)+1(8,8)+1←(7,6)+1←(6,4)+1←(5,2)+1←(4,4)+1←(3,2)+1←(2,2)+1←(1,1)+1

    最终到达奇数项的时候我们可以直接求出奇数项，所以对于偶数项我们就模拟这种递归的操作并统计需要加多少 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/*
打表找规律：奇数项不变
偶数项递推：n个数的第m偶数项=n-1个数的第m-2项直至推到奇数项
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    ll n, q;
    while (cin >> n >> q) {
        while (q--) {
            ll idx;
            cin >> idx;
            if (idx % 2 != 0)  //奇数项不变
                cout << (idx + 1) / 2 << endl;
            else {
                ll ans = 0, nn = n;
                while (idx % 2 == 0) {
                    ll cnt = idx / 2;  //一直向前递推到第0项的行数
                    nn -= cnt;         //计算此时递推到的当前行数
                    idx = nn;          //第0项转化为当前行最后一项
                    ans += cnt;        //每递推一行就+1
                }
                cout << ans + (idx + 1) / 2 << endl;  //最终计算的奇数项加上递推过来的累计的1
            }
        }
    }
    // system("pause");
    return 0;
}