google code jam2016资格赛题解

A. Counting Sheep
小数据暴力呗。大数据也一样。。
B. Revenge of the Pancakes
小数据暴力呗。大数据没做。。
C. Coin Jam
小数据暴力呗。大数据没做。。
D. Fractiles
题意:一个序列由两种字符组成:L、G.给出k,c,s。表示序列初始长度k,变换了c次。每次变换:L的地方用最初始序列代替,G的地方用k个G代替。
现序列各个位置的值是看不到的,你可以选择查看其中的s个位置的值。问:能否通过小于等于s次查看,来推断出现序列是否包含G。
这题我是这样做的。小数据大数据一个做法。
如果查看一个位置发现是G,那么我们就知道序列是含有G的了,所以问题其实是在问:有没有一种查看的策略使得在查看的值都是L的情况下,可以断定序列必定没有G。
我们可以把整个变换的过程画出来,可以发现是一棵k叉树(注意一点这里我把原始序列的k个结点最为统一的“根结点”)。叶子节点是现序列。关键一点在于当得到了位置pos的值是L之后,我们就知道了pos位置的值是L之后,就知道了pos的父节点是L,它的父节点也是L。换言之,pos到树根的路径上的结点都是L。
那么为了尽可能通过一次查看得到最多信息,我们可以查看根节点的第二个子结点的第三个子结点的…………(一直到叶子结点)的值。这样就得到了min(c,k)个连续位置的值,接下来重复这个查看过程就行。
这个还是有个图比较好解释。。下次加个图。

linux内核模块编程笔记

最近因为实验室项目,开始接触了一点linux内核模块编程
内核编译选项.config所在路径:/usr/src/相应内核版本/.config
内核符号表:在编写内核模块的时候,因为LKM是动态加载到内核中,也就是说这时的内核是在内存中运行的,所以正确获取内核函数和变量的地址很重要。如果我们在内核模块中直接将地址写死,那么显然不通用,在另一个内核上可能地址就变了。内核符号表就是用于解决这个问题。每个内核都有其内核符号表,里面是内核导出的符号及其地址。我们编写的内核模块通过访问这个内核符号表就可以得到当前正在运行的内核的可用函数和变量的确切地址。
那么怎样使用内核未导出的符号呢?
我们可以使用kallsyms_lookup_name(char*)这个函数,该函数参数是符号名,返回unsigned long型的函数/变量地址。这个方法有个前提,那就是kallsyms_lookup_name(char*)这个符号本身是被内核导出的,所以要用CONFIG_KALLSYMS=y来编译内核,或者修改内核源码中的kallsyms.c文件,增加EXPORT_SYMBOL(kallsyms_lookup_name);手动将该符号导出
————————————————————————————————————————————————————————————————————————————
过程中的问题和要点:
linux内核的三种内存模型
page结构中的_count和_mapcount
_mapcount:在页表中每增加一个映射项,_mapcount就加1.初始值是-1

虚拟化笔记

VMM进程地址空间中存储了各个虚拟机具体的硬件环境(如PC值、EAX值等等,PC值指向guestOS的代码),guestOS在运行时(其实就是VMM将真实寄存器等硬件环境改为guestOS的环境,PC改为指向guestOS的代码,这样guestOS的代码就开始运行了),其代码是真正运行在真实cpu上的,由于guestOS是在ring3,所以执行特权指令时触发异常,VMM的异常处理模块截获异常,然后再做安排。

Node.js资料临时记录

文档:http://docs.run.pivotal.io/starting/index.html
web应用控制台:https://console.run.pivotal.io
关于manifest.yml文件:http://docs.run.pivotal.io/devguide/deploy-apps/manifest.html#minimal-manifest
node.js的事件循环:http://blog.mixu.net/2011/02/01/understanding-the-node-js-event-loop/
node.js的初步入门:http://ourjs.com/detail/529ca5950cb6498814000005
pivotal Cloud Foundry:https://console.run.pivotal.io/organizations/0c2e2745-b6fd-4bd1-a2ec-291beb58c84e/spaces/d2b83c2c-d217-4c7a-a662-6fc3a41205e2
Cloud Foundry的Environment variable:http://docs.run.pivotal.io/devguide/deploy-apps/environment-variable.html

又是熬夜

今天偶然看到一本叫《Windows 内核安全与驱动开发》的书。。。。。。。的电子试读版,看的挺过瘾,熬夜看了半宿,现在又陷入什么都想学的状态了。。但是毕业设计都还没做啊。。

