A.Add Odd or Subtract Even

题意：

给定 $a、b$ 两个数，每次操作可以将 $a$ 增加任意一个奇数或是减少任意一个偶数。问最少几次使两个数字相等。

题解：

1） $a=b$ ：0次。
2） $a>b$ ：奇偶性相同1次，不同2次。
3） $a<b$ ：奇偶性不同1次，相同2次。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3fLL;
void solve()
{
    int a, b;
    scanf("%d%d", &a, &b);
    if (a == b)
        puts("0");
    else if (a > b)
    {
        if (a % 2 == b % 2)
            puts("1");
        else
            puts("2");
    }
    else
    {
        if (a % 2 == b % 2)
            puts("2");
        else
            puts("1");
    }
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
    return 0;
}

B.WeirdSort

题意：

给定两个数组 $a$ 和 $p$ 。问是否能够通过交换 $a[p_i]$ 和 $a[p_{i+1}]$ 使得 $a$ 数组从小到大排序。

题解：

连续的 $p$ 可以使得一个区间内的数任意排列，因此通过数组 $p$ 划分 $n$ 个区间，顺序扫描每个区间进行内部排序，最后check一下整个数组是否完全排序。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3fLL;
int a[maxn], b[maxn];
bool p[maxn];
void solve()
{
    memset(p, 0, sizeof(p));
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]), b[i] = a[i];
    sort(b + 1, b + n + 1);
    for (int i = 1, x; i <= m; i++)
    {
        scanf("%d", &x);
        p[x] = true;
    }
    for (int i = 1; i <= n; i++)
    {
        if (!p[i])
            continue;
        int j = i;
        while (j <= n && p[j])
            j++;
        sort(a + i, a + j + 1);
        i = j;
    }
    for (int i = 1; i <= n; i++)
        if (a[i] != b[i])
        {
            puts("NO");
            return;
        }
    puts("YES");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
    return 0;
}

C.Perform the Combo

题意：

给定一个长度为 $n$ 小写字母字符串和一个长度为 $m$ 数字数组。顺序输入字符串但是碰到数字数组中所含数字时必须从头开始输入。问 $26$ 个小写字母各输入了多少次。

题解：

$cnt[]$ 记录数字数组在下标中每位出现的次数，倒着遍历，当前字母出现的次数加上此时的贡献，每次贡献都加上对应下标的 $cnt$ ，别忘了字母字符串最终一定会遍历完，所以贡献从 $1$ 开始。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3fLL;
int cnt[maxn];
void solve()
{
    memset(cnt, 0, sizeof(cnt));
    int n, m;
    scanf("%d%d", &n, &m);
    string s;
    cin >> s;
    for (int i = 0, x; i < m; i++)
    {
        scanf("%d", &x);
        cnt[x]++;
    }
    int k = 1;
    int ans[26] = {0};
    for (int i = n - 1; i >= 0; i--)
    {
        ans[(int)s[i] - 'a'] += k;
        k += cnt[i];
    }
    for (int i = 0; i < 26; i++)
        printf("%d ", ans[i]);
    puts("");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
    return 0;
}

D.Three Integers

题意：

给 $a、b、c$ 三个数，每次操作可以使任意一个数字 $+1$ 或者 $-1$ .问最少操作几次使得 $c$ 被 $b$ 整除， $b$ 被 $a$ 整除。

题解：

根据题意显然a的变化范围只能在 $[1,2a]$ （如果 $>2a$ 就可以把 $a$ 变为 $1$ ，显然更优）。 $b$ 同理。所以我们可以对于 $a$ 范围内的每一个 $A$ ，遍历 $b$ 范围里所有 $A$ 的倍数 $B$ ，来确定一个 $C$ 使得 $|C-c|$ 最小。那么问题就转化为 $C$ 的求法。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3fLL;
int cnt[maxn];
void solve()
{
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    int ans = INF, A, B, C;
    for (int i = 1; i <= 2 * a; i++)
        for (int j = i; j <= 2 * b; j += i)
            for (int k = 0; k <= 1; k++)
            {
                int l = j * (c / j) + k * j;
                int tmp = abs(i - a) + abs(j - b) + abs(c - l);
                if (tmp < ans)
                {
                    ans = tmp;
                    A = i;
                    B = j;
                    C = l;
                }
            }
    printf("%d\n%d %d %d\n", ans, A, B, C);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
    return 0;
}

