Welcome to here

简单即生活

我的操作系统

2014-10-16

OS
终于成功了
- 终于成功了
上面的图床程序坏了，所以，没有什么价值了。

下面的OS专题需要我们好好研究了。

DIY OS
Read All
再出发

2014-10-15

mood

mood

##时隔三个月，重新开始写博客时间回流三个月，那时的自己还信心满满的准备ACM，谁能想到现在的自己居然没有目标了确切的讲，不是自己没有目标，而是自己过多参考了别人的意见。有句话说的好，20多岁的年龄，最不想成为的就是自己。接下来的路，简单而又迷茫，我想走linux相关的技术路线，还有考研的想法，其实张老师对我已经很好了，走她的方向并做她的研究生。我自己也知道这是一个别人不曾拥有的机会，可是，你知道有个成语叫“一见钟情”吗？大胆的追求你喜欢的…工作和爱情吧

Read All

1.问题描述

自己使用Debian系统也已经很长时间了，触摸板是一直无法使用，感觉没什么大问题也就得过且过，最近发现触摸板上的单击键不太灵敏了，这才觉得这样下去不是办法，于是乎，google了一下，发现问题是如此的简单，在这里，分享给需要帮助的朋友。系统： Debian Wheezy Xfce

2.解决过程

1.首先，保证安装了 synaptics驱动
sudo apt-get install xserver-xorg-input-synaptics
2.复制 /usr/share/X11/xorg.conf.d到 /etc/X11
sudo cp -R /usr/share/X11/xorg.conf.d /etc/X11
3.将原 /etc/X11/xorg.conf.d/10-evdev.conf配置文件中的 TouchPad相关的部分修改如下：
Section "InputClass"
	Identifier "evdev touchpad catchall"
	MatchIsTouchpad "on"
	MatchDevicePatch "/dev/input/event*"
	Driver "synaptics"
	Option "TapButton1" "1"
	Option "TapButton2" "2"
	Option "TapButton2" "3"
EndSection

3.重启系统

reboot

这样就解决了困扰我很久的在 Debian Wheezy Xfce上触摸板无法使用的问题
[参考原文](www.linuxdc.com/Linux/2013-07/87680.htm)

Read All

暂时不熟悉的用法

暂时不熟悉的用法
- 宏定义：
  - define L(x) (x«1)//将x乘以2
  - define R(x) (x«1|1)//将x乘以2加1，注意后面|1就是加1,其他的不一定正确
hdu 1166我居然挂了20多次

宏定义：

define L(x) (x«1)//将x乘以2

define R(x) (x«1|1)//将x乘以2加1，注意后面|1就是加1,其他的不一定正确

线段树的深度为log2(b-a+1) 线段数组基本知识： 1.通常我们用lowbit(x)表示x对应的2^k; 2.lowbit(x)=x&(-x); 3.lowbit(x)实际上就是x的二进制表示形式留下最右边的1，其他位都变成0 数组a对应的线段数组应该是C[i]=a[i-lowbit(i)+1]+…+a[i]

hdu 1166我居然挂了20多次

hdu 1166 虽然是一个人的战场，但你永远不会独行！you nerver go alone! 线段树的简单使用可以用以下模板，高级还需自己慢慢领会

下面是基于线段树结构的代码

#include<cstring>
#include<cstdio>
#include<iostream>
#define lson t<<1,l,m
#define rson t<<1|1,m+1,r
#define MID(x,y) (x+y)>>1
#define N 50010
using namespace std;
int st[N<<2];
void PushUp(int t)
{
	st[t]=st[t<<1]+st[t<<1|1];

}
void build(int t,int l,int r)
{
	if(l==r)
	{
		scanf("%d",&st[t]);
		return ;
	}
	int m=MID(l,r);
	build(lson);
	build(rson);
	PushUp(t);
}
void display(int t,int l,int r)
{
	if(l==r)
	{
		printf("%d->",st[t]);
		return ;
	}
	int m=MID(l,r);
	display(lson);
	display(rson);

}

