syrsteven

净月潭航线

2018-08-21

字数统计: 369字 | 阅读时长: 1min

##【问题描述】
净月潭国家森林公园是吉林省著名的5A级景区，因为公园中有一深潭而命名，这个深潭是圆形的，吉林省的OIER们要在圆潭的边上建N个码头，用以建立航线（可能为0条航线），航线只能是一个码头到另一个码头，并且多条航线之间不能相交，共用码头也算相交。请OIER们算一下，共有多少建立航线的方案？

##【输入格式】

从文件route.in中输入数据。

一行一个数N

##【输出格式】

输出到文件route.out中。

由于结果可能很大，你只需要输出这个答案mod 12345的值。

展开全文 >>

HuffmanTree

2018-08-21

字数统计: 726字 | 阅读时长: 3min

以下摘自度娘。。。

哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。
Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，
有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）。

构造方法：

⒈把n个终端节点加入优先队列，则n个节点都有一个优先权Pi，1 ≤ i ≤ n
⒉如果队列内的节点数>1，则：

⑴从队列中移除两个最大的Pi节点，即连续做两次remove(max(Pi), Priority_Queue)
⑵产生一个新节点，此节点为（1）之移除节点之父节点，而此节点的权重值为（1）两节点之权重和
⑶把（2）产生之节点加入优先队列中

⒊最后在优先队列里的点为树的根节点（root）

而此算法的时间复杂度（ Time Complexity）为O（n log n）；因为有n个终端节点，所以树总共有2n-1个节点，使用优先队列每个循环须O（log n）。

展开全文 >>

LCA

2018-07-26

字数统计: 1.2k字 | 阅读时长: 6min

在这篇博客中，主要讲三种求LCA的方法。

tarjan

#include<bits/stdc++.h>
using namespace std;
int n,q,rt;
template<typename Type>inline void read(Type &xx)
{
    Type f=1;char ch;xx=0;
    for(ch=getchar();ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())xx=xx*10+ch-'0';
    xx*=f;
}
struct node
{
	int ne,to,w;
}ed[1000010];
node e[1000010];
int head[2][500100],cnt,tot;
void add(int u,int v)
{
	ed[++cnt].to=v;
	ed[cnt].ne=head[0][u];
	head[0][u]=cnt;
}
void adde(int u,int v,int w)
{
	e[++tot].to=v;
	e[tot].ne=head[1][u];
	e[tot].w=w;
	head[1][u]=tot;
}
int fa[500100];
int get(int x)
{
	return (fa[x]==x)?x:fa[x]=get(fa[x]);
}
int vis[500100],ans[500100];
void tarjan(int x)
{
	vis[x]=1;
	fa[x]=x;
	for(int i=head[1][x];i;i=e[i].ne)
	{
		int v=e[i].to,w=e[i].w;
		if(vis[v])
			ans[w]=get(v);
	}
	for(int i=head[0][x];i;i=ed[i].ne)
	{
		int v=ed[i].to;
		if(vis[v]) continue;
		tarjan(v);
		fa[v]=x;
	}
}
int main()
{
	read(n),read(q),read(rt);
	for(int i=1;i<n;i++)
	{
		int u,v;
		read(u),read(v);
		add(u,v);
		add(v,u);
	}
	for(int i=1;i<=q;i++)
	{
		int u,v;
		read(u),read(v);
		adde(u,v,i);
		adde(v,u,i);
	}
	tarjan(rt);
	for(int i=1;i<=q;i++)
	{
		cout<<ans[i]<<endl;
	}
	return 0;
 }

展开全文 >>