E:Construct the Binary Tree

题意：

给定 $n$ 个结点，要求构造出一棵二叉树使得所有节点距离根节点的距离之和为 $d$ 。

题解：

两种解法：1.从一条链不断将子节点上移。2.从一个完全二叉树开始退化。
这里采用第二种。每层节点选择一个代表并标记。后从大到小将未标记的节点作为本层代表的子节点。若当层代表还有其他子节点，继续下移。直到移动到最后一层后自己作为新一层的代表并标记即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5005;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3fLL;
int dep[maxn], pre[maxn], node[maxn];
bool flag[maxn];
void solve()
{
    memset(flag, 0, sizeof(flag));
    int n, d;
    scanf("%d%d", &n, &d);
    int mxd = 0;
    node[0] = 1;
    for (int i = 2; i <= n; i++)
    {
        pre[i] = i / 2;
        dep[i] = dep[pre[i]] + 1;
        d -= dep[i];
        mxd = max(mxd, dep[i]);
    }
    if (d < 0)
    {
        puts("NO");
        return;
    }
    int idx = n;
    while (idx)
    {
        node[dep[idx]] = idx;
        flag[idx] = true;
        idx = pre[idx];
    }
    for (int i = n; i >= 1; i--)
    {
        if (flag[i])
            continue;
        int tmp = mxd;
        while (dep[pre[i]] < tmp && d)
        {
            pre[i] = node[dep[i]];
            dep[i]++;
            if (dep[i] > mxd)
            {
                mxd = dep[i];
                node[dep[i]] = i;
                flag[i] = 1;
            }
            d--;
        }
    }
    if (d)
    {
        puts("NO");
        return;
    }
    puts("YES");
    for (int i = 2; i <= n; i++)
        printf("%d ", pre[i]);
    puts("");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
    return 0;
}

F:Moving Points

题意:

定 $n$ 个点的初始坐标和速度。定义 $dis(i,j)$ 为点 $i$ 和点 $j$ 在任意时刻的距离的最小值。求 $1-n$ 之间所有点对的 $dis(i,j)$ 的和。

题解：

分两种情况。

　　1）若 $x_i<x_j$ 且 $v_i>v_j$ ，则 $dis(i,j)=0$ （即一定有某一时刻两点相遇）。

　　2）others， $dis(i,j)$ 即为初始两点的距离。

即仅others的情况对答案有贡献。

所以只要将所有点按照坐标从小到大排序，另开一个数组存所有的速度，排序并去重。利用二分查找速度数组得出小于当前点速度的点个数。开两个树状数组，一个 $cnt$ 维护速度小于 $v$ 的个数，一个 $sum$ 维护速度小于 $v$ 的 $x$ 之和。从左向右扫描一遍所有的点，每次加上 $x*cnt-sum$ ，并将状态加入树状数组中维护即可。当然也可以使用线段树等其他数据结构维护。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3fLL;
ll c[maxn][2];
vector<int> b;
pair<int, int> a[maxn];
inline int lowbit(int x) { return x & (-x); }
void add(int x, int val)
{
    for (; x < maxn; x += lowbit(x))
    {
        c[x][0]++;
        c[x][1] += 1ll * val;
    }
}
ll query(int x, int k)
{
    ll res = 0;
    for (; x; x -= lowbit(x))
        res += c[x][k];
    return res;
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i].first);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i].second);
        b.push_back(a[i].second);
    }
    sort(a, a + n);
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());
    ll ans = 0;
    for (int i = 0; i < n; i++)
    {
        int idx = lower_bound(b.begin(), b.end(), a[i].second) - b.begin() + 1;
        ans += a[i].first * query(idx, 0) - query(idx, 1);
        add(idx, a[i].first);
    }
    printf("%lld\n", ans);
    return 0;
}

Codeforces Round #624 (Div. 3)