欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

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

程序员文章站 2022-03-19 22:35:58
Codeforces Round #675 (Div. 2)、Codeforces Round #676 (Div. 2)A. XORwice# include # include void solve() {int a, b;scanf("%d%d", &a, &b);int x = a & b;int ans = (a ^ x) + (b ^ x);printf("%d\n", ans)...

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

A. XORwice

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

a b x x sum sum
0 0 0 1 0 2
0 1 0 1 1 1
1 0 0 1 1 1
1 1 0 1 2 0

对于 a a a b b b的任意一位,只有当 a a a b b b的该位同时为 1 1 1的时候 x x x的该位为 1 1 1才能让该位的和比 x x x的该位为 0 0 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 ⊕ b + ( a & b ) ∗ 2 a+b=a\oplus b +(a \&b) * 2 a+b=ab+(a&b)2
此公式中的+代表加法,*代表乘法
证明:二进制计算中, 0 + 0 = 0 0+0=0 0+0=0 0 + 1 = 1 0+1=1 0+1=1 1 + 0 = 1 1+0=1 1+0=1 1 + 1 = 0 ′ 1+1=0' 1+1=0,但 1 + 1 = 0 1+1=0 1+1=0需要向高位进一位,相当于加上 ( a & b ) < < 1 (a\&b)<<1 (a&b)<<1
另外,如果 a + b ≥ ( a & b ) ∗ 2 a+b\ge (a\&b)*2 a+b(a&b)2并且 a ⊕ b a\oplus b ab的每一个二进制位都和 a & b a\&b a&b不同时为1,那么 a ⊕ b = a + b − ( a & b ) ∗ 2 a\oplus b=a+b-(a\&b)*2 ab=a+b(a&b)2

B. Putting Bricks in the Wall

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

S A
B
D
C F

只需要将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 n n的字符串 s s s,对该字符串进行 k k k操作,每次操作可以选择以下两种操作中的一种:
操作 L L L:选择一个下标 i ( 2 ≤ i ≤ n − 1 ) i(2\le i\le n-1) i(2in1),将 s 2 s 3 . . . s i s_2s_3...s_i s2s3...si复制(append)下来,然后倒置,再将其放到字符串的开头。
操作 R R R:选择一个下标 i ( 2 ≤ i ≤ n − 1 ) i(2\le i\le n-1) i(2in1),将 s i s i + 1 . . . s n − 1 s_is_{i+1}...s_{n-1} sisi+1...sn1复制(append)下来,然后倒置,再将其放到字符串的末尾。
0 ≤ k ≤ 30 0\le k \le30 0k30,目标是将字符串转为回文串。输出任意一种情况均可。

假设字符串是 a b c d e abcde abcde,经过 L   n L\ n L n的操作后会变成 d c b a b c d e dcbabcde dcbabcde。这个字符串除了 e e e以外其余都是对称的。如果先将原字符串 a b c d e abcde abcde经过 R   n − 1 R\ n-1 R n1操作后变成 a b c d e d abcded abcded,再经过 L   n L\ n L n的操作得到 e d c b a b c d e d edcbabcded edcbabcded,再经过 L   2 L\ 2 L 2就可以得到 d e d c b a b c d e d dedcbabcded 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

有一个正六边形构成的蜂窝网,每一个正六边形对应一个坐标,坐标的表示形式如图所示。
Codeforces Round #675 (Div. 2)、Codeforces Round #676 (Div. 2)

共有6个方向向量 C 1 ( 1 , 1 ) C_1(1, 1) C1(1,1) C 2 ( 0 , 1 ) C_2(0,1) C2(0,1) C 3 ( − 1 , 0 ) C_3(-1,0) C3(1,0) C 4 ( − 1 , − 1 ) C_4(-1,-1) C4(1,1) C 5 ( 0 , − 1 ) C_5(0,-1) C5(0,1) C 6 ( 1 , 0 ) C_6(1,0) C6(1,0),每个方向向量有一个权重,代表往该方向走的花费。求从起点 ( 0 , 0 ) (0,0) (0,0)到终点 ( x , y ) (x,y) (x,y)的最小花费。
Codeforces Round #675 (Div. 2)、Codeforces Round #676 (Div. 2)

