正文

算法入门经典-第五章例题5-7丑数

Tina  Tina  2022-09-16  678

关键词：

#include<iostream>
#include<vector>
#include<queue>
#include<set>
using namespace std;
typedef long long ll;
const int coeff= {2,3,5};
int main()
{
    //一些常见的优先队列，STL提供了更为简单的定义方法
    //对于任意丑数x 则 2x,3x,5x也是丑数，判断一个丑数是否生成过 
    //每次取出最小的丑数，生成3个新的丑数 
    priority_queue<LL,vector<LL>,greater<LL> > pq;
    set<LL> s;
    pq.push(1);
    s.insert(1);
    for(int i=1;; i++)
    {
        LL x=pq.top();
        pq.pop();//序列 
        if(i==1500)
        {
            cout<<"The 1500th ugly number is"<<x<<".
";
            break;
        }
        for(int j=0; j<3; j++)
        {
            LL x2=x*coeff[j];
            if(!s.count(x2))

            {
                s.insert(x2);
                pq.push(x1);
            }
        }
        return 0;
    }

算法入门经典-第五章例题5-5集合栈计算机

TheSetStackComputerTimelimit:3.000seconds 题目是这样的：有一个专门为了集合运算而设计的“集合栈”计算机。该机器有一个初始为空的栈，并且支持以下操作：PUSH：空集“{}”入栈DUP：把当前栈顶元素复... 查看详情

算法入门经典-第五章例题5-6团体队列

题目背景队列和优先级队列是大多数计算机科学家都知道的数据结构。但是团队队列却不被人熟知，尽管在生活中经常出现。比如，午餐时间的食堂门口的队列就是一个团队队列。在一个团队队列中，每个元素属于一个团队。如... 查看详情

算法入门经典　第五章

例题5-4　反片语输入一些单词（以“#”为结束标志），找出所有满足如下条件的单词：该单词不能通过字母的重排，得到输入文本中的另一个单词。在判断是否满足条件是不分大小写，但是在输出时应保留输入时的大小写... 查看详情

《算法竞赛入门经典》例题5.4.1(代码片段)

题目：现代数学的著名证明之一是GeorgCantor证明了有理数是可枚举的。他是用下面这一张表来证明这一命题的：第一项是1/1，第二项是是1/2，第三项是2/1，第四项是3/1，第五项是2/2，……。输入n，... 查看详情

第五章例题

1#include<iostream>2#include<sstream>3#include<string>4#include<set>56usingnamespacestd;78set<string>dict;910intmain()11{12strings,buf;1314while(cin>>s)15{16f 查看详情

dfs与dp算法之关系与经典入门例题(代码片段)

...具体代码dp思路解题思路具体代码声明本文不介绍dfs、dp算法的基础思路，有想了解的可以自己找资源学习。本文适合于刚刚接触dfs和dp算法的人，发现两种算法间的内在联系。本人算法之路走之甚短，如果理解出现问题欢迎大家... 查看详情

有关int范围的例题（算法竞赛入门经典）

对于任意大于1的自然数n，若n为奇数，则将n变为3n＋1，否则变为n的一半。经过若干次这样的变换，一定会使n变为1。例如，3→10→5→16→8→4→2→1。输入n，输出变换的次数。n≤109。样例输入：3样例输出：71#include<iostream>2#... 查看详情

算法入门经典-第七章例题7-1除法

除法输入正整数n，按从小到大的顺序输出所有形如abcde/fghij=n的表达式，其中a~j恰好为数字0~9的一个排列，2<=n<=79.样例输入：62样例输出：79546/01238=6294736/01528=62#include<stdio.h>#include<string.h>intmain(){intn;//x/y=nx用abcde表示... 查看详情

算法竞赛入门经典例题3-4回文串

输入一个字符串。求出当中最长的回文子串。子串的含义是：在原串中连续出现的字符串片段。回文的含义是：正着看和倒着看同样。如abba和yyxyy。在推断时，应该忽略全部标点符号和空格。且忽略大写和小写。但输出应保持原... 查看详情

算法入门经典第六章例题6-5移动盒子

例题6-5移动盒子（BoxesinaLine,UVa127675）问题给定一行盒子，从左到右编号依次为1，2，...，n.可以执行以下命令：1XY 把盒子X移动到Y的左边（如果已经在左边，忽略此命令）2XY 把盒子X移动到Y右边（如果X已经在Y的右边，忽... 查看详情

算法入门经典-第七章例题7-2八皇后问题

原本利用回溯思想解决的经典八皇后问题，其实也是可以用递归解决的~八皇后的递归解决思路：从第一行开始，依次判断0~8列的哪一列可以放置Queen，这样就确定了该行的Queen的位置，然后行数递增，继而递归实现下一行的判断... 查看详情

算法入门经典-第七章例题7-2-2可重集的排列

可重：如果问题变成输入数组p，并按字典序输出数组A个元素的所有全排列，则需要修改代码集的全排列//RujiaLiu#include<cstdio>#include<algorithm>usingnamespacestd;intP[100],A[100];//输出数组P中元素的全排列。数组P中可能有... 查看详情

算法入门经典第六章例题6-15给任务排序

假设有n个变量，还有m个二元组（u，v），分别表示变量u小于v。那么，所有变量从小到大排列起来应该是什么样子呢？例如，有4个变量a,b,c,d,若已知a<b,c<b,d<c,则这4个变量的排序可能是a<d<c<b。尽管还有其他可能... 查看详情

算法入门经典-第四章例题4-3救济金发放

救济金的问题抽象出来就是几个人围成一个圈坐，给每一个人编号，一个人从1开始，一个人从n开始，从一开始的点到k时，出列一人，n逆时针点人，点到m出列一人。如果我们出列用删除操作，则大大的降低了效率，我们将删除... 查看详情

算法入门经典第六章例题6-14abbott的复仇(abbott'srevenge)bfs算法实现

SampleInput31N33 11WLNR* 12WLFNRER* 13NLER* 21SLWRNF* 22SLWFELF* 23SFREL* 0SampleOutput(3,1)(2,1)(1,1)(1,2)(2,2)(2,3)(1,3)(1,2)(1,1)(2,1) (2,2)(1,2)(1,3)( 查看详情

算法动态规划dp自学笔记入门：基本知识+经典例题(代码片段)

...述动态规划，是利用历史记录来避免重复计算的一种算法，是求解决策过程最优化的过程。一般用一维数组/二维数组来保存历史记录。一般动态规划有三个步骤：定义数组元素的含义，一般求什么就定义成什么找... 查看详情

算法入门经典-第七章例题7-4-1拓展n皇后问题回溯法

...决很多的问题，如：N皇后问题和迷宫问题。一.概念回溯算法实际类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现不满足条件的时候，就回溯返回，尝试别的路径。百度解释：回溯法（探索与回溯法）... 查看详情

第五章序列：字符串列表和元组

5.1　序列类型操作符seq[ind]：获得下标为ind的元素seq[ind1：ind2]：获得下标ind1到ind2间的元素集合，不能获得seq[ind2]的值seq*expr：序列重复expr次seq1+seq2：连接序列1和序列2objinseq：判断obj元素是否包含在序列中objnotinseq：判断obj元素... 查看详情

正文