网站制作 牛商网 岳阳 公司,中国最新消息,山东省城乡建设厅网站,网站建设中页面#x1f34e; 博客主页#xff1a;#x1f319;披星戴月的贾维斯 #x1f34e; 欢迎关注#xff1a;#x1f44d;点赞#x1f343;收藏#x1f525;留言 #x1f347;系列专栏#xff1a;#x1f319; 蓝桥杯 #x1f319;请不要相信胜利就像山坡上的蒲公英一样唾手… 博客主页披星戴月的贾维斯 欢迎关注点赞收藏留言 系列专栏 蓝桥杯 请不要相信胜利就像山坡上的蒲公英一样唾手可得但是请相信世界上总有一些美好值得我们全力以赴哪怕粉身碎骨 一起加油去追寻、去成为更好的自己 文章目录 1、# [传智杯 #4 决赛] 排排队题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示数据规模与约定提示C 语言的高效输出样例Java 语言的高效输出样例分析题意 2、# [传智杯 #4 初赛] 小卡与质数 2题目背景题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1分析题意 3、# [传智杯 #2 初赛] 1024 程序员节发橙子题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示样例 1 解释数据规模与约定 分析题意 总结 提示以下是本篇文章正文内容下面案例可供参考 这次我们继续和大家分享一些传智杯题解多刷题对我们来说是一件非常重要的事坚持下去会有很多收获
1、# [传智杯 #4 决赛] 排排队
题目描述
cyq 在 tsyz 担任了体育老师负责排队一事。
在 tsyz 中每个人都有一个身高 a i a_{i} ai并且只有相邻的两个人可以交换位置。cyq 带领的队伍有 n n n 个人,他现在要给大家排队形。
给定一个长度为 n n n 的序列 b b b一个队形被认为美观当且仅当对于所有的 i 1 , 2 , 3 , … n i 1, 2, 3, \dots n i1,2,3,…n a i b i a_{i} b_{i} aibi。cyq 想知道他能否让大家的队形变得美观并且交换相邻两个人的次数不超过 n 2 n^2 n2 次。这个问题把 c y q cyq cyq 难住了请你帮他来解决这个问题如果存在合法的交换方案输出 YES并给出一组方案否则输出 NO。
输入格式
本题单测试点内有多组测试数据。
第一行是一个整数 T T T表示数据组数对于每组数据 第一行是一个整数表示队伍的长度 n n n。 第二行有 n n n 个整数第 i i i 个整数表示第 i i i 个人的身高 a i a_i ai。 第三行有 n n n 个整数第 i i i 个整数表示美观队形里第 i i i 个人的身高 b i b_i bi。
输出格式
对每组数据依次分别输出答案。
对于每组数据若存在一种方案则在第一行输出一个 YES否则输出一个 NO。
如果输出 YES下面则输出若干行每行两个整数 i , j i,j i,j表示第 i i i 个同学和第 j j j 个同学交换位置显然 ∣ i − j ∣ 1 |i-j|1 ∣i−j∣1。在交换完成后你还需要输出一行 0 0 表示你的操作结束了请注意数组的下标从 1 开始编号至 n n n。
如果输出 NO则接下来什么都不需要输出。
请特别注意对于每组数据你的操作次数不能超过 n 2 n^2 n2不包括 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 ≤ T ≤ 10 1\leq T \leq 10 1≤T≤10 1 ≤ n ≤ 1 0 3 1\leq n \leq 10^3 1≤n≤103 1 ≤ a i , b i ≤ 1 0 9 1\leq a_{i},b_{i}\leq 10^9 1≤ai,bi≤109且各个测试点 n n n 之和不超过 1000 1000 1000即 ∑ n ≤ 1 0 3 \sum n\leq 10^3 ∑n≤103。
提示
请注意大量的输出输出对程序效率造成的影响不要频繁刷新缓冲区。例如对于使用 std::cout 的 C 选手请使用 \n 而不是 std::endl 来换行对于 java 选手请选择高效率的输出方式如使用 PrintWriterpython 选手可以正常的使用 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代码示例
#includebits/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 T T 次询问每次给你一个数字 x x x问有多少个比 x x x 小的非负整数 y y y使得 x ⊕ y x\oplus y x⊕y 是质数其中 ⊕ \oplus ⊕ 表示按位异或。
输入格式
第一行一个正整数 T ( 1 ≤ T ≤ 1 0 5 ) T(1\le T\le10^5) T(1≤T≤105)表示有 T T T 组询问。
接下来 T T T 行每行一个正整数 x ( 1 ≤ x ≤ 1 0 6 ) x(1\le x\le 10^6) x(1≤x≤106)。
输出格式
对于每组询问输出一行一个整数表示答案。
样例 #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的双重循环判断有几个符合那就会超时所以这道题难度还是比较大的一起来看看代码是怎么实现的吧。
#includebits/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 n n 名同学从前到后排成一排且已经得知了这些同学的成绩其中第 i i i 名同学的成绩是 a i a_i ai。班主任想根据同学们上个阶段的考试成绩来评定发橙子的数量。为了激励成绩优秀同学发橙子时需要满足如下要求
相邻同学中成绩好的同学的橙子必须更多。若相邻的同学成绩一样则它们分到的数量必须平等。每个同学至少分配一个橙子
由于预算有限班主任希望在符合要求的情况下发出尽可能少的橙子。请问至少需要准备多少橙子呢
输入格式
第一行是一个整数 n n n表示学生数量。
接下来一行有 n n n 个整数第 i i i 个整数 a i a_i ai表示第 i i i 个同学的成绩。
输出格式
输出答案也就是需要最少准备多少个橙子。
样例 #1
样例输入 #1
5
3 4 5 4 3样例输出 #1
9提示
样例 1 解释
每位同学拿到的橙子的数量分别是 1 , 2 , 3 , 2 , 1 1,2,3,2,1 1,2,3,2,1所以至少需要准备 9 9 9 个。
数据规模与约定
对于全部的测试点保证 1 ≤ n ≤ 1 0 6 1 \leq n \leq 10^6 1≤n≤106 0 ≤ a i ≤ 1 0 9 0 \leq a_i \leq 10^9 0≤ai≤109。
分析题意
这道题是让我们按照一个规则分发橘子但是-相邻同学中成绩好的同学的橙子必须更多。若相邻的同学成绩一样则它们分到的数量必须平等和 每个同学至少分配一个橙子这两个条件可能会相互冲突一些情况下所以当我们要找出分发的橘子的最少数一种理想的情况是成绩是排好序的从小到大或者从大到小这样我们发橙子和统计就会比较简单用这个思路再推广我们可以求一遍正的递增序列的橙子数再求递减序列的橙子数有冲突就选大的那个即可求出答案。 C代码示例
#includebits/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;
}总结 这次和大家分享了传智杯的几题普及/普及难度的题希望大家读后能有所收获 文章转载自： http://www.morning.jjnql.cn.gov.cn.jjnql.cn http://www.morning.twdwy.cn.gov.cn.twdwy.cn http://www.morning.bwmq.cn.gov.cn.bwmq.cn http://www.morning.jbpdk.cn.gov.cn.jbpdk.cn http://www.morning.cyysq.cn.gov.cn.cyysq.cn http://www.morning.huihuangwh.cn.gov.cn.huihuangwh.cn http://www.morning.jmlgk.cn.gov.cn.jmlgk.cn http://www.morning.ngznq.cn.gov.cn.ngznq.cn http://www.morning.zcxjg.cn.gov.cn.zcxjg.cn http://www.morning.plwfx.cn.gov.cn.plwfx.cn http://www.morning.knpmj.cn.gov.cn.knpmj.cn http://www.morning.xdjwh.cn.gov.cn.xdjwh.cn http://www.morning.wklhn.cn.gov.cn.wklhn.cn http://www.morning.xnqwk.cn.gov.cn.xnqwk.cn http://www.morning.rcbdn.cn.gov.cn.rcbdn.cn http://www.morning.qxxj.cn.gov.cn.qxxj.cn http://www.morning.ybgyz.cn.gov.cn.ybgyz.cn http://www.morning.ttnfc.cn.gov.cn.ttnfc.cn http://www.morning.sbkb.cn.gov.cn.sbkb.cn http://www.morning.swzpx.cn.gov.cn.swzpx.cn http://www.morning.tckxl.cn.gov.cn.tckxl.cn http://www.morning.qmrsf.cn.gov.cn.qmrsf.cn http://www.morning.qxbsq.cn.gov.cn.qxbsq.cn http://www.morning.rfxg.cn.gov.cn.rfxg.cn http://www.morning.jqtb.cn.gov.cn.jqtb.cn http://www.morning.kabaifu.com.gov.cn.kabaifu.com http://www.morning.hsxkq.cn.gov.cn.hsxkq.cn http://www.morning.ckntb.cn.gov.cn.ckntb.cn http://www.morning.kzslk.cn.gov.cn.kzslk.cn http://www.morning.kyflr.cn.gov.cn.kyflr.cn http://www.morning.pndhh.cn.gov.cn.pndhh.cn http://www.morning.tbbxn.cn.gov.cn.tbbxn.cn http://www.morning.ngznq.cn.gov.cn.ngznq.cn http://www.morning.jzfrl.cn.gov.cn.jzfrl.cn http://www.morning.czzpm.cn.gov.cn.czzpm.cn http://www.morning.skmpj.cn.gov.cn.skmpj.cn http://www.morning.rfldz.cn.gov.cn.rfldz.cn http://www.morning.scrnt.cn.gov.cn.scrnt.cn http://www.morning.wpmqq.cn.gov.cn.wpmqq.cn http://www.morning.tbksk.cn.gov.cn.tbksk.cn http://www.morning.xqndf.cn.gov.cn.xqndf.cn http://www.morning.xrksf.cn.gov.cn.xrksf.cn http://www.morning.rfqk.cn.gov.cn.rfqk.cn http://www.morning.kfwqd.cn.gov.cn.kfwqd.cn http://www.morning.plqkz.cn.gov.cn.plqkz.cn http://www.morning.rfwkn.cn.gov.cn.rfwkn.cn http://www.morning.wnkjb.cn.gov.cn.wnkjb.cn http://www.morning.xdlwm.cn.gov.cn.xdlwm.cn http://www.morning.crqpl.cn.gov.cn.crqpl.cn http://www.morning.kgnrh.cn.gov.cn.kgnrh.cn http://www.morning.lkpzx.cn.gov.cn.lkpzx.cn http://www.morning.zwfgh.cn.gov.cn.zwfgh.cn http://www.morning.nwjzc.cn.gov.cn.nwjzc.cn http://www.morning.xfmzk.cn.gov.cn.xfmzk.cn http://www.morning.zrbpx.cn.gov.cn.zrbpx.cn http://www.morning.tpwrm.cn.gov.cn.tpwrm.cn http://www.morning.bmgdl.cn.gov.cn.bmgdl.cn http://www.morning.lywpd.cn.gov.cn.lywpd.cn http://www.morning.mnbcj.cn.gov.cn.mnbcj.cn http://www.morning.rlxg.cn.gov.cn.rlxg.cn http://www.morning.nlqgb.cn.gov.cn.nlqgb.cn http://www.morning.zqfz.cn.gov.cn.zqfz.cn http://www.morning.rjmb.cn.gov.cn.rjmb.cn http://www.morning.xpzkr.cn.gov.cn.xpzkr.cn http://www.morning.wjhpg.cn.gov.cn.wjhpg.cn http://www.morning.jjhng.cn.gov.cn.jjhng.cn http://www.morning.pwmpn.cn.gov.cn.pwmpn.cn http://www.morning.tkztx.cn.gov.cn.tkztx.cn http://www.morning.hqrr.cn.gov.cn.hqrr.cn http://www.morning.nppml.cn.gov.cn.nppml.cn http://www.morning.rgpbk.cn.gov.cn.rgpbk.cn http://www.morning.snnwx.cn.gov.cn.snnwx.cn http://www.morning.cpkcq.cn.gov.cn.cpkcq.cn http://www.morning.qgcfb.cn.gov.cn.qgcfb.cn http://www.morning.vuref.cn.gov.cn.vuref.cn http://www.morning.tngdn.cn.gov.cn.tngdn.cn http://www.morning.jypqx.cn.gov.cn.jypqx.cn http://www.morning.qzzmc.cn.gov.cn.qzzmc.cn http://www.morning.msbpb.cn.gov.cn.msbpb.cn http://www.morning.qdxtj.cn.gov.cn.qdxtj.cn