从原点到任意一点的最短路线仅仅只需要使用两个方向向量若干次。证明:假设目标点在原点的右边(在其他方向的证明过程也类似。),那么只需要 C 1 C_1 C1 C 2 C_2 C2 C 3 C_3 C3就可以到达该目标点,如果使用 C 4 C_4 C4 C 5 C_5 C5 C 6 C_6 C6就会和 C 1 C_1 C1 C 2 C_2 C2 C 3 C_3 C3相抵消,只会增加距离。而 C 2 C_2 C2刚好等于先走一步 C 1 C_1 C1再走一步 C 3 C_3 C3,因此如果 C 1 + C 3 < C 2 C_1+C_3 < C_2 C1+C3<C2那么就在需要走 C 2 C_2 C2时换成走一步 C 1 C_1 C1再走一步 C 3 C_3 C3,如果 C 1 + C 3 ≥ C 2 C_1+C_3 \ge C_2 C1+C3C2那么就在 C 1 C_1 C1 C 3 C_3 C3都存在时将 C 1 C_1 C1 C 3 C_3 C3替换成 C 2 C_2 C2,那么就只需要若干步 C 1 C_1 C1和若干步 C 2 C_2 C2 或者 若干步 C 3 C_3 C3和若干步 C 2 C_2 C2就可以以最少的代价到达目标点。

假设目标点的坐标为 ( x , y ) (x, y) (x,y),需要选择的方向向量为 ( i x , i y ) (i_x,i_y) (ix,iy) ( j x , j y ) (j_x,j_y) (jx,jy),需要走 k 1 k_1 k1步的 i i i k 2 k_2 k2步的 j j j,那么
( x , y ) = k 1 ∗ ( i x , i y ) + k 2 ∗ ( j x , j y ) (x,y)=k_1*(i_x,i_y)+k_2*(j_x,j_y) (x,y)=k1(ix,iy)+k2(jx,jy)

