Jove's Blog

POJ 2190 ISBN C++版

发表于 2013-04-07 更新于 2022-03-12

水题但是有些小细节还是要注意，解释下题意，根据给出的规则依次给每个位数加权求和，这里有一个特殊情况，也就是第十位上为X的情况，也就是这位上为10的情况，这里我没有注意，后来才发现的。

我用的方法就是枚举？可以取到的值，来求解！不多解释看注释

代码如下：

/*Problem: 2190		User: awq123
**Memory: 232K		Time: 16MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cstdio>

using namespace std;

int main()
{
    char str[12];
    cin>>str;
    int sum=0,flag=0,ok=0;
    //判断？在哪一位并算出除了那位的总和
    for(int i=0;i<10;i++)
    {
	if(str[i]=='?')
	    flag=i;
	else if(str[i]=='X')
	    sum+=10*(10-i);
	else
	    sum+=(10-i)*(str[i]-'0');
    }
    //依次枚举0-9
    for(int i=0;i<10;i++)
	if((sum+(10-flag)*i)%11==0)
	{
	    cout<<i;
	    ok=1;
	}
    //最后一位为10也就是x的情况
    if(ok==0&&flag;==9)
	if((sum+10)%11==0)
	{
	    cout<<"X";
	    ok=1;
	}
    //如果都不是
    if(ok==0)
	cout<<"-1";
}

POJ 2039 To and Fro C++版

发表于 2013-04-07 更新于 2022-03-12

题目链接：http://poj.org/problem?id=2039

解释下题意，一个简单的字符串加密解密实现，给出了算法，让你实现，这里是给出一个数字和加密的字符串让你解密。

解释下加密算法，将字符串写成一个矩阵，依次由上到下，由左到又，加密后的字符串就是横着读的结果，单数行正着读，双数行反着读。这里搞懂了就不难了，这样的题难在矩阵参数的判断。

前面我也纠结了好久那个矩阵的排布，这里我建议先用笔在纸上，先花好理解好其关系，在来解题不急。

代码如下：

/*Problem: 2039		User: awq123
**Memory: 248K		Time: 0MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;

int main()
{
    int n,m;
    char data[205][25],str[205];
    while(cin>>n)
    {
	if(n==0)
	    break;
	cin>>str;
	int l=strlen(str);
	m=l/n;
	for(int i=0;i<l;i++)
	{
	    if((i/n)%2==0)
	        data[i/n][i%n]=str[i];
	    else
	        data[i/n][n-1-i%n]=str[i];
	}
	for(int i=0;i<n;i++)
	{
	    for(int j=0;j<m;j++)
	        cout<<data[j][i];
	}
	cout<<endl;
    }
}

交换你的Caps-Lock和右Control键

发表于 2013-04-07 更新于 2022-03-12

前阵子，无意中在网上发现一篇文章Effective Emacs中文版，第一条就是说把Caps-Lock和Control键互换，作者是这样说的：

条款1：把Caps-Lock和Control键互换！
在Windows和苹果Mac键盘上，那个Ctrl键居然被远远地放在左下角，而Ctrl对于emacs的使用却是时时刻刻都很重要的，
如果你不把Ctrl放到一个更舒服的位置，你就很难成一个emacs艺术大师了。这位置应该与你的基本手位处于同一行，
那么，Caps Lock是最佳选择。在很多unix工作站上，这个位置放的就是Ctrl键，原因同上。

我觉得说的挺有道理的，于是乎，赶紧照着说明把caps lock键和右ctrl键交换过来了，右ctrl键使用的更少，你还可以把caps lock键和右ctrl键旁边的那个右键菜单键，那个键使用的更不频繁。交换方法如下：(以下方法是交换caps lock键和左ctrl键)

要想在w2000或者XP中实现这个互换，需要修改注册表。从开始菜单中选择“运行”，输入regedit。在左边的树状视图中，找到：
HKEY_LOCAL_MACHINESYSTEMCurrentControlSetControlKeyboard Layout
点击 KeyboardLayout 项，使之获得焦点。再从“编辑”菜单中选择新建一个二进制值，命名为 "Scancode Map"，它的类型应该显示为 REG_BINARY。
然后选择这个新建的"Scancode Map"值项，用“编辑”菜单中选择修改二进制值，在二进制编辑对话框中，输入下列数据：
 0000: 00 00 00 00 00 00 00 00
 0008: 03 00 00 00 3A 00 1D 00
 0010: 1D 00 3A 00 00 00 00 00
 
选择OK关闭对话框，退出注册表编辑器，注销后重登入，你的caps和ctrl键应该就互换成功了。也可能要重启一次。
 
在linux的X-Window中，可以使用xmodmap工具。在你的主目录新建一个名字为.xmodmap的文件，如果已经存在则只需修改。向该文件加入下列内容：
 !
 ! Swap Caps_Lock and Control_L
 !
 remove Lock = Caps_Lock
 remove Control = Control_L
 keysym Control_L = Caps_Lock
 keysym Caps_Lock = Control_L
 add Lock = Caps_Lock
 add Control = Control_L
保存，再向你的 /etc/rc.local 文件加入一行：
xmodmap ~/.xmodmap 2>/dev/null
 
在Mac OS X（Panther或Jaguar）中，你得安装一个修改过的键盘驱动，这说来有些吓人，但是很有效。
这儿有个关于驱动的讨论：
http://www.macosxhints.com/article.php?story=20031102032521826
如果你用的不是Mac笔记本，好像有一个XML文件可以编辑来实现，可以参考这儿：
http://www.eecs.wsu.edu/%7Eschneidj/mac-os-x-10.3.html#swap
下面的URL有一条关于在其它系统上实现的信息：
http://www.manicai.net/comp/swap-caps-ctrl.html

刚开始的时候特别不习惯，因为要用左小拇指来按那个caps lock键，而左小拇指不太容易用力，其中比较难按的键有Ctrl+A，Ctrl+S，Ctrl+Q，Ctrl+Z，主要是那些与caps lock键离的很近的键，不过天将降大任于斯人也，必先苦其心志阿，我经过几天的折磨我的左小拇指，终于能非常熟练的把caps lock键当ctrl键使了，确实方便多了，敲caps lock键的时候，手根本不需要离开键盘区域，特别方便，我现在到别人的机器上，去按Ctrl键，感觉好不习惯，明显觉得Ctrl键比caps lock键难按多了，:)当然, 并不是只有用emacs才需要交换这两个键, 不用emacs的话当然也可以交换, 毕竟快捷键基本上都是以Ctrl键开头的.

xfce双显示屏配置

发表于 2013-04-07 更新于 2022-03-12

最近一直用xfce，的确感觉到了相比gnome时的轻量，最近老感觉自己笔记本的显示面积小了。所以试了下双显示屏设置

xfce不像gnome shell中一样在设置里就可以轻易的修改两个屏幕的平铺，

首先我们打开显示设置，开始–>设置–>设置管理器–>显示，启用两个显示器
xfce

然后打开终端输入

xrandr

你会得到类似这样的输出结果

::txt
Screen 0: minimum 320 x 200, current 2806 x 900, maximum 2806 x 2806
LVDS connected 1366x768+1440+0 (normal left inverted right x axis y axis) 309mm x 174mm
   1366x768       60.1*+
   1280x768       60.1 +
   1280x720       60.1 +
   1024x768       60.1 +
   1024x600       60.1 +
   800x600        60.1 +
   800x480        60.1 +
   720x480        60.1 +
   640x480        60.1 +
DFP1 disconnected (normal left inverted right x axis y axis)
CRT2 connected 1440x900+0+0 (normal left inverted right x axis y axis) 410mm x 256mm
   1366x768       59.9 +
   1440x900       59.9*+
   1280x1024      75.0     60.0  
   1280x960       60.0  
   1280x800       75.0     60.0  
   1152x864       75.0     60.0  
   1280x768       59.9  
   1280x720       60.0  
   1024x768       75.0     70.1     60.0  
   1024x600       60.0  
   800x600        72.2     75.0     70.0     60.3     56.2  
   800x480        60.0  
   720x480        60.0  
   640x480        75.0     72.8     60.0

这里可以看到自己的两个显示器的名称，分别在connected前面没，我的是LVDS和CRT2，这里记住这两个单词

最后我们在终端输入

xrandr –output LVDS –left-of CRT2
[
请根据你的具体情况修改参数，这样你会发现，完美的平铺两个桌面了，

PS：这里如果你是长期使用两个显示器的人可以考虑添加一个启动项来实现开机自动双显示器平铺～

POJ3624 Charm Bracelet C++版

发表于 2013-04-07 更新于 2022-03-12

题目链接：http://poj.org/problem?id=3624

标准01背包问题，利用动态规划解题。

大概题意：有n件物品和一个容量为m的背包。第i件物品的重量是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。（来自百度百科）

用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]} 。可以压缩空间，f[v]=max{f[v],f[v-c[i]]+w[i]}

这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f [i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。

转移方程还有点难理解的，改天多研究下。
代码如下：

/*Problem: 3624		User: awq123
**Memory: 364K		Time: 344MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cstdio>
using namespace std;

int max(int a,int b)
{
    return a>b?a:b;
}
int main()
{
    //freopen("in.txt", "r", stdin);
    int c[3500],w[13000],f[13000];

    int n,m;
    cin>>n>>m;

    for(int i=1;i<=n;i++)
	cin>>c[i]>>w[i];

    for(int i=1;i<=n;i++)
	for(int v=m;v>=c[i];v--)
	    f[v]=max(f[v],f[v-c[i]]+w[i]);

    cout<<f[m];
}

POJ 2623 Sequence Median C语言版

发表于 2013-04-07 更新于 2022-03-12

题目链接：http://poj.org/problem?id=2623

这个题目不难，基本的快速排序，算法可以参考我的一篇文章《快速排序的C++表现》，但是还是有两个小细节是我没注意到的：

1：44行我原本有那个的float型的可以一直WA，不知道为什么，后来参考别人的代码才发现用double就好了，
2：文章中输出有这样一句要求：

You should print the value of the median with exactly one digit after decimal point.

就算是整数，也要保留一位小数，也就是在后面输出个“.0”

下回要注意审题了，呵呵！

代码如下：

/*Problem: 2623		User: awq123
**Memory: 1156K		Time: 250MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cstdio>
using namespace std;

int num[250020];
void quicksort(int s,int e)
{
	if(e-s<1)
		return;
	int i=s,j=e;
	int tmp=num[s];
	while(i<j)
	{
		while(i<j&&num;[j]>tmp)
			j--;
		if(j>i)
			num[i++]=num[j];
	
		while(i<j&&num;[i]<tmp)
			i++;
		if(i<j)
			num[j--]=num[i];
	}
	num[i]=tmp;
	quicksort(s,i-1);
	quicksort(i+1,e);
}

int main()
{
	//freopen("in.txt", "r", stdin);
	int n;
	scanf("%d",&n;);
	for(int i=0;i<n;i++)
		scanf("%d",&num;[i]);
	quicksort(0,n-1);
	//for(int i=0;i<n;i++)
		//printf("%d ",num[i]);
	if(n%2==0)
		printf("%0.1lf",((double)num[n/2]+(double)num[n/2-1])/2.0);
	else
		printf("%d.0",num[n/2]);
}

UBUNTU下双显示器设置

发表于 2013-04-07 更新于 2022-03-12

ubuntu（GNOME）现在已经能很好的处理双屏了，无论是克隆方式还是扩展方式！
但有时我们需要一个不同的管理器如awesome、fluxbox这类简单的窗口管理器中又如何设置成双显呢？其实也很容易－－xrandr就可以了！

1、了解设置的名称

直接运行xrandr（不带任何参数）就可以显示出当前的显示设备及设备的模式。如，笔记本会显示出LVDS和VGA。要留意LVDS及VGA的名称，如有的可能显示是LVDS1和VGA1！这就是显示设备的名称，下面会用到。

2、测试你的配置文件xorg.conf的内容是否支持多显！可以运行：

xrandr –output VGA –right-of LVDS –auto
测试下你的系统关于显示设备是否正确，如果提示超出屏幕大小限制，一般是因为xorg.conf设置有问题，可以在Section “Screen”中添加一虚拟屏的设置（粗体部分）：
Section “Screen”
Identifier “Default Screen”
Monitor “Configured Monitor”
Device “Configured Video Device”
SubSection “Display”
Virtual 2560 1024
EndSubSection
EndSection

注：2560 1024是因为一个屏是1280＊800（笔记本液晶），另一个是1280＊1024（液晶显示器），宽取二屏之和，高取二者中最大值。
提示：有人说可以把此处设置的更大一些，不必根据当前的二个屏宽高，直接设到如4000x2000，这样以后外屏改变也不必重新设置xorg.conf的这段内容了，没试过所以这里仅仅提示一下！

3、xrandr常用命令（这里的VGA与LVDS分别换成第1步中的设备名，如VGA1、LVDS1）：
xrandr –output VGA –same-as LVDS –auto
打开外接显示器(–auto:最高分辨率)，与笔记本液晶屏幕显示同样内容（克隆）
xrandr –output VGA –same-as LVDS –mode 1280x1024
打开外接显示器(分辨率为1280x1024)，与笔记本液晶屏幕显示同样内容（克隆）
xrandr –output VGA –right-of LVDS –auto
打开外接显示器(–auto:最高分辨率)，设置为右侧扩展屏幕
xrandr –output VGA –off
关闭外接显示器
xrandr –output VGA –auto –output LVDS –off
打开外接显示器，同时关闭笔记本液晶屏幕（只用外接显示器工作）
xrandr –output VGA –off –output LVDS –auto
关闭外接显示器，同时打开笔记本液晶屏幕（只用笔记本液晶屏）

北京ITAT的点点滴滴

发表于 2013-04-07 更新于 2022-03-12

本来想每天写一点的，想想还是等回来一起写吧，总的来说这次参加比赛，带免费旅游还是很爽的，

第一天，本来7点应该到的火车，因为晚点8点多才到，来到报道的酒店，人真多，忙忙碌碌一上午就混过去了，到中午酒店安顿好了，也就出来逛逛，也不敢多走，必定第二天还要比赛呢，

第二天，参加比赛，题目还是可以接受的，没有想象中的那么难，第一题我用的枚举，第二和第三，都是用的DFS，不过啊第三题，自己想漏了点东西，后来想起来了，悲剧ing，考完出来都是2点了，在北科大转了转，来到走天安门，碰巧还遇到降旗，升期是没有了，反着看也差不多吧，天安门下看看毛爷爷，还是有点味道的，呵呵，

阅读全文 »

12-9 一点小感想

发表于 2013-04-07 更新于 2022-03-12

下个星期就要去北京了，参加itat的决赛，其实这个比赛含金量真的不高，不过公费旅游还是不错滴，但愿能得到一个好的名次，最近想看看算法的书，借了本algorithms（中文的啦！哥英语压力大！），可以怎么也看不进，我还是老样子，学不进的时候木有办法，也是偶然的机会认识了db89，这也算是我开设这个站点以来结交的第一个朋友了，正如关于里说的，我希望通过这样一个平台分享自己的点滴结交更多的朋友，很巧的是db89主攻linux方向，有机会自己也要想他多学习啦！

PS：昨天调整分区windows和linux大小的时候，出了点意外，伤不起啊，哥以前写的小软件都木有啦，忙了一天就搞两个系统的安装，到现在，总算回复我原来的开发环境了，果然备份vim配置还是有点用的！