Codeforces Round #675 (Div. 2)、Codeforces Round #676 (Div. 2)

A. XORwice

已知$a,b$，对于任意的$x$，计算$(a\oplus x)+(b\oplus x)$的最小值。

对于$a$、$b$的任意一位，只有当$a$、$b$的该位同时为$1$的时候$x$的该位为$1$才能让该位的和比$x$的该位为$0$的时候小。

# include <iostream>
# include <cstdio>

void solve() {
   
	int a, b;
	scanf("%d%d", &a, &b);
	
	int x = a & b;
	int ans = (a ^ x) + (b ^ x);
	printf("%d\n", ans);
}

int main() {
   
	int T;
	std::cin >> T;
	
	while (T--) {
   
		solve();
	}
	
	return 0;
}

另外，位运算中还有一个公式：$a+b=a\oplus b+(a\&b)\ast 2$
此公式中的+代表加法，*代表乘法
证明：二进制计算中，$0+0=0$，$0+1=1$，$1+0=1$，$1+1=0^{\prime }$,但$1+1=0$需要向高位进一位，相当于加上$(a\&b)<<1$。
另外，如果$a+b\ge (a\&b)\ast 2$并且$a\oplus b$的每一个二进制位都和$a\&b$不同时为1，那么$a\oplus b=a+b-(a\&b)\ast 2$。

B. Putting Bricks in the Wall

给定一个由$0$和$1$构成的$n\times n$的矩阵，有一个人从起点 $(1,1)$走到终点 $(n,n)$，他只能够走相同的数字，要么全部路过元素为$1$的格子，要么全部路过元素为$0$的格子。
现最多给两次操作，每一次操作可以选择该数组的一个元素（除了起点和终点以外）从$0$变成$1$，也可以选择该数组的一个元素从$1$变成 $0$。在操作后使得走迷宫的人不能走到终点。输出任意一种方案。

只需要将A，B，C，D中的AB全变为0，CD全变为1，或者AB全变为1，CD全变为0即可。

# include <iostream>
# include <cstdio>

const int N = 205;
char a[N][N];

void solve() {
   
	int n;
	scanf("%d", &n);

	for (int i = 1; i <= n; i++) {
   
		scanf("%s", a[i] + 1);
	}

	int A, B, C, D;
	A = a[1][2] - '0';
	B = a[2][1] - '0';
	C = a[n][n-1] - '0';
	D = a[n-1][n] - '0';

	int num = (A << 3) + (B << 2) + (C << 1) + D;
	switch (num) {
   
		case 0: {
   
			printf("2\n1 2\n2 1\n");
			break;
		}
		case 1: {
   
			printf("1\n%d %d\n", n, n-1);
			break;
		}
		case 2: {
   
			printf("1\n%d %d\n", n-1, n);
			break;
		}
		case 3: {
   
			puts("0");
			break;
		}
		case 4: {
   
			printf("1\n1 2\n");
			break;
		}
		case 5: {
   
			printf("2\n2 1\n%d %d\n", n, n-1);
			break;
		}
		case 6: {
   
			printf("2\n2 1\n%d %d\n", n-1, n);
			break;
		}
		case 7: {
   
			printf("1\n2 1\n");
			break;
		}
		case 8: {
   
			printf("1\n2 1\n");
			break;
		}
		case 9: {
   
			printf("2\n2 1\n%d %d\n", n - 1, n);
			break;
		}
		case 10: {
   
			printf("2\n1 2\n%d %d\n", n - 1, n);
			break;
		}
		case 11: {
   
			printf("1\n1 2\n");
			break;
		}
		case 12: {
   
			printf("0\n");
			break;
		}
		case 13: {
   
			printf("1\n%d %d\n", n-1, n);
			break;
		}
		case 14: {
   
			printf("1\n%d %d\n", n, n-1);
			break;
		}
		case 15: {
   
			printf("2\n1 2\n2 1\n");
			break;
		}
	}

}

int main() {
   
	int T;
	std::cin >> T;

	while (T--) {
   
		solve();
	}

	return 0;
}

C. Palindromifier