//p is where of update,add is value,**
//i don't understand clearly
void update(int p,int add,int t,int l,int r)
{
	//找准一个条件即可，如此递归下去就成了
	if(l==r){
		st[t]+=add;
		return ;
	}
	int m=MID(l,r);
	if(p<=m)
		update(p,add,lson);
	else
		update(p,add,rson);
	PushUp(t);

}
//more argument more clearly,L and R is Query from to
int getSum(int L,int R,int t,int l,int r)
{//区间在最左侧或最右侧/不理解,还有，每个结点的ret要清0，由分支再求和
	//求和的函数确实难以理解
	//For example,get sum(1,3),肯定要分支才行，下面用笔画画
	if(L<=l && r<=R)
	{

	return st[t];
	}
	int m=MID(l,r);
	int ret=0;
	if(L<=m)
		ret+=getSum(L,R,lson);
	if(R>m)
		ret+=getSum(L,R,rson);
	return ret;

}
int main()
{
	freopen("in.txt","r",stdin);
	int k;
	int j,p,q,n;
	char str[6];
	scanf("%d",&k);
		for(int j=1;j<=k;j++){
			scanf("%d",&n);
				build(1,1,n);
			//	display(1,1,n);
			printf("Case %d:\n",j);
			while(scanf("%s",str)&&str[0]!='E'){
				scanf("%d%d",&p,&q);
				switch(str[0]){
					case 'Q':
						{
	//						printf("Query %d %d\n",p,q);
							printf("%d\n",getSum(p,q,1,1,n));
						}
						break;
					case 'S':
						{
	//						printf("Sub %d %d\n",p,q);
							update(p,-q,1,1,n);
	//						display(1,1,n);
						}
						break;
					case 'A':
						{
	//						printf("Add %d %d \n",p,q);
							update(p,q,1,1,n);
	//						display(1,1,n);
						}
						break;
				}
			}
		}

	return 0;
}

这是树状数组的做法，参考了

树状数组;

