ATCoder 乱做记录

听说做点 AT 题非常好玩，于是就来了。但是笔者太菜了，所以都不会。

PART-A

james1 是菜狗。

AtCoder Regular Contest 104

A. Plus Minus

查看代码

#include <iostream>
#include <cstdio>

using namespace std;

int main(void) 
{
    int a, b;
    cin >> a >> b;
    cout << (a + b) / 2 << ' ' << (a - b) / 2 << endl;
    return 0;
}

B. DNA Sequence

Portal.

查看代码

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int n, ans = 0;
char a[5005];
int cnt[4];

int main(void) 
{
    scanf("%d%s", &n, a + 1);
    for (int i = 1; i <= n; ++i) {
        memset(cnt, 0, sizeof(cnt));
        for (int j = i; j <= n; ++j) {
            if (a[j] == 'A') ++cnt[0];
            else if (a[j] == 'T') ++cnt[1];
            else if (a[j] == 'G') ++cnt[2];
            else ++cnt[3];
            if (cnt[0] == cnt[1] && cnt[2] == cnt[3]) ++ans;
        }
    }
    printf("%d\n", ans);
    return 0;
}

C. Fair Elevator

Portal.

先考虑几个基本条件：必须有 $b>a$ ，每一个位置最多有一个人上下，否则显然不合法。

发现 $n\le 100$ ，因此可以想的暴力一点。想要给 $-1$ 的位置填数字不太好搞，那么就依次考虑楼层，给楼层安排上这一层上或者是下的人。

设 $f(i)$ 代表考虑前 $i$ 层楼是否可以做到合法，初始时 $f(0)=1$ ，目标为 $f(2n)$ 。转移显然是：

$f(i)=\vee\{f(j-1)\wedge \text{calc}(j,i)\}(1\le j<i,2\mid i-j+1)$

注意区间长度一定要是 $2$ 的倍数，否则是不可能合法的（根本填不进去）。

现在问题就是如何实现判断区间合法的 calc 函数。显然这段区间必须是"封闭"的当中的任何位置都不可以跑到区间外面去。再就是必须在前半段上电梯，后半段下电梯，否则必定可以划分成更小的区间。此时上下电梯的位置必须是前半段中的第 $i$ 个和后半段中的第 $i$ 个，这样才能保证坐电梯的层数是相等的。

时间复杂度 $O(n^3)$ 。

查看代码

#include <iostream>
#include <cstdio>

using namespace std;

int n;
int a[105], b[105];
int cnt[205], p[205];
bool f[205];

bool calc(int L, int R)
{
    for (int i = L; i <= R; ++i) {
        // 在此处下，上来的地方小于 L
        if (p[i] < 0 && a[-p[i]] != -1 && a[-p[i]] < L) return false;
        // 在此处上，下去的地方大于 R
        if (p[i] > 0 && b[p[i]] != -1 && b[p[i]] > R) return false;
    }
    int half = (R - L + 1) >> 1;
    for (int i = L; i <= L + half - 1; ++i) {
        if (p[i] < 0) return false; // 前半段下，不行
        if (p[i + half] > 0) return false; // 后半段上，不行
        if (p[i] && p[i + half] && p[i] + p[i + half]) return false; // 距离不相等，不行
    }
    return true;
}

int main(void)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", a + i, b + i);
        if (a[i] != -1 && b[i] != -1 && a[i] >= b[i]) return puts("No"), 0;
        if (a[i] != -1) ++cnt[a[i]], p[a[i]] = i;
        if (b[i] != -1) ++cnt[b[i]], p[b[i]] = -i;
    }
    n <<= 1;
    for (int i = 1; i <= n; ++i)
        if (cnt[i] > 1) return puts("No"), 0;
    f[0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = ((i & 1) ? 2 : 1); j <= i; j += 2)
            if (f[j - 1]) f[i] |= calc(j, i);
    puts(f[n] ? "Yes" : "No");
    return 0;
}

ATCoder Regular Contest 105

Portal.

A. Fourtune Cookies

Portal.

查看代码

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int main(void)
{
    int a[4];
    cin >> a[0] >> a[1] >> a[2] >> a[3];
    sort(a, a + 4);
    if (a[3] == a[0] + a[1] + a[2] || a[1] + a[2] == a[0] + a[3] || a[0] + a[1] == a[2] + a[3]) puts("Yes");
    else puts("No");
    return 0;
}

B. MAX-=min

Portal.

这个过程就是更相减损法，所以求 $\gcd$ 即可。

查看代码

#include <iostream>
#include <cstdio>

using namespace std;

int gcd(int x, int y) {
    if (y == 0) return x;
    return gcd(y, x % y);
}

