Codeforces Round 519 |

好像又是没有数据结构和数学题的一天。

A

Description

有 A、B 两个人要竞选，有 $n$ 个人，每个人有 $k$ 票，其中给 B 投 $a_i$ 票，剩下的投 A。问要使 A 的票数大于 B，$k$ 最小是多少。

Solution

$$ nk-\sum a_i>\sum a_i\Rightarrow k>\frac{2\times\sum a_i}{n} $$

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using std::cin;
using std::cout;
using std::endl;

int read()
{
    int x;
    cin >> x;
    return x;
}

const double eps = 1e-8;

int main()
{
    int n, sum = 0, mx = 0;
    cin >> n;
    for (int i = 1, x; i <= n; i++)
        x = read(), sum += x, mx = std::max(mx, x);
    int ans = 2 * sum / n + 1;
    cout << std::max(ans, mx) << endl;
}

B

Description

有一个长度为 $n$ 序列 $\{a_i\}$，求满足以下条件的序列 $\{x_i\}$ 的数目：$a_i=x_{(i-1)\ \bmod\ k}+a_{i-1}$。其中 $k$ 是序列 $\{x_i\}$ 的长度。

Solution

发现如果没有取模的限制，要求的就是差分数组，有了这个限制也就是说要找到他的循环节，那么构建一下 KMP 中的 $next$ 数组跳一跳就行。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using std::cin;
using std::cout;
using std::endl;

int read()
{
    int x;
    cin >> x;
    return x;
}

const int maxn = 1010;

int nxt[maxn], a[maxn], b[maxn], n;
std::vector<int> ans;

void get_nxt()
{
    for (int i = 1, j = 0; i < n; i++)
    {
        while (j && b[i] != b[j])
            j = nxt[j];
        if (b[i] == b[j])
            j++;
        nxt[i + 1] = j;
    }
}

void solve()
{
    int now = n;
    while (now)
    {
        ans.push_back(n - nxt[now]);
        now = nxt[now];
    }
    cout << ans.size() << endl;
    for (int i : ans)
        cout << i << " ";
    cout << endl;   
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++)
        b[i] = a[i + 1] - a[i];
    get_nxt();
    solve();
}

C

Description

有一个只有 a 和 b 的字符串，从前往后扫一遍，在每一位你可以选择将其前缀翻转，问如何操作得到字符串字典序最小。

Solution

假如我们得到了当前这一位之前的操作方案，且这一位是 a，我们显然需要把这个 a 翻转到前面去。那么我们把前一位翻转一下，再把这一位翻转一下即可。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using std::cin;
using std::cout;
using std::endl;

int read()
{
    int x;
    cin >> x;
    return x;
}

const int maxn = 1010;

char s[maxn];
int ans[maxn];

int main()
{
    cin >> s;
    int n = strlen(s);
    for (int i = 1; i < n; i++)
        if (s[i] == 'a')
            ans[i] ^= 1, ans[i - 1] ^= 1;
    for (int i = 0; i < n; i++)
        cout << ans[i] << " ";
    cout << endl;
    
}

D

Description

有 $m$ 个长度为 $n$ 的 $1\sim n$ 的排列。你可以对一个排列删除任意长度的前缀或后缀（可以不删或只删前缀或只删后缀），但不能删空。最终使得到的排列全都相同，求删除的方案数。$m\leq10,n\leq10^5$。

Solution

对于第一个排列中的一个子序列，发现它合法等价于其他所有排列中也存在这个子序列，那么我们只需要考虑第一个排列中的所有合法子序列长度即可。

对于一个长度为 $n$ 的合法子序列，他对答案的贡献是 $n+\dfrac{(n\times(n-1))}{2}=\dfrac{n\times(n+1)}{2}$，即任意选一个或任意选两个。

求所有子序列的长度可以用类似双指针的算法实现。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <utility>
using std::cin;
using std::cout;
using std::endl;
using std::cerr;

namespace IO
{
	// 为了简短代码省略了
}
using namespace IO;

const int maxn = 1e5 + 10, maxm = 15;

int b[maxm][maxn];
int a[maxm][maxn];
int n, m;
long long len[maxn];

bool check(int x, int y)
{
    for (int i = 2; i <= m; i++)
        if (a[i][b[i][x] + 1] != y)
            return false;
    return true;
}

int main()
{
    n = read(), m = read();
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            a[i][j] = read(), b[i][a[i][j]] = j;
    int l = 1, r = 1;
    for (; l <= n; l = r)
    {
        len[l] = 1;
        r++;
        while (r <= n && check(a[1][r - 1], a[1][r]))
            r++, len[l]++;
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++)
        ans += 1ll * len[i] * (len[i] + 1) / 2;
    cout << ans << endl;
    return 0;
}

E

Description

有 $n$ 个人，给出 $m$ 组互相不喜欢的人，每个人与他喜欢的人都要组队一次，组队之后要挑战两个任务 A、B，每个人对 A、B 有一个不擅长程度 $x_i,y_i$，组队时每人挑战其中一个任务，一次组队的不擅长程度是做两个任务的人对应的不擅长程度之和，并希望最小化这次组队的不擅长程度。

需要求出每个人所有组队的不擅长程度之和。

$n\leq3\times10^5,m\leq3\times10^5$。

（建议参考原题面和样例三，我尽力讲明白了）

