ZAKIR

目前本人已购买独立主机，故暂停在is-Programmer的更新，请大家移步http://www.zkgo.info

目前已迁移到新浪SAE，用的是自己写的Blog程序，地址是http://blog.wamaker.net

今年我们很荣幸地参加了ACM杭州赛区的比赛，以下的比赛总结，希望对今后参赛的同学能有所帮助。

    2010年10月22日，我们Triplz和Sauce一起踏上杭州之旅，经过一路火车的颠簸次日中午到达上海并转车到杭州。之后入住宾馆，修整了一下。

    23日，大雨，早上参观阿里巴巴在杭州的总部，此次略去。下午练习赛，比预计时间晚开了半个多小时，开始后看了下环境，有Netbean和Eclipse，唯独没有Vim。热身赛总共三个题，第一题水仙花数，瞬间过掉。第二题给出点求六边形数目，郑臻哲一开始想复杂了，跟张龙攀讨论之后得到一种比较直观的方法，最终改掉一个=和==的错误后在最后几分钟过掉。第三题理解题意花了不少时间，看懂以后认为是字典树，但有些复杂的转化没搞清楚，热身赛结束也没能解出来，之后据说暴力就能过。

热身赛后，我们拿着两个气球表示压力巨大！回到宾馆后便开始整理模板，把所有书都翻了一遍就洗洗睡了。

    24日，大雨，上午9点比赛正式开始，张龙攀看前三题，郑臻哲看中间三题，我看最后四题。最后一题我看了一眼觉得是个简单的字符串概率题，看完题目就立马上机敲了一下，跑第二组样例时才发现有很多重复的情况没有考虑。张龙攀表示全场过得最多的H题有思路，于是让他敲H题，敲完后提交WA了一次，改了个低级错误就过了。期间我一直在纠结最后一题重复情况的处理，等张龙攀敲完H后，我们讨论了一下，发觉要用自动机DP求解，我就把题交给张龙攀来想，自己去看别的题。郑臻哲发现现场很多队伍过了C题，于是就看了一下，产生了一个比较暴力的思路，我们都觉得复杂度太高了应该开不了，而且要开一个1000*1000*1000的bool数组，但幸好早上看教练通知上说比赛内存不限。当时确实也没别的题可写，就让郑臻哲去试试，第一次提交因为cin超时了，后来用scanf返回了WA，也就是说复杂度应该没问题。但改了几次后仍然是WA，期间我一直在想一个图论的题，郑臻哲拿了打印的代码让我看一下，我扫一眼发现了一个问题：读入数字的时候用的是字符串，转为整数的时候直接拿一个字符的ASCII码值减‘0’，这在一位数的时候当然没问题，两位数以上就错了，而样例恰好都是一位数。这个问题当然很低级，但就算在基地的平时训练中也有两三个人犯过这样的错。把这个Bug改掉后C就过了。之后，郑臻哲发现F是个计算几何，张龙攀上去敲最后一题，开始思路有点乱WA了几次，最后用自动机过掉了。最后一个多小时，郑臻哲上去敲计算几何，但是由于时间太紧压力过大，虽然敲出来了，但没能顺利过掉。最终比赛结束，拿到了三个气球。

      这次比赛暴露了我们的许多问题，首先，就我个人而言，平时只研究图论和数据结构方面的题目，而这次比赛的图论题太难，全场也没多少队能过，队友在写DP和计算几何时我想帮又帮不上。所以想给下几届的同学一个忠告：在成为全能选手之前不要只专一个方向；其次，对一些基本问题的理解不够透彻，郑臻哲写的计算几何题需要求图形的重心，由于之前没写过，只好在黑书临时找算法。结果黑书上的算法要用的是有向面积而模板上确把叉积的计算取绝对值了，回来之后把绝对值去掉在杭电上一交就通过了；最后，心理素质和编码能力不行，关键时刻老犯低级错误，把时间浪费在调试和罚时上。

       虽然很遗憾，2010赛季终究是结束了，TripleZ只拿到了铜牌一枚。在此，特别感谢张老师对我们队的支持，感谢基地同学们一直以来对我们的关心与帮助。谢谢大家！

       刚回来就听说操作系统要上机，内容是给linux系统添加一个系统调用，依据参数是否大于0返回两个数。表示毫无思路，Google了一下，发现网上的教程很多（难道各学校的作业都一样么？），但是写的都比较烦而且用的内核都比较旧，有些步骤在新内核的编译是没必要的。按照他们写的来做把我纠结死了，所以搞成了以后打算写一个简易的新的教程，希望让后人能少走些弯路。

