AtCoder Regular Contest 113

比赛地址

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

	}

}

巴特西

AtCoder Regular Contest 113

A（暴力）

B（思维）

C（贪心）

D（排列组合+快速幂）

最新文章

热门文章