2021-03-06

2020 ACM-ICPC, Asia Jinan Regional

字数统计: 2.5k字 | 阅读时长: 12分

solved	A	B	C	D	E	F	G	H	I	J	K	L	M
6 / 13	Ø	·	O	O	·	·	O	·	·	Ø	·	·	O

O：比赛时通过
Ø：赛后通过
!：比赛时尝试了未通过
·：比赛时未尝试

比赛链接

A. Matrix Equation

solved by Tryna.(-)

题意： 给出两个 $n * n$ 的方阵 $A$ 和 $B$ ，求 $C$ 矩阵的数量满足$$A × C = B ⊙ C$$
我们对每一列进行单独考虑，比如第一列:

\begin{bmatrix}A_{11}\ A_{12}\ A_{13}& \cdots & A_{1n}\\ A_{21}\ A_{22}\ A_{23}& \cdots & A_{2n}\\ \vdots & \ddots & \vdots\\ A_{n1}\ A_{n2}\ A_{n3}& \cdots & A_{nn}\\ \end{bmatrix} * \begin{bmatrix}C_{11}\\ C_{21}\\ \vdots \\ C_{n1} \end{bmatrix} = \begin{bmatrix} B_{11}*C_{11}\\ B_{21}*C_{21}\\ \vdots \\ B_{n1}*C_{n1} \end{bmatrix}

展开并且移项：

(A_{11} - B_{11}) * C_{11} + A_{12} * C_{21} + \cdots + A_{1n} * C_{n1} = 0

所以就变成了这样：

\begin{bmatrix}A_{11} - B_{11}\ \ \ \ A_{12} \ \ \ A_{13}& \cdots & A_{1n}\\ A_{21}\ \ \ \ \ \ \ \ A_{22} - B_{21}\ A_{23}& \cdots & A_{2n}\\ \vdots & \ddots & \vdots\\ A_{n1}\ A_{n2}\ A_{n3}& \cdots & A_{nn} - B_{n1}\\ \end{bmatrix} * \begin{bmatrix}C_{11}\\ C_{21}\\ \vdots \\ C_{n1} \end{bmatrix} = \begin{bmatrix} 0\\ 0\\ \vdots \\ 0 \end{bmatrix}

因为题目要求模 $2$ 加法，其实就相当于异或。
所以我们只要用高斯消元求&n&个异或方程组的自由元数量 $sum$ 就行了,因为只能取 $0$ 或 $1$ ，所以答案是 $2^{sum}$

AC代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define PAUSE system("pause")
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
const int maxn = 2e2 + 10;
const int mod = 998244353;
int t, n, a[maxn][maxn], A[maxn][maxn], B[maxn][maxn], x[maxn];
bool freeX[maxn];
ll b[maxn]; 
ll quick_power(ll n, ll k){
	ll ans=1;
	while(k){
		if(k&1){
			ans=(ans*n)%mod;
		}
		n=n*n%mod;
		k>>=1;
	}
	return ans%mod;
}
int Gauss(int equ,int var){
    for(int i=0;i<=var;i++){
        x[i]=0;
        freeX[i]=0;
    }
    int col=0;//当前处理的列
    int num=0;//自由变元的序号
    int row;//当前处理的行
    for(row=0;row<equ&&col<var;row++,col++){//枚举当前处理的行
        int maxRow=row;//当前列绝对值最大的行
        for(int i=row+1;i<equ;i++){//寻找当前列绝对值最大的行
            if(abs(a[i][col])>abs(a[maxRow][col]))
                maxRow=i;
        }
        if(maxRow!=row){//与第row行交换
            for(int j=row;j<var+1;j++)
                swap(a[row][j],a[maxRow][j]);
        }
        if(a[row][col]==0){//col列第row行以下全是0，处理当前行的下一列
            freeX[num++]=col;//记录自由变元
            row--;
            continue;
        }
        for(int i=row+1;i<equ;i++){
            if(a[i][col]!=0){
                for(int j=col;j<var+1;j++){//对于下面出现该列中有1的行，需要把1消掉
                    a[i][j]^=a[row][j];
                }
            }
        }
    }
    for(int i=row;i<equ;i++)
        if(a[i][col]!=0)
            return -1;
    int temp=var-row;//自由变元有var-row个
    if(row<var)//返回自由变元数
        return temp;
    return 0;
}
void init() {
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++)
			a[i][j] = A[i][j];
	}
}
void solve() {
    scanf("%d", &n);
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) 
			scanf("%d", &A[i][j]);
	}
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++)
			scanf("%d", &B[i][j]);
	}
	ll ans = 1;
	for(int i = 0; i < n; i++) {
		init();
		for(int j = 0; j < n; j++) {
			a[j][j] = abs((a[j][j] - B[j][i]) % 2);
		}
		int num = Gauss(n, n);
		if(num == -1) continue;
		ans = ans * quick_power(2, num) % mod;
	}
	printf("%lld\n", ans);
}
int main() {
    // scanf("%d", &t);
    // while(t--)
    solve();
	PAUSE;
	return 0;
}