环境：Ubuntu 10.04

准备工作：Linux内核（在这里可以下载，我用的是2.6.36）。

具体步骤：

Step 1:使用root权限，没有设置root的可以执行以下命令来设置密码

sudo passwd root

输入su和密码获取root权限。

su

Step 2：把内核压缩包移至/usr/src，并解压

mv linux-2.6.36.tar.bz2 /usr/src
tar -jxvf linux-2.6.36.tar.bz2 

Step 3: 修改内核，共需修改3个文件。就如同小区里新搬进一家住户，首先去物业那里注册一下，获得门牌号（这号是连续的，在定义编号的时候杯具了一回）。

gedit /usr/src/linux-2.6.36/arch/x86/kernel/syscall_table_32.S

打开以后，在最后添加

.long sys_mysyscall

你的新调用的编号就是上一行的编号+1，记住这个编号，后面要用。

接下来写函数的实现，就相当于把家具搬进去。

gedit /usr/src/linux-2.6.36/kernel/sys.c

在最后添加

asmlinkage long sys_mysyscall(int number)
{
	if(number>0)return 123456
	else return 654321;
}

最后，为了方便访客，还需要到传达室的王大爷那儿登记一下，这样以后访客只要报上你的名字就可以知道你家的门牌号了。

gedit /usr/src/linux-2.6.36/arch/x86/include/asm/unistd_32.h

最后添加

#define __NR_mysyscall 341       //这341是之前记下的那个编号

Step 4:利用root权限进入/usr/src,清除以前编译的内核，第一次编译的话可以跳过

make mrproper

Step 5：定制内核。

make menuconfig

刚装的系统可能会缺少ncurse库而导致这一步失败(没有跳出一个蓝色的窗口)，从网上下一个ncurse.tar.gz，解压后进入解压出来的文件夹，依次执行

./configure
make
make install

Step 6:编译内核！！！利用root权限在/usr/src/linux-2.6.36/下

make

漫长的等待（在虚拟机耗了一个多小时）

Step 7：生成文件并安装内核

make modules_install
make install

Step 8：生成引导文件

mkinitramfs -o initrd.img-2.6.36 2.6.36

完成以后将生成的initrd.img -2.6.36复制到/boot

mv initrd.img-2.6.36 /boot

Step 9：更新引导列表

update-grub

Step 10：重新启动

启动完以后在终端执行

uname -a

看看你的版本号是否已经变成2.6.36 。成了的话就恭喜了！

Step 11：测试

编一个测试程序：

#include<stdio.h>
#inlcude<unistd.h>

int main()
{
	printf(“%d\n%d\n”,syscall(341,1),syscall(341,0));//这里的341是之前的编号，请自行更改
	return 0;
}

编译执行一下，看结果对不？

终于写完了，貌似我也写得有些繁琐了，毕竟是修改内核嘛。随着版本号和RP函数的波动，以上步骤不能保证一定能出结果，但大体原理是相同的，如果有童鞋杯具了。。。多Google多试几次。。。。

        本来想把这题放在Splay学习笔记里的，但是这题卡了我一天，而且网上解题报告很少，所以我单独拿出来写一篇报告吧。

