Question

几个关于算法的题目

题目一：选村长
一村N人，先要进行村长选举，现需要在村民中选出村长候选人，村长候选人应满足：
1.被所有人认识
2.不认识所有人
设konw(i,j)返回i认识j否
请在O(n)时间内选出所有村长候选人

题目二：实现大整数相乘（100位以内）

题目三：有W行H列方形区域（W≥1，H≤11）先用一1*2方砖铺满，请问有多少种铺法。

求大神给个大概的算法介绍就行了
不必代码
谢

Answer 1

第1题，先统计一下每一点的入度和出度，出度代表认为几个人，入度代表被几个人认识。
最后看看哪一个人的入度是==n-1,出度是0的就行

大整数相乘的话可以模拟小学生摆竖式。
先把数字的每一位存在整型数组中。
然后一位一位乘过去。把结果加起来就行。复杂度是n*m

最后一个是状态压缩DP
设dp[i][j]代表前i-1已经摆好，第i行每一状态是j的情况下的种数。

然后按行行转移。
复杂度是2^n*2^n*n