试题 A: 子 2023
本题总分：\(5\) 分
【问题描述】
小蓝在黑板上连续写下从 \(1\) 到 \(2023\) 之间所有的整数，得到了一个数字序列：
\(S = 12345678910111213 . . . 20222023\)。
小蓝想知道 \(S\) 中有多少种子序列恰好等于 \(2023\)？
提示，以下是 \(3\) 种满足条件的子序列（用中括号标识出的数字是子序列包含的数字）：
\(1[2]34567891[0]111[2]1[3]14151617181920212223…\)
\(1[2]34567891[0]111[2]131415161718192021222[3]…\)
\(1[2]34567891[0]111213141516171819[2]021222[3]…\)
注意以下是不满足条件的子序列，虽然包含了 \(2、0、2、3\) 四个数字，但是顺序不对：
\(1[2]345678910111[2]131415161718192[0]21222[3]…\)
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分
【解释】
当遇到字符 ‘2’ 的时候字符串 “2” 的数量+1，字符串 “202” 的数量加上字符串 “20” 的数量
当遇到字符 ‘0’ 的时候字符串 “20” 的数量加上字符串 “2” 的数量
当遇到字符 ‘3’ 的时候字符串 “2023” 的数量加上字符串 “202” 的数量
最后 “2023” 的数量就是答案
点击查看代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
int n, ans, cnt;
bool st[N];
void solve()
{
string s;
for(int i = 1; i <= 2023; i ++)
s += to_string(i);
vector<int> f(5, 0);
for(int i = 0; i < s.size(); i ++)
{
if(s[i] == '2')
{
f[0] ++;
f[2] += f[1];
}
else if(s[i] == '0')
f[1] += f[0];
else if(s[i] == '3')
f[3] += f[2];
}
cout << f[3] << '\n';
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
// init();
int _ = 1;
// cin >> _;
while(_ --)
solve();
return _ ^ _;
}
//5484660609
【答案】5484660609
试题 B: 双子数
本题总分：\(5\) 分
【问题描述】
若一个正整数 \(x\) 可以被表示为 \(p2 × q2\)，其中 \(p、q\) 为质数且 \(p , q\)，则 \(x\) 是一个 “双子数”。请计算区间 \([2333, 23333333333333]\) 内有多少个 “双子数”？
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
【解释】
先用欧拉筛求出 \(10\) 的 \(7\) 次方内的素数，求出之后暴力枚举两个数即可
点击查看代码
#include <bits/stdc++.h>
#define int __int128
using namespace std;
const int N = 1e7 + 10;
int n, ans, cnt;
int prime[N];
bool st[N];
void init()
{
for(int i = 2; i < N; i ++)
{
if(!st[i]) prime[cnt ++] = i;
for(int j = 0; j < cnt&&prime[j] * i < N; j ++)
{
st[prime[j] * i] = true;
if(i % prime[j] == 0) break;
}
}
}
void solve()
{
int ans = 0;
for(int i = 0; i < cnt; i ++)
for(int j = i + 1; j < cnt; j ++)
{
int a = prime[i], b = prime[j];
if(a * a * b * b > 23333333333333) break;
if(a * a * b * b < 2333) continue;
ans ++;
}
cout << (long long)ans << '\n';
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
init();
int _ = 1;
// cin >> _;
while(_ --)
solve();
return _ ^ _;
}
//947293
【答案】947293
试题 C: 班级活动
时间限制: \(1.0s\) 内存限制: \(256.0MB\) 本题总分：\(10\) 分
【问题描述】
小明的老师准备组织一次班级活动。班上一共有 \(n\) 名（\(n\) 为偶数）同学，老师想把所有的同学进行分组，每两名同学一组。为了公平，老师给每名同学随机分配了一个 \(n\) 以内的正整数作为 \(id\)，第 \(i\) 名同学的 \(id\) 为 \(a_i\)。
老师希望通过更改若干名同学的 \(id\) 使得对于任意一名同学 \(i\)，有且仅有另一名同学 \(j\) 的 \(id\) 与其相同\(（a_i = a_j）\)。请问老师最少需要更改多少名同学的 \(id\)？
【输入格式】
输入共 \(2\) 行。
第一行为一个正整数 \(n\)。
第二行为 \(n\) 个由空格隔开的整数 \(a_1, a_2, …, a_n\)。
【输出格式】
输出共 \(1\) 行，一个整数。
【样例输入】
4
1 2 2 3
【样例输出】
1
【样例说明】
仅需要把 \(a_1\) 改为 \(3\) 或者把 \(a_3\) 改为 \(1\) 即可。
【评测用例规模与约定】
对于 \(20\%\) 的数据，保证 \(n ≤ 10^3\)。
对于 \(100\%\) 的数据，保证 \(n ≤ 10^5\)。
【解释】
把题目捋清楚就很容易实现了
1、先用 \(map\) 存下每个数字的数量
2、数量大于等于 \(2\) 的那么就减去二，剩下的一定要转换，存到 \(sum1\) 中，小于二的另外统计到sum2中
3、\(sum1>=sum2\)，那么答案是\(sum1，sum1<sum2\)，那么答案是 \(sum1+(sum2-sum1)/2\) ;
点击查看代码
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)
#define int long long
#define fi first
#define se second
using namespace std;
const int N = 2e5 + 10;
int a[N], n, s1, s2;
void solve()
{
cin >> n;
unordered_map<int, int> mp;
for(int i = 1; i <= n; i ++)
{
int x;
cin >> x;
mp[x] ++;
}
for(auto x : mp)
{
if(x.se >= 2)
s1 += x.se - 2;
else s2 += x.se;
}
if(s1 >= s2) cout << s1 << '\n';
else cout << s1 + (s2 - s1) / 2 << '\n';
}
signed main()
{
IOS;
int _ = 1;
// cin >> _;
while(_ --)
solve();
return _ ^ _;
}
试题 D: 合并数列
时间限制: \(1.0s\) 内存限制: \(256.0MB\) 本题总分：\(10\) 分
【问题描述】
小明发现有很多方案可以把一个很大的正整数拆成若干正整数的和。他采取了其中两种方案，分别将他们列为两个数组 \(\{a_1, a_2, …, a_n\}\) 和 \(\{b_1, b_2, …, b_m\}\)。两个数组的和相同。
定义一次合并操作可以将某数组内相邻的两个数合并为一个新数，新数的值是原来两个数的和。小明想通过若干次合并操作将两个数组变成一模一样，即 \(n = m\) 且对于任意下标 \(i\) 满足 \(a_i = b_i\)。请计算至少需要多少次合并操作可以完成小明的目标。
【输入格式】
输入共 \(3\) 行。
第一行为两个正整数 \(n, m\)。
第二行为 \(n\) 个由空格隔开的整数 \(a_1, a_2, …, a_n\)。
第三行为 \(m\) 个由空格隔开的整数 \(b_1, b_2, …, b_m\)。
【输出格式】
输出共 \(1\) 行，一个整数。
【样例输入】
4 3
1 2 3 4
1 5 4
【样例输出】
1
【样例说明】
只需要将 \(a_2\) 和 \(a_3\) 合并，数组 \(a\) 变为 \(\{1, 5, 4\}\)，即和 \(b\) 相同。
【评测用例规模与约定】
对于 \(20\%\) 的数据，保证 \(n, m ≤ 10^3\)。
对于 \(100\%\) 的数据，保证 \(n, m ≤ 10^5，0 < a_i, b_i ≤ 10^5\)。
【解释】
其实就是一个贪心题
1、对比两个数组最左边的数字，哪边小就合并哪一边
2、如果两个数组最左边的数字相等就出队
双端队列
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)
#define int long long
#define fi first
#define se second
#define fr front
#define pb push_back
#define pf pop_front
using namespace std;
const int N = 2e5 + 10;
int n, m, ans;
void solve()
{
deque<int> q1, q2;
cin >> n >> m;
for(int i = 0; i < n; i ++)
{
int x;
cin >> x;
q1.pb(x);
}
for(int i = 0; i < m; i ++)
{
int x;
cin >> x;
q2.pb(x);
}
while(!q1.empty())
{
if(q1.fr() == q2.fr())
{
q1.pf();
q2.pf();
}
else if(q1.fr() > q1.fr())
{
q2[1] += q2[0];
q2.pf();
ans ++;
}
else
{
q1[1] += q1[0];
q1.pf();
ans ++;
}
}
cout << ans << '\n';
}
signed main()
{
IOS;
int _ = 1;
// cin >> _;
while(_ --)
solve();
return _ ^ _;
}
数组
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)
#define int long long
#define fi first
#define se second
#define fr front
#define pb push_back
#define pf pop_front
using namespace std;
const int N = 2e5 + 10;
int n, m, ans, sa, sb;
int a[N], b[N];
void solve()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++)
cin >> a[i];
for(int i = 1; i <= m; i ++)
cin >> b[i];
int i = 1, j = 1;
while(i <= n + 1&&j <= m + 1)
{
if(sa == sb) sa += a[i ++], sb += b[j ++];
else if(sa < sb) ans ++, sa += a[i ++];
else ans ++, sb += b[j ++];
}
cout << ans << '\n';
}
signed main()
{
IOS;
int _ = 1;
// cin >> _;
while(_ --)
solve();
return _ ^ _;
}
试题 E: 数三角
时间限制: \(1.0s\) 内存限制: \(256.0MB\) 本题总分：\(15\) 分
【问题描述】
小明在二维坐标系中放置了 \(n\) 个点，他想在其中选出一个包含三个点的子集，这三个点能组成三角形。然而这样的方案太多了，他决定只选择那些可以组成等腰三角形的方案。请帮他计算出一共有多少种选法可以组成等腰三角形？
【输入格式】
输入共 \(n + 1\) 行。
第一行为一个正整数 \(n\)。
后面 \(n\) 行，每行两个整数 \(x_i, y_i\) 表示第 \(i\) 个点的坐标。
【输出格式】
输出共 \(1\) 行，一个整数。
【样例输入】
5
1 4
1 0
2 1
1 2
0 1
【样例输出】
4
【样例说明】
一共有 \(4\) 种选法：\(\{2, 3, 4\}、\{3, 4, 5\}、\{4, 5, 2\}、\{5, 2, 3\}\)。
【评测用例规模与约定】
对于 \(20\%\) 的数据，保证 \(n ≤ 200\)。
对于 \(100\%\) 的数据，保证 \(n ≤ 2000，0 ≤ x_i, y_i ≤ 10^9\)。
【解释】
样例应该输出5，比赛时勘误了，{1, 3, 5}也是可以的
1、枚举每个点，计算其它点与该点的距离，距离相同的两条边可以构成等腰三角型
2、注意要考虑共线问题
3、其实这个方法不是很行，等边三角形会被重复计算，正解是什么不是很清楚
点击查看代码
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)
#define int long long
#define fi first
#define se second
#define fr front
#define pb push_back
#define pf pop_front
using namespace std;
const int N = 3010, M = 2e6 + 10;
int n, m, ans;
int x[N], y[N];
int st[N][N];
int s[M];
int dis(int i, int j)
{
int a = x[i] - x[j], b = y[i] - y[j];
return a * a + b * b;
}
void solve()
{
cin >> n;
for(int i = 0; i < n; i ++)
{
cin >> x[i] >> y[i];
st[x[i] + 1500][y[i] + 1500] = 1;
}
int ans = 0;
for(int i = 0; i < n; i ++)
{
for(int j = 0; j < n; j ++)
{
if(i == j) continue;
ans += s[dis(i, j)];
s[dis(i, j)] ++;
if(st[2 * x[i] - x[j] + 1500][2 * y[i] - y[j] + 1500]) m ++;
}
for(int j = 0; j < n; j ++)
{
if(i == j) continue;
s[dis(i, j)] = 0;
}
}
cout << ans - m / 2 << '\n';
}
signed main()
{
IOS;
int _ = 1;
// cin >> _;
while(_ --)
solve();
return _ ^ _;
}
试题 F: 删边问题
时间限制: \(1.0s\) 内存限制: \(256.0MB\) 本题总分：\(15\) 分
【问题描述】
给定一个包含 \(N\) 个结点 \(M\) 条边的无向图 \(G\)，结点编号 \(1 . . . N\)。其中每个结点都有一个点权 \(W_i\)。
你可以从 \(M\) 条边中任选恰好一条边删除，如果剩下的图恰好包含 \(2\) 个连通分量，就称这是一种合法的删除方案。
对于一种合法的删除方案，我们假设 \(2\) 个连通分量包含的点的权值之和分别为 \(X\) 和 \(Y\)，请你找出一种使得 \(X\) 与 \(Y\) 的差值最小的方案。输出 \(X\) 与 \(Y\) 的差值。
【输入格式】
第一行包含两个整数 \(N\) 和 \(M\)。
第二行包含 \(N\) 个整数，\(W_1, W_2, . . . W_N\)。
以下 \(M\) 行每行包含 \(2\) 个整数 \(U\) 和 \(V\)，代表结点 \(U\) 和 \(V\) 之间有一条边。
【输出格式】
一个整数代表最小的差值。如果不存在合法的删除方案，输出 \(−1\)。
【样例输入】
4 4
10 20 30 40
1 2
2 1
2 3
4 3
【样例输出】
20
【样例说明】
由于 \(1\) 和 \(2\) 之间实际有 \(2\) 条边，所以合法的删除方案有 \(2\) 种，分别是删除 \((2, 3)\) 之间的边和删除 \((3, 4)\) 之间的边。
删除 \((2, 3)\) 之间的边，剩下的图包含 \(2\) 个连通分量：\(\{1, 2\}\) 和 \(\{3, 4\}\)，点权和分别是 \(30、70\)，差为 \(40\)。
删除 \((3, 4)\) 之间的边，剩下的图包含 \(2\) 个连通分量：\(\{1, 2, 3\}\) 和 \(\{4\}\)，点权和分别是 \(60、40\)，差为 \(20\)。
【评测用例规模与约定】
对于 \(20\%\) 的数据，\(1 ≤ N, M ≤ 10000\)。
对于另外 \(20\%\) 的数据，每个结点的度数不超过 \(2\)。
对于 \(100\%\) 的数据，\(1 ≤ N, M ≤ 200000，0 ≤ W_i ≤ 10^9，1 ≤ U, V ≤ N\)。
【解释】
会缩点的话这题就不成问题了！但是我不会提供点思路
1、用Tarjan算法将环缩成一个点，缩点后将会的到一棵树
2、统计树每个节点的字节点和( \(dfs\) 一遍就可以实现)
3、枚举每个点，答案就是每个点的 \(abs\) (总分数-节点分数-节点分数)，取最小值
试题 G: AB 路线
时间限制: \(1.0s\) 内存限制: \(256.0MB\) 本题总分：\(20\) 分
【问题描述】
有一个由 \(N × M\) 个方格组成的迷宫，每个方格写有一个字母 \(A\) 或者 \(B\)。小蓝站在迷宫左上角的方格，目标是走到右下角的方格。他每一步可以移动到上下左右相邻的方格去。
由于特殊的原因，小蓝的路线必须先走 \(K\) 个 \(A\) 格子、再走 \(K\) 个 \(B\) 格子、再走 \(K\) 个 \(A\) 格子、再走 \(K\) 个 \(B\) 格子……如此反复交替。
请你计算小蓝最少需要走多少步，才能到达右下角方格？
注意路线经过的格子数不必一定是 \(K\) 的倍数，即最后一段 \(A\) 或 \(B\) 的格子可以不满 \(K\) 个。起点保证是 \(A\) 格子。
例如 \(K = 3\) 时，以下 \(3\) 种路线是合法的：
\(AA\)
\(AAAB\)
\(AAABBBAAABBB\)
以下 \(3\) 种路线不合法：
\(ABABAB\)
\(ABBBAAABBB\)
\(AAABBBBBBAAA\)
【输入格式】
第一行包含三个整数 \(N、M\) 和 \(K\)。
以下 \(N\) 行，每行包含 \(M\) 个字符（\(A\) 或 \(B\)），代表格子类型。
【输出格式】
一个整数，代表最少步数。如果无法到达右下角，输出 \(−1\)。
【样例输入】
4 4 2
AAAB
ABAB
BBAB
BAAA
【样例输出】
8
【样例说明】
每一步方向如下：下右下右上右下下；路线序列：\(AABBAABBA\)。
【评测用例规模与约定】
对于 \(20\%\) 的数据，\(1 ≤ N, M ≤ 4\)。
对于另 \(20\%\) 的数据，\(K = 1\)。
对于 \(100\%\) 的数据，\(1 ≤ N, M ≤ 1000，1 ≤ K ≤ 10\)。
【解释】
经典的 \(Dijkstra\)，熟练的话随便做了，用一个数组统计最优值，有更优的值就更新即可，就不多解释了，可以看看代码
试题 H: 抓娃娃
时间限制: \(1.0s\) 内存限制: \(256.0MB\) 本题总分：\(20\) 分
【问题描述】
小明拿了 \(n\) 条线段练习抓娃娃。他将所有线段铺在数轴上，第 \(i\) 条线段的左端点在 \(l_i\)，右端点在 \(r_i\)。小明用 \(m\) 个区间去框这些线段，第 \(i\) 个区间的范围是 \([L_i, R_i]\)。如果一个线段有 至少一半 的长度被包含在某个区间内，则将其视为被这个区间框住。请计算出每个区间框住了多少个线段？
【输入格式】
输入共 \(n + m + 1\) 行。
第一行为两个正整数 \(n, m\)。
后面 \(n\) 行，每行两个整数 \(l_i,r_i\)。
后面 \(m\) 行，每行两个整数 \(L_i, R_i\)。
【输出格式】
输出共 \(m\) 行，每行一个整数。
【样例输入】
3 2
1 2
1 3
3 4
1 4
2 4
【样例输出】
3
2
【评测用例规模与约定】
对于 \(20\%\) 的数据，保证 \(n, m ≤ 10^3\)。
对于 \(100\%\) 的数据，保证 \(n, m ≤ 10^5，l_i < r_i，0 < l_i,r_i, L_i, R_i ≤ 10^6，max\{r_i −l_i\} ≤ min\{R_i − L_i\}\)
【解释】
题目勘误了，样例最后一行应该是 \(2 4\)，而不是\(2 3\)
1、其实题目保证了\(max\{r_i,−l_i\} ≤ min\{R_i − L_i\}\)，那么如果占了区间一半的话，那么肯定包含了区间中点，我们就用这个原理做一个前缀和就好了
2、因为涉及了小数，给每个数字都乘以 \(2\) 先吧
点击查看代码
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)
#define int long long
#define fi first
#define se second
#define fr front
#define pb push_back
#define pf pop_front
using namespace std;
const int N = 2e6 + 10;
int n, m, ans;
int s[N << 1];
void solve()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++)
{
int l, r;
cin >> l >> r;
s[l + r] ++;
}
for(int i = 1; i < N * 2; i ++)
s[i] += s[i - 1];
while(m --)
{
int l, r;
cin >> l >> r;
cout << s[2 * r] - s[2 * l - 1] << '\n';
}
}
signed main()
{
IOS;
int _ = 1;
// cin >> _;
while(_ --)
solve();
return _ ^ _;
}
试题 I: 拼数字
时间限制: \(1.0s\) 内存限制: \(256.0MB\) 本题总分：\(25\) 分
【问题描述】
小蓝要用 \(N\) 个数字 \(2\) 和 \(M\) 个数字 \(3\) 拼出一个 \(N + M\) 位的整数。请你计算小蓝能拼出的最大的 \(2023\) 的倍数是多少？
【输入格式】
两个整数 \(N\) 和 \(M\)。
【输出格式】
一个 \(N + M\) 位的整数，代表答案。如果拼不出 \(2023\) 的倍数，输出 \(−1\)。
【样例输入】
2 8
【样例输出】
2233333333
【评测用例规模与约定】
对于 \(20\%\) 的数据，\(1 ≤ N, M ≤ 12\)。
对于 \(40\%\) 的数据，\(1 ≤ N, M ≤ 100\)。
对于 \(60\%\) 的数据，\(1 ≤ N, M ≤ 10000\)。
对于 \(100\%\) 的数据，\(1 ≤ N, M ≤ 1000000\)。
【解释】
不会做啊，痛苦！！！
试题 J: 逃跑
时间限制: \(1.0s\) 内存限制: \(256.0MB\) 本题总分：\(25\) 分
【问题描述】
小明所在星系有 \(n\) 颗星球，编号为 \(1\) 到 \(n\)。这些星球通过 \(n − 1\) 条无向边连成一棵树。根结点为编号为 \(1\) 的星球。
为了在星际战争到来时逃到其他星系，小明在根结点设置了逃离用的传送门。每个星球的人只需要一直往父结点星球移动就可以抵达根结点。为了方便各个星球的人去往根结点，小明将其中 \(m\) 个星球设置为了跳板星球。在从某个星球去往根结点的路径上，当一个人经过任意星球（包括起点星球）时，他可以尝试直接跳跃到 其前往根结点路径上的除当前星球以外的第一个跳板星球，其时间花费和走到父结点星球的时间花费相同，都是 \(1\) 单位时间。
然而，因为技术问题，向跳板星球的跳跃并不一定成功，每一次跳跃都有 \(p\) 的概率失败，并转而跳跃到当前星球的父结点星球（相当于直接走到父结点星球）；同时此跳板星球失效，将不再视为跳板星球。
为了衡量移动效率，小明想知道，如果一个人在这 \(n\) 颗星球中随机选择一颗出发前往根结点，其花费的最短时间的期望是多少单位时间？
【输入格式】
输入共 \(n + 1\) 行，第一行为两个正整数 \(n、m\) 和一个浮点数 \(p\)。
后面 \(n − 1\) 行，每行两个正整数 \(x_i, y_i\) 表示第 \(i\) 条边的两个端点。
最后一行，共 \(m\) 个正整数表示所有跳板星球的编号。
【输出格式】
一行，一个浮点数，表示答案（请保留两位小数）。
【样例输入】
4 1 0.2
1 2
2 3
3 4
2
【样例输出】
1.30
【样例说明】
从 \(1\) 号星球出发的时间花费为 \(0\)；
从 \(2\) 号星球出发的时间花费为 \(1\)；
从 \(3\) 号星球出发的时间花费为 \(2\)；
从 \(4\) 号星球出发的时间花费为 \(0.8 × 2 + 0.2 × 3 = 2.2\)。
所以期望时间为 \((0+1+2+2.2)/4 = 1.3\)。
【评测用例规模与约定】
对于 \(30\%\) 的数据，保证 \(1 ≤ n ≤ 2000\)。
对于 \(100\%\) 的数据，保证 \(1 ≤ n ≤ 10^6，1 ≤ m ≤ n，0 < p < 1\)。
【解释】
也不会做啊，痛苦！！！