题意：给出一个无序序列，请用翻转的方法给它排序：翻转的起点依次递增，输出每次翻转的终点。比如3 4 5 1 6 2这个序列，最小的元素在4位置，第一遍排序的时候以1为起点4为终点转后为1 5 4 3 6 2；第二遍的时候最小的在位置6，则以2为起点6为终点转成1 2 6 3 4 5；第三遍最小的在4，旋转3 4；。。。。。。

解析：

        由于涉及到区间的翻转，所以用Splay会比较方便，用Splay树记录未最终定位的元素，中序遍历Splay树即可知道当前经过翻转后的序列，每排好一个元素，就把它从树里面删除。

        每次翻转的终点都是未排序的序列的最小元素，我们可以预处理下，把每个元素在树中的位置记录下来。然后把序列按值大小排序，依次处理每个元素。

        对于一个序列中的元素，它在Splay树中序序列里面的位置加上已排好序的元素个数就是翻转的终点。而元素在树中的位置已经记录下来了，我们只要把它Splay到根结点，统计它左子树的元素个数就是中序遍历序列在该元素左边的元素个数。

        pos(i)=i左边元素个数+已排好序的元素个数+1;

        由于i已经排好了序，把它删除即可。

        为了方便提取区间和删除，添加了一个开始端点和结束端点，因为翻转会把端点翻到左子树里面导致在统计左子树元素个数的时候令我蛋疼不已。最后不得已在节点里添加了一项记录该子树除端点以外的节点个数。如果各位网友有更好的办法，欢迎留言赐教，小弟不胜感激！

最后附上代码：

#include <cstring>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

struct IN
{
	int val,pos;
}in[100001];

bool cmp(const IN &a,const IN &b)
{
	if(a.val==b.val)
		return a.pos<b.pos;
	return a.val<b.val;
}

struct Node
{
	Node *pre,*ch[2];//前驱结点，左右孩子
	bool rev;               //标记是否被翻转
	int size,val,rsz;     //子树大小,结点的值，子树除端点以外的大小
}*root,buf[100010],*null;

Node *rec[100010];
const int INF=1<<28;
int idx,N;

Node *addNode()
{
	Node *p;
	p=&buf[idx++];
	p->rsz=p->size=1;
	p->rev=false;
	p->ch[0]=p->ch[1]=p->pre=null;
	return p;
}

inline void UpdateSize(Node *p)
{
	p->size=p->ch[0]->size+p->ch[1]->size+1;
	p->rsz=p->ch[0]->rsz+p->ch[1]->rsz;
	if(p->val!=-1)p->rsz++;
}

inline void UpdateRev(Node *p)//更新处理翻转
{
	if(p==null||!p||!p->rev)return;
	swap(p->ch[0],p->ch[1]);
	if(p->ch[0]!=null)p->ch[0]->rev=!p->ch[0]->rev;
	if(p->ch[1]!=null)p->ch[1]->rev=!p->ch[1]->rev;
	p->rev=false;
}

void Init()
{
	idx=0;
	null=addNode();
	null->size=0;null->val=-1;null->rsz=0;
	root=addNode();                                //此处添加了两个端点
	root->ch[1]=addNode();root->val=-1;root->rsz=0;
	root->ch[1]->pre=root;root->ch[1]->val=-1;root->ch[1]->rsz=0;
	UpdateSize(root);
}

void Rotate(Node *x,int c)
{
	Node *y=x->pre;
	y->ch[!c]=x->ch[c];
	if(x->ch[c]!=null)
		x->ch[c]->pre=y;
	x->pre=y->pre;
	if(y->pre!=null)
		if(y->pre->ch[0]==y)
			y->pre->ch[0]=x;
		else
			y->pre->ch[1]=x;
	x->ch[c]=y;y->pre=x;
	if(y==root)root=x;
	UpdateSize(y);
}

