「THP3考前信心赛」解题报告

<!–

(adsbygoogle=window.adsbygoogle||[]).push({})

–>

(adsbygoogle=window.adsbygoogle||[]).push({})

<!–
–>

写在前面&总结：
T1
T2
T3
T4

写在前面&总结：

\\(LuckyBlock\\) 良心出题人！暴力分给了 \\(120pts\\)

\\(T1\\) 貌似是个结论题，最后知道怎么算了，用前缀和搞了两下，写挂了就很草，最后只能靠暴力拿了 \\(30pts\\)

\\(T2\\) 显然数论题，但是我不会化简/kk，不过用前缀和优化了一下暴力 \\(40pts\\);

\\(T3\\) 依旧暴力，\\(O(n^2)\\) 可拿 \\(40pts\\)

\\(T4\\) 部分分 \\(5pts\\) \\(+\\) \\(lps\\) 随机输出 \\(\’7\’\\) \\(5pts\\);

不会打暴力的 \\(OIer\\) 不是好 \\(OIer\\) ，不打暴力的都是**（没错说的就是CSP2020上的我

感觉 \\(LuckyBlock\\) 这次考察的芝士点比较详细，先粘个题解网址咕着，以后再补

T1

T158717 「THP3考前信心赛」A 未来宇宙

改自 CF1422C

发现可以当做取出一段序列，把剩下的拼接起来

在拼接过程中发现有许多部分是重复计算的，可以用后缀和和开个 \\(10^i\\) 的数组预处理

算了我也说不清楚直接放代码吧嘻嘻

