AtCoder Regular Contest 113

2021 年 2 月 21 日
筆記
比賽

比賽地址

A（暴力）

題目：
給出$K$，求出滿足$A\times B\times C\le K$的$(A,B,C)$對數

解析：
將C移動到等式右邊，得到$A\times B\le\frac{K}{C}$，對於$t=\lfloor\frac{K}{C}\rfloor$,統計$t$向下整除$1\sim t$的和即為結果

#include<bits/stdc++.h>
using namespace std;
/*===========================================*/

int main() {
	int k;
	LL result = 0;
	scanf("%d", &k);
	for (int i = 1; i <= k; ++i) {
		int end = k / i;
		for (int j = 1; j <= end; ++j)
			result += k / i / j;
	}
	printf("%lld", result);
}

B（思維）

題目鏈接
⭐⭐

題目：
求出$A^{B^C}$的個位數字

解析：
不難得到以下循環

1 1 1 1 1 …（1）
2 4 8 6 2 …（4）
3 9 7 1 3 …（4）
4 6 4 6 4 …（2）
5 5 5 5 5 …（1）
6 6 6 6 6 …（1）
7 9 3 1 7 …（4）
8 4 2 6 8 …（4）
9 1 9 1 9 …（2）
0 0 0 0 0 …（1）

對於循環長度為1，則直接輸出本身
循環長度為2，則考慮$B$奇偶性（奇數的冪還是奇數，偶數的冪還是偶數）
循環長度為4分$B$的奇偶討論
- 如果$B$為奇數且模4為1，則他的冪模4還是1，否則模值在3 1循環
- 如果為偶數則一定含有2，如果能被4整除則冪數模4一定是0，否則看2（因子）的出現次數，即冪數是否大於1，比1大模值為0，比一小模值1

#include<bits/stdc++.h>
using namespace std;
/*===========================================*/

map<int, map<int, int>> m;
int main() {
	int a, b, c;
	scanf("%d%d%d", &a, &b, &c);
	m[4][0] = 4, m[4][1] = 6;
	m[9][0] = 9, m[9][1] = 1;
	m[2][0] = 2, m[2][1] = 4, m[2][2] = 8, m[2][3] = 6;
	m[3][0] = 3, m[3][1] = 9, m[3][2] = 7, m[3][3] = 1;
	m[8][0] = 8, m[8][1] = 4, m[8][2] = 2, m[8][3] = 6;
	m[7][0] = 7, m[7][1] = 9, m[7][2] = 3, m[7][3] = 1;
	a %= 10;
	if (a == 0 || a == 1 || a == 5 || a == 6)
		printf("%d", a);
	else if (a == 4 || a == 9)
		printf("%d", m[a][b % 2 == 0]);
	else {
		if (b & 1) {
			if (b % 4 == 1)
				printf("%d", m[a][0]);
			else {
				if (c & 1)
					printf("%d", m[a][2]);
				else
					printf("%d", m[a][0]);
			}
		}
		else {
			if (b % 4 == 0)
				printf("%d", m[a][3]);
			else {
				if (c >= 2)
					printf("%d", m[a][3]);
				else
					printf("%d", m[a][1]);
			}
		}
	}
}

C（貪心）

題目鏈接
⭐⭐

題目：
給出一個字元串，以及操作：如果$s_i=s_{i+1}\ne s_{i+2}$，則將$s_{i+2}$替換成$s_i$，詢問最多操作次數

解析：
那如果又兩個連續的字元$c$，則後序字元肯定能都變成$c$，那麼可以考慮從後向前進行替換，這樣可以保證最大次數
如此則需要從前向後統計第一次出現的某字元$c$與下一個和他不一樣的連續字元$c’$之間存在多少個$c$（這些字元不可以被操作需要從答案中減去），後序字元都可以被替換，因為操作時從後向前，後序字元均會被替換成$c’$

#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
/*===========================================*/

const int maxn = 2e5 + 5;
char str[maxn];

int main() {
	scanf("%s", str);
	int len = strlen(str);
	char last = 1;
	int lpos = -1;
	LL ret = 0;
	for (int i = 0; i <= len; ++i) {
		if (str[i] == str[i + 1] && str[i] != last)
		{
			if (~lpos)
				ret += 1LL * len - lpos;
			lpos = i;
			last = str[i];
		}
		if (str[i] == last)
			--ret;
	}
	printf("%lld", ret + 1);
}

D（排列組合+快速冪）

題目鏈接
⭐⭐⭐

題目：
給出$n,m,k$，規定$A_i$為第$i$行最小的數字，$B_i$為第$i$行最大的數字，則有多少種序列的可能性（答案取模998244353）

解析：

要保證$A$中的最大值一定得小於等於$B$中最小值，因為假設A中最大值對應位置為$(i,j)$，則在第$j$列的最大值要大於等於$i$不可能小於$i
所以可以枚舉$i$，即$pow(i,n)\times pow(k+1-i,m)$，但是這樣的情況下對於左邊（或者右邊）可能出現包含的情況，所以一定要保證$i$在序列中至少出現1次（或者保證$j$）

\[\sum_{i=1}^k(i^n-(i-1)^n)*(k-i+1)^m \ \%mod
\]

注意：
考慮$n==1||m==1$的特殊情況

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 998244353;
LL pw(LL n, int x) {
	LL ret = 1;
	LL t = n;
	while (x) {
		if (x & 1) ret = ret * t % mod;
		t = t * t % mod;
		x >>= 1;
	}
	return ret;
}

int main() {
	int n, m, k;
	scanf("%d%d%d", &n, &m, &k);
	if (n == 1)
		printf("%lld", pw(k, m));
	else if (m == 1)
		printf("%lld", pw(k, n));
	else {
		LL ret = 0;
		for (int i = 1; i <= k; ++i)
			ret = ((pw(i, n) - pw(i - 1, n) + mod) % mod * pw(k + 1 - i, m) % mod + ret) % mod;
		printf("%lld", ret);
	}
}

Tags: 比賽