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

2024 年 7 月 15 日 15点热度 0人点赞 0条评论

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

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

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

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

题目描述

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

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

给定一个长度为 $n$ 的序列 $b$ ，一个队形被认为美观，当且仅当对于所有的 $\dots n$ ， $a_{i} =b_{i}$ 。cyq 想知道，他能否让大家的队形变得美观，并且交换相邻两个人的次数不超过 $n^2$ 次。这个问题把 $cy q$ 难住了，请你帮他来解决这个问题，如果存在合法的交换方案，输出 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

样例输出 #1

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

提示

数据规模与约定

对于全部的测试点，保证 $1\leq T \leq 10$ ， $1\leq n \leq 10^3$ ， $1\leq a_{i},b_{i}\leq 10^9$ ，且各个测试点 $n$ 之和不超过 $1000$ ，即 $\sum n\leq 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\le10^5)$ ，表示有 $T$ 组询问。

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

输出格式

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

样例 #1

样例输入 #1

样例输出 #1

分析题意：

我们通过审题不难发现这题是考我们筛质数和位运算的，但是看这道题的数据量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

提示

样例 1 解释

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

数据规模与约定

对于全部的测试点，保证 $\leq n \leq 10^6$ ， $\leq a_i \leq 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;
}