ABC390游记（A~D）

Atcoder ABC390个人游记（A~D）

比赛链接

作者今天很无语，被dmy恶心后状态不好，以为atc会简单，结果又被恶心了，脑子抽了，写的不如以前详细，但是我还是不会改的（

A. 12435

题面

给你一个整数序列 $A=(A_1,A_2,A_3,A_4,A_5)$ ，它是通过对 $(1,2,3,4,5)$ 进行置换得到的。

请判断 $A$ 是否可以通过对 $A$ 中相邻的两个元素进行1次的交换操作来按升序排序。

思路

把正确的数组弄出来，比较差异就行了，很简单。

有没看到相邻结果挂1发的乐子吗

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a[5];
    cin >> a[0] >> a[1] >> a[2] >> a[3] >> a[4];
    int b[5]={a[0], a[1], a[2], a[3], a[4]};
    sort(b, b + 5);
    int pos = 0;
    for (int i = 0; i < 5; i++) {
        if (a[i] != b[i]) {
            pos = i;
            break;
        }
    }
    swap(a[pos], a[pos + 1]);
    for (int i = 0; i < 5; i++) {
        if (a[i] != b[i]) {
            cout << "No";
            return 0;
        }
    }
    cout << "Yes";
    return 0;
}

B.Geometric Sequence

题面

问题陈述

给你一个长度为 $N$ 的正整数序列 $A=(A_1,A_2,\ldots,A_N)$ 。

请判断 $A$ 是否为几何级数。

思路

很多人因为deepl翻译成几何级数就喷它，你们都是乐子。

百度百科自己访问。

还有开double的被卡的，hack数据一个循环小数就找出来了。

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    n -= 2;
    int a, b;
    cin >> a >> b;
    int tp = __gcd (a, b);
    a /= tp;
    b /= tp;
    pair<int, int> pii = {a, b};
    b *= tp;
    while (n--) {
        int c;
        cin >> c;
        tp = __gcd (b, c);
        b /= tp;
        c /= tp;
        if (make_pair(b, c) != pii) {
            cout << "No";
            return 0;
        }
        c *= tp;
        b = c;
    }
    cout << "Yes";
    return 0;
}

C.Paint to make a rectangle

题面

给你一个行数为 $H$ 列数为 $W$ 的网格。
让 $(i,j)$ 表示从顶部起位于第 $i$ ( $1 \leq i \leq H$ ) 行和从左侧起位于第 $j$ ( $1 \leq j \leq W$ ) 列的单元格。
网格的状态由长度为 $W$ 的 $H$ 字符串 $S_1, S_2, \ldots, S_H$ 表示，如下所示：

• 如果 $S_i$ 的 $j$ -th 字符是 “#”，则单元格 $(i,j)$ 被涂成黑色。
• 如果 $S_i$ 的 $j$ -th 字符是 .，则单元格 $(i,j)$ 被涂成白色。
• 如果 $S_i$ 的 $j$ -th 字符是 ?，则单元格 $(i,j)$ 尚未涂黑。

高桥希望将每个尚未涂色的单元格涂成白色或黑色，这样所有的黑色单元格就组成了一个矩形。
更确切地说，他希望存在一个四元整数 $(a,b,c,d)$ ( $1 \leq a \leq b \leq H$ , $1 \leq c \leq d \leq W$ )，使得：

对于每个单元格 $(i,j)$ ( $1 \leq i \leq H, 1 \leq j \leq W$ )，如果有 $a \leq i \leq b$ 和 $c \leq j \leq d$ 则该单元格为黑色；
否则，单元格为白色。

确定这是否可能。

思路

这题让你把所有的黑色格子都要用上，把边界上的找到，再遍历一遍整个数组就好了。

还是很水。C题要想一想，为了防止乐子看不懂，我善意的写好了变量名。

代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int h, w;
    cin >> h >> w;
    vector<string> grid(h);
    for (int i = 0; i < h; i++)
    {
        cin >> grid[i];
    }
    int row_min = h, row_max = -1;
    int col_min = w, col_max = -1;
    for (int r = 0; r < h; r++)
    {
        for (int c = 0; c < w; c++)
        {
            if (grid[r][c] == '#')
            {
                row_min = min(row_min, r);
                row_max = max(row_max, r);
                col_min = min(col_min, c);
                col_max = max(col_max, c);
            }
        }
    }
    for (int r = row_min; r <= row_max; r++)
    {
        for (int c = col_min; c <= col_max; c++)
        {
            if (grid[r][c] == '.')
            {
                cout << "No";
                return 0;
            }
        }
    }
    cout << "Yes";
    return 0;
}

D.Stone XOR

题面

有 $N$ 个袋子，分别标有袋子 $1$ 、袋子 $2$ 、 $\ldots$ 、袋子 $N$ 。
袋子 $i$ （ $1 \leq i \leq N$ ）装有 $A_i$ 块石头。

