lp1341 无序字母对

仔细观察这题:考虑到字母对可以反向,我们不妨把它们看作无序数对。这就把题意转化为了,给你n个无序数对,让你找到一个n+1个数的序列,使得无序数对在序列的相邻两项中各自至少出现一次。
观察到这无序数对组和图的相似性,我们可以尝试把无序数对看成一条边,然后建一张图。在这种情况下,这个序列就是这张图上的一个遍历顺序,使得经过每一条边至少一次。
深入考虑,这个序列也只能经过每条边至多一次。这是因为,一条n条边的路径,恰好包含了n+1个点。
问题就转化为了欧拉路径问题。

判断一张图是否是半欧拉图是很容易的。一张半欧拉图中,恰好有两个点的度数为奇数——这两个点各自作为欧拉路径的起点和终点。
求解欧拉回路的方法是很容易的。对于每一个点,我们只需要找到与它相邻的所有环即可。
问题在于——这很不显然——为什么相同的求法放到欧拉路径上,只需从奇数入度点开始,就是合法的?
我们不妨把整个欧拉路径抽象成一条链上面挂着一堆环套环套环套环套环。一个令人好奇的问题是,为什么搜索的时候不会直接走到链的另一端,而是先把环跑完,或者反过来?
我们注意到把点加入答案数组的方式:对于两个栈——答案栈和搜索栈来说,点被加入的顺序是不仅相同的。
模拟一下,一个点能从搜索栈出来,被加入答案栈,当且仅当从这个点出发无路可走了。
显然,有且仅有终点是无路可走的。那么,无论终点是在什么时候被访问到的,只要它被访问到,那么它就会被立刻退出搜索栈并被加入答案栈,剩下的点也是同理。

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

int hash[200];int hsah[200];
int mp[60][60],in[60];
int n;
int st[3005],tp=0;
inline void dfs(int X){
	for(int i=0;i<52;++i){
		if(mp[X][i]){
			printf("%d %d\n",X,i);
			--mp[X][i],--mp[i][X];
			dfs(i);
		}
	}
	printf("%d\n",X); 
	st[++tp]=X;
}
void init(){
	for(int i=0;i<26;++i){
		hash['A'+i]=i;hash['a'+i]=i+26;
		hsah[i]='A'+i;hsah[i+26]='a'+i;
	}
	scanf("%d",&n);
	char ch[4];
	for(int i=1;i<=n;++i){
		std::cin>>ch+1;
		++mp[hash[ch[1]]][hash[ch[2]]],++mp[hash[ch[2]]][hash[ch[1]]];
		++in[hash[ch[1]]],++in[hash[ch[2]]];
	}
	int ans=0,nans=-1;
	for(int i=0;i<52;++i){
		if(in[i]&1){
			++ans;
			if(nans<0){nans=i;}
		}
	}
	if(ans&&ans!=2){
		puts("No Solution");
		return;
	}
	if(!ans){
		for(int i=0;i<52;++i){
			if(in[i]){
				nans=i;
				break;
			}
		}
	}
	dfs(nans);
	if(tp!=n+1){
		puts("No Solution");
		return;
	}
	while(tp){
		putchar(hsah[st[tp--]]);
	}
}
int main(){
	init();
	return 0;
}

lp4363 九省联考2018 一双木棋chess

快要省选了,需要学习一些乱搞操作。
在这里学习一下Min-Max对抗搜索。
首先了解一下Min-Max对抗搜索。
首先我们知道,对于一个零和有限信息确定性博弈游戏,我们可以将整个游戏的所有局面建成一个有向图。而在几乎所有此类游戏中,整个游戏的所有局面应当能组成一个DAG。
对于这样一个DAG,我们可以对它进行分层,最后得到的应当是一张分层图。这张分层图上的每一层象征着一方正在进行操作。
那么显然这个游戏的最终解是可以知道的。无非就是直接把整张图DFS一遍罢了。
然而,在绝大部分游戏中,这么做的复杂度都太大了,以至于根本无法接受。我们考虑一种被称为Min-Max对抗搜索的搜索方法。
我们首先定义先手方为Max方,后手方为Min方,然后设置一个搜索范围。那么每一个节点的值是这样确定的:
如果它的深度是搜索深度边缘,亦或者它干脆就是一个终止局面,那么它的值就是一个精心设计的估价函数的值。这个估价函数应当能够较好地估计整个局面倾向于哪一方。
如果这个节点是由Max方行动,那么它的值是所有子局面里的值的最大值,因为Max方会向对自己最有利的局面走。
如果这个节点是由Min方行动,那么它的值是所有子局面里的值的最小值,因为Min方会向对Max方最不利的局面,也就是对自己最有利的局面走。
这样就能够求得当前局面的权值,从而得到一个较优秀的决策支了。
本来打算学一下alpha-beta剪枝的,但是这一题好像不是很需要…