int main(void)
{
    int n, x, g = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &x);
        g = gcd(g, x);
    }
    printf("%d\n", g);
    return 0;
}

C. Camels and Bridge

Portal.

有 $n(2\le n\le 8)$ 只骆驼，第 $i$ 只骆驼的重量是 $w_i$ ，你可以任意排列骆驼的顺序，并令骆驼之间的距离为非负实数（可以不等距），骆驼在过一座有 $M(1\le M \le 10^5)$ 个部分的桥时会保持队形，第 $i$ 部分桥有一个长度 $l_i$ 和一个承重能力 $v_i$ ，上面的骆驼质量不可以超过桥的城中能力。找出骆驼过桥的最短队形长度，可以证明这一定是一个整数，若骆驼不可能过去则输出 $-1$ 。

$n$ 的范围很小，因此可以想的暴力一点。考虑枚举全排列，然后使用 DP 来计算最小长度： $f(i)$ 为到第 $i$ 个骆驼为止的最小距离，转移的时候要枚举右端点，然后依次向左端扩展寻找最大值。可以使用状态压缩预处理出一个骆驼集合需要的最长那一段的距离。

查看代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int n, m, ans = 1e9;
int w[10], a[10], f[10], W[500];
int l[100005], v[100005];

bool vis[10];
void dfs(int x) 
{
    if (x == n) {
        memset(f, 0, sizeof(f));
        for (int i = 1; i < n; ++i) {
            int now = (1 << a[i]);
            for (int j = i - 1; j >= 0; --j) {
                now |= (1 << a[j]);
                f[i] = max(f[i], f[j] + W[now]);
            }
        }
        ans = min(ans, f[n - 1]);
        return;
    }
    for (int i = 0; i < n; ++i)
        if (!vis[i]) {
            vis[a[x] = i] = true;
            dfs(x + 1);
            vis[i] = false;
        }
}

int main(void)
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) scanf("%d", w + i);
    sort(w, w + n);
    for (int i = 0; i < m; ++i) {
        scanf("%d%d", l + i, v + i);
        if (v[i] < w[n - 1]) return puts("-1"), 0;
    }
    for (int i = 1; i < (1 << n); ++i) {
        int s = 0;
        for (int j = 0; j < n; ++j)
            if ((i >> j) & 1) s += w[j];
        for (int j = 0; j < m; ++j)
            if (s > v[j]) W[i] = max(W[i], l[j]);
    }
    dfs(0);
    printf("%d\n", ans);
    return 0;
}

D. Let’s Play Nim

Portal.

有 $n(1 \leq n\leq 10 ^ 5)$ 个背包， $n$ 个盘子，背包 $i$ 里有 $a _ i(1 \leq a _ i \leq 10 ^ 9)$ 个硬币，初始时盘子里没有硬币。

两个人轮流操作，如果还有背包有硬币，那么可以选择一个背包，把全部硬币导入某个盘子中，如果没有背包有硬币，那么可以选择一个盘子，至少取走一个硬币，最后不能操作的人输。

$n$ 为奇数时后手必胜， $n$ 为偶数时如果所有数的出现次数都为偶数那么还是后手必胜，否则先手必胜。

查看代码

#include <iostream>
#include <cstdio>
#include <map>

using namespace std;

int main(void)
{  
    int T; scanf("%d", &T);
    while (T--) {
        int n; map<int, int> s;
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) {
            int x; scanf("%d", &x);
            s[x] += 1;
        }
        if (n & 1) puts("Second");
        else {
            bool flag = false;
            for (auto x : s)
                if (x.second & 1) {
                    flag = true;
                    break;
                }
            puts(flag ? "First" : "Second");
        }
    } 
    return 0;
}

E. Keep Graph Disconnected

Portal.

给定一张无向图，由两个玩家轮流连边，不可以连重边和自环，不能使 $1$ 和 $n$ 相连，谁不能操作谁输。问谁必胜。

最终局面，点归作两个集合，一个与 $1$ 属于同一个集合，一个与 $n$ 属于同一个集合，还需要连的边数为 $n\times(n-1)\div 2-m-k(n-k)$ 。

当 $n$ 为奇数时， $k(n-k)$ 必定为偶数，那么可以直接根据奇偶性判断。

当 $n$ 为偶数时，考虑与 $1,n$ 相连的集合大小分别为 $x,y$ ，那么若 $x,y$ 奇偶性不同，则先手可以随意控制 $k$ 的奇偶性（第一步达到，然后接下来维护不变），必胜。若相同，则考虑 $n\times (n-1)\div 2 -m -xy$ 的奇偶性，因为每一方总能让奇偶性不变。