有一个仅由英文小写字母组成的长度为$n$的字符串$s$，对该字符串进行$k$操作，每次操作可以选择以下两种操作中的一种：
操作$L$：选择一个下标 $i(2\le i\le n-1)$，将$s_2{s}_3...s_i$复制(append)下来，然后倒置，再将其放到字符串的开头。
操作$R$：选择一个下标 $i(2\le i\le n-1)$，将$s_i{s}_{i+1}...s_{n-1}$复制(append)下来，然后倒置，再将其放到字符串的末尾。
$0\le k\le 30$，目标是将字符串转为回文串。输出任意一种情况均可。

假设字符串是$abcde$，经过$Ln$的操作后会变成$dcbabcde$。这个字符串除了$e$以外其余都是对称的。如果先将原字符串$abcde$经过$Rn-1$操作后变成$abcded$，再经过$Ln$的操作得到$edcbabcded$，再经过$L2$就可以得到$dedcbabcded$，这是一个回文字符串。其余的字符串也能通过此方法得到回文字符串。
答案就是
3
R n-1
L n
L 2

# include <iostream>
# include <string>

int main() {
   
	std::string s;
	std::cin >> s;
	int n = s.size();
	
	std::cout << "3\nR " << n - 1 << "\nL " << n << "\nL 2";
 
	return 0;
}

D. Hexagons

有一个正六边形构成的蜂窝网，每一个正六边形对应一个坐标，坐标的表示形式如图所示。

共有6个方向向量$C_1(1,1)$，$C_2(0,1)$，$C_3(-1,0)$，$C_4(-1,-1)$，$C_5(0,-1)$，$C_6(1,0)$，每个方向向量有一个权重，代表往该方向走的花费。求从起点$(0,0)$到终点$(x,y)$的最小花费。

从原点到任意一点的最短路线仅仅只需要使用两个方向向量若干次。证明：假设目标点在原点的右边（在其他方向的证明过程也类似。），那么只需要$C_1$、$C_2$、$C_3$就可以到达该目标点，如果使用$C_4$、$C_5$、$C_6$就会和$C_1$、$C_2$、$C_3$相抵消，只会增加距离。而$C_2$刚好等于先走一步$C_1$再走一步$C_3$，因此如果$C_1+C_3<C_2$那么就在需要走$C_2$时换成走一步$C_1$再走一步$C_3$，如果$C_1+C_3\ge C_2$那么就在$C_1$和$C_3$都存在时将$C_1$和$C_3$替换成$C_2$，那么就只需要若干步$C_1$和若干步$C_2$ 或者 若干步$C_3$和若干步$C_2$就可以以最少的代价到达目标点。

假设目标点的坐标为$(x,y)$，需要选择的方向向量为$(i_x,i_y)$和$(j_x,j_y)$，需要走$k_1$步的$i$和$k_2$步的$j$，那么
$$(x,y)=k_1\ast (i_x,i_y)+k_2\ast (j_x,j_y)$$

