AtCoder Beginner Contest 353 A~E(F,G更新中...)

A.Buildings

题意

给出若干个建筑，每个建筑有一个高度，问，从第二个建筑开始，比第一个建筑高的建筑中编号最小的是多少？如果不存在，输出-1.

分析

边输入边比较即可，如果循环结束还未找到，输出-1.

代码

#include<bits/stdc++.h>

using namespace std;

int a[200005];

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (i - 1 && a[i] > a[1]) {
            cout << i << endl;
            return;
        }
    }
    cout << -1 << endl;
}

int main() {
    solve();
    return 0;
}

B.AtCoder Amusement Park(模拟)

题意

有 $n$ 个小团体需要乘坐小船，第 $i$ 个团体有 $a_i$ 个人，而小船只有 $k$ 个座位。同时，小团体需要按照给出的顺序来乘坐小船，且同一个团体中的人必须乘坐同一艘小船，问，需要多少只小船，才能满足所有的小团体。

分析

模拟即可，每次检查当前小船是否还能放下当前的团体人数，如果够，就加入当前小船中，如果不够，开一艘新的小船，用于放置当前的小团体。

代码

#include<bits/stdc++.h>

using namespace std;

int a[200005];

void solve() {
    int n, k;
    cin >> n >> k;
    int sum = 0, cnt = 1;
    for (int i = 1; i <= n; i++) {
        int a;
        cin >> a;
        sum += a;
        if (sum > k) {
            sum = a;
            cnt++;
        }
    }
    cout << cnt << endl;
}

int main() {
    solve();
    return 0;
}

C.Sigma Problem(前缀和+二分)

题意

给出一个函数 $10^{8}$ ，求：

$\sum\limits_{i = 1}^{n - 1}\sum\limits_{j = i + 1}^{n} f(a_i, a_j)$ 。

分析

由于给出的函数 $f (x, y)$ 是将两个数字相加，而加法是可交换的，那么 $f (x, y) = f (y, x)$ 。然后求和要求的是任意两个不同数字经过函数运算后相加的结果，那么任意交换给出的数字是不会改变答案的。

因此，为了便于处理，可以把数组排序。

排序完成后，可以先维护前缀和，因为不难发现，对于每个 $a [i]$ ，均需要与前面每个数字进行一次函数运算，那么在不考虑取模的情况下，产生的结果为 $\times a[i]$ ，其中 $p re [i - 1]$ 表示前 $i - 1$ 个数字的前缀和。

然后考虑取模需要减掉的部分，不难想到，对于 $x + y < 10^{8}$ 的情况，是不需要进行取模的，而 $\ge 10^{8}$ 时，则每次运算的取模均相当于减去一个 $10^{8}$ ，由于数组已经经过排序了，那么只需要通过二分对 $10^{8} - a[i]$ 进行查找，就可以知道需要减去的数字所在的起点是多少，那么这个查找到的位置到下标 $i - 1$ 之间的所有数字与当前数字 $a [i]$ 进行运算，均需要减掉 $10^{8}$ ，令 $c n t$ 为需要减去的数量，则 $a [i]$ 产生的贡献为

$\times a[i] - cnt * 10^{8}$

代码

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int mod = 1e8;
ll a[300005], pre[300005];


void solve() {
    ll n;
    ll ans = 0;
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
    }
    sort(a + 1, a + n + 1);
    for (ll i = 1; i <= n; i++) {
        pre[i] = pre[i - 1] + a[i];
    }
    for (ll i = 2; i <= n; i++) {
        int id = lower_bound(a + 1, a + i, mod - a[i]) - a;
        ans += pre[i - 1] + (i - 1) * a[i] - (mod * (i - id));
    }
    cout << ans << endl;
}

int main() {
    solve();
    return 0;
}

D.Another Sigma Problem(后缀和)

题意

给出一个函数 $f (x, y) = x y$

例：

$f (3, 14) = 314$
$f (100, 1) = 1001$