查看代码

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

int fa[100005], siz[100005];
int find(int x) {
    if (x == fa[x]) return x;
    return fa[x] = find(fa[x]);
}

int n, m;

void solve(void)
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) fa[i] = i, siz[i] = 1;
    for (int i = 1; i <= m; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        int uu = find(u), vv = find(v);
        if (uu != vv) fa[vv] = uu, siz[uu] += siz[vv];
    }
    if (find(1) == find(n)) return puts("Second"), void();
    if (n % 2) return puts((1ll * n * (n - 1) / 2 - m) % 2 ? "First" : "Second"), void();
    int x = siz[find(1)], y = siz[find(n)];
    if (x % 2 != y % 2) return puts("First"), void();
    if ((1ll * n * (n - 1) / 2 - m - x * y) % 2) puts("First");
    else puts("Second");
}

int main(void)
{
    int T; scanf("%d", &T);
    while (T--) solve();
    return 0;
}

AtCoder Regular Contest 143

Portal.

A. Three Integers

Portal.

查看代码

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long i64;

int main(void) {
    i64 a[3];
    cin >> a[0] >> a[1] >> a[2];
    sort(a, a + 3);
    if (a[0] + a[1] < a[2]) puts("-1");
    else printf("%lld\n", a[2]);
    return 0;
}

C. Piles of Pebbles

Portal.

分类讨论。

查看代码

#include <iostream>
#include <cstdio>

using namespace std;

int n, x, y;
int a[200005];

int main(void) {
	scanf("%d%d%d", &n, &x, &y);
	bool flag = 0, g = 0;
	for (int i = 1; i <= n; ++i) {
		scanf("%d", a + i);
		a[i] %= x + y;
		if (a[i] != 0) flag = true;
	}
	if (!flag) return puts("Second"), 0;
	if (x <= y) puts("First");
	else {
		flag = 0;
		for (int i = 1; i <= n; ++i)
			if (a[i] < x) flag = true;
		if (flag) puts("Second");
		else puts("First");
	}
	return 0;
}

AtCoder Regular Contest 145

Portal.

A. AB Palindrome

Portal.

查看代码

#include <iostream>
#include <cstdio>

using namespace std;

int n;
char s[200005];

int main(void)
{
    scanf("%d%s", &n, s);
    if (s[0] == 'A' && s[n - 1] == 'A') puts("Yes");
    else if (s[0] == 'A' && s[n - 1] == 'B') puts("No");
    else if (s[0] == 'B' && s[n - 1] == 'A') 
    {
        if (n > 2) puts("Yes");
        else puts("No");
    }
    else puts("Yes");
    return 0;
}

B. AB Game

Portal.

$n$ 轮游戏，第 $i$ 轮有 $i$ 个石子。Alice 先手，每次可以取 $a$ 的倍数的石子，Bob 后手，可以取 $b$ 的倍数的石子。谁取不了石子，谁就输。问 Alice 赢几场。

可以肯定，能取多少就取多少。

当 $n<a$ 时，显然直接死。
当 $a<b$ 时，除了一开始 $n-1$ 轮，剩下都赢。
当 $a\ge b$ 时，可以发现有胜利循环节。

查看代码

#include <iostream>
#include <cstdio>

using namespace std;
typedef long long i64;

int main(void) {
    i64 n, a, b;
    cin >> n >> a >> b;
    if (n < a) puts("0");
    else if (n == a) puts("1");
    else if (a < b) printf("%lld\n", n - a + 1);
    else {
        i64 ans = 1;
        n -= a;
        ans += n / a * b;
        n %= a;
        ans += min(n, b - 1);
        printf("%lld\n", ans);
    }
    return 0;
}

C. Split and Maximize

Portal.

对于一个 $1\sim2n$ 的排列 $[p_{1},p_{2},\dots,p_{2n}]$ ，考虑将 $P$ 拆分为两个子序列 $[a_1,a_2,\dots,a_n]$ 和 $[b_1,b_2,\dots,b_n]$ ， $P$ 的分数定义为所有拆分方案中的 $\sum a_i b_i$ 的最大值。请求出分数取到最大值的排列的数量，对 $998244353$ 取模。

显然只能 $(1,2),(3,4)\dots (2n-1,2n)$ 这样配对，而每一个配对的左右顺序是不影响的，所以答案基数为 $2^n$ 。

而且要保证是子序列，所以相当于在 $2n$ 中选择 $n$ 个位置进行放置，方案数为 $\binom{2n}{n}$ 。

所以答案为 $2^n\binom{2n}{n}$ 。

查看代码

#include <iostream>
#include <cstdio>

