2024年信奥赛C++提高组csp-s初赛真题及答案解析（阅读程序第3题）

2024年信奥赛C++提高组csp-s初赛真题及答案解析（阅读程序第3题）

第 3 题

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 1000000 + 5;
const int P1 = 998244353, P2 = 1000000007;
const int B1 = 2, B2 = 31;
const int K1 = 0, K2 = 13;

typedef long long ll;

int n;
bool p[maxn];
int p1[maxn], p2[maxn];

struct H {
int h1, h2, l;
H(bool b = false) {
h1 = b + K1;
h2 = b + K2;
l = 1;
}

H operator + (const H & h) const {
H hh;
hh.l = l + h.l;
hh.h1 = (1ll * h1 * p1[h.l] + h.h1) % P1;
hh.h2 = (1ll * h2 * p2[h.l] + h.h2) % P2;
return hh;
}

bool operator == (const H & h) const {
return l == h.l && h1 == h.h1 && h2 == h.h2;
}

bool operator < (const H & h) const {
if (l != h.l) return l < h.l;
else if (h1 != h.h1) return h1 < h.h1;
else return h2 < h.h2;
}
} h[maxn];

void init() {
memset(p, 1, sizeof(p));
p[0] = p[1] = false;
p1[0] = p2[0] = 1;
for (int i = 1; i <= n; ++i) {
p1[i] = (1ll * B1 * p1[i–1]) % P1;
p2[i] = (1ll * B2 * p2[i–1]) % P2;
if (!p[i]) continue;
for (int j = 2 * i; j <= n; j += i) {
p[j] = false;
}
}
}

int solve() {
for (int i = n; i; —i) {
h[i] = H(p[i]);
if (2 * i + 1 <= n) {
h[i] = h[2 * i] + h[i] + h[2 * i + 1];
} else if (2 * i <= n) {
h[i] = h[2 * i] + h[i];
}
}

cout << h[1].h1 << endl;
sort(h + 1, h + n + 1);
int m = unique(h + 1, h + n + 1) – (h + 1);
return m;
}

int main() {
cin >> n;
init();
cout << solve() << endl;
}

判断题

选择题

题解

程序分析

该程序实现了一个基于双哈希的子树哈希计算算法，主要步骤包括：

判断题解析

选择题解析

专栏推荐：信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新） https://blog.csdn.net/weixin_66461496/category_13125089.html

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<"########## 一站式掌握信奥赛知识! ##########";
cout<<"############# 冲刺信奥赛拿奖! #############";
cout<<"###### 课程购买后永久学习，不受限制! ######";
return 0;
}

1、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划： https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL： https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践： https://blog.csdn.net/weixin_66461496/category_13113932.html

2、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

3、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）： https://blog.csdn.net/weixin_66461496/category_13117178.html

4、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<"跟着王老师一起学习信奥赛C++";
cout<<" 成就更好的自己！ ";
cout<<" csp信奥赛一等奖属于你! ";
return 0;
}