在默认的STL中，priority_queue一般是大根堆，如果想要改成小根堆或者自定义数据类型，就需要写仿函数，例子如下：
[c language=”++”]
struct cmp
{
bool operator()(const int&a, const int&b)
{//小根堆
return a > b;
}
};
priority_queue<int, vector<int>, cmp> minHeap;
[/c]
需要说明的是，需要return a>b，这样才构成小根堆，因为原STL中，调用的是a<b操作构成的大根堆。
如果需要自定义数据结构，同样采取上述办法即可。
安装了centOS后，发现display选项里面只有1024*768和800*600的选项，而显示屏是1920*1080的。于是开始想办法进行分辨率的适配。
通过查资料知道，修改分辨率主要有两种方法：
方法一：使用xorg.conf文件（这个方法失败了！原因尚未找到，想要解决办法的童鞋可以直接看第二种方法）
这个时候就可以进入桌面系统修改分辨率了。首先使用cvt命令生成modeline，生成一些配置信息。然后把这个配置信息添加到xorg.conf的section“Monitor”中（这个修改需要在root用户下面进行），如下图：
然后，理论上已经修改了分辨率，重启后也会正常的，但是实际没有效果！！失败了。。原因待查。
方法二：使用xrandr+开机启动选项进行修改。
同样还是先使用cvt生成modeline信息，然后用以下三行xrandr命令进行更改，效果立竿见影！红色部分为cvt生成的modeline信息，去掉了“modeline”字串（必须去掉）。
[shell]
xrandr –newmode <span style="color: #ff0000;">"1920×1080" 173.00 1920 2048 2248 2576 1080 1083 1088 1120 -hsync +vsync</span>
xrandr –addmode VGA1 1920×1080
xrandr –output VGA1 –mode 1920×1080
[/shell]
当然，这种办法不是永久的，每次重启都需要重新设置。
为了使每次开机都执行上述的命令，把上述三个指令写到sh文件中去，如上图，我命名为change-resolution.sh。
然后需用使用chmod u+x change-resolution.sh更改为可执行文件，在应用程序->系统工具->启动应用程序中，添加这个脚本即可。
1.题目给出n个学生，编号为0~n-1，并给出每个学生的兴趣，求有共同兴趣的学生团体数量，和每个团体的学生数目。
2.仔细观察测试例子，发现凡是有相同兴趣的同学，都可以归为一类，并不需要团体里所有的学生都有共同兴趣，譬如学生0有兴趣A，学生1有兴趣A、B，学生2有兴趣B，那么0和1有共同兴趣A，归为一类，而2和1有共同兴趣B，所以也把2归在1所在的类，所以这个团体有3个学生。
3.主要是考察并查集。我们把每个学生的兴趣都合并到第一个兴趣所在的集合，然后统计每个学生的第一个兴趣属于哪个集合，从而把学生归到相应的集合。
When register on a social network, you are always asked to specify your hobbies in order to find some potential friends with the same hobbies. A “social cluster” is a set of people who have some of their hobbies in common. You are supposed to find all the clusters.
Input Specification:
Each input file contains one test case. For each test case, the first line contains a positive integer N (<=1000), the total number of people in a social network. Hence the people are numbered from 1 to N. Then N lines follow, each gives the hobby list of a person in the format:
Ki: hi[1] hi[2] … hi[Ki]
where Ki (>0) is the number of hobbies, and hi[j] is the index of the j-th hobby, which is an integer in [1, 1000].
Output Specification:
For each case, print in one line the total number of clusters in the network. Then in the second line, print the numbers of people in the clusters in non-increasing order. The numbers must be separated by exactly one space, and there must be no extra space at the end of the line.
Sample Input:
8 3: 2 7 10 1: 4 2: 5 3 1: 4 1: 3 1: 4 4: 6 8 1 5 1: 4
Sample Output:
3 4 3 1
AC代码：
[c language=”++”]
//#include<string>
//#include <iomanip>
#include<vector>
#include <algorithm>
//#include<stack>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
using namespace std;
bool cmp(const int&a, const int&b)
{
return a > b;
}
int find(int x, map<int, int>&r)
{
if (r[x] == 0)
{//利用题目中兴趣大于0的特点，进行初始化
r[x] = x;
return x;
}
else if (r[x] == x)
return x;//如果代表就是自己，则返回x
else
{//如果代表不是自己，就把自己的代表更改为自己的代表的代表
r[x] = find(r[x], r);
return r[x];
}
}
int main(void)
{
int total;
scanf("%d", &total);
map<int, int> r;
vector<int> student(total);
for (int i = 0; i < total; i++)
{
int sum;
scanf("%d:", &sum);
//把第一个兴趣当作代表
int firstITR;
scanf("%d", &firstITR);
r[firstITR] = find(firstITR, r);//找出代表
student[i] = r[firstITR];
for (int j = 1; j < sum; j++)
{
int tmp;
scanf("%d", &tmp);
r[find(tmp, r)] = r[firstITR];//把tmp和firstITR合并
}
}
map<int, int> interestSet;
for (int i = 0; i < student.size(); i++)
{//找出各个学生所属的兴趣集合,把这个集合的人数++
interestSet[find(student[i], r)]++;
}
vector<int> ans(0);
for (map<int, int>::iterator ite = interestSet.begin(); ite != interestSet.end(); ite++)
{//把兴趣统计放到vector中
ans.push_back(ite->second);
}
//进行排序
sort(ans.begin(), ans.end(), cmp);
printf("%d\n", ans.size());
for (int i = 0; i < ans.size(); i++)
{
printf("%d", ans[i]);
if (i != ans.size() – 1)
printf(" ");
}
printf("\n");
return 0;
}
[/c]
1.该题是供应链问题，实则是构建一棵树，然后使用BFS进行层序遍历，找出最早出现叶子节点的层，统计该层的叶子节点，然后直接输出结果。
A supply chain is a network of retailers（零售商）, distributors（经销商）, and suppliers（供应商）– everyone involved in moving a product from supplier to customer.
Starting from one root supplier, everyone on the chain buys products from one’s supplier in a price P and sell or distribute them in a price that is r% higher than P. Only the retailers will face the customers. It is assumed that each member in the supply chain has exactly one supplier except the root supplier, and there is no supply cycle.
Now given a supply chain, you are supposed to tell the lowest price a customer can expect from some retailers.
Input Specification:
Each input file contains one test case. For each case, The first line contains three positive numbers: N (<=105), the total number of the members in the supply chain (and hence their ID’s are numbered from 0 to N-1, and the root supplier’s ID is 0); P, the price given by the root supplier; and r, the percentage rate of price increment for each distributor or retailer. Then N lines follow, each describes a distributor or retailer in the following format:
Ki ID[1] ID[2] … ID[Ki]
where in the i-th line, Ki is the total number of distributors or retailers who receive products from supplier i, and is then followed by the ID’s of these distributors or retailers. Kj being 0 means that the j-th member is a retailer. All the numbers in a line are separated by a space.
Output Specification:
For each test case, print in one line the lowest price we can expect from some retailers, accurate up to 4 decimal places, and the number of retailers that sell at the lowest price. There must be one space between the two numbers. It is guaranteed that the all the prices will not exceed 1010.
Sample Input:
10 1.80 1.00 3 2 3 5 1 9 1 4 1 7 0 2 6 1 1 8 0 0 0
Sample Output:
1.8362 2
AC代码：
[c language=”++”]
//#include<string>
//#include <iomanip>
#include<vector>
#include <algorithm>
//#include<stack>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
using namespace std;
bool cmp(const int&a, const int&b)
{
return a > b;
}
struct ChainNode{
vector<int> list;
ChainNode() :list(0){};
};
int main(void)
{
int total;
double rootPrice, higher;
scanf("%d %lf %lf", &total, &rootPrice, &higher);
vector<ChainNode> chain(total);
for (int i = 0; i < total; i++)
{
int nextTotal;//下游数量
scanf("%d", &nextTotal);
for (int j = 0; j < nextTotal; j++)
{
int tmp;
scanf("%d", &tmp);
chain[i].list.push_back(tmp);//记录下游节点
}
}
queue<int> q;
q.push(0);
int count1 = 1;
int count2 = 0;
int retailerSum = 0;//该层零售商数量
while (!q.empty())
{
for (int i = 0; i < count1; i++)
{
int head = q.front();
q.pop();
if (chain[head].list.size() == 0)
retailerSum++;//如果出现子节点，则进行计数记录
else
{//否则压入队列，下次遍历
for (int j = 0; j < chain[head].list.size(); j++)
{
count2++;
q.push(chain[head].list[j]);
}
}
}
//如果存在叶子节点，直接跳出
if (retailerSum != 0) break;
count1 = count2;
count2 = 0;
rootPrice *= (1 + higher / 100.0);
}
printf("%.4lf %d\n", rootPrice, retailerSum);
return 0;
}
[/c]
1.回旋矩阵，主要是给出一个数组，先对数组进行降序排序，使用sort和重写比较函数，然后填充到回旋矩阵中。
2.回旋矩阵填充思路：先建立一个m*n的所有值为-1的矩阵，-1表示数值没被填充，
（1）一开始往右填充，当右边到达边界值或者右边的数已经被填充，就改为往下填充；
（2）往下填充遇到边界值或者下边的数已经被填充，则往左填充；
（3）往左填充遇到边界值或者左边的数已经被填充，改为往上走；
（4）往上填充遇到边界值或者上边的数已经被填充，则往右填充，回到（1）。
This time your job is to fill a sequence of N positive integers into a spiral matrix in non-increasing order. A spiral matrix is filled in from the first element at the upper-left corner, then move in a clockwise spiral. The matrix has m rows and n columns, where m and n satisfy the following: m*n must be equal to N; m>=n; and m–n is the minimum of all the possible values.
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N. Then the next line contains N positive integers to be filled into the spiral matrix. All the numbers are no more than 104. The numbers in a line are separated by spaces.
Output Specification:
For each test case, output the resulting matrix in m lines, each contains n numbers. There must be exactly 1 space between two adjacent numbers, and no extra space at the end of each line.
Sample Input:
12 37 76 20 98 76 42 53 95 60 81 58 93
Sample Output:
98 95 93 42 37 81 53 20 76 58 60 76
AC代码：
[c language=”++”]
//#include<string>
//#include <iomanip>
#include<vector>
#include <algorithm>
//#include<stack>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
using namespace std;
bool cmp(const int&a, const int&b)
{
return a > b;
}
int main(void)
{
int total;
scanf("%d", &total);
vector<int> num(total, 0);
for (int i = 0; i < total; i++)
{//读取数据
scanf("%d", &num[i]);
}
//进行排序
sort(num.begin(), num.end(), cmp);
int matM, matN;
int minDiff = INT_MAX;
//求出m>=n且abs(m-n)最小时，m与n的取值
for (int i = 1; i <= sqrt((double)total) + 1; i++)
{
if (i*(total / i) == total&&abs(i – (total / i)) < minDiff)
{//如果符合要求，且差比上次的小，则进行更新
matM = i;
matN = total / i;
minDiff = abs(matM – matN);
}
}
if (matM < matN)
swap(matM, matN);
//读取的都是正数，利用-1来表示还没填充
vector<vector<int>>mat(matM, vector<int>(matN, -1));
int direction = 0;//方向，0表示往右，1表示往下，2表示往左，3表示往上
int m = 0, n = 0;//m,n表示上次填充的位置
for (int i = 0; i < total; i++)
{
mat[m][n] = num[i];
if (direction == 0)
{//往右走
if (n == matN – 1 || mat[m][n + 1] != -1)
{//如果遇到边界，或者右边的位置已经填充数值，则往下走
direction = 1;
m++;
}
else//继续往右走
n++;
}
else if (direction == 1)
{//往下走
if (m == matM – 1 || mat[m + 1][n] != -1)
{//如果遇到边界，或者下边的位置已经填充数值，则往左走
direction = 2;
n–;
}
else//继续往下走
m++;
}
else if (direction == 2)
{//往左走
if (n == 0 || mat[m][n – 1] != -1)
{//如果遇到边界，或者左边的位置已经填充数值，则往上走
direction = 3;
m–;
}
else//继续往左走
n–;
}
else if (direction == 3)
{//往上走
if (m == 0 || mat[m – 1][n] != -1)
{//如果遇到边界，或者上边的位置已经填充数值，则往右走
direction = 0;
n++;
}
else//继续往上走
m–;
}
}
for (int i = 0; i < matM; i++)
{
for (int j = 0; j < matN; j++)
{
printf("%d", mat[i][j]);
if (j != matN – 1)
printf(" ");
}
printf("\n");
}
return 0;
}
[/c]
1.题目要求一个序列中的所有连续子序列和的和。如下：对于序列{0.1, 0.2, 0.3, 0.4},有10个连续子序列: (0.1) (0.1, 0.2) (0.1, 0.2, 0.3) (0.1, 0.2, 0.3, 0.4) (0.2) (0.2, 0.3) (0.2, 0.3, 0.4) (0.3) (0.3, 0.4) (0.4).
2.直接进行暴力计算会超时，需要寻找出出现次数的数学关系。
3.关系如下，数组a[0],a[1],a[2]….a[n-1]共n个数，假设数字a[0]出现的次数times，对即a[0],a[0]a[1],a[0]a[1]a[2]…..不难看出出现了n次，除去包含a[0]序列，我们可以看出a[1]出现的次数为n-1次，然后我们再观察包含a[0]的序列中，a[1]出现了times-1次，那么a[1]出现的次数为times1=times-1+n-1。同样，把序列分为包含a[1]和不包含a[1]d两种情况分析，a[2]出现的次数为times2=times1-2+n-2，以此类推：a[3]出现的次数为times3=times2-3+n-3。
所以转化公式为a[i]出现的次数times[i]=times[i-1]-i+n-i。
通过上述公式，可以在O（n）的时间复杂度内计算出结果。
Given a sequence of positive numbers, a segment is defined to be a consecutive subsequence. For example, given the sequence {0.1, 0.2, 0.3, 0.4}, we have 10 segments: (0.1) (0.1, 0.2) (0.1, 0.2, 0.3) (0.1, 0.2, 0.3, 0.4) (0.2) (0.2, 0.3) (0.2, 0.3, 0.4) (0.3) (0.3, 0.4) (0.4).
Now given a sequence, you are supposed to find the sum of all the numbers in all the segments. For the previous example, the sum of all the 10 segments is 0.1 + 0.3 + 0.6 + 1.0 + 0.2 + 0.5 + 0.9 + 0.3 + 0.7 + 0.4 = 5.0.
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N, the size of the sequence which is no more than 105. The next line contains N positive numbers in the sequence, each no more than 1.0, separated by a space.
Output Specification:
For each test case, print in one line the sum of all the numbers in all the segments, accurate up to 2 decimal places.
Sample Input:
4 0.1 0.2 0.3 0.4
Sample Output:
5.00
AC代码：
[c language=”++”]
//#include<string>
//#include <iomanip>
#include<vector>
#include <algorithm>
//#include<stack>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
using namespace std;
int main(void)
{
int n;
scanf("%d", &n);
vector<double> num(n, 0);
for (int i = 0; i < n; i++)
{
scanf("%lf", &num[i]);
}
double ans = 0;
long long times = 0;//需要使用long long，避免溢出
for (int i = 0; i < n; i++)
{//当前数字出现的次数与上一个数字出现的次数有联系，联系为times = times – i + n – i;
times = times – i + n – i;
ans += times*num[i];
}
printf("%.2lf\n", ans);
return 0;
}
[/c]
今天中午刚考完PAT甲级（Advance Level）冬季考试（20151205），4道题目分别考察的内容如下：
1.数学统计，题目给出了sequence的定义，根据该定义进行统计，通过定义我们可以找出每个数出现的次数规律，譬如有数组a[0],a[1],a[2]….a[n-1]共n个数，假设数字a[0]出现的次数times，那么a[1]出现的次数为times1=times-1+n-1，a[2]出现的次数为times2=times1-2+n-2，a[3]出现的次数为times3=times2-3+n-3，如此类推，最后可以在O（n）的时间内计算出结果。暴力解法需要O（n^3）的时间复杂度。
2.回旋矩阵，主要是给出一个数组，先对数组进行降序排序，使用sort和重写比较函数，然后填充到回旋矩阵中，回旋矩阵填充思路：先建立一个m*n的所有值为-1的矩阵，-1表示数值没被填充，（1）一开始往右填充，当右边到达边界值或者右边的数已经被填充，就改为往下填充；（2）往下填充遇到边界值或者下边的数已经被填充，则往左填充；（3）往左填充遇到边界值或者左边的数已经被填充，改为往上走；（4）往上填充遇到边界值或者上边的数已经被填充，则往右填充，回到（1）。
3.关于供应链问题，实则是建立一棵树，进行层次遍历，找到最早出现叶子节点的那一层，然后统计该层的叶子节点数量。实则是BFS，之前的练习题中出现了两道关于供应链的题目，所以比较容易理解。
4.并查集的考察。题目给出一些学生和该学生相应的兴趣，其中学生之间有两个共同的兴趣，即可归为一个cluster，不必所有兴趣都相同。所以采用并查集，把学生进行归类，最后进行统计。
题目尚未出现比较难的临界值，通过练习熟练掌握sort、BFS、并查集知识后可以较为轻松地应对这次考试。平时需要多练习，多手写代码，多整理自己的解题思路。后续练习题中出现本次的题目后，我再进行详细的解释和上代码。
1.之前在本机一直没有发现博客打开有问题，但是在手机端或者别的电脑打开就会体会到速度非常慢，当时还没了解到是什么原因。
2.今天在另外一台电脑上面用火狐登录的时候发现显示正在解析fonts.googleapis.com的网站，然后想起会不会是加载了google的字体文件导致慢？因为google很多网址都被墙了，恰好我的电脑一直有翻墙，所以没有体会到。后来实际实验，这个网址没有被墙，但是通过查看Network，它竟然请求了200多s！
3.于是我通过F12的调试器查看Resources选项，发现加载了很多来自fonts.gstatic.com网站的font文件，这个网站实际上会解析到gstaticadssl-china.l.google.com。
4.解决办法：找到wp-content\themes\XXXX（XXXX为主题名）中相应的functions.php文件，把其中的fonts.googleapis.com改为fonts.useso.com，把wp-includes\script-loader.php中的googleapis或者gstatics全部改为useso。
这两个系统在第一次这行locate命令时，都会出现找不到db的问题。
1.centOS
出现如下的问题：
[shell]
# locate test
locate: can not stat () `/var/lib/mlocate/mlocate.db’: No such file or directory
[/shell]
这个时候可以执行sudo updatedb进行建立索引数据库；
2.MacOS
可以根据提示进行操作，输入sudo /usr/libexec/locate.updatedb即可，因为要建立索引数据库，需要等待一段时间才能执行locate命令。
1.通过GitHub第一步：生成ssh keys，我们成功通过SSH连接github，接下来，我们介绍如何进行同步和提交。
2.同步github到本地，有下面的命令：
[shell]
git clone git://github.com:xxxx/test.git ##以gitreadonly方式克隆到本地，只可以读
git clone git@github.com:xxx/test.git ##以SSH方式克隆到本地，可以读写
git clone https://github.com/xxx/test.git ##以https方式克隆到本地，可以读写
git fetch git@github.com:xxx/xxx.git ##获取到本地但不合并
git pull git@github.com:xxx/xxx.git ##获取并合并内容到本地
[/shell]
3.本地提交项目到github，首先我们需要进行配置：
其中，为了各个帐号保持一致，即在github的profile里面有contributions记录，这里设置的user.email要与github帐号的email一致，否则不会有contributions记录，每台电脑上面的user.name可以不一样，email一致即可。
[shell]
git config –global user.name ‘siukwan’
git config –global user.email ‘siukwan@foxmail.com’ #全局联系方式，可选
[/shell]
然后进行add，commit
[shell]
git init #初始化一个本地库
git add testfile.txt#添加文件到本地仓库
git commit -m "first commit" #提交到本地库并备注，此时变更仍在本地。
git commit -a ##自动更新变化的文件，a可以理解为auto，注意需要添加注释，在:wq保存退出
[/shell]
这个时候，只是commit了本地的文件，还未把本地更新变更到github服务器上。通过下面的命令可以把更新推送到服务器上：
[shell]
git push #将本地文件提交到Github的remoname版本库中。此时才更新了本地变更到github服务上。
[/shell]
在进入到github的branch目录里面，可以直接进行git pull和git push操作。
注意：
如果在每次push的时候都需要输入帐号和密码，是因为使用了https方式 push（这个可以使用svn）
在终端里面输入
[shell]
git remote -v
[/shell]
可以看到下面的结果
[shell]
origin https://github.com/com:siukwan/unix (fetch)
origin https://github.com/com:siukwan/unix (push)
[/shell]
下面把它换成ssh方式的：
[shell]
git remote rm origin
git remote add origin git@github.com:siukwan/unix
git push origin
[/shell]
这时我们再次输入查看信息：
[shell]
git remote -v
[/shell]
可以看到下面的结果，这样在下次push的时候就不再需要输入帐号密码了。
[shell]
origin git@github.com:siukwan/unix (fetch)
origin git@github.com:siukwan/unix (push)
[/shell]
把当前目录添加到github仓库：
[shell]
git init
git push -u origin master
[/shell]
