关键词：
题目描述
panda是个数学怪人，他非常喜欢研究跟别人相反的事情。最近他正在研究筛法，众所周知，对一个范围内的整数，经过筛法处理以后，剩下的全部都是质数，不过panda对这些不感兴趣，他只对被筛掉的数感兴趣，他觉得在这些被筛掉的数中一定隐藏着重要的宇宙秘密，只是人们还没有发现罢了。
panda还觉得如果只是单纯地从小到大筛的话，还不足够发现其中的奥秘，于是他决定对至多只包含某些质因数的数进行研究（比如说至多只包含质因数2，3的数有2,3,4,6,8,9,……），他需要得到这些数中第k小的数（k是panda认为的宇宙系数），请你编个程序，帮助他找到这个数。
输入输出格式
输入格式：
第1行有2个数n,k，n代表质因数的个数，k代表那个宇宙系数（1<=n<=100，1<=k<=100000）
第2行有n个数，代表这n个质因数。（每个均小于1000，且不相同）
输出格式：
仅1行，即至多只包含这n个质因数的数中第k小的数。（这个数不会超过2000000000）
输入输出样例
2 7 3 5
45
说明
样例说明：前6个分别是3，5，9，15，25，27。
分析：一个想法是维护一个优先队列，每次取最小值和所有素数相乘,结果放进优先队列里直到出现k个元素，这样也可以拿到很高的分数，但是不是最好的，对于可以用优先队列做的题，有一个非常常用的方法就是把优先队列转化为普通队列.such as:noip2016蚯蚓，只要想方设法把一个队列变成单调的队列就好了，那么这道题怎么变呢？
先把所有的质数依次放到队列里，一开始是单调的，我们要用优先队列的方式来维护，当一个质数乘了第i个元素后，它下一个乘的一定是第i+1个元素，而且保证结果是单调的。每个质数乘一下后会得到多个质数，找到最小的那个数，插入队列里，在插入之前要先判一下重.
这个判重有点小技巧，我一开始想着一个bool数组，可是太大了开不下，map似乎也不行，其实这个队列是单调的，我们只需要看队尾元素有没有重复就好了......
优先队列---->“单调队列”，神奇的优化.而这个优化的关键，就是我们要如何让它单调，像优先队列一样操作.
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <queue> #include <cmath> #include <map> using namespace std; const int inf = 2000000000; int n,k,prime[110],q[100010],tot,mx; int cnt[110],cc; map <int,int> flag; int main() { scanf("%d%d",&n,&k); for (int i = 1; i <= n; i++) scanf("%d",&prime[i]); q[++tot] = 1; for (int i = 1; i <= n; i++) cnt[i] = 1; while (tot != k + 1) { mx = inf; for (int i = 1; i <= n; i++) { int t = q[cnt[i]] * prime[i]; if (t < mx) { cc = i; mx = t; } } cnt[cc]++; if (mx != q[tot]) q[++tot] = mx; } printf("%d\n",q[k + 1]); return 0; }
洛谷p2530[shoi2001]化工厂装箱员
题目描述118号工厂是世界唯一秘密提炼锎的化工厂，由于提炼锎的难度非常高，技术不是十分完善，所以工厂生产的锎成品可能会有3种不同的纯度，A：100%，B：1%，C：0.01%，为了出售方便，必须把不同纯度的成品分开装箱，装箱... 查看详情
洛谷-p2163[shoi2007]园丁的烦恼(离线二维数点)(代码片段)
题目链接：点击查看题目大意：二维平面坐标系中给出nnn个坐标点，然后是mmm次询问，每次询问需要回答一个闭合矩阵中有多少个点题目分析：想挂树套树来着，但是复杂度有点大。本题不带修且可以离线... 查看详情
题解shoi2001化工厂装箱员
————传送：洛谷P2530这道题目还是挺简单的，状态也容易想到。数据范围非常的小，所以即便是很多维度，复杂度也完全可以接受。定义状态：dp[i][a][b][c]为手上的货物拿到第i个时三种物品分别有a,b,c个所用的最少次数。状... 查看详情
bzoj13821935:[shoi2007]tree园丁的烦恼
1935:[Shoi2007]Tree园丁的烦恼TimeLimit: 15Sec MemoryLimit: 357MBSubmit: 1261 Solved: 578[Submit][Status][Discuss]Description很久很久以前，在遥远的大陆上有一个美丽的国家。统治着这个美丽国家的国王是一个园 查看详情
bzoj1935:[shoi2007]tree园丁的烦恼
1935:[Shoi2007]Tree园丁的烦恼Description很久很久以前，在遥远的大陆上有一个美丽的国家。统治着这个美丽国家的国王是一个园艺爱好者，在他的皇家花园里种植着各种奇花异草。有一天国王漫步在花园里，若有所思，他问一个园丁... 查看详情
bzoj1935[shoi2007]tree园丁的烦恼(代码片段)
(verb|bzoj1935[SHOI2007]Tree园丁的烦恼|)静态询问平面点数(x_i,y_iin[0,10^7],,mleq5 imes10^5)二维偏序，cdq分治可以直接cdq分治，也可以离散化后用BIT做、、注意排序时若(x,y)相同，要将点放在询问前面时间复杂度(O(nlogn))代码cdq分治#include<b... 查看详情
p2163[shoi2007]园丁的烦恼(代码片段)
#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>usingnamespacestd;constintN=3e6+5;constintM=1e7+5;inlineintread()charc=getchar();int 查看详情
[bzoj1935][shoi2007]tree园丁的烦恼_树状数组
Tree园丁的烦恼bzoj-1935Shoi-2007题目大意：给定平面上的$n$个点，$m$次查询矩形点个数。注释：$1len,mle5cdot10^5$。想法：静态二维数点。$OrzWinniechen$，真tm敢写$KD-Tree$，虽然$T$了..正常这种静态的二维数点我们都要请到树状数组。最简... 查看详情
bzoj1935:[shoi2007]tree园丁的烦恼(代码片段)
这题本来是想用二维树状数组水的。然后不会动态开数组，所以顺便补了一发cdq。第一维时间，第二维x，第三维y，（其实我自己的感觉是第一维可以不要的），xy很大so离散化谢谢。询问拆成4个。大家都懂。#include<cstdio>#inc... 查看详情
p2163[shoi2007]园丁的烦恼(二维数点模板题)(代码片段)
P2163[SHOI2007]园丁的烦恼题意：在一个二维平面内有一些点，给你一个左上角和右下角的点，问这个范围内有多少点题解：二维数点模板题我们设F(a,b)表示以(0,0)为左下角，(a,b)为右上角的矩阵内有多少点如图不... 查看详情
bzoj千题计划143：bzoj1935:[shoi2007]tree园丁的烦恼
http://www.lydsy.com/JudgeOnline/problem.php?id=1935 二维偏序问题排序x，离散化树状数组维护y #include<cstdio>#include<iostream>#include<algorithm>#definelowbit(x)x&-xusingnamespacestd;#de 查看详情
bzoj.1935.[shoi2007]tree园丁的烦恼(cdq分治三维偏序)
题目链接矩形查询可以拆成四个点的前缀和查询(树套树显然但是空间不够)每个操作表示为(t,x,y)，t默认有序，对x分治，y用树状数组维护初始赋值需要靠修改操作实现。//119964kb4380ms#include<cstdio>#include<cctype>#include<algori... 查看详情
bzoj1935:[shoi2007]tree园丁的烦恼[树状数组离线离散化]
传送门 刚才我还在郁闷网上怎么没人用$CDQ$分治做突然发现根本没有时间序....#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>usingnamespacestd;constintN=3e6+5;inlin 查看详情
luogup2526_[shoi2001]小狗散步_二分图匹配
luoguP2526_[SHOI2001]小狗散步_二分图匹配题意：Grant喜欢带着他的小狗Pandog散步。Grant以一定的速度沿着固定路线走，该路线可能自交。Pandog喜欢游览沿途的景点，不过会在给定的N个点和主人相遇。小狗和主人同时从(X1，Y1)点出发，... 查看详情
排序工作量之新任务（shoi2001）
排序工作量之新任务（SHOI2001）给出两个整数n和t，求n的全排列中逆序对数为t的个数，和逆序对数为t的字典序最小全排列。首先第一个问题可以用dp解决，\(f[i][j]\)表示前i个数，j个逆序对的序列数，那么\(f[i][j]=f[i-1][j-k]\(k<i)(k... 查看详情
洛谷p1678烦恼的高考志愿(代码片段)
...sp; 洛谷P1678烦恼的高考志愿题目背景计算机竞赛小组的神牛V神终于结束了万恶的高考，然而作为班长的他还不能闲下来，班主任老t给了他一个艰巨的任务：帮同学找出最合... 查看详情
洛谷p4332[shoi2014]三叉神经树题解(代码片段)
一、题目：洛谷原题二、思路：这道题怎么说呢？只能说有点意思，让我第一次见识了LCT怎么应用。首先一个非常明显的性质，就是比如我现在修改了某个叶子结点，记为\\(leaf\\)，那么因此而状态发生改变的点一定是从\\(leaf\\)... 查看详情
洛谷3833shoi2012魔法树
【题解】 树链剖分模板题。。#include<cstdio>#include<algorithm>#include<queue>#defineN500010#definergregister#definels(u<<1)#definers(u<<1|1)#definemid((a[u].l+a[u].r)>>1)#defin 查看详情