{ x = k 1 ∗ i x + k 2 ∗ j x y = k 1 ∗ i y + k 2 ∗ j y \left\{ \begin{aligned} x = k_1*i_x+k_2*j_x \\ y=k1*i_y+k2*j_y \end{aligned} \right. {x=k1ix+k2jxy=k1iy+k2jy

k 1 = ∣ x j x y j y ∣ ∣ i x j x i y j y ∣ k 2 = ∣ x j x y j y ∣ ∣ i x j x i y j y ∣ k_1=\frac{\left|\begin{array}{cccc} x & j_x \\ y & j_y \end{array}\right| }{\left|\begin{array}{cccc} i_x & j_x \\ i_y & j_y \end{array}\right| }\quad k_2=\frac{\left|\begin{array}{cccc} x & j_x \\ y & j_y \end{array}\right| }{\left|\begin{array}{cccc} i_x & j_x \\ i_y & j_y \end{array}\right| } k1=ixiyjxjyxyjxjyk2=ixiyjxjyxyjxjy

枚举所有可以选择的方向向量对,删除方向相反的方向向量对,删除 ∣ i x j x i y j y ∣ = 0 \left|\begin{array}{cccc} i_x & j_x \\ i_y & j_y \end{array}\right|=0 ixiyjxjy=0的方向向量对,删除 k 1 k_1 k1 k 2 k_2 k2小于 0 0 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 a a b b b c c c,求边长 d d d,使得 a a a b b b c c c d d d能够构成一个非退化四边形(non-degenerate simple quadrilateral)。非退化四边形指的是四边形的四个角没有0度或者180度的情况。

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

# 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 × m n×m n×m的矩阵,每一次操作可以将该矩阵内的一个元素+1或者-1,求最小操作次数使得该矩阵的每一行、每一列都变成回文序列。

如果矩阵的每一行、每一列都是回文序列,那么 a [ i ] [ j ] = a [ i ] [ m − j − 1 ] = a [ n − i − 1 ] [ j ] a[i][j]=a[i][m-j-1]=a[n-i-1][j] a[i][j]=a[i][mj1]=a[ni1][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 ≤ n ≤ 1 0 1 0 5 ) n(1\le n\le 10^{10^5}) n(1n10105),求 n n n的所有子字符串的和(不含原子串,但包含空串)。
枚举每个字符,考虑这一位能够将答案的和增加多少。
该位可增加的值分为:删除的区间在该位之前的贡献和删除的区间在该位之后的贡献。
以左边的数字为高位,右边的数字为低位,从0开始计数。
删除的区间在该位之前的贡献为 s [ i ] ∗ 1 0 i ∗ ( n − i ) ∗ ( n − i + 1 ) 2 s[i]*10^i*\frac{(n-i)*(n-i+1)}{2} s[i]10i2(ni)(ni+1)
删除的区间在该位之后的贡献为 i ∗ 1 0 i − 1 + ( i − 1 ) ∗ 1 0 i − 2 + . . . + 2 ∗ 1 0 1 + 1 ∗ 1 0 0 i*10^{i-1}+(i-1)*10^{i-2}+...+2*10^1+1*10^0 i10i1+(i1)10i2+...+2101+1100

\quad \quad S ( n ) = 1 ∗ 1 0 0 + 2 ∗ 1 0 1 + . . . + ( n − 1 ) ∗ 1 0 n − 2 + n ∗ 1 0 n − 1 S(n)=1*10^0+2*10^1+...+(n-1)*10^{n-2}+n*10^{n-1} S(n)=1100+2101+...+(n1)10n2+n10n1
\quad 10 ∗ S ( n ) = 1 ∗ 1 0 1 + . . . + ( n − 2 ) ∗ 1 0 n − 1 + ( n − 1 ) ∗ 1 0 n − 1 + n ∗ 1 0 n 10*S(n)=\quad\quad \quad \quad1*10^1+...+(n-2)*10^{n-1}+(n-1)*10^{n-1}+n*10^n 10S(n)=1101+...+(n2)10n1+(n1)10n1+n10n
− 9 ∗ S ( n ) = 1 ∗ 1 0 0 + 1 ∗ 1 0 1 + . . . + 1 ∗ 1 0 n − 2 + 1 ∗ 1 0 n − 1 − n ∗ 1 0 n \quad-9*S(n)=1*10^0+1*10^1+...+1*10^{n-2}+1*10^{n-1}-n*10^n 9S(n)=1100+1101+...+110n2+110n1n10n
− 9 ∗ S ( n ) = 1 0 n − 1 9 − n ∗ 1 0 n \quad-9*S(n)=\frac{10^n-1}{9}-n*10^n 9S(n)=910n1n10n
S ( n ) = ( 9 ∗ n − 1 ) ∗ 1 0 n + 1 81 S(n)=\frac{(9*n-1)*10^n+1}{81} S(n)=81(9n1)10n+1

在取模运算中, ( a + b ) % p = ( a % p + b % p ) % p (a+b)\%p=(a\%p+b\%p)\%p (a+b)%p=(a%p+b%p)%p
此写法等价于 ( a + b ) ≡ ( a % p + b % p ) ( m o d   p ) (a+b)\equiv(a\%p+b\%p) (mod\ p) (a+b)(a%p+b%p)(mod p)。这个写法叫做“同余”。
( a − b ) % p = ( a % p − b % p + p ) % p (a-b)\%p=(a\%p-b\%p+p)\%p (ab)%p=(a%pb%p+p)%p
( a ∗ b ) % p = ( a % p ∗ b % p ) % p (a*b)\%p=(a\%p*b\%p)\%p (ab)%p=(a%pb%p)%p

b b b p p p互质, a b % p = a % p ∗ b ϕ ( p ) − 1 % p \frac{a}{b}\%p=a\%p*b^{\phi(p)-1}\%p ba%p=a%pbϕ(p)1%p
b ϕ ( p ) − 1 b^{\phi(p)-1} bϕ(p)1被称作 b b b的乘法逆元。也可以通过扩展欧几里得算法算出乘法逆元。

1 1 1~ n n n中与 n n n互质的数的个数叫做欧拉函数。记为 ϕ ( n ) \phi(n) ϕ(n)。当 n n n为质数时, ϕ ( n ) = n − 1 \phi(n)=n-1 ϕ(n)=n1

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;
}

本文地址:https://blog.csdn.net/qq_43450413/article/details/109191141

相关标签: Codeforces