【传智杯】排排队、小卡与质数 2、1024 程序员节发橙子题解

🍎 博客主页：🌙@披星戴月的贾维斯
🍎 欢迎关注：👍点赞🍃收藏🔥留言
🍇系列专栏：🌙 蓝桥杯
🌙请不要相信胜利就像山坡上的蒲公英一样唾手可得，但是请相信，世界上总有一些美好值得我们全力以赴，哪怕粉身碎骨！🌙
🍉一起加油，去追寻、去成为更好的自己！

提示：以下是本篇文章正文内容，下面案例可供参考

---

    这次我们继续和大家分享一些传智杯题解，多刷题对我们来说是一件非常重要的事，坚持下去会有很多收获！

🍎1、# [传智杯 #4 决赛] 排排队

题目描述

cyq 在 tsyz 担任了体育老师，负责排队一事。

在 tsyz 中，每个人都有一个身高 $a_i$，并且只有相邻的两个人可以交换位置。cyq 带领的队伍有 $n$ 个人,他现在要给大家排队形。

给定一个长度为 $n$ 的序列 $b$，一个队形被认为美观，当且仅当对于所有的 $i=1,2,3,\dots n$，$a_i=b_i$。cyq 想知道，他能否让大家的队形变得美观，并且交换相邻两个人的次数不超过 $n^2$ 次。这个问题把 $cyq$ 难住了，请你帮他来解决这个问题，如果存在合法的交换方案，输出 YES，并给出一组方案；否则，输出 NO。

输入格式

本题单测试点内有多组测试数据。

第一行是一个整数 $T$，表示数据组数，对于每组数据：
第一行是一个整数，表示队伍的长度 $n$。
第二行有 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个人的身高 $a_i$。
第三行有 $n$ 个整数，第 $i$ 个整数表示美观队形里第 $i$ 个人的身高 $b_i$。

输出格式

对每组数据依次分别输出答案。

对于每组数据，若存在一种方案，则在第一行输出一个 YES，否则输出一个 NO。

如果输出 YES，下面则输出若干行每行两个整数 $i,j$，表示第 $i$ 个同学和第 $j$ 个同学交换位置，显然 $|i-j|=1$。在交换完成后，你还需要输出一行 0 0 表示你的操作结束了，请注意数组的下标从 1 开始编号至 $n$。

如果输出 NO，则接下来什么都不需要输出。

请特别注意，对于每组数据，你的操作次数不能超过 $n^2$（不包括 0 0 一行），否则将得到 WA(Wrong Answer) 的结果。

样例 #1

样例输入 #1

3
4
1 2 2 3
3 2 2 1
3
1 2 3
1 2 4
1
1
1

样例输出 #1

YES
4 3
2 3
1 2
3 2
3 4
0 0
NO
YES
0 0

提示

数据规模与约定

对于全部的测试点，保证 $1\le T\le 10$，$1\le n\le 10^3$，$1\le a_i,b_i\le 10^9$，且各个测试点 $n$ 之和不超过 $1000$，即 $\sum n\le 10^3$。

提示

• 请注意大量的输出输出对程序效率造成的影响，不要频繁刷新缓冲区。例如，对于使用 std::cout 的 C++ 选手，请使用 '\n' 而不是 std::endl 来换行；对于 java 选手，请选择高效率的输出方式，如使用 PrintWriter；python 选手可以正常的使用 print 而无需考虑效率问题。
• 请按照输出格式的要求输出您的答案，如果格式不符合要求，返回的评测信息将可能是 TLE、RE、WA、UKE 等任何结果。

C++ 语言的高效输出样例

#include <iostream>
int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);for (int i = 1; i <= 5; ++i) {std::cout << i << '\n'; // 注意这里不能使用 std::endl}
}

Java 语言的高效输出样例

