A-Turtle Puzzle: Rearrange and Negate

题意

对一个数组执行两个操作：

对数组进行重新排序或保持元素顺序不变
选择连续的一段，对该段中的元素取相反数，也可以不选择任何一段，即保持所有的元素符号不变。

求进行上述操作之后数组的最大和是多少。

数据范围

$t(1≤t≤1000)$

$n(1≤n≤50)$

$a_i(-100\le a_i\le 100)$

思路

遍历数组，对所有的数取非负后相加。

参考代码

1
void solve() {
2
    int n;cin >> n;
3
    ll ans = 0ll;
4
    for (int i = 0;i < n;i++) {
5
        ll x;cin >> x;
6
        if (x < 0)ans -= x;
7
        else ans += x;
8
    }
9
    cout << ans << '\n';
10
}

B-Turtle Math: Fast Three Task

题意

有一个数组，可以对数组中的数进行任意次下方两种操作：

将数移除
将该数的数值加1

求至少进行多少次上述操作，可以使数组所有元素之和是3的倍数？

数据范围

$t(1≤t≤10^4)$

$n(1≤n≤10^5)$

$a_i(1\le a_i\le 10^4)$

思路

统计数组 $a$ 中模3为0、1、2的数量和余数总和。记总和为 $sum$ ，余1的数量为 $x$ ，余2的数量为 $y$ 。考虑：

若 $sum$ 模3为0，则不需要操作
若 $sum$ 模3为2，则给任意一个数加1即可，操作1次。
若 $sum$ 模3为1，若有余1的数，则去掉这个数即可，否则进行两次加1操作。

参考代码

1
void solve() {
2
    int n;cin >> n;
3
    vector<ll>aa(n);
4
    ll ans = 0;
5
    ll x = 0, y = 0;
6
    for (int i = 0;i < n;i++) {
7
        cin >> aa[i];
8
        aa[i] %= 3;
9
        ans += aa[i];
10
        if (aa[i] == 1)x++;
11
        else if (aa[i] == 2)y++;
12
    }
13
    if (ans%3 == 0) {
14
        cout<<0<<'\n';
15
    }
16
    else if (ans % 3 == 2) {
17
        cout << 1 << '\n';
18
    }
19
    else {
20
        if (x > 0)cout << 1 << '\n';
21
        else cout << 2 << '\n';
22
    }
23
}

C-Turtle Fingers: Count the Values of k

题意

给3个正整数 $a,b,l$ ，找出满足 $l=k\times a^x\times b^y$ 的 $k$ 的个数， $k,x,y$ 均为非负整数。

数据范围

$t(1≤t≤10^4)$

$a,b,l(2\le a,b\le 100,1\le l\le 10^6)$

思路

$2^{20}\gt 10^6$ ，可知， $x,y$ 的范围不超过20。

预处理 $a^x$ 和 $b^y$ ，然后暴力遍历即可。

参考代码

1
void solve() {
2
    ll a, b, l;cin >> a >> b >> l;
3
    vector<ll>ax, by;
4
    ax.push_back(1);by.push_back(1);
5
    for (int i = 1;ax.back() <= l;i++) {
6
        ax.push_back(ax.back() * a);
7
    }
8
    for (int i = 1;by.back() <= l;i++) {
9
        by.push_back(by.back() * b);
10
    }
11
    set<ll>k;
12
    for (int i = 0;i < ax.size();i++) {
13
        for (int j = 0;j < by.size();j++) {
14
            if (l%(ax[i] * by[j]) == 0) {
15
                k.insert(l/(ax[i] * by[j]));
16
            }
17
        }
18
    }
19
    cout << k.size() << '\n';
20
}

D-Turtle Tenacity: Continual Mods

题意

给数组 $a$ 重新排序，判断是否存在排序使得 $a_1 \text{ }mod\text{ } a_2 \text{ }mod\text{ } a_3\dots a_{n-1}\text{ }mod\text{ }a_n=0$ 。

数据范围

$t(1≤t≤10^4)$

$n(2≤n≤10^5)$

$a_i(1\le a_i\le 10^9)$

思路

思考 $x\text{ }mod\text{ }y$

如果 $x\lt y$ ，则结果还是 $x$
如果 $x=y$ ，则结果是0