请你求出以下操作取模后的结果：

$\sum\limits_{i = 1}^{n - 1}\sum\limits_{j = i + 1}^{n}f(a_i, a_j)$

分析

当前给出的函数 $f (x, y)$ 可以将数字分为两个部分，前半部分需要乘上 $10^{\text{y的十进制位数}}$ ，后半部分直接加上。

那么对于 $a_i$ 来说，与前面的 $i - 1$ 个数字运算后，产生的贡献为 $\times a_i$ ，与后面的 $n - i$ 个数字运算后，产生的贡献为 $\sum\limits_{j = 1}^{10} 10^{j} \times cnt_j \times a_i$ ，其中 $cnt_j$ 表示 $a_{i + 1} \sim a_n$ 中十进制位数为 $j$ 的数字数量。

对于 $\times a_i$ ，可以直接通过计算得到，而 $cnt_j$ 可以通过预处理后缀和来快速计算得到，即使用 $n x t [i] [j]$ 表示 $\sim n$ 之间十进制位数为 $j$ 的数字个数.

代码

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int mod = 998244353;
ll a[300005], nxt[300005][15];

int getlen(int x) {
    int cnt = 0;
    while (x) {
        cnt++;
        x /= 10;
    }
    return cnt;
}

void solve() {
    ll n;
    ll ans = 0;
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (ll i = n; i >= 1; i--) {
        for (int j = 1; j <= 10; j++) {
            nxt[i][j] = nxt[i + 1][j];
        }
        nxt[i][getlen(a[i])]++;
    }
    for (ll i = 1; i <= n; i++) {
        ans += (i - 1) * a[i] % mod;
        ans %= mod;
        ll mul = 1;
        for (int j = 1; j <= 10; j++) {
            mul *= 10;
            ans = (ans + mul * nxt[i + 1][j] % mod * a[i] % mod) % mod;
        }
    }
    cout << ans << endl;
}

int main() {
    solve();
    return 0;
}

E.Yet Another Sigma Problem(哈希)

题意

给出一个函数 $f (x, y)$ ，表示字符串 $x$ 和 $y$ 的最长公共前缀长度。

请你求出:

$\sum\limits_{i = 1}^{n - 1}\sum\limits_{j = i + 1}^{n}f(S_i, S_j)$ 。

分析

可以不用直接考虑当前字符串与前面所有字符串中的最长公共前缀长度，而是依次考虑长为 $\sim S_i.size()$ 的前缀在前面的字符串中作为前缀的个数。

为什么可以这么做？

不难想到，此时将所有长度的字符串均设置为贡献1，那么长度为1的前缀会产生1点贡献，长度为2的前缀也会产生1点贡献，依次类推，最后计算出的贡献与所求的答案是一致的。

而字符串匹配是比较麻烦的，很难快速的进行检查，因此，可以使用哈希将字符串转化为数字(为了避免冲突，这里选择了双模数)，而转化成的数字范围也是较大的，使用数组并不方便维护，可以使用map进行维护，即 $ma p [x] = y$ 表示字符串 $x$ 作为前缀的出现次数为 $y$ 。

那么对于每个字符串，枚举这个字符串所有的前缀字符串，然后加上这个前缀在前面字符串中的出现次数，并将该前缀更新到map中。

代码

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

map<pair<int, int>, int> H;

int base = 131, mod[] = {1000000007, 998244353};


void solve() {
    int n;
    cin >> n;
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        string s;
        ll hashCode[5] = {0, 0};
        cin >> s;
        for (auto j : s) {
            hashCode[0] = (hashCode[0] * base % mod[0] + j) % mod[0];
            hashCode[1] = (hashCode[1] * base % mod[1] + j) % mod[1];
            ans += H[make_pair(hashCode[0], hashCode[1])];
            H[make_pair(hashCode[0], hashCode[1])]++;
        }
    }
    cout << ans << endl;
}

int main() {
    solve();
    return 0;
}