回到这一题,如果我们暴力储存每一个状态,那么很显然时间会爆炸。有没有更好的思路呢?
直觉告诉我们,一个格子放置的次序和答案是没有关系的。所以我们不妨假定当前放置的格子总是左上角的一整个块。这样状态数大概就在10^10以内了。
然而实际上并不需要这么多的状态。所以可以Hash以后用map离散化。

#include<iostream>
#include<cstdio>
#include<tr1/unordered_map>

inline int Max(int A,int B){
	return A>B?A:B;
}

inline int Min(int A,int B){
	return A<B?A:B;
}
const int INF=0x3f3f3f3f;
std::tr1::unordered_map<long long,int> mp;
int a[11][11],b[11][11],f[11],n,m;

inline long long hsh(){
	long long RT=0;
	for(int i=1;i<=n;++i){
		RT*=12;
		RT+=f[i];
	}
	return RT;
}

inline void ahsh(long long X){
	for(int i=n;i>=1;--i){
		f[i]=X%12;
		X/=12;
	}
}

inline int dfs(long long X,bool typ){
	if(mp.count(X)){
		return mp[X];
	}
	int RT=typ?-INF:INF;
	long long nw;
	ahsh(X);
	for(int i=1;i<=n;++i){
		if(f[i]<f[i-1]){
			++f[i];nw=hsh();
			RT=typ?Max(RT,dfs(nw,0)+a[i][f[i]]):Min(RT,dfs(nw,1)-b[i][f[i]]);
			--f[i];
		}
	}
	return mp[X]=RT;
}

void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			scanf("%d",&a[i][j]);
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			scanf("%d",&b[i][j]);
		}
	}
	for(int i=0;i<=n;++i){
		f[i]=m;
	}
	mp[hsh()]=0;
	printf("%d\n",dfs(0,1));
}

int main(){
	init();
	return 0;
}

lp5145 漂浮的鸭子

一道tarjan缩点的裸题。
我们仍然可以考虑一个很有趣的做法。那就是,把非环边删去,然后统计环的边权。

#include<iostream>
#include<cstdio>

struct ee{
	int v;
	int w;
}e[100005];

int n,in[100005];
bool vis[100005];

void init(){
	scanf("%d",&n);
	int v,w;
	for(int i=1;i<=n;++i){
		scanf("%d%d",&v,&w);
		e[i]=(ee){v,w};
		++in[v];
	}
	int ans=0,x,nw;
	for(int i=1;i<=n;++i){
		x=i;
		while(!in[x]&&!vis[x]){
			vis[x]=1;
			--in[e[x].v];
			x=e[x].v;
		}
	}
	for(int i=1;i<=n;++i){
		if(!vis[i]){
			nw=e[i].w;
			x=e[i].v;
			vis[i]=1;
			while(x!=i){
				vis[x]=1;
				nw+=e[x].w;
				x=e[x].v;
			}
			ans=std::max(ans,nw);
		}
	}
	printf("%d\n",ans);
}

int main(){
	init();
	return 0;
}

lp2052 NOI2011 道路修建

作为一道NOI的题,它一度令我以为它是2001的。
不曾想,NOI竟然有这么水的题。
我一开始以为自己的写法错了。
但是…
唉,反正就是计算子树大小就对了。
另:存树的时候绝·对·不·可·以「u>v?u^=v^=u^=v:0」!!!这样会导致错误。反例:1->3,3->2。NOIP因为这个丢了很多分。

#include<iostream>
#include<cstdio>
#include<cmath>