import java.io.PrintWriter;public class Main {public static void main(String[] args) {PrintWriter ot = new PrintWriter(System.out);for (int i = 1; i <= 5; ++i) {ot.println(i);}ot.flush(); // 请务必保证在程序结束时运行本条语句，否则在缓冲区的内容无法输出}
}

分析题意：

我们先看题目，发现该题的输出不仅要我们判断队形是否“美观”，而且如果，美观，我们还要输出交换的过程，就是这个输出交换过程会让人比较头疼，但是结合题目的意思，我们每次只能交换相邻的两个数，这个不就对上了我们的冒泡排序了吗，然后我们把每次交换的位置输出即可，然后如果是判断队形是否美观，我们可以用另外两个对照数组，排序后，如果是美观，就输出YES，否则NO，因为冒泡排序复杂度最差是n方，不用考虑题目的限制 n <1000，等等。
C++代码示例：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 +10;
int t;
int a[N], b[N], c[N], d[N];void solve()
{int n;bool flag = false;cin >> n;for(int i = 1; i <= n; i++){cin >> a[i];c[i] = a[i];// c数组是a的对照数组}for(int i = 1; i <= n; i++){cin >> b[i];d[i] = b[i];}sort(c + 1, c + 1 + n);sort(d + 1, d + 1 + n);for(int i = 1; i <= n; i++){if(c[i] != d[i]){cout << "NO" << '\n';flag = true;break;}}if(!flag){cout << "YES\n";for(int i = 1; i <= n; i++){if(a[i] != b[i]){for(int j = i; j <= n; j++)if(a[j] == b[i]){for(int k = j; k > i; k--){swap(a[k], a[k - 1]);cout << k << " " << k - 1 << '\n';}break;}}}cout << "0 0\n";}
}
int main ()
{ios::sync_with_stdio(0);cin.tie(0);cin >> t;while(t --){solve();}return 0;
}

---

🍎2、# [传智杯 #4 初赛] 小卡与质数 2

题目背景

小卡迷上了质数！

题目描述

小卡最近迷上了质数，所以他想把任何一个数都转化为质数！

小卡有 $T$ 次询问，每次给你一个数字 $x$，问有多少个比 $x$ 小的非负整数 $y$，使得 $x\oplus y$ 是质数，其中 $\oplus$ 表示按位异或。

输入格式

第一行一个正整数 $T(1\le T\le 10^5)$，表示有 $T$ 组询问。

接下来 $T$ 行，每行一个正整数 $x(1\le x\le 10^6)$。

输出格式

对于每组询问，输出一行一个整数，表示答案。

样例 #1

样例输入 #1

9
5
6
7
8
9
10
100
1000
10000

样例输出 #1

2
4
4
2
2
4
22
163
1132

分析题意：

我们通过审题不难发现这题是考我们筛质数和位运算的，但是看这道题的数据量1e5次询问，所以会很卡时间复杂度，筛质数的复杂度是nlogn，刚好能过，如果是n*n的双重循环判断有几个符合，那就会超时，所以这道题难度还是比较大的，一起来看看代码是怎么实现的吧。

#include<bits/stdc++.h>
using namespace std;const int N = 2e6 + 10;
int t;
int primes[N], cat[26];
bool st[N];
int n, cnt;
void get_primes(int n)
{for(int i = 2; i <= n; i++){if(!st[i]) primes[++cnt] = i;//把每个数的倍数删掉for(int j =1; j <= cnt &&i*primes[j] <= n; j++){st[primes[j] * i] = true;if(i % primes[j] == 0) break;}}for(int i = 1; i <= cnt; i++)for(int j = 25; j >= 1; j--)if(primes[i]&(1 << (j - 1))){cat[j]++;break;}
}
void solve()
{int x;int ans = 0;cin >> x;for(int i = 25; i >= 1; i--)if(x&(1<<(i - 1)))ans += cat[i];cout << ans << endl;}
int main ()
{get_primes(N);cin >> t;while(t --){solve();}return 0;
}

---

🍎3、# [传智杯 #2 初赛] 1024 程序员节发橙子

题目描述

每年的 1024 程序员节日，黑马程序员都会举办大型的庆祝活动。今年的程序员节也不例外，每个班级的同学都发了橙子。

班级里有 $n$ 名同学从前到后排成一排，且已经得知了这些同学的成绩，其中第 $i$ 名同学的成绩是 $a_i$。班主任想根据同学们上个阶段的考试成绩来评定发橙子的数量。为了激励成绩优秀同学，发橙子时需要满足如下要求：

• 相邻同学中成绩好的同学的橙子必须更多。若相邻的同学成绩一样，则它们分到的数量必须平等。
• 每个同学至少分配一个橙子

由于预算有限，班主任希望在符合要求的情况下发出尽可能少的橙子。请问，至少需要准备多少橙子呢？

输入格式

第一行是一个整数 $n$，表示学生数量。

接下来一行有 $n$ 个整数，第 $i$ 个整数 $a_i$，表示第 $i$ 个同学的成绩。

输出格式

输出答案，也就是需要最少准备多少个橙子。

样例 #1

样例输入 #1

5
3 4 5 4 3

样例输出 #1

9

提示

样例 1 解释

每位同学拿到的橙子的数量分别是 $1,2,3,2,1$，所以至少需要准备 $9$ 个。

数据规模与约定

对于全部的测试点，保证 $1\le n\le 10^6$，$0\le a_i\le 10^9$。

分析题意：

这道题是让我们按照一个规则分发橘子，但是-相邻同学中成绩好的同学的橙子必须更多。若相邻的同学成绩一样，则它们分到的数量必须平等和 每个同学至少分配一个橙子这两个条件可能会相互冲突（一些情况下），所以当我们要找出，分发的橘子的最少数，一种理想的情况是成绩是排好序的从小到大或者从大到小，这样我们发橙子和统计就会比较简单，用这个思路再推广，我们可以求一遍正的递增序列的橙子数，再求递减序列的橙子数，有冲突就选大的那个，即可求出答案。
C++代码示例

#include<bits/stdc++.h>
using namespace std;const int N = 1e6 + 10;
typedef long long ll;
int a[N], t[N]; //a组存成绩，t组存橘子数
int n, k;
ll ans = 0;
int main ()
{cin >> n;for(int i = 1; i <= n; i++) cin >> a[i], t[i] = 1;//求正递增子序列for(int i = 2; i <= n; i++){if(a[i - 1] < a[i]) t[i] = t[i - 1] + 1;if(a[i - 1] == a[i]) t[i] = t[i - 1];}//求反不降子序列for(int i = n; i >= 2; i --){if(a[i] < a[i - 1]) t[i - 1] = max(t[i - 1], t[i] + 1);if(a[i - 1] == a[i]) t[i - 1] = t[i];}for(int i = 1; i <= n; i++) ans += t[i];cout << ans << endl;return 0;
}

---

🍎总结

    这次和大家分享了传智杯的几题普及/普及+难度的题，希望大家读后能有所收获！