主席树

今天看了下主席树,感觉好神奇,代码精简而且实用,例如静态区间第k大之类的题,用主席树直接秒杀线段树套平衡树之类的写法。就是空间有点大。。
具体请参考:
1.clj的论文
2.博文一篇,代码写的很精炼:http://im.librazy.org/article/837/note-chairtree-via-functional-segtree/
其实很好理解的。
入门题:
hdu2665
静态区间第k小,注意题目描述可能不恰当。。

1020

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define inf 1000000000
int dest[15];
int dist[100000][100000];
int ans,s;
bool visit[15];
void dfs(int pre,int cur,int len,int cnt)
{
	int i;
	if(cur!=0)
		visit[cur]=1;
	len+=dist[pre][cur];
	if(cnt==s)
	{
		len+=dist[cur][0];
		if(len<ans)
			ans=len;
		return;
	}
	for(i=1;i<=s;i++)
	{
		if(!visit[dest[i]])
		{
			dfs(cur,dest[i],len,cnt+1);
			visit[dest[i]]=0;
		}
	
	}
	return;
}
int main()
{
    int t;
	int i,j,k;
	scanf("%d",&t);
	while(t--)
	{
		int n,m;

		scanf("%d %d",&n,&m);
		for(i=0;i<=n-1;i++)
			for(j=0;j<=n-1;j++)
				if(i==j)
					dist[i][j]=0;
				else
					dist[i][j]=inf;
		int a,b,w;
		for(i=1;i<=m;i++)
		{
			scanf("%d%d%d",&a,&b,&w);
			if(w<dist[a][b])
			{
				dist[a][b]=dist[b][a]=w;
			}
		}
		scanf("%d",&s);
		for(i=1;i<=s;i++)
		{
			scanf("%d",&dest[i]);
		}
		for(k=0;k<=n-1;k++)
			for(i=0;i<=n-1;i++)
				for(j=0;j<=n-1;j++)
				{
					if(dist[i][k]+dist[k][j]<dist[i][j])
						dist[i][j]=dist[i][k]+dist[k][j];
				}
		memset(visit,0,sizeof(visit));
		ans=inf;
		dfs(0,0,0,0);
		printf("%d\n",ans);
	
	
	
	
	
	}

system("pause");
return 0;
}

Intelligent IME 暂存

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct Trie{
	int v;
	struct Trie* next[27];
}Trie;
Trie* root=(Trie*)malloc(sizeof(Trie));
int 
void insert(char s[])
{
	int i,len=strlen(s);
	Trie *p=root,*q;
	for(i=0;i<=len-1;i++)
	{
		int x=s[i]-'a'+1;
		if(p->next[x])
		{
			p=p->next[x];
		}
		else
		{
			q=(Trie*)malloc(sizeof(Trie));
			q->v=0;
			for(int j=1;j<=26;j++)
				q->next[j]=NULL;
			p->next[x]=q;
			p=q;
		}
	}
	p->v=1;
	return;
}
int find(char s[])
{
	int i,len=strlen(s);
	Trie* p=root;
	for(i=0;i<=len-1;i++)
	{
		int x=s[i]-'a'+1;
		if(p->next[x])
		{
			p=p->next[x];	
		}
		else
			return 0;
	}
	return p->v;//
}
void init()
{
	int i;
	for(i=1;i<=26;i++)
		root->next[i]=NULL;
	root->v=0;

	return;
}
void del(Trie*root)
{
	int i;
	for(i=1;i<=26;i++)
		if(root->next[i])
			del(root->next[i]);
	free(root);
	return;
}
void reset()
{
	int i;
	for(i=1;i<=26;i++)
		del(root->next[i]);
	return;	
}
void dfs(char num[],int cur,int len)
{
	int i;
	
	



}
int main()
{
	int t;
	int i,j;
	scanf("%d",&t);
	while(t--)
	{
		init();
		int n,m;
		scanf("%d %d",&n,&m);
		getchar();
		char num[5010][10];
		char s[10];
		int cnt[5010];
		memset(cnt,0,sizeof(cnt));
		for(i=1;i<=n;i++)
		{
			gets(num[i]);
		}
		for(i=1;i<=m;i++)
		{
			gets(s);
			insert(s);
		}
		for(i=1;i<=n;i++)
		{
			int len=strlen(num[i]);
			dfs(num[i],0,len);
		}
	
	
		reset();
	}
	
	del(root);
system("pause");
return 0;
}