mhlwsk的博客

·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·
题目链接：http://poj.org/problem?id=1731
STL中的next_permutation，作用是生成当前序列的字典序较大的下一个序列，如果能生成则返回true，否则返回false。
还有一个反向的函数prev_permutation。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
int main() {
	std::ios::sync_with_stdio(false);
	std::string str;
	std::cin >> str;
	sort(str.begin(),str.end());
	std::cout << str << std::endl;
	while(next_permutation(str.begin(),str.end())) {
		std::cout << str << std::endl;
	}
	return 0;
}

·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·
题目链接：http://codeforces.com/problemset/problem/798/D

一开始想写个这样的贪心：大家同时开始做，多余的人向前走，做完的人向前补，不过这个贪心好像不太对。。

后来知道这题是二分答案，思路换了一下，既然在二分答案的条件下，每个人时间是给定的，就无所谓谁先做了，一个一个派出去，看看能不能在给定时间搬完就行了。

·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1012

这题每次都只查看最后l位的最大值，因而位置靠后的数如果大于前面的数，则前面的数是没有用的，直接扔掉即可。这样维护了一个单调递减的栈，同时再维护一个同步的位置栈，查询时需要根据位置栈找到所需最大值的位置，输出对应的最大值即可。

·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·
题目链接：http://poj.org/problem?id=1182
参考博客：Azrael_Death的博客

以下引用自Azrael_Death大神：

逻辑推理的题有一部分和并查集有关，此题是种类并查集的经典例题。
首先我们把每个动物分成三个点，对于点i，点i表示第i个动物的种类，点i+n表示第i个动物的食物，点i+2n表示第i个动物的天敌。
这样一来，提供信息：x和y同类，相当于提供三条信息：
1.x、y在同一个集中
2.x+n、y+n在同一个集中
3.x+2n、y+2n在同一个集中
于是我们merge(x, y), merge(x+n, y+n), merge(x+2n, y+2n);
同理，提供信息：x吃y，相当于提供三条信息：
1.x、y+2n在同一个集中
2.x+n、y在同一个集中
3.x+2n、y+n在同一个集中
于是我们merge(x, y+2n), merge(x+n, y), merge(x+2n, y+n);
如果在接到信息x和y同类后，发现x和y+n同类或x和y+2n同类，则此信息与先前信息矛盾。因为对称性，我们不用再判断y是否和x+n或x+2n同类。同理可处理x吃y的情况。

感觉最重要的思想是那个拆点。。这样就把各种关系具体化了

·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·
题目链接：https://cn.vjudge.net/problem/CodeForces-591B

模拟题

这题如果直接去字符串里面修改的话会超时，所以这里借鉴了字符串指针排序的思路，首先建立一个26*200 000的int数组，记录26个字母所在字符串中的位置，然后建立一个指针数组（索引）指向这个int数组的第一维，交换两个字母时，直接交换对应指针数组元素的值就行了。

·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6216

这题考察的是数学思维。

一开始想用打表暴力枚举出所有（满足a^3-(a-1)^3<=2*10^12）的a^3，然后枚举b^3并判断b^3+p是否在枚举出的a^3中，但因为要开816498的long long数组内存吃不消，所以只能作罢。

·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·
题目链接： https://cn.vjudge.net/problem/CodeForces-201A

这题是找规律题，但又有点奇怪，一开始尝试按照题目要求那样枚举x找n变化的规律，但是找不到。。后来才知道这题是枚举n找x的变化规律，可以证明除了x=3的情况，只要方阵的sharpness>=x，对应的n就一定满足条件（证明见下），因而只要找到能使矩阵的最大sharpness>=x的最小的n就行了。

我是C++选手，但学校要求用C考试，所以来总结一下C下快速排序的实现方案。
NOIP考试时，C++下有sort，pascal下有可用的示例文件，C就比较尴尬了。
这里用手写和使用qsort的方式实现快排。

其实本来感觉没有必要写这篇文章的，但是几个周前gentoo升级时搜狗输入法滚挂了，解决问题后，我感觉有些之前没有遇到的问题，有必要记下来，以方便以后自己查看。这里汇总一下最近安装fcitx输入法框架遇到的问题，一并把搜狗输入法的安装写进来。

·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·
相信安装无线网卡驱动是许多linux初学者遇到的一个棘手的问题。Ubuntu默认使用开源网卡驱动，比如针对broadcom网卡，有b43、brcm80211等开源驱动，如果显卡型号适配，那么恭喜你，在安装时你就可以连接至无线网络，但如果不适配，就要手动安装无线网卡驱动。尤其是现在的许多超薄本、变形本和PC平板二合一没有传统网线插口（RJ45接口），安装无线网卡驱动就会变得更加棘手。
这篇文章适用于有网络和无网络的情况，也适用于没有网线接口的情况。