$$\{\begin{array}{r}x=k_1\ast i_x+k_2\ast j_x\\ y=k1\ast i_y+k2\ast j_y\end{array}$$

$$k_1=\frac{\left|\begin{array}{cc}x& j_x\\ y& j_y\end{array}\right|}{\left|\begin{array}{cc}{i}_x& j_x\\ i_y& j_y\end{array}\right|}{k}_2=\frac{\left|\begin{array}{cc}x& j_x\\ y& j_y\end{array}\right|}{\left|\begin{array}{cc}{i}_x& j_x\\ i_y& j_y\end{array}\right|}$$

枚举所有可以选择的方向向量对，删除方向相反的方向向量对，删除$\left|\begin{array}{cc}{i}_x& j_x\\ i_y& j_y\end{array}\right|=0$的方向向量对，删除$k_1$或$k_2$小于$0$的方向向量对，剩下的所有方案中选最小值。

# include <iostream>

typedef long long ll;

const int dx[6] = {
   1, 0, -1, -1, 0, 1};
const int dy[6] = {
   1, 1, 0, -1, -1, 0};
int weight[6];

void solve() {
   
	int x, y;
	scanf("%d%d", &x, &y);
	for (int i = 0; i < 6; i++) {
   
		scanf("%d", &weight[i]);
	}

	ll min = 4e18;
	for (int i = 0; i < 6; i++) {
   
		for (int j = i + 1; j < 6; j++) {
   
			if (j - i == 3) {
   
				continue;
			}

			int delta = dx[i] * dy[j] - dx[j] * dy[i];
			if (delta == 0) {
   
				continue;
			}

			int delta_a = x * dy[j] - dx[j] * y;
			int k1 = delta_a / delta;
			int delta_b = y * dx[i] - dy[i] * x;
			int k2 = delta_b / delta;

			if (k1 < 0 || k2 < 0) {
   
				continue;
			}

			ll ans = 1ll * k1 * weight[i] + 1ll * k2 * weight[j];
			min = std::min(min, ans);
		}
	}

	printf("%lld\n", min);
}

int main() {
   
	int T;
	std::cin >> T;
	while (T--) {
   
		solve();
	}

	return 0;
}

A. Fence

给定三条边$a$，$b$，$c$，求边长$d$，使得$a$、$b$、$c$、$d$能够构成一个非退化四边形(non-degenerate simple quadrilateral)。非退化四边形指的是四边形的四个角没有0度或者180度的情况。

输出$max(a,b,c)$~$(a+b+c-1)$之间的任意一个值都可。

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

typedef long long ll;

int random() {
   
	return (rand() << 15) | rand();
}

// [0, n)
int random(int n) {
   
	return random() % n;
}

// [l, r)
int random(const int &l, const int &r) {
   
	if (l == r) {
   
		return l;
	}

	return l + random(r - l);
}

long long randomll() {
   
	return ((long long)random() << 30) | random();
}

long long randomll(const long long &n) {
   
	return randomll() % n;
}

long long randomll(const long long &l, const long long &r) {
   
	if (l == r) {
   
		return l;
	}

	return l + randomll(r - l);
}

long double randoml() {
   
	return (long double)randomll() / (1ll << 60);
}

long double randoml(const long double &n) {
   
	return randoml() * n;
}

long double randoml(const long double &l, const long double &r) {
   
	return l + randoml(r - l);
}

void solve() {
   
	int a, b, c;
	scanf("%d%d%d", &a, &b, &c);
	
	ll l = std::max(std::max(a, b), c);
	ll r = 1ll * a + b + c;
	ll ans = randomll(l, r);
	printf("%lld\n", ans);
}

int main() {
   
	int T;
	std::cin >> T;
	
	while (T--) {
   
		solve();
	}
	
	return 0;
}

B. Nice Matrix

给定一个$n\times m$的矩阵，每一次操作可以将该矩阵内的一个元素+1或者-1，求最小操作次数使得该矩阵的每一行、每一列都变成回文序列。

如果矩阵的每一行、每一列都是回文序列，那么$a[i][j]=a[i][m-j-1]=a[n-i-1][j]$。对三个数进行+1或者-1的操作使得三个数相等，花费最小，最优的方法是另外两个数通过+1或者-1变成中位数的值。对矩阵的每一个元素都进行此操作，记录下每一次操作的花费，求和即是答案。

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

typedef long long ll;

int a[105][105];

void solve() {
   
	int n, m;
	scanf("%d%d", &n, &m);
	
	for (int i = 0; i < n; i++) {
   
		for (int j = 0; j < m; j++)
			scanf("%d", &a[i][j]);
	}
	
	ll ans = 0;
	for (int i = 0; i < n; i++) {
   
		for (int j = 0; j < m; j++) {
   
			std::vector<int> b;
			b.push_back(a[i][j]);
			b.push_back(a[i][m-j-1]);
			b.push_back(a[n-i-1][j]);
			std::sort(b.begin(), b.end());
			
			a[i][j] = a[i][m - j - 1] = a[n - i - 1][j] = b[1];
			
			ans += 1ll * b[2] - b[1] + b[1] - b[0];
		}
	}
	
	printf("%lld\n", ans);
}

int main() {
   
	int T;
	std::cin >> T;
	while (T--){
   
		solve();
	}
	
	return 0;
}

C. Bargain

给定一个数字$n(1\le n\le 10^{10^5})$，求$n$的所有子字符串的和(不含原子串，但包含空串)。
枚举每个字符，考虑这一位能够将答案的和增加多少。
该位可增加的值分为：删除的区间在该位之前的贡献和删除的区间在该位之后的贡献。
以左边的数字为高位，右边的数字为低位，从0开始计数。
删除的区间在该位之前的贡献为$s[i]\ast 10^i\ast \frac{(n-i)\ast (n-i+1)}{2}$
删除的区间在该位之后的贡献为$i\ast 10^{i-1}+(i-1)\ast 10^{i-2}+...+2\ast 10^1+1\ast 10^0$。

令 \quad \quad $S(n)=1\ast 10^0+2\ast 10^1+...+(n-1)\ast 10^{n-2}+n\ast 10^{n-1}$
\quad $10\ast S(n)=1\ast 10^1+...+(n-2)\ast 10^{n-1}+(n-1)\ast 10^{n-1}+n\ast 10^n$
$-9\ast S(n)=1\ast 10^0+1\ast 10^1+...+1\ast 10^{n-2}+1\ast 10^{n-1}-n\ast 10^n$
$-9\ast S(n)=\frac{10^n-1}{9}-n\ast 10^n$
$S(n)=\frac{(9\ast n-1)\ast 10^n+1}{81}$

在取模运算中，$(a+b)\%p=(a\%p+b\%p)\%p$
此写法等价于$(a+b)\equiv (a\%p+b\%p)(modp)$。这个写法叫做“同余”。
$(a-b)\%p=(a\%p-b\%p+p)\%p$
$(a\ast b)\%p=(a\%p\ast b\%p)\%p$

若$b$与$p$互质，$\frac{a}{b}\%p=a\%p\ast b^{\varphi (p)-1}\%p$。
$b^{\varphi (p)-1}$被称作$b$的乘法逆元。也可以通过扩展欧几里得算法算出乘法逆元。

$1$~$n$中与$n$互质的数的个数叫做欧拉函数。记为$\varphi (n)$。当$n$为质数时，$\varphi (n)=n-1$

int phi(n) {
   
	int ans = n;
	for (int i = 2; i <= n / i; i++) {
   
		if (n % i == 0) {
   
			ans = ans / i * (i - 1);
			
			while (n % i == 0) {
   
				n /= i;
			}
		}
	}
	
	if (n > 1) {
   
		ans = ans / n * (n - 1);
	}
	
	return ans;
}

或者在main函数下的第一行使用init()函数求S[n]

int S[N];
void init() {
   
	S[0] = 0;
	S[1] = 1;
	int p10 = 10;
	for (int i = 2; i < N; i++) {
   
		S[i] = (S[i-1] + 1ll * i * p10 % mod) % mod;
		p10 = 1ll * p10 * 10 % mod;
	}
}

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

typedef long long ll;
const int mod = 1e9 + 7;

int inv;

int qpow(int a, int b) {
   
	int ans = 1 % mod;

	while (b) {
   
		if (b & 1) {
   
			ans = 1ll * ans * a % mod;
		}

		b >>= 1;
		a = 1ll * a * a % mod;
	}

	return ans;
}

int qsum(int n) {
   
	if (n == 0) {
   
		return 0;
	}

	int fz = 1ll * (9 * n - 1) * qpow(10, n) % mod + 1;
	fz %= mod;

	return 1ll * fz * inv % mod;
}

int main() {
   
	inv = qpow(81, mod - 2);
	std::string s;
	std::cin >> s;
	std::reverse(s.begin(), s.end());
	int n = s.size() - 1;

	ll ans = 0, p10 = 1;

	for (int i = 0; i < s.size(); i++) {
   
		int d = s[i] - '0';
		ll sum1 = 1ll * (n - i) * (n - i + 1) / 2 % mod * p10 % mod * d % mod;
		ll sum2 = 1ll * d * qsum(i) % mod;
		ans = ((ans + sum1) % mod + sum2) % mod;
		p10 = p10 * 10 % mod;
	}

	std::cout << ans << "\n";

	return 0;
}