void Splay(Node *x,Node *f)
{
	while(x->pre!=f)
	{
		Node *y=x->pre,*z=y->pre;
		UpdateRev(z);UpdateRev(y);UpdateRev(x);;
		if(x->pre->pre==f)
			Rotate(x,x->pre->ch[0]==x);
		else
		{
			if(z->ch[0]==y)
				if(y->ch[0]==x)
					Rotate(y,1),Rotate(x,1);
				else
					Rotate(x,0),Rotate(x,1);
			else
				if(y->ch[1]==x)
					Rotate(y,0),Rotate(x,0);
				else
					Rotate(x,1),Rotate(x,0);
		}
	}
	UpdateSize(x);
}

void Select(int kth,Node *f)
{
	int tmp;
	Node *t=root;
	while(1)
	{
		UpdateRev(t);
		tmp=t->ch[0]->size;
		if(tmp+1==kth)break;
		if(kth<=tmp)
			t=t->ch[0];
		else
		{
			kth-=tmp+1;
			t=t->ch[1];
		}
	}
	Splay(t,f);
}

Node *Build(int l,int r)
{
	if(l>r)return null;
	int mid=(l+r)>>1;
	Node *p=addNode();
	rec[mid]=p;p->val=in[mid].val;
	p->ch[0]=Build(l,mid-1);
	if(p->ch[0]!=null)
		p->ch[0]->pre=p;
	p->ch[1]=Build(mid+1,r);
	if(p->ch[1]!=null)
		p->ch[1]->pre=p;
	UpdateSize(p);
	return p;
}

void Delete()
{
	Node *oroot=root;
	root=root->ch[1];
	root->pre=null;
	Select(1,null);
	root->ch[0]=oroot->ch[0];
	root->ch[0]->pre=root;
	UpdateSize(root);
}

void Gao()
{
	for(int i=1;i<=N;i++)
		in[i].pos=i;
	sort(in+1,in+N+1,cmp);
	for(int i=1;i<=N;i++)
	{
		Splay(rec[in[i].pos],null);
		if(root->ch[0]!=null)
			root->ch[0]->rev=!root->ch[0]->rev;
		printf("%d",root->ch[0]->rsz+i);
		if(i!=N)putchar(' ');
		Delete();
	}
	puts("");
}

int main()
{
	while(scanf("%d",&N),N)
	{
		Init();
		for(int i=1;i<=N;i++)
			scanf("%d",&in[i].val);

		Node *troot=Build(1,N);
		root->ch[1]->ch[0]=troot;
		troot->pre=root->ch[1];
		UpdateSize(root->ch[1]);
		UpdateSize(root);
		Splay(root->ch[1],null);
		Gao();
	}
	return 0;
}

//这题Gao死我了！！！

Gao

题意：Gao这个函数可以用来算出有向图中从0到达某点的最短路径条数，用Gao算出0到所有点的最短路径条数了，现问有多少条路径经过点v。输出答案的后10位。

解析：首先，这题有10000个点50000条边，对每点求最短路径是不可能的。观察最短路径以后我们可以知道，一个点v在一条最短路径里最多出现1次，要么出现在路径的末尾，要么出现在路径的中间，对于出现在末尾的最短路径数我们定义为cnt1[v]，而我们在计算0点到所有点的最短路径过程中是可以记录cnt1[v]的：

if(dis[u]+w<dis[v])                  //u->v权值为w
{
	dis[v]=dis[u]+w;
	cnt1[v]=cnt1[u];
	tmp.v=v;tmp.dis=dis[v];
	que.push(tmp);
}
else if(dis[u]+w==dis[v])
{	cnt1[v]+=cnt1[u];
	cnt1[v]%=MOD;
}