struct ee{
    int v;
    int w;
    int nxt;
}e[2000005];
int h[1000005],et=0;
inline void add(int u,int v,int w){
    e[++et]=(ee){v,w,h[u]};
    h[u]=et;
}

int n,in[1000005];
int f[10000005];
bool vis[1000005];
long long ans=0;
inline void dfs(int X){
    for(int i=h[X];i;i=e[i].nxt){
        if(vis[e[i].v]==1){
            continue;
        }
        vis[e[i].v]=1;
        dfs(e[i].v);
        ans+=1LL*e[i].w*(std::abs(((f[e[i].v]<<1)-n)));
        f[X]+=f[e[i].v];
    }
    ++f[X];
}


void init(){
    scanf("%d",&n);
    int u,v,w;
    for(int i=1;i<n;++i){
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
    }
    vis[1]=1;
    dfs(1);
    printf("%lld",ans);
}

int main(){
    init();
    return 0;
}

 

NOIP2018 旅行

题目大意:求一棵树的最小DFS序,和一张n条边的连通图删去任意一条边以后的最小DFS序。
话说这一题和我出过的某一道题非常神似,都是在求一些特定的DFS序。就连对DFS的描述也和我的描述非常相似。
所以在考场上我用了几分钟的时间概括出了简要题面,然后用了十分钟写掉了。
第一个子问题很简单,贪心地DFS即可,这是因为字典序的特性,使得,如果每一次拓展都选择的是当前最小的,那么总是不会更劣。
对于第二个子问题,它不再是求纯粹的DFS序了,但是看到\(n=5000\)的数据范围,可以想到暴力枚举删边,这就转化为第一个问题。
如果依然是一边DFS一边删边的话,最坏情况下可能会达到\(O(n^2*logn)\)的复杂度,尽管有32Gi7,也很难通过一些大数据。
我们考虑预处理。首先将读入的边排序,然后插入边表。这样遍历的顺序就是从小到大了。
注意对边进行预排序时,由于插入边表是倒序插入,所以应当让末端点从大到小排序。
这就做完了。

#include<iostream>
#include<cstdio>
#include<algorithm>
int n,m;
struct ee{
	int v;
	int nxt;
}e[10005];
int h[5005],et=0;
inline void add(int u,int v){
	e[++et]=(ee){v,h[u]};
	h[u]=et;
}
struct e0{
	int u;
	int v;
	bool operator<(const e0 &B)const{
		return (u==B.u)?(v>B.v):(u<B.u);
	}
}e0[10005],e00[5005];
int Du,Dv,ans[5005],Ans[5005],at=0;
bool vis[5005];
inline void dfs(int X){
	vis[X]=1,ans[++at]=X;
	for(int i=h[X];i;i=e[i].nxt){
		if(vis[e[i].v]||(e[i].v==Du&&X==Dv)||(e[i].v==Dv&&X==Du)){
			continue;
		}
		dfs(e[i].v);
	}
}
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		scanf("%d%d",&e0[i].u,&e0[i].v);
		e00[i].u=e0[i].u,e00[i].v=e0[i].v;
		e0[i+m].u=e0[i].v,e0[i+m].v=e0[i].u;
	}
	std::sort(e0+1,e0+(m<<1|1));
	for(int i=1;i<=(m<<1);++i){
		add(e0[i].u,e0[i].v);
	}
	if(m==n-1){
		Du=0,Dv=0;
		dfs(1);
		for(int i=1;i<=n;++i){
			printf("%d ",ans[i]);
		}
		return;
	}else if(m==n){
		for(int i=1;i<=n;++i){
			Ans[i]=0x3f3f3f3f;
		}
		for(int i=1;i<=m;++i){
			Du=e00[i].u,Dv=e00[i].v;
			at=0;
			for(int j=1;j<=n;++j){
				vis[j]=0;
			}
			dfs(1);
			if(at==n){
				for(int j=1;j<=n;++j){
					if(ans[j]==Ans[j]){
						continue;
					}else if(ans[j]>Ans[j]){
						break;
					}else{
						for(int k=1;k<=n;++k){
							Ans[k]=ans[k];
						}
						break;
					}
				}
			}
		}
		for(int i=1;i<=n;++i){
			printf("%d ",Ans[i]);
		}
	}
}
int main(){
	init();
	return 0;
}