ITeye博客

Jianquan的博客

Jianquan · 共 21 篇文章

UVa 10422 Knights in FEN

题目: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1363 #include<cstdio> #include<cstring> #include<queue> #include<set> using namespace std; struct State { short step,x,y; char map[5][5]; }; struct cmp { bool operator () (State a,State b) const { ret…

2012-09-07 08:40 · UVa · 评论(0)

UVa 639 Don't Get Rooked

题目: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=580 最多16个格,2^16=65536可以枚举完,而且很多都是可以剪枝的,用dfs枚举就可以。 要注意的是如果在dfs之前用vis数组标记放下了“车”,那么要在dfs之后清除掉。 #include<cstdio> #include<cstring> #define clear(x) (memset(x,0,sizeof(x))) char map[4][4]; bool vis[4][4]; …

2012-08-30 23:01 · UVa · 评论(0)

UVa 216 Getting in Line

题目: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=152 最多只有8个点,枚举所有的排列即可,可以用一个二维数组记录所有的排列以便最后输出。 这道题目是一道水题,但是它的题目描述有点复杂,所以需要一点耐心去读懂题意。有两点可以从题意中得出:不一定要把第一个点当做起点;不必考虑相交的情况。明白这两点就很简单了。 #include<iostream> #include<cstdio> #include<algorithm> #include<cmat…

2012-08-29 20:48 · UVa · 评论(0)

UVa 10474 Where is the Marble?

题目: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=108&page=show_problem&problem=1415 快排+二分,就是不知道跟回溯法有什么关系。 #include<stdio.h> #include<stdlib.h> #define MAXN 10000+10 int marble[maxn]; int cmp(void const *a,void const *b) { return *((int *)a)-*((int *)b); } int binsea…

2012-08-28 13:45 · UVa · 评论(0)

UVa 592 Island of Logic

题目: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=533 人数最多只有5个人,加上时间,所以可以用6个循环枚举所有的情况。 输入的时候可以根据某个特定的字符去判断这个陈述的内容,比如带有'd'的是'divine'。 判断该陈述是否合法还要结合说话人的身份去判断。如果所有的陈述都合法,那么枚举的这种情况是可能的,把它保存下来,枚举完所以情况后再进行判断。 #include<iostream> #include<cstdio> #include<st…

2012-08-27 11:05 · UVa · 评论(1)

UVa 11205 The broken pedometer

题目: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2146 题目大意是求最少的工作正常的LED(一条横杠或竖杠代表一个正常的LED)能够表示出题目给定的所有数字。LED最大数目是15,每一条LED要么亮(正常)要么不亮(不正常),所以最多的情况就是2^15=32768种,我们把所有的情况枚举完毕,得出所需的最少的正常的LED。 这道题目我们可以用二进制的1代表LED工作正常,0代表不正常。所以我们只需要从0开始枚举,一直枚举到2^P-1。即for…

2012-08-25 17:28 · UVa · 评论(0)

UVa 131 The Psychic Poker Player

题目: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=107&page=show_problem&problem=67 对于每一个输入样例(10张牌),我们要构造出它所有的32种牌型组合,这是一个比较困难的地方,方法是用递归枚举。每次我们可以从手牌中分别选取0~5张牌,然后剩余的牌从牌堆中补充。从手牌中选牌,就是组合数C(5,0),C(5,1),C(5,2),C(5,3),C(5,4),C(5,5),这道题中,我们不仅要知道组合数是多少,更重要的是把具体的牌型构造出来。 我们可以把构…

2012-08-24 22:28 · UVa · 评论(0)

UVa 729 The Hamming Distance Problem

题目: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=670 枚举十进制数0~2^N-1,对于每一个数都跟0异或,并把异或的结果转换成二进制,计算二进制数中1的个数,如果等于H,那么把该二进制数输出,注意不要忽略了前导零。 #include<stdio.h> #include<math.h> void solve(int XOR,int N,int H) { int res[20],top=0,cnt=0; while(XOR>0) { int tm…

2012-08-24 12:18 · UVa · 评论(0)

Uva 10098 Generating Fast

题目: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=107&page=show_problem&problem=1039 具体思路请参考刘汝佳的《算法竞赛入门经典》7.2.2生成可重集的排列 #include<stdio.h> #include<stdlib.h> #include<string.h> #define MAX 11 char A[max],P[max]; void print_permutation(int len,int cur) { int i,j; if(cu…

2012-08-23 15:28 · UVa · 评论(0)

UVa 146 ID Codes

题目: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=107&page=show_problem&problem=82 题目的要求是找出字典序中的下一个排列。 从后往前查找,如果一直都是非递减的,那么就是“No Successor”。一旦发现不符合条件的字符(if(str*<str),那么就把该字符与它后面的所有字符中恰好比它大的字符调换,比方说sample中的abaacb,我们找到第一个不符合非递减条件的字母:中间的那个a,然后将它与b调换,因为在那个a后面是cb,恰好比a大的是b…

2012-08-20 18:46 · UVa · 评论(0)

UVa 10167 Birthday Cake

题目: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=107&page=show_problem&problem=1108 直接从-500到500枚举A和B,非常简单。 #include<iostream> #include<cmath> #include<cstring> #define MAXN 100 using namespace std; int x[maxn],y[maxn]; int main() { //freopen("in.txt","r",stdin); int…

2012-08-16 20:57 · UVa · 评论(0)

UVa 10129 Play on Words

题目: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=105&page=show_problem&problem=1070 题目大意是给你一串单词,判断能否连接成一条长串,两个单词能够连接的条件是后一个单词的首字母与前一个单词的尾字母相同(单词至少有2个字母)。单词仅由小写字母组成。 这个题目对于我们新手来说还是有难度的。首先这是一个图论问题,我们把单词看作是点,单词之间的连接关系看作是边。题目所给的数据规模:单词的个数到达10万,所以我们不能把每一个单词看作一个点,而是把相同的单词…

2012-08-15 22:49 · UVa · 评论(0)

UVa 10596 Morning Walk

题目: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=105&problem=1537&mosmsg=Submission+received+with+ID+10476587 无向图的欧拉回路。先判断连通性,从任意一个点出发进行dfs,看看是否能够把所有点都遍历,如果可以就是连通,否则不连通。然后再判断是否存在欧拉回路,因为题意是要回到原点,所以所有点的度都必须是偶数,也就是说连接每个点的边都是偶数条,满足这个条件就存在欧拉回路。 #include…

2012-08-14 22:05 · UVa · 评论(0)

Uva 10305 Ordering Tasks

题目: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=105&page=show_problem&problem=1246 拓扑排序,直接dfs,具体看刘汝佳的《算法竞赛入门经典》。而且这道题目的题意是一定存在拓扑排序,所以更加简单。 #include<stdio.h> #include<string.h> #define MAXN 100+10 int vis[MAXN],edge[MAXN][MAXN],topo[MAXN],t,n; void dfs(int i) { int …

2012-08-13 23:40 · UVa · 评论(0)

Uva 10004 Bicoloring

题目: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=105&page=show_problem&problem=945 主要用dfs #include<iostream> #include<cstdio> #include<cstring> #define MAXN 200+10 using namespace std; int edge[MAXN][MAXN],vis[MAXN],color[MAXN],n;//color数组的值为0、1分别代表2种不同的颜色 bool dfs(…

2012-08-13 23:34 · UVa · 评论(0)