gzxcyy-CSDN博客

原创返回连续子序列，使得和最大（变形）

编程珠玑上一道老题：一个数组，找出连续子序列使得和最大。我们可以使用线性扫描的算法来解决，这道题变形之后成为：找出连续子序列，使得和最接近某个数。原来的时间复杂度为线性的方法行不通了，我们可以累加数组，然后排序，求的相邻的差，最接近k的数就是所求。代码如下：int approximate(int * pArry, int len) { int * cum = 0

2014-03-15 21:06:31 1024

原创左旋字符串——编程珠玑和STL所想到的

在看编程珠玑时候有这么一题：将一个长为n的字符串左旋i位，例如abcdefg左旋3位得到：defgabc在书上提到了两种解法，分别如下，习题中有这么一个问题：i和n的最大公约数如何才能被程序用到？一时间没有思路，看看STL是怎么实现的，果然用到了最大公约数。最后就介绍STL中的rotate算法。法一：从a[0]开始，每隔i位，将后面的元素移到前面去，将a[i]移到a[0],a[2*

2014-03-15 21:06:06 967

原创 codeforces好题记录——4D

题目见http://codeforces.com/problemset/problem/4/D这道题是LIS（longgest increasing string）的一个变种版本。对于LIS问题，我倒是很快能写出答案，但是如果加上一些限制条件，写起来就有点难度了。我们常用的做法是简单的dp，时间复杂度是O(n^2)，如果想要达到O(nlogn)，就要在选择最大长度上做一些优化。如下：

2014-03-15 21:05:48 983

原创 codeforces好题记录——3D

题目见http://codeforces.com/problemset/problem/3/D给定一个字符串，里面有'?'和'(', ')'。我们需要替换‘？’为左括号或者右括号，使得整个串的左右括号正好匹配。如果单纯是上面的要求，就可以用一个stack来做，遇到成对的就出栈。但是题目有其他的要求：给定每一个问号替换成左括号和右括号所需的代价，求所有的替换方案中总代价最小的那一个。

2014-03-15 21:05:33 983

原创 codeforces好题记录——2B

题目见http://codeforces.com/problemset/problem/2/B给定一个正方形数组，只能向下或向右移动，求从左上移动到右下，在这个路径上的所有数字的乘积末尾的0最少。考虑到要使乘积末尾有0，则路径上必须有10，或者有2和5，有几个10末尾就有几个0这里是一个求最优的问题，考虑用dp来做，要求就是路径上2和5的个数中的最小值最小！！！但是这样直接dp

2014-03-15 21:05:14 839

原创有关const的一些知识点

const可以在运行时初始化，也可以在编译时初始化。cosnt int i = get_size() //运行时初始化const int i = 4 //编译时初始化，编译器会在用到i的地方进行替换默认情况下，const只在文件内有效。如果确实需要在文件间共享，可以使用extern关键字（不管是定义或者声明都需要添加）。const作用到引用上，则该引用不能修改被引用的值。初始化对

2014-03-12 10:06:48 754

原创 trivial和non-trivial在构造析构中的作用

triavial通常是指没有意义，在构造类对象的时候，有时候编译器会自动生成构造函数（拷贝构造以及＝号运算符号），有时候这些函数对于用户来说是没有意义的（尤其是在类里边有动态分配的指针时）。但在以下4种情况下，缺省的构造函数是有意义的：1.类里边有其他类变量（该类有缺省构造函数）2.类是从另外一个类继承而来（基类有缺省构造函数）3.类里边有虚函数。4.虚继承的情况。//

2014-03-12 10:06:22 2675

原创 STL的榨汁机——type traits

STL中关于类型提取器的详细介绍，我再此就不赘述了，只是记下其中关键部分，供我以后学习之用。nested type，这种方法能获得一个类的associated type，如下代码中，想要获得myIter类的T类型，可以在此类中nested一个typedef，将T保存下来，其他类中，就可以使用typename I::value_type来获得I类中nested进去的type（typena

2014-03-12 10:05:27 1039

原创 trivial、standard layout和POD的比较

POD的含义可以从两个显著的特性说明：它支持静态初始化，而且在C++中编译POD类型会和C中编译的struct类型得到相同的内存布局正是因为这个，这个定义被划分为两个不同的概念：trivial 类型和standard-layout 类型，因为这比POD类型更有用。新标准中已经很少使用POD这个术语了，而是更多的在使用更精确的概念：trival和stand-layout。 POD s

2014-03-11 13:38:31 2008 1

原创【PAT Advanced Level】1033. To Fill or Not to Fill (25)

网上策略说的很详细了，利用贪心算法：假设我们现在在A点，A能到达的最远距离之内有B, C, D三个点：1. 如果B， C， D中有比A小的，则找到离A最近的，A加的油刚好够到这个点；2. 如果没有比A小的，A加满油，到B\C\D中最小的一个点停下来，再加油。代码注意细节：当第一个点距离不是0时，车子哪里都去不了！#include #include #include #

2013-11-10 16:26:15 1043

原创【PAT Advanced Level】1032. Sharing (25)

这题如果用C++标准库里的string的话，会超时，还是用int或者char数组来保存吧。先遍历一遍，每个节点打上标记，再换一个头，遍历第二遍，如果碰到标记，就是所求。#include #include #include using namespace std;struct node{ char s; int next; bool flag; node(char s

2013-11-10 16:20:33 848

原创【PAT Advanced Level】1031. Hello World for U (20)

简单题，算算就可以了。#include #include using namespace std;int main(){ string s; cin>>s; int n1, n2; n2 = (s.size() % 2 == 1)?3 : 4; while (n2 <= s.size()) { n1 = (s.size() - n2)/2 + 1; if(n1

2013-11-10 16:17:41 896

原创【PAT Advanced Level】1030. Travel Plan (30)

先用Djikstra算出最短路径，纪录下相同的最短路径，再回溯计算花费最少的路径。其实不用回溯，直接在比较最短路径的时候比较花费最少就可以了。#include #include #include #include using namespace std;struct node{ int index; int curDist; vector preCity; nod

2013-11-10 16:16:24 977

原创【PAT Advanced Level】1029. Median (25)

#include #include #include #include using namespace std;vector v1;vector v2;int main(){ int a, b; long tmp; scanf("%d", &a); int i = 0; while (i < a) { scanf("%ld", &tmp); v1.push_

2013-11-10 16:14:07 893

原创算法导论22.4-5 构造拓扑排序

题目要求用非DFS得方法构造拓扑排序。找出入度为0的节点，删除该点并删除该点所有的出边。删除的顺序就是拓扑排序的顺序。要求复杂度O(V + E)。方案：1. 遍历邻接表一遍，统计每个元素的入度。（O(E)）2. 找出一个入度为0的点u，将u的所有出边的目的点v的入度减一。（O(V + E)）3. 继续步骤一。

2013-11-08 10:56:29 1569

转载算法导论22.4-3 判断无向图是否包含回路

给出一个算法，用它来确定一个给定的无向图G=(V,E)中是否包含一个回路。所给出的算法的运行时间为O(V)，这一时间独立于|E|解答：我们都知道对于一个无向图而言，如果它能表示成一棵树，那么它一定没有回路，并且有|E|=|V|-1，如果在这个树上添加一条边，那么就构成了回路，如果在这个树中去掉一个边就成了森林（注意：如果只是限定|E| 对于这个题目我们可以用DFS来做，每当

2013-11-08 10:32:32 5321

原创算法导论22.4-2 有向无环图的路径数目

要求在一个有向无环图中，给定两点，求出这两点之间有多少条路径。该章节是讲拓扑排序，考虑先拓扑排序，将图排序成P336页的图22-7类似的样子，然后对E(s, t)之间的部分进行DP可以证明所有路径都仅存在于s, t之间。递归式如下（L(s, t)表示s到t的路径的数目）：直接用DFS好像是不可行的，代码就不写了。

2013-11-08 10:12:20 6901 2

原创【PAT Advanced Level】1025. PAT Ranking (25)

简单模拟题。#include #include #include #include #include using namespace std;struct stu{ string reg; int score; int final_rank; int location_num; int local_rank; stu(string r, int s, int ln,

2013-11-07 21:24:37 832

原创【PAT Advanced Level】1024. Palindromic Number (25)

回文数#include #include #include #include #include #include #include #include using namespace std; string Reverse(string a) { string ans; for(int i = 0; i < a.size(); ++i)

2013-11-07 20:18:57 842

原创【PAT Advanced Level】1023. Have Fun with Numbers (20)

#include #include #include #include #include #include #include #include using namespace std; void GetCntTable(string a, vector& cntTable) { cntTable.assign(10, 0); for(int i

2013-11-07 20:17:51 852

原创【PAT Advanced Level】1022. Digital Library (30)

这题其他没什么，就是输入输出比较麻烦，还怪自己太不熟练。#include #include #include #include #include #include using namespace std;struct book{ string id; string title; string author; vector keywords; string pub

2013-11-07 18:51:09 1080

转载字符，字节和编码

级别：中级摘要：本文介绍了字符与编码的发展过程，相关概念的正确理解。举例说明了一些实际应用中，编码的实现方法。然后，本文讲述了通常对字符与编码的几种误解，由于这些误解而导致乱码产生的原因，以及消除乱码的办法。本文的内容涵盖了“中文问题”，“乱码问题”。掌握编码问题的关键是正确地理解相关概念，编码所涉及的技术其实是很简单的。因此，阅读本文时需要慢读多想，多思考。引言“

2013-11-07 15:04:19 664

原创【PAT Advanced Level】1021. Deepest Root (25)

这题分两个步骤：1. 求出图中有几个连通子图2. 如果只有一个连通图，找出最长的路径（图的直径）我直接用了一个DFS求连通子图的个数，其实更通用的方法是并查集。找出最长路径，我们进行了n次DFS，每次以一个节点作为根节点。后来看了网上的解法，其实只需要两次DFS就可以求得。昨天我刚刚看了怎么求树的直径，今天该用到的时候又忘了，真是学的不牢啊。具体求法见http://blog.c

2013-11-06 15:19:43 784

原创【PAT Advanced Level】1020. Tree Traversals (25)

这题给定后序和中序遍历的结点顺序，要求层序遍历的结点顺序。可以通过后序和中序构造出这棵树，然后再BFS给出层序遍历。构造的规则为：1. 找到后序遍历的最后一个元素，这个元素肯定是整个树的根。2. 根据上面找到的元素，将中序遍历的序列分为两边，左边肯定是根的左子树，右边是根的右子树3. 递归左子树和右子树#include #include #include #inclu

2013-11-06 12:58:30 836

原创求树的“直径”以及所想到的

算法导论22.2-7题：树T=（V,E）的直径（diameter）定义为max(u,v)，亦即，树的直径是树中所有最短路径长度中的最大值。试写出计算树的直径的有效算法，并分析算法的运行时间。如果这里的树T是简单的二叉树或者多叉树，我们可以用递归来解决（Diameter(tree T)表示T的直径）;1. 求出T左子树的最深节点的深度Dleft，求出T右子树最深节点的深度Dright。2

2013-11-05 14:59:07 2292

原创算法导论22.2-6 好选手、坏选手

//算法导论22.2-6题 “好选手、差选手”//题意就是要判断一个图是否是二分图//二分图又称双分图、二部图、偶图，指顶点可以分成两个不相交的集使得在同一个集内的顶点不相邻（没有共同边）的图。//二分图又称作二部图，是图论中的一种特殊模型。设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(U,V)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同

2013-11-05 14:06:18 1522

原创【PAT Advanced Level】1019. General Palindromic Number (20)

这题就是简单的模拟题，为了确保不越界，我使用了long long要注意加入0的判断！#include #include #include using namespace std;int main(){ long long a, b; cin>>a>>b; if(a == 0) { cout<<"Yes"<<endl<<0<<endl; return 0;

2013-11-04 21:56:36 836

原创【PAT Advanced Level】1018. Public Bike Management (30)

这题还是比较有难度的。题目中要纪录的东西比较多，比较繁琐。这题我考虑先用Dijkstra算法计算单源最短路径，在计算过程中纪录每个点的最短路径的前序（如果最短路径有多条，每个前序都需要纪录），然后再递归深搜出具有最少携带自行车数量的路径。这题还有几个点没过，先放着吧，感觉整体思路没什么问题。#include #include #include #include #inclu

2013-11-04 21:55:08 1004

原创【PAT Advanced Level】1017. Queueing at Bank (25)

先排序，然后模拟事件。简单的模拟题。#include #include #include using namespace std;const int opened = 8 * 60 * 60;const int closed = 17 * 60 * 60;struct customer{ int hour; int minute; int second; int

2013-11-03 15:25:37 1004 1

原创【PAT Advanced Level】1016. Phone Bills (25)

注意细心，简单模拟题。#include#include#include#include#include#includeusing namespace std;const int HOURS=24;const int NAME=21;typedef struct Record{ char name[NAME]; int mou; int dd; int hh; i

2013-11-02 22:06:17 783

原创【PAT Advanced Level】1068. Find More Coins (30)

最近在学习动态规划，PAT中的这一题就是一个典型的dp问题。这一题和01背包问题很类似，M相当于背包问题中的背包容量，硬币面值相当于每件物品的重量，背包问题中要求物品价值最大，这里要求物品总重（面值和）等于M，从可选方案中选择最优的是根据给定的比较方法。我们解决问题的难点：如何选择出最小的序列？首先来看递归式：L(i, j)表示在前i号硬币中选择，并且总价值小于等于j的序列的最大面值和

2013-11-01 19:53:17 1885 1

原创【PAT Advanced Level】1015. Reversible Primes (20)

转换进制&&逆序可以在一起进行，有一点技巧，不要用十进制数来表示低进制，容易溢出。#include #include using namespace std;bool isPrime(int n){ if(n < 2) return false; if(n == 2) return true; if(n % 2 == 0) return false; for(

2013-10-31 20:06:02 763

原创【PAT Advanced Level】1014. Waiting in Line (30)

简单模拟题，注意读懂题意就行#include #include using namespace std;#define CUSTOMER_MAX 1000+1#define INF 0x6fffffff #ifndef LOCAL// #define LOCAL#endif LOCALint n; // number of windows <=20int m ;/

2013-10-31 19:22:26 722

原创【PAT Advanced Level】1013. Battle Over Cities (25)

这题给定了一个图，我用DFS的思想，来求出在图中去掉某个点后还剩几个相互独立的区域（连通子图）。在DFS中，每遇到一个未访问的点，则对他进行深搜，把它能访问到的所有点标记为已访问。一共进行了多少次这样的搜索，就是我们要求的独立区域的个数。#include #include #include using namespace std;const int maxNum = 10

2013-10-31 14:12:55 775

原创【PAT Advanced Level】1012. The Best Rank (25)

注意点：排名顺序如果有并列，则往后延续比如1 1 1 4 5而不是1 1 1 2 3每次排序后更新每个学生的最好排名情况。#include #include #include #include #include using namespace std;struct Student{public: string id; int score[4]; int bes

2013-10-31 13:18:09 807

原创【PAT Advanced Level】1011. World Cup Betting (20)

简单模拟题，遍历一遍即可。考察输入输出。#include #include #include #include using namespace std;#define N 3int main(){ char res[3]={'W','T','L'}; char max_res[N]; int i,j; float tmp,sum=1,odd; for(i=0;i<

2013-10-30 22:11:06 698

原创 trivial destructor

trivial理解为无用的,无意义的; non-trivial自然就是有实际意义的如果一个class没有定义destructor,如果这个class中的一个数据成员拥有destructor,那么编译器会自动合成出这个class的destructor来.在这个class的合成的destructor里调用那个数据成员的destructor,这个合成的 class的destructor是有意

2013-10-30 14:25:23 971

原创 Strict Weak Ordering

DescriptionA Strict Weak Ordering is a Binary Predicate that compares two objects, returning true if the first precedes the second. This predicate must satisfy the standard mathematical definition

2013-10-29 20:15:57 804

原创 STL中priority_queue的使用注意事项

今天在使用priority_queue写一个算法的时候，总是报heap异常，查了很久，才知道原因。我们知道优先级队列的底层是用heap来实现的，每次push和pop操作后，都会调用heapify来调整最大堆得结构。我们先来看看priority_queue的声明：priority_queue, vector>, cmp> pq;这是我使用的一个优先级队列，队列里每

2013-10-29 19:58:53 2412

原创【PAT Advanced Level】1045. Favorite Color Stripe (30)

这几天在复习动态规划（DP），故在pat上找了两道dp的题目来练练手。这一题看似跟动态规划扯不上，其实是可以把它看做动态规划问题——最长递增子序列（LIS）问题的一个变形。题目中给定的第一个数组a[n]，就相当于给定了“递增”的顺序。如果一个元素a[i]在a中的下标大于或等于另一个元素a[j]（i>=j），我们就称a[i]>a[j]故只需把原来LIS问题中的判断大小部分改为现在的判定大

2013-10-26 20:53:19 650

空空如也

空空如也