本题总分：\(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” 的数量就是答案

【答案】947293

时间限制: \(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> n; unordered_map mp; for(int i = 1; i > x; mp[x] ++; } for(auto x : mp) { if(x.se >= 2) s1 += x.se - 2; else s2 += x.se; } if(s1 >= s2) cout 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 _; while(_ --) solve(); return _ ^ _; } 数组 #include #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 > a[i]; for(int i = 1; i > b[i]; int i = 1, j = 1; while(i 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 _; 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\) (总分数-节点分数-节点分数)，取最小值

时间限制: \(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\)，熟练的话随便做了，用一个数组统计最优值，有更优的值就更新即可，就不多解释了，可以看看代码

时间限制: \(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\) 先吧

时间限制: \(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\)。

【解释】

  不会做啊，痛苦！！！

时间限制: \(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\)。

【解释】

  也不会做啊，痛苦！！！