高桥可以进行以下任意次数的运算，有可能是零：

选择两个袋子 A 和 B，将 A 袋中的所有棋子移入 B 袋。

在重复操作后，求以下可能出现的不同数值的个数。

• $B_1 \oplus B_2 \oplus \cdots \oplus B_N$ ，其中 $B_i$ 是袋子 $i$ 中石头的最终数量。
  这里， $\oplus$ 表示位向 XOR。

关于位向 XOR 对于非负整数 $a$ 和 $b$ ，位向 XOR $a \oplus b$ 的定义如下：

在 $a \oplus b$ 的二进制表示中，当且仅当 $a$ 和 $b$ 的 $2^k$ 位上的数字中正好有一位是 $1$ 时， $2^k$ 位（ $k \ge 0$ ）上的数字是 $1$ ；否则，它是 $0$ 。

例如， $3 \oplus 5 = 6$ （二进制为 $011 \oplus 101 = 110$ ）。
一般来说，对于 $k$ 非负整数 $x_1, x_2, \ldots, x_k$ ，它们的比特 XOR $x_1 \oplus x_2 \oplus \cdots \oplus x_k$ 被定义为 $(\cdots((x_1 \oplus x_2) \oplus x_3) \oplus \cdots) \oplus x_k$ ，这与 $x_1, x_2, \ldots, x_k$ 的阶数无关。

可以证明，在这个问题的约束条件下，可能的值是有限的。

• $2 \leq N \leq 12$
• $1 \leq A_i \leq 10^{17}$
• 所有输入值均为整数。

思路

不是，不是，你们看到$XOR$就以为它是数学的吗？

不是，不是，你们看到$10^{17}$还想着$DP$？

不是，不是，你们没看到时限$3$秒吗？

子集枚举就ok了，你可以再用状压，也可以再用$hash$表，不理解为什么那么多人没过。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector<ll> a(n);
	for (auto &x : a) cin >> x;
	vector<ll> c(n, 0);
	for (int i = 0; i < n; i++) c[i] = min(a[i], (ll)(n - i - 1));
	int max_iters = 10;
	while (max_iters--) {
		vector<ll> add(n + 2, 0LL);
		for (int j = 0; j < n; j++) {
			if (c[j] == 0) continue;
			ll l = j + 1;
			ll r = j + c[j];
			if (l >= n) continue;
			r = min(r, (ll)(n - 1));
			add[l] += 1;
			if (r + 1 < n) add[r + 1] -= 1;
		}
		vector<ll> received(n, 0);
		received[0] = add[0];
		for (int i = 1; i < n; i++) received[i] = received[i - 1] + add[i];
		bool changed = false;
		for (int i = 0; i < n; i++) {
			ll new_c = min(a[i] + received[i], (ll)(n - i - 1));
			if (new_c != c[i]) {
				c[i] = new_c;
				changed = true;
			}
		}
		if (!changed) break;
	}
	vector<ll> add_final(n + 2, 0LL);
	for (int j = 0; j < n; j++) {
		if (c[j] == 0) continue;
		ll l = j + 1;
		ll r = j + c[j];
		if (l >= n) continue;
		r = min(r, (ll)(n - 1));
		add_final[l] += 1;
		if (r + 1 < n) add_final[r + 1] -= 1;
	}
	vector<ll> received_final(n, 0);
	received_final[0] = add_final[0];
	for (int i = 1; i < n; i++) received_final[i] = received_final[i - 1] + add_final[i];
	vector<ll> final_gems(n, 0);
	for (int i = 0; i < n; i++) {
		ll given = c[i];
		ll received = received_final[i];
		final_gems[i] = a[i] - given + received;
	}
	for (int i = 0; i < n; i++) {
      cout << final_gems[i] << ' ';
    }
}#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[12], n;
unordered_set<int> s;
void dfs(int idx, int used, int blockSum[12])
{
    if (idx == n)
    {
        if (used <= n)
        {
            int x = 0;
            for (int i = 0; i < used; i++)
            {
                x ^= blockSum[i];
            }
            s.insert(x);
        }
        return;
    }
    for (int i = 0; i < used; i++)
    {
        blockSum[i] += a[idx];
        dfs(idx + 1, used, blockSum);
        blockSum[i] -= a[idx];
    }
    blockSum[used] = a[idx];
    dfs(idx + 1, used + 1, blockSum);
    blockSum[used] = 0;
    return;
}
signed main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    int blockSum[12];
    memset(blockSum, 0, sizeof(blockSum));
    dfs(0, 0, blockSum);
    cout << s.size();
    return 0;
}

E.Vitamin Balance

数组开小了居然TLE，没改出来，痛失。

（我说为什么只有AC和TLE的点而且两个时间差距大的离谱）

总结

总个锤啊，有啥好总结的。

要总结，就是数组开小可能会TLE，但是我还是不知道为啥。