using namespace std;
typedef long long i64;
const int MOD = 998244353;

int poww(int a, int b) {
    int res = 1;
    for (; b; b >>= 1, a = 1ll * a * a % MOD)
        if (b & 1) res = 1ll * res * a % MOD;
    return res;
}

int main(void) {
    int n; cin >> n;
    i64 ans = poww(2, n);
    for (int i = n + 2; i <= (n << 1); ++i)
        ans = ans * i % MOD;
    cout << ans << endl;
    return 0;
}

D. Non Arithmetic Progression Set

Portal.

构造一个有 $n$ 个整数的集合 $S$ ，满足所有数的和为 $M$ ，而且每个数的值域均为 $[-10^7,10^7]$ 中，并且对于任意 $x,y,z\in S, x<y<z$ ，都有 $y-x\neq z-y$ 。

首先， $y-x\neq z-y$ 相当于 $x+z\neq 2y$ 。

我们先抛开和为 $M$ 的限制，考虑如何搞定最后那个不等的限制条件。
这里先给出结论：将数写成三进制，当数的所有位都是 $0,1$ 时可以满足。
为什么呢？考虑 $x+z=2y$ ， $y$ 乘上 $2$ 之后每一位都是 $0$ 或 $2$ ，而 $x$ 和 $z$ 必定有一位不一样（否则就相等了），加上之后肯定有一位是 $1$ ，必定不等于 $2y$ 。所以不等关系永远满足。

现在假定我们构造出来的集合可以表示为递增序列 $a$ ，然后进行下面对 $M$ 的限制的讨论。

假设我们的 $s$ 与 $M$ 的差为 $x$ ，整个序列如果同时加上或减去一个数，其性质仍然满足。那么我们可以通过这一点将差 $x$ 控制在 $0\sim n-1$ 内。我们将三进制位的最后一位留白（即最后一位不进行构造，留出来一个 $0$ ），然后选择任意 $x$ 个数加上 $1$ 即可，最后一位的改变并不会影响答案。

查看代码

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long i64;

int n, a[10005];
i64 m, s = 0;

int main(void) {
    cin >> n >> m;
    for (int p = 1; p <= n; ++p) {
        int x = 0, i = p * 2;
        for (int j = 0, z = 1; j < 16; ++j, z *= 3)
            if ((i >> j) & 1) x += z;
        a[p] = x; s += a[p];
    }
    int x = ((m - s) % n + n) % n;
    for (int i = 1; i <= x; ++i) ++a[i], ++s;
    i64 buf = (m - s) / n; s = 0;
    for (int i = 1; i <= n; ++i) printf("%d ", a[i] + buf);
    putchar('\n');
    return 0;
}

AtCoder Regular Contest 147

Portal.

A. Max Mod Min

Portal.

可以预计答案不会很大，直接模拟。

查看代码

#include <iostream>
#include <cstdio>
#include <set>

using namespace std;

int main(void) {
    ios::sync_with_stdio(false);
    int n, x; multiset <int, greater<int>> s;
    cin >> n;
    while (n--) {
        cin >> x;
        s.insert(x);
    }
    int res = 0;
    while (s.size() > 1) {
        auto i = s.end(), j = s.begin();
        --i;
        int t = (*j) % (*i);
        s.erase(j);
        if (t) s.insert(t);
        ++res;
    }
    printf("%d\n", res);
    return 0;
}

B. Swap to Sort

Portal.

现有一个 $1$ 到 $N$ 的排列 $P=(P_1,P_2,\ldots,P_N)$ 。你可以重复执行以下两种操作来使 $P$ 从小到大排序。

操作 $A:$ 选择一个整数 $i$ 满足 $1\ \leq\ i\ \leq\ N-1$ ，然后交换 $P_i$ 和 $P_{i+1}$ 。
操作 $B:$ 选择一个整数 $i$ 满足 $1\ \leq\ i\ \leq\ N-2$ ，然后交换 $P_i$ 和 $P_{i+2}$ 。

请找出一个操作序列满足操作 $A$ 的数量最少。

只要奇数都在奇数位置，偶数都在偶数位置，那么只需要 2 操作就可以完成。因此我们只需要 1 操作修正奇偶性。

查看代码

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;
typedef pair<int,int> pii;

int n;
int a[405];
vector <pii> ans;

void f(int ty, int x) {
	ans.emplace_back(make_pair(ty, x));
	swap(a[x], a[x + ty]);
}