C. Stone Game

solved by all. 0:51(+)

题意： 两堆石子的数量分别为 $x$ 和 $y$ ，合并他们需要花费 $(x mod 3) * (y mod 3)$ 。现有数量为 $1，2，3$ 的石子堆若干，求合并他们的最小花费是多少。

题解： 很明显要尽量往3凑。优先合并 $1，2$ ，凑出 $3$ ，然后把 $3$ 的都合并在一起，最后把剩下的 $1，2$ 合并了。注意下只有一种数量的石子堆的情况，因为可能凑不出一堆数量为 $3$ 的倍数的石子。

AC代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll a[5];

int main() {
	scanf("%lld %lld %lld", &a[1], &a[2], &a[3]);
	int num = 0;
	ll tot = 0;
	for (int i = 1; i <= 3; ++i) {
		if (a[i] == 0) num++;
		tot += a[i];
	}
	if (tot == 1) {
		puts("0");
		return 0;
	}
	ll ans = 0;
	if (num == 2) {
		if (a[1]) {
			if (a[1] == 2) {
				puts("1");
				return 0;
			}
			ans = a[1] / 3 * 3;
			a[1] %= 3;
			if (a[1] == 2) ans += 1;
			printf("%lld\n", ans);
		}
		if (a[2]) {
			if (a[2] == 2) {
				puts("4");
				return 0;
			}
			ans = a[2] / 3 * 6;
			a[2] %= 3;
			if (a[2] == 2) ans += 4;
			printf("%lld\n", ans);
		}
		if (a[3]) {
			puts("0");
		}
		return 0;
	}
	if (a[1] >= a[2]) {
		ans = a[2] * 2 + (a[1] - a[2]) / 3 * 3;
		a[1] -= a[2];
		a[1] %= 3;
		if (a[1] == 2) ans += 1;
		printf("%lld\n", ans);
	} else {
		ans = a[1] * 2 + (a[2] - a[1]) / 3 * 6;
		a[2] -= a[1];
		a[2] %= 3;
		if (a[2] == 2) ans += 4;
		printf("%lld\n", ans);
	}
	return 0;
}

D. Fight against involution

solved by Sstee1XD & lllllan. 1:21(+1)

题意： 给你每个人的权值分布，刚开始所有人权值取最大，从大到小进行排名。接下来你可以任意降低人的权值，使得他们的排名不会下降，并且所有人的权值和最小，问你最小的权值和是多少。

题解： 以权值右边界为第一关键字，从大到小排序，以左边界为第二关键字，从小到大排序。遍历排序后的序列，遇到右边界值相同的，把他们放在一起处理，权值统一改为前一个人的权值和当前左边界值取大后的值。

AC代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 1e5 + 10;

int n;