至于v出现在最短路径的中间的情况，定义cnt2[v]表示最短路径中从v出发的路径条数，那么根据组合数学定义,v出现在最短路中间的最短路径条数=cnt1[v]*cnt2[v]。cnt2[v]可以用Calc(v)进行递归计算(貌似也可以叫树形DP,好像还可以拓扑排序以后之间DP），假如有t1,t2,t3...tn与v邻接且v->t1,v->t2,v->t3...,v->tn都在最短路径上，那么同样根据组合数学加法原理有cnt2[v]=cnt2[t1]+cnt2[t2]+...cnt[tn]。因为t1,t2,tn都在最短路径上，所以cnt2[v]+=n;

最终ans[v]=cnt1[v]+cnt1[v]*cnt2[v]。

这题比较阴险的地方在于答案要保留后10位，而进行乘法的过程中会超long long（事实证明，在计算cnt1的过程中也会超long long，在这地方无限WA T_T）要用到布斯(Booth)乘法：

long long Mul(long long lhs,long long rhs)
{
	long long lhs2=lhs%100000;
	long long rhs2=rhs%100000;
	return ((lhs/100000*rhs2+rhs/100000*lhs2)*100000+lhs2*rhs2)%MOD;
}

最后贴一个完整的代码：

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;

const long long MOD=10000000000LL;

struct Edge
{
	int v,next,w;
}buf[50010];

struct Node
{
	int v,dis;
};

const int INF=1<<30;

bool operator<(Node a,Node b)
{
	return a.dis>b.dis;
}

int head[10010];
int dis[10010];
long long cnt[10010];
bool flag[10010];
int N,M,nE,Q;

void addEdge(int u,int v,int w)
{
	buf[nE].v=v;buf[nE].w=w;buf[nE].next=head[u];head[u]=nE++;
}

long long Mul(long long lhs,long long rhs)
{
	long long lhs2=lhs%100000;
	long long rhs2=rhs%100000;
	return ((lhs/100000*rhs2+rhs/100000*lhs2)*100000+lhs2*rhs2)%MOD;
}

long long add(long long a,long long b)
{
	a+=b;
	if(a>=MOD)
		a-=MOD;
	return a;
}

void Dijkstra(int src)
{
	Node tmp,cur;
	tmp.v=src;tmp.dis=0;
	for(int i=0;i<=N;i++)
		dis[i]=INF;
	dis[src]=0;

	memset(flag,false,sizeof(flag));
	memset(cnt,0,sizeof(cnt));
	priority_queue<Node> que;
	cnt[src]=1;
	que.push(tmp);
	while(!que.empty())
	{
		cur=que.top();que.pop();
		int u=cur.v,d=cur.dis;
		if(flag[u])continue;
		flag[u]=true;
		for(int i=head[u];i!=-1;i=buf[i].next)
		{
			int v=buf[i].v,w=buf[i].w;
			if(d+w<dis[v])
			{
				dis[v]=d+w;
				cnt[v]=cnt[u];
				tmp.v=v;tmp.dis=dis[v];
				que.push(tmp);
			}
			else if(d+w==dis[v])
			{	cnt[v]+=cnt[u];
				cnt[v]%=MOD;
			}
		}
	}
}

long long rec[10010];

long long Gao(int s)
{
	long long c=0;
	if(rec[s]!=-1)return rec[s];
	for(int i=head[s];i!=-1;i=buf[i].next)
	{
		int v=buf[i].v;
		if(dis[s]+buf[i].w==dis[v]&&s!=v)
		{
			c++;
			if(rec[v]==-1)
				rec[v]=Gao(v);
			c=add(c,rec[v]);
		}
	}
	return c%MOD;
}

int main()
{
	//freopen("data","r",stdin);
	//freopen("mout","w",stdout);
	while(scanf("%d%d%d",&N,&M,&Q)!=EOF)
	{
		memset(head,0xff,sizeof(head));
		memset(rec,0xff,sizeof(rec));
		nE=0;
		while(M--)
		{
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			addEdge(u,v,w);
		}
		Dijkstra(0);
		int q;
		while(Q--)
		{
			scanf("%d",&q);
			if(cnt[q]<0)while(1);
			long long ans=Mul(cnt[q],Gao(q)+1);
			ans=ans%MOD;
			printf("%010lld\n",ans);
		}
		//putchar(10);
	}
	return 0;
}