Solution

对于每次组队 $(x,y)$，不擅长程度是 $\min(x_i+y_j,x_j+y_i)$，也就是说每次组队的和只有两种，且选哪种是很确定的，我们考虑一个贪心。

选 $x_i+y_j$ 当且仅当 $x_i+y_j<x_j+y_i\Leftrightarrow x_i-y_i<x_j-y_j$，那么我们按照 $x_i-y_i$ 从小到大排序，对于一个人，他和前面的人组队一定取 $x_i+y_j$，和后面的人组队一定取 $x_j+y_i$。

对 $x_i,y_i$ 搞一个前缀和就能很方便统计答案。有边的提前减掉就行。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <utility>
using std::cin;
using std::cout;
using std::endl;
using std::cerr;

namespace IO
{
	// 省略了
}
using namespace IO;

const int maxn = 3e5 + 10;
typedef long long ll;

std::vector<int> e[maxn];
inline void add(int x, int y) { e[x].push_back(y), e[y].push_back(x); }

struct node
{
    int i, j, pos;
    ll ans;
    bool operator<(const node &b) const { return i - j < b.i - b.j; }
} a[maxn];
bool cmppos(const node &a, const node &b) { return a.pos < b.pos; }

int n, m;
ll down[maxn], up[maxn], ans[maxn];

int main()
{
    n = read(), m = read();
    for (int i = 1; i <= n; i++)
        a[i].i = read(), a[i].j = read(), a[i].pos = i;
    for (int i = 0; i < m; i++)
        add(read(), read());
    for (int i = 1; i <= n; i++)
        for (int j : e[i])
            a[i].ans -= std::min(a[i].i + a[j].j, a[i].j + a[j].i);    
    std::sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; i++)
        down[i] = down[i - 1] + a[i].i, up[i] = up[i - 1] + a[i].j;
    for (int i = 1; i <= n; i++)
    {
        a[i].ans += 1ll * (i - 1) * a[i].j + down[i - 1];
        a[i].ans += 1ll * (n - i) * a[i].i + up[n] - up[i];
    }
    std::sort(a + 1, a + 1 + n, cmppos);
    for (int i = 1; i <= n; i++)
        cout << a[i].ans << " ";
    cout << endl;
}

F

Description

有 $n$ 个数的集合 $\{a_i\}$，求它的最小子集的大小，使其中数的最大公约数是 $1$。$n\leq3\times10^5,a_i\leq3\times10^5$。

Solution

能发现答案最大是 $7$，一个数最多只有 $6$ 个公约数。那么我们可以从小到大枚举答案。

然后就不会了，看了题解：

存在性问题可以转化为求方案数。

$f(i,j)$ 表示选了 $i$ 个数，当前 gcd 是 $j$ 的方案数。

$f(i,j)=C_{cnt_j}^i-\sum f(i,k)$，其中 $cnt_j$ 表示是 $j$ 倍数的数的个数，$k$ 是 $j$ 的倍数。

解释一下：所有倍数减去不是最大公约数的。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <utility>
using std::cin;
using std::cout;
using std::endl;
using std::cerr;

typedef long long ll;
const int maxn = 3e5 + 10;
const int N = 3e5;

ll fac[maxn], ifac[maxn], f[10][maxn], cnt[maxn], mod = 1e9 + 7;
int n;

ll qpow(ll a, ll x)
{
    ll res = 1;
    for (; x; x >>= 1, a = a * a % mod)
        if (x & 1)
            res = res * a % mod;
    return res;
}

void init(int n = 3e5)
{
    fac[0] = 1;
    for (int i = 1; i <= n + 1; i++)
        fac[i] = fac[i - 1] * i % mod;
    ifac[n + 1] = qpow(fac[n + 1], mod - 2);
    for (int i = n; i >= 0; i--)
        ifac[i] = ifac[i + 1] * (i + 1) % mod;
}

inline ll C(int n, int m) { return m < 0 || n < 0 || n < m ? 0 : fac[n] * ifac[m] % mod * ifac[n - m] % mod; }

inline void upd(ll &x, ll y) { x -= y, x += mod, x %= mod; }

int main()
{
    n = read();
    init();
    for (int x, i = 1; i <= n; i++)
    {
        cnt[read()]++;
    }
    for (int i = 1; i <= N; i++)
        for (int j = i + i; j <= N; j += i)
            cnt[i] += cnt[j];
    for (int i = 1; i < 10; i++)
    {
        for (int j = N; j >= 1; j--)
        {
            f[i][j] = C(cnt[j], i);
            for (int k = j + j; k <= N; k += j)
                upd(f[i][j], f[i][k]);
        }
        if (f[i][1] > 0)
        {
            writeln(i);
            return 0;
        }
    }
    writeln(-1);
}

G

不会，好像要后缀数组。

A¶

Description¶

Solution¶

Code¶

B¶

Description¶

Solution¶

Code¶

C¶

Description¶

Solution¶

Code¶

D¶

Description¶

Solution¶

Code¶

E¶

Description¶

Solution¶

Code¶

F¶

Description¶

Solution¶

Code¶

G¶

A

Description

Solution

Code

B

Description

Solution

Code

C

Description

Solution

Code

D

Description

Solution

Code

E

Description

Solution

Code

F

Description

Solution

Code

G