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

目录
写在前面&总结：
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;

}

T4

「THP3考前信心赛」D 博物之志

改自 CF1422C

只拿了部分分就不粘码了嘻嘻

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

写在前面&总结：

T1

T2

T3

T4

「THP3考前信心赛」解题报告的相关教程结束。

相关推荐

洛谷 P2048 [NOI2010]超级钢琴解题报告

考前必备fa宝——对拍

NOIp2016 Day1&Day2 解题报告

noip2011提高组day1+day2解题报告

[ [Ynoi2013] 无力回天 NOI2017 ] 解题报告

cf1774f解题报告

[[SCOI2008]城堡] 解题报告

[[SCOI2008]城堡] 解题报告

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

写在前面&总结：

T1

T2

T3

T4

「THP3考前信心赛」解题报告的相关教程结束。

相关推荐

洛谷 P2048 [NOI2010]超级钢琴 解题报告

考前必备fa宝——对拍

NOIp2016 Day1&Day2 解题报告

noip2011提高组day1+day2解题报告

[ [Ynoi2013] 无力回天 NOI2017 ] 解题报告

cf1774f解题报告

[[SCOI2008]城堡] 解题报告

[[SCOI2008]城堡] 解题报告

洛谷 P2048 [NOI2010]超级钢琴解题报告