#include #include using namespace std; int st[50005]; //2^k==lowbit(x) int lowbit(int a) { return a&(-a); } void update(int p,int val,int N) { while(p<=N) { st[p]+=val;//主要是向后衍生使用的 p+=lowbit(p); }

} int getsum(int p) { int res=0; while(p){ res+=st[p]; p-=lowbit(p); } return res;

} void display(int n) { for(int i=1;i<=n;i++) printf(“%d “,st[i]);

} int main() { freopen(“in.txt”,”r”,stdin); int k,n,x; int p,q; char str[5]; scanf(“%d”,&k); for(int j=1;j<=k;j++){ memset(st,0,sizeof(st)); printf(“Case %d:\n”,j); scanf(“%d”,&n); for(int i=1;i<=n;i++) { scanf(“%d”,&x); update(i,x,n); }

	while(scanf("%s",str)&&str[0]!='E'){
		scanf("%d%d",&p,&q);
		if(str[0]=='A'){

			update(p,q,n);

		}
		if(str[0]=='S'){
			update(p,-q,n);
		}
		if(str[0]=='Q'){
			printf("%d\n",getsum(q)-getsum(p-1));
		}
	}

Read All

DP简介

2014-07-16

algorithm

LIS(最大上升子序列)
- 2016.08.18
- hdu 1087

这儿有两种方法处理，一个称为自顶向下，另一个称为自下向顶.前者称为可记忆化，后者被称为动态。

在动态规划中，所有的子问题(即使没用到的)被解决，但是在递归中，只有要求到的子问题被解决。

LIS(最大上升子序列)

这个问题是从一个给定的字符串中，找到一个最大的上升子序列。很经典的dp，状态转移方程

Opt[i]=max{1，Opt[j]+1};{A[j]<=A[i],1<=j<i}

其实自己连什么是LIS都不知道，是指序列中从小到大的个数，不用管其在序列上是否为连续的。

L(i)={1+Max(L(j))} where j<i and arr[j]<arr[i] and if there is no such j then L(i)=1

我的问题是自己能隐隐约约体会到其中一点的转移，但是在代码实现上就麻烦了，自己始终不能流畅的写出来。最后想了想，其实上面的状态转移方程还是不太容易理解，网上有个是这么说的maxlen[i]=(max(maxlen[k],1,2,3..k..i-1&&str[k]<str[i])+1) a下面代码中m可以堪看成临时变量temp，它的作用就是搜索maxlen[i]前面最大的dp[i] ,想明白了这道，hdu 1087也就1y了

2016.08.18

已经过去很长时间了，算法这块的难处还是很难啃的。正如上面讲的，自己最欠缺的地方是如何将状态转移方程写成代码的能力，这一点不是其他外力就能控制的。

伪代码如下：

LS[1] = 1
for i from 1 to n
	m=LS[i]
	for j from i-1 to 0
		a[i]>a[j] && LS[j]>m
			m=LS[i];
	LS[i]=m+1
	max{LS[i]}

/*
 *     File Name: dp_lis.c
 *     Author: Bo Yu
 *     Mail: [email protected]
 *     Created Time: 2016年08月18日 星期四 02时52分56秒
 */
/*
 *     关于动态规划的入门题
 *     求一个数列的最大上升子序列
 状态方程：
 *L(i) = { 1 + Max ( L(j) ) } 
 where j < i and arr[j] < arr[i] and if there is no such j then L(i) = 1
 *
 */
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int LS[100];
int LIS(int a[], int n)
{

	int ans = 1, m, i, j;
	LS[1] = 1;
	
	for(i = 1; i < n; i++){

		m = LS[i];/*Reset m==0 */

			for( j = i - 1; j >= 0; j --)
				if(a[j] < a[i] && LS[j] > m)
					m = LS[j]; /*寻到前面的最大LIS*/
		/*从前面(i-1)个LS中加上1*/
		LS[i] = m + 1;
		/*找寻最大的LS*/
		if (LS[i] > ans)
				ans = LS[i];

	}
	return ans;
}
int main()
{
	int a[10] = {10, 22, 9, 33, 21, 50, 41, 60, 80};

	/*int a[20] = {5,7,6,1,3,9,5,3,4,1,4,5,6,7,8};*/
	memset(LS, 0, sizeof(LS));
	int k = LIS(a, 9);
	printf("THE LIS is %d\n", k);


}

代码时间复杂度是O（n^2）,并且n<=12000,并不是最优的。

hdu 1087

#include<cstring>
#include<cstdio>
#include<iostream>

using namespace std;
int dp[1001];//less than 12000
int a[1001];
int LIS(int* a,int n)
{
	int ans=1,m//m是临时变量;
	dp[1]=1;
	for(int i=2;i<=n;i++)
	{
		m=dp[i];//?

		for(int j=i-1;j>=1;j--)
			
			if((a[j]<a[i])&&(dp[j]>m))
				m=dp[j];
			dp[i]=m+1;

			if(dp[i]>ans)
				ans=dp[i];
	}
	return ans;

}
int main()
{
	freopen("in.txt","r",stdin);
	int k;
	int n;

	scanf("%d",&k);//数据组数
	while(k--){
		memset(a,0,sizeof(a));
		memset(dp,0,sizeof(dp));
		scanf("%d",&n);//每组数列的个数
		for(int i=1;i<=n;i++)
			scanf("%d",&a[i]);
		int k=LIS(a,n);
		printf("%d\n",k);
	}
}

Read All

计划

2014-07-15

plan

#简单的总结

现在已经是2014年7月15日，放假已经快两周了，现在的练习怎么样了，只能由自己慢慢体会了。不过，今天倒是在动态规划的LIS理解上给自己一针鸡血，希望自己继续努力下去。现在开始看01背包

Read All

88/90

Welcome to here

我的操作系统

终于成功了

再出发

Debian解决触摸板无法使用的问题

1.问题描述

2.解决过程

3.重启系统

线段树

暂时不熟悉的用法

宏定义：

define L(x) (x«1)//将x乘以2

define R(x) (x«1|1)//将x乘以2加1，注意后面|1就是加1,其他的不一定正确

hdu 1166我居然挂了20多次

DP简介

LIS(最大上升子序列)

2016.08.18

hdu 1087

计划