如果最小的数是唯一的，则一定有解；如果最小的数不唯一，考虑是否有较大的数 $z$ 使得 $z\text{ }mod\text{ }x≠0$ ，如果存在，则有更小的唯一最小值，可以有解，否则无解。

参考代码

1
void solve() {
2
    int n;cin >> n;
3
    vector<ll>a(n);
4
    for (int i = 0;i < n;i++) {
5
        cin >> a[i];
6
    }
7
    sort(a.begin(), a.end());
8
    if (a[0] != a[1]) {
9
        cout << "YES\n";
10
        return;
11
    }
12
    for (int i = 1;i < n;i++) {
13
        if (a[i] % a[0] != 0) {
14
            cout << "YES\n";
15
            return;
16
        }
17
    }
18
    cout << "NO\n";
19
}

E-Turtle vs. Rabbit Race: Optimal Trainings

题意

训练量 $k$ 是连续一段时间的每天的训练量的总和，每次训练的提高值 $u$ 按照训练次数递减（第1次 $u$ ，第2次 $u-1$ ，第3次 $u-2$ ，…，第 $k$ 次 $u-k+1$ ，，提高值可以是负数），每次给定一个起始日 $l$ 和提高值 $u$ ，寻找一个最佳的结束日 $r$ ，使得训练提高值总和最高，如果有多个 $r$ 的结果提供最高训练值，选 $r$ 较小的那个。

数据范围

$t(1≤t≤10^4)$

$n(1≤n≤10^5)$

$a_i(1\le a_i\le 10^4)$

$q(1\le q\le 10^5)$

$l,u(1\le l\le n,1\le u \le 10^9)$

思路

训练提高值总量 $S$ 与训练量 $k$ 之间的关系是 $S(k)=u\times k-\frac{k\times (k-1)}{2}$ ，是一个关于 $k$ 先增后减的函数，最高值在 $k=u+0.5$ 处取到，由于 $k$ 为整数， $S(k)$ 的最高值应该在 $u$ 和 $u+1$ 处取到。

在对称轴左边，二分查找在 $[l,u]$ 的范围内最靠近 $u$ 的 $k$ 的取值，即小于等于 $u$ 的最后一个 $k$ 值。
在对称轴右边，二分查找 $[u+1,n]$ 的范围内最靠近 $u+1$ 的 $k$ 值，即大于等于 $u+1$ 的第一个 $k$ 值。

$k$ 值可以通过前缀和进行筛选， $k=pre[r]-pre[l-1]$ ，则对 $pre$ 数组进行二分查找 $u+pre[l-1]$ 和 $u+1+pre[l-1]$ 即可。

对比这两个值对应的 $S(k)$ 和 $r$ ，以及只在 $l$ 那天训练的效果，择优选择。

参考代码

1
ll f(ll u, ll k) {
2
    return k * u - k * (k - 1) / 2;
3
}
4

5
void solve() {
6
    int n;cin >> n;
7
    vector<ll>a(n + 1);
8
    vector<ll>pre(n + 1);
9
    pre[0] = 0;a[0] = 0;
10
    for (int i = 1;i <= n;i++) {
11
        cin >> a[i];
12
        pre[i] = pre[i - 1] + a[i];
13
    }
14
    int q;cin >> q;
15
    while (q--) {
16
        ll l, u;cin >> l >> u;
17
        ll x = pre[l - 1];
18
        int ru = upper_bound(pre.begin() + l, pre.end(), x + u) - pre.begin() - 1;
19
        ll ans = a[l], ansr = l;
20
        if (ru >= l && ru <= n) {
21
            if (f(u, pre[ru] - x) > ans) {
22
                ans = f(u, pre[ru] - x);
23
                ansr = ru;
24
            }
25
        }
26
        int ru1 = lower_bound(pre.begin() + l, pre.end(), x + u + 1) - pre.begin();
27
        if (ru1 >= l, ru1 <= n) {
28
            if (f(u, pre[ru1] - x) > ans) {
29
                ans = f(u, pre[ru1] - x);
30
                ansr = ru1;
31
            }
32
        }
33
        cout << ansr << ' ';
34
    }
35
    cout << '\n';
36
}