struct node { ll l, r; } a[maxn];
int cmp (node A, node B) { 
	if (A.r == B.r) return A.l < B.l;
	return A.r < B.r;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) scanf("%lld%lld", &a[i].l, &a[i].r);
	sort(a + 1, a + n + 1, cmp);
	
	ll pre = -1;
	ll ans = 0;
	for (int i = 1; i <= n; ++i) {
		ll len = 1;
		while (i < n && a[i + 1].r == a[i].r) i++, len++;
		if (pre == -1) pre = a[i].l;
		else pre = max(pre, a[i].l);
		ans += pre * len;
	}
	printf("%lld\n", ans);
//	for (int i = 1; i <= n; ++i) {
//		printf("%lld %lld\n", a[i].l, a[i].r);
//	}
	
	
	return 0;
}

G. Xor Transformation

solved by Sstee1XD & Tryna. 0:22(+)

题意： 给一个 $X$ 和 $Y$ ,每次选择一个 $A$ , 使得 $X = X xor A$ ，最多不超过五次操作，使得 $X = Y$ , 输出操作次数和每次的 $A$

题解： 对于任何数，最多只需要两次操作就能变成 $Y$ , 首先第一步是将 $X$ 变成当前二进制位数下的最大值，第二步选取的 $A$ 就是最大值与 $Y xor$ 的结果

AC代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll x, y;

int main() {
	scanf("%lld %lld", &x, &y);
	ll go = 0;
	ll m = __lg(x);
	for (ll i = 0; i < m; ++i) {
		if (((x >> i) & 1) == 0) go += 1ll << i;
//		printf("%d %lld\n", i, (x >> i) & 1);
	}
	printf("2\n%lld %lld\n", go, (go + x) ^ y);
	return 0;
}

J Tree Constructer

solved by lllllan. (-)

题意： 给树上的每个节点赋值，要求直接连接的两点 $u、v$ 的权值相加和为 $2^{60} - 1$ ，同时要求不直接相连的两点权值和一定不能为 $2^{60} - 1$

题解： 对树上所有节点进行染色（黑白两色），直接相连的父子节点染成不同颜色。先对某种颜色的所有节点开始赋值（要先对节点数量较少的一部分），此时这些点的两两权值和一定不能为 $2^{60} - 1$ ，将数值转换成二进制进行分析，每个权值都可以看成是 $2^{60}$ 在不同的位次上减去了1。这样就能满足两联权值和不为 $2^{60} - 1$ 的要求。然后再对另一颜色的所有节点进行赋值，将数值转换成二进制进行分析，每个权值可以看出是0在不同为此上加上了1，至于是哪些位次，依据为该节点的父节点和子节点的减去1的位次。

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 110;


int n;
int id[maxn];
ll ans[maxn];

vector<int> G[maxn];
vector<int> col[maxn];

void DFS (int u, int fa, int c) {
	col[c].push_back(u);
	for (int v : G[u]) {
		if (v == fa) continue;
		DFS (v, u, c ^ 1);
	}
}

int main () {
	scanf("%d", &n);
	for (int i = 1, u, v; i < n; ++i) {
		scanf("%d%d", &u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	
	DFS(1, 0, 1);
	if (col[0].size() > col[1].size()) swap(col[0], col[1]);
	
	int cnt = 0;
	for (int v : col[0]) {
		ans[v] = (1ll << 60) - 1 - (1ll << cnt) - (1ll << 59);
		id[v] = cnt++;
	}
	for (int u : col[1]) {
		ans[u] = (1ll << 59);
		for (int v : G[u]) {
			ans[u] += (1ll << id[v]);
		}
	}
	for (int i = 1; i <= n; ++i) printf("%lld ", ans[i]);
	return 0;
}

M. Cook Pancakes!

solved by Sstee1XD & Tryna. 0:08(+)

题解： 签到，特判下饼的数量小于一次能煎的数量就行了。

AC代码

#include <bits/stdc++.h>

using namespace std;

int n, k;

int main() {
	scanf("%d %d", &n, &k);
	if (n <= k) {
		puts("2");
		return 0;
	}
	int ans = (2 * n + k - 1) / k;
	printf("%d\n", ans);
	return 0;
}