int main(void) {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) scanf("%d", a + i);
	// 奇偶性修正 
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n - 2; ++j)
			if (a[j] % 2 != a[j + 2] % 2 && a[j] % 2 != j % 2) f(2, j);
	for (int i = 1; i < n; ++i)
		if (a[i] % 2 != i % 2) f(1, i);
	// 维护大小 
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n - 2; ++j)
			if (a[j] > a[j + 2]) f(2, j);
	cout << ans.size() << endl;
	for (auto x : ans)
		printf("%c %d\n", x.first == 1 ? 'A' : 'B', x.second);
	return 0;
}

PART-B

想了想可以扩大一下范围，ABC 也可以做一做，但简单题就不写了。

ATCoder Regular Contest 144

Portal.

C. K Derangement

Portal.

求字典序最小的 $1\sim n$ 的排列 $p$ 满足 $\left|p_i-i\right|\geq k$ ，无解输出 $-1$ 。
$2\leq n\leq10^5$ ， $1\leq p<n$ 。

显然， $k>\cfrac{n}{2}$ 的时候无解。

否则呢？比如我们来看这样一个：9 1，它的答案是 2 1 4 3 6 5 8 9 7。

按位构造，考虑每一个 $i$ ，如果 $i+k$ 不在 $A_1,\dots,A_{i-1}$ 里，而且满足 $i+k>n-k$ ，那么就让 $A_i\leftarrow i+k$ ，这是什么意思？就是说，如果我们只是去找最小的，可能最终的构造会出现死局，这种时候就是要出现死局了，于是就不能使用“否则”这个方式；
否则就找到一个最小的可用的 $x$ 满足 $|x-i|\ge k$ 。

现在如何实现更是个难题。

当 $n\ge 4k$ 时，我们会以 $2k$ 的长度作为循环，长成 $k+1,\dots,2k,1,\dots,k$ 这样子。

接下来就不能循环了，否则可能把它后面整成无法构造的。只可能有两种情况（否则已经被判为无解）：

$2k\le n\le 3k$ ，可以构造成 $A_i=\begin{cases}i+k,&1\le i \le n-k,\\i-n+k,&n-k<i\le n.\end{cases}$
$3k<n\le 4k$ ，可以构造成 $A_i=\begin{cases}i+k,&1\le i\le k,\\i-k,&k<i\le n-2k,\\i+k,&n-2k<i\le n-k,\\i-2k,& n-k<i\le 3k,\\i-k,&3k<i\le n.\end{cases}$

查看代码

#include <iostream>
#include <cstdio>

using namespace std;

int main(void) {
	int n, k;
	cin >> n >> k;
	if (k > n / 2) return puts("-1"), 0;
	int m = 0;
	while (n - m >= k * 4) {
		for (int i = 1; i <= k; ++i) printf("%d ", m + k + i);
		for (int i = 1; i <= k; ++i) printf("%d ", m + i);
		m += 2 * k;
	}
	if (n - m <= 3 * k) {
		for (int i = m + k + 1; i <= n; ++i) printf("%d ", i);
		for (int i = m + 1; i <= m + k; ++i) printf("%d ", i);
	} else {
		int d = n - m - 3 * k;
		for (int i = 1; i <= k; ++i) printf("%d ", m + k + i);
		for (int i = 1; i <= d; ++i) printf("%d ", m + i);
		for (int i = 1; i <= k; ++i) printf("%d ", n - k + i);
		for (int i = d + 1; i <= k; ++i) printf("%d ", m + i);
		for (int i = 1; i <= d; ++i) printf("%d ", m + 2 * k + i);
	}
	putchar('\n');
	return 0;
}

ATCoder Regular Contest 144

Portal.

A. Digit Sum of 2x

Portal.

一个数的第一位是 $1$ ，能对答案产生贡献的数的区间是：

$[1,2)$ ，
$[10, 20)$ ，
$[100, 200)$ ，
…

第二位是 $1$ 能对答案产生贡献的是：

$[11,12)$ ，
$[110,120)$ ,
…

枚举前面 $1$ 的个数作为下界闭区间，再加上 $1$ 作为上界开区间，不断乘 $10$ 来获得新的上下界，需要注意边界条件 $n$ 和当前算的数要取一个最小值。时间复杂度 $O(\log^2 n)$ 。

查看代码

#include <iostream>
#include <cstdio>

using namespace std;
typedef long long i64;

int main(void) {
    i64 n, ans = 0, base = 0;
    scanf("%lld", &n);
    for (int i = 1; i <= 16; ++i) {
        base = base * 10 + 1;
        i64 w = base, t = base + 1;
        for (int j = i; j <= 16 && w <= n; ++j) {
            ans += (min(t, n + 1) - w);
            w *= 10, t *= 10;
        }
    }
    printf("%lld\n", ans);
    return 0;
}