/*

Work by: Suzt_ilymics

Knowledge: ??

Time: O(??)

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

using namespace std;

const int MAXN = 2e6+6;

const int INF = 1;

const int mod = 1e9+7;

LL hsum[MAXN], jc[MAXN];

char ch[MAXN];

LL ans;

int read(){

	int s = 0, w = 1;

	char ch = getchar();

	while(ch < \'0\' || ch > \'9\') { if(ch == \'-\') w = -1; ch = getchar(); }

	while(ch >= \'0\' && ch <= \'9\') s = (s << 1) + (s << 3) + ch - \'0\' , ch = getchar();

	return s * w;

}

LL quick(LL x, LL p, LL mod){

	LL res = 1;

	for( ; p; p >>= 1){

		if(p & 1) res = res * x % mod;

		x = x * x % mod;

	}

	return res;

}

signed main()

{

	cin>>ch;

	LL len = strlen(ch);

	int cnt = 0;

	cnt = 1; jc[0] = 1;

	for(int i = 1; i <= len; ++i){

		jc[i] = jc[i - 1] * 10 % mod;

	}

	cnt = 0;

	for(int i = len - 1; i >= 0; --i){//求后缀数

		cnt = (cnt + (ch[i] - \'0\') * jc[len - 1 - i] % mod) % mod;

		hsum[i] = cnt;

//		cout<<hsum[i]<<\' \';

	}

	LL val = 0, sum = 0;

	for(int i = 0; i < len; ++i){

		ans += sum * jc[len - 1 - i] % mod;

		ans += i * hsum[i] % mod;

		ans %= mod;

		val = (10 * val % mod + ch[i] - \'0\') % mod;

		sum = (sum + val) % mod;

	}

	printf(\"%lld\", ans % mod);

	return 0;

}

暴力部分核心代码：

	for(int l = 0; l < len; ++l){

		LL cnt = 0;

		for(int r = l; r < len; ++r){

			for(int i = 0; i < len; ++i){

				if(i < l || i > r){

					cnt = (cnt * 10 % mod + ch[i] - \'0\') % mod;

				}

			}

			ans = (ans + cnt) % mod;

		}

	}

T2

「THP3考前信心赛」B 空海澄澈

\\(40pts\\) 暴力：

求 \\(gcd(i, n)\\) 是有多次求的，可以用前缀和预处理 \\(2000\\) 个点然后 \\(O(n)\\) 出结果

/*

Work by: Suzt_ilymics

Knowledge: ??

Time: O(??)

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int MAXN = 1e6+6;;

const int INF = 1;

const int mod = 998244353;

int T, l, r;

int gcd[2010][2010];

int sum[2020];

int read(){

	int s = 0, w = 1;

	char ch = getchar();

	while(ch < \'0\' || ch > \'9\') { if(ch == \'-\') w = -1; ch = getchar(); }

	while(ch >= \'0\' && ch <= \'9\') s = (s << 1) + (s << 3) + ch - \'0\' , ch = getchar();

	return s * w;

}

int Gcd(int x, int y){

	return x % y == 0 ? y : Gcd(y, x % y);

}

void init(){

	for(int i = 1; i <= 2000; ++i){

		for(int j = 1; j <= i; ++j){

//			a[i][j] = Gcd(j, i);

			sum[i] = (sum[i] + Gcd(j, i)) % mod ;

		}

	}

}

int main()

{

	init();

	T = read();

	while(T--){

		l = read(), r = read();

		int ans = 0;

		for(int i = l; i <= r; ++i){

			ans = (ans + sum[i]) % mod;

		}

		printf(\"%d\\n\", ans);

	}

	return 0;

}

\\(100pts\\) 正解

考虑化一下 \\(f\\) 。

\\[f(n) = \\sum_{i = 1}^{n} \\gcd (i, n)
\\]

考虑对于每一个 \\(1 \\sim n\\) 的值，能作为多少数对的 \\(gcd\\) ，于是有：

\\[f(n) = \\sum_{i = 1}^{n}d\\sum_{i = 1}^{n}[gcd(i, n) = d]
\\]

发现 \\(gcd(i, n) = d\\) 的必要条件是 \\(d \\mid n\\) ，原式可以改为：

\\[f(n) = \\sum_{d \\mid n} d \\sum_{i = 1}^{n}[gcd(i, n) = d]
\\]

考虑什么样的 \\(i\\) ，满足 \\(\\gcd(i, n) = d\\) ，显然当且仅当 \\(i = kd(k \\in \\mathbb{N^*})\\) ，且 \\(\\gcd(k, \\frac{n}{d}) = 1\\) 是满足条件。为保证 \\(i \\le n\\) ，有 \\(k \\le \\left\\lfloor\\frac{n}{d}\\right\\rfloor\\) 。

于是考虑把 \\(d\\) 提出来，改为枚举上述的 \\(k\\) ，原式等于：

\\[f(n) = \\sum_{d|n} d \\sum_{k=1}^{\\left\\lfloor\\frac{n}{d}\\right\\rfloor}\\left[\\gcd\\left(k,\\frac{n}{d}\\right)=1\\right]
\\]

考虑后面一个 \\(\\sum\\) 的实际意义，表示 \\(1 \\sim \\frac{n}{d}\\) 中与 \\(\\frac{n}{d}\\) 互质的个数，符合欧拉函数的定义，于是原式等于：

\\[f(n) = \\sum_{d|n} d \\cdot \\varphi\\left(\\frac{n}{d}\\right)
\\]

线性筛预处理 \\(\\varphi\\) 后，有埃氏筛即可筛出 \\(1 \\sim 10^{6}\\) 的所有的 \\(f\\) 。

做个前缀和即可回答区间询问

复杂度 \\(O(n\\ \\log \\ n + m)\\)

（Solution来自LuckyBlock的题解）

/*

Work by: Suzt_ilymics

Knowledge: ??

Time: O(??)

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int MAXN = 1e6+5;

const int kMax = 1e6;

const int INF = 1;

const int mod = 998244353;

int p_cnt, p[MAXN], phi[MAXN];

int f[MAXN], sum[MAXN];

bool vis[MAXN];

int read(){

	int s = 0, w = 1;

	char ch = getchar();

	while(ch < \'0\' || ch > \'9\') { if(ch == \'-\') w = -1; ch = getchar(); }

	while(ch >= \'0\' && ch <= \'9\') s = (s << 1) + (s << 3) + ch - \'0\' , ch = getchar();

	return s * w;

}

void init(){

	phi[1] = 1;

	for(int i = 2; i <= kMax; ++i){

		if(!vis[i]){

			p[++p_cnt] = i;

			phi[i] = i - 1;

		}

		for(int j = 1; j <= p_cnt && i * p[j] <= kMax; ++j){

			vis[i * p[j]] = true;

			if(i % p[j] == 0){

				phi[i * p[j]] = phi[i] * p[j];

				break;

			}

			phi[i * p[j]] = phi[i] * (p[j] - 1);

		}

	}

	for(int i = 1; i <= kMax; ++i){

		for(int j = i; j <= kMax; j += i){

			f[j] = (f[j] + 1ll * phi[i] * (j / i) % mod) % mod;

		}

	}

	for(int i = 1; i <= kMax; ++i){

		sum[i] = (sum[i - 1] + f[i]) % mod;

	}

}

int main()

{

	init();

	int m = read();

	while(m--){

		int l = read(), r = read();

		printf(\"%d\\n\", (sum[r] - sum[l - 1] + mod) % mod);

	}

}

T3

T158720 「THP3考前信心赛」C 旧约酒馆

\\(40pts\\) 暴力：

暴力更改区间起点暴力求所有情况的最大值即可

/*

Work by: Suzt_ilymics

Knowledge: ??

Time: O(??)

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int MAXN = 1;

const int INF = 1;

const int mod = 1;

int n;

char a[50100], b[50010];

int read(){

	int s = 0, w = 1;

	char ch = getchar();

	while(ch < \'0\' || ch > \'9\') { if(ch == \'-\') w = -1; ch = getchar(); }

	while(ch >= \'0\' && ch <= \'9\') s = (s << 1) + (s << 3) + ch - \'0\' , ch = getchar();

	return s * w;

}

int main()

{

	n = read();

	cin>>a>>b;

	int ans = -1;

	for(int i = 0; i < n; ++i){

		int cnt = 0;

		for(int j = 0; j < n; ++j){

			int x = i + j;

			x = (x >= n ? x - n : x);

			if(a[j] == \'1\' && b[x] == \'1\'){

				cnt++;

			}

		}

		ans = max(ans, cnt);

	}

	printf(\"%d\", ans);

	return 0;

}

\\(100pts\\) 正解：

利用 bitset 容器，详细介绍请看 Oi-Wiki

/*

Work by: Suzt_ilymics

Knowledge: ??

Time: O(??)

*/

#include<iostream>

#include<cstdio>

#include<cctype>

#include<cstring>

#include<string>

#include<algorithm>

#include<bitset>

using namespace std;

const int MAXN = 1e5+10;

const int INF = 1;

const int mod = 1;

int n, ans;

char s1[MAXN], s2[MAXN];

bitset <MAXN> a, b, c;

int read(){

	int s = 0, w = 1;

	char ch = getchar();

	while(ch < \'0\' || ch > \'9\') { if(ch == \'-\') w = -1; ch = getchar(); }

	while(ch >= \'0\' && ch <= \'9\') s = (s << 1) + (s << 3) + ch - \'0\' , ch = getchar();

	return s * w;

}

void max(int &x, int y){if(x < y) x = y; }

int main()

{

	n = read();

	scanf(\"%s\", s1 + 1);

	scanf(\"%s\", s2 + 1);

	for(int i = 1; i <= n; ++i){

		a[i] = (s1[i] == \'1\');

		b[i] = (s2[i] == \'1\');

	}

	for(int i = 1; i <= n; ++i){

		b[n + 1] = b[1];

		b >>= 1;

		max(ans, (a & b).count());

	}

	printf(\"%d\", ans);

	return 0;

}