那些严重拖慢做题进度的题以及遇到的坑5
那些严重拖慢做题进度的题以及遇到的坑5
1297 Children’s Queue
There are many students in PHT School. One day, the headmaster whose name is PigHeader wanted all students stand in a line. He prescribed that girl can not be in single. In other words, either no girl in the queue or more than one girl stands side by side. The case n=4 (n is the number of children) is like
FFFF, FFFM, MFFF, FFMM, MFFM, MMFF, MMMM
Here F stands for a girl and M stands for a boy. The total number of queue satisfied the headmaster’s needs is 7. Can you make a program to find the total number of queue with n children?
分析：
这一题有两个坑，第一个是递推表达式特别难想，第二个就是结果特别大，就算用unsigned long long也是完全不行的…必须要自己构造大数模板…
题目的大意是女生不能落单，也就是说不能出现一个女生旁边都是男生。这是一个递推题于是就按照递推的思路来做：
- 如果新加入一个男生，那没什么问题，a[n - 1]
- 如果新加入的是女生，那就麻烦了，必须前面最后是女生
- 如果前面n-2合法，那么直接加入两个女生，当然是成立的，也就是a[n - 2]
- 如果前面n-2不合法，要加入两个女生才合法，那么结尾必定是MF，于是最后为MFFF，前面是什么都可以，就是a[n - 4]
- 至于为什么没出现a[n - 3]，那是因为当最后是FF的时候，如果合法的话倒数第二位是什么就无所谓了，但是如果不合法就要通过新加入的变得合法了
下面一个坑就是大数了，思想就是用多个数拼起来来代替一个数，就是用一个二维数组，第一维表示是第几个数，第二维中的每一个数据都代表数的一部分，不妨假设最大为9999，那么这个数就是由多个9999拼成的，再怎么大也不会再越界了。
先来一个非常完整的大数模板，实现了加减乘除输出等等，链接在这里
然后再看一下一个比较基础的具体的实现吧
int a[1005][105];
void add(int n)
{
// k相当于进位数，同时在传递值的时候也暂时接受了加出来的数
int k = 0;
int i;
for (i = 1; i <= 100; ++i)
{
k += a[n - 1][i] + a[n - 2][i] + a[n - 4][i];
// 尾数留给a[n][j]
a[n][j] = k / 10000;
// 进位数传递下去
k /= 10000;
}
// 如果数组的第二位足够大，那么到这里应该就不会有问题了
}
void print(int n)
{
int i;
for (i = 100; i >= 1; --i)
{
if (a[n][i] != 0)
break;
}
printf("%d", a[n][i]); // 最开始的不用补0
for (i = i - 1; i >= 1; --i)
printf("%04d", a[n][i]); // 四位，不够的用0来补充
printf("\n");
}这种直接用一个变量来表示进位以及加起来结果的方法还是很巧妙的…当时我就感觉思路很乱于是就直接找模板了…
1438 钥匙计数之一
一把锁匙有N个槽，槽深为1，2，3，4。每锁匙至少有3个不同的深度且至少有1对相连的槽其深度之差为3。求这样的锁匙的总数。
分析：
这是一道很让人蛋疼的题…因为情况太多太难想了…
先贴出来参考出处
设one[i]为第一个槽为1总共有i个槽的情况，类似有two[i], three[i]…易得lock[i] = one[i] + … + four[i]
因为对称的原因，实际上one[i]和four[i]是相同的，同理two[i]和three[i]也是相同的。
先对one[i]进行讨论：
- 如果第一个数对后面没有影响，那么就直接是lock[i - 1]
- 如果有影响
- 那么第二个一定是4，这样才能让去掉第一个后就不合法，这时候一共有4^(i-2)种情况
- 但是又因为要合法，所以后面n-2不能全都是1，4，所以要减掉2^(i-2)
- 又因为去掉后不合法，所以要减去以4开头合法的情况，也就是four[i - 1]
总共为:
one[i] = one[i-1] + two[i-1] + three[i-1] + four[i-1] + 4 ^ (i-2) - one[i-1] -2^(i-2)
再对two[i]讨论
- 第一个数对后面没影响的话就和前面相同
- 有影响的话
- 要想后面不合法那就只能是不满三个数了，而且因为加上去后合法，于是后面就全是1和4了，情况有2^(i-1)，但是不能全为1或4，于是要减去2
有：
two[i] = 2 ^ (i - 1) - 2
于是lock[i]有：
lock[i] = 6 one[i-1] + 8 two[i-1] + 2 4^(i-2) + 2 2^(i-2) -4
换成C语言就是
// 注意pow的类型要进行转换，不然可能因为精度报错
one[i] = one[i - 1] + 2 * two[i - 1] + (long long)pow((double)4, i - 2) - (long long)pow((double)2, i - 2);
two[i] = 2 * one[i - 1] + 2 * two[i - 1] + (long long)pow((double)2, i - 1) - 2;
lock[i] = 2 * one[i] + 2 * two[i];1480 钥匙计数之二
一把钥匙有N个槽，2<N<26槽深为1，2，3，4,5,6。每钥匙至少有3个不同的深度且相连的槽其深度之差不得为5。求这样的钥匙的总数。
分析：
这个和前面那个只是改了一下，相当于逆向思维，所以加一点就可以了，然而还是有一点坑的。
还是和上面一样从one[i]到six[i]，因为是不得为5，正好和只要一个为5互补，所以只要按照前一题的做法再减一下就可以了。
one[i]和six[i]是对称的，其他的所有是对称的，lock[i]还是所有的和。
而我们要求的基数就是至少有三个不同深度的情况，一开始我是这样写的
b[n] = 6 ^ n - 15 * 2 ^ n
然而这里我把从头到尾都是一个数的情况多减了好多次，所以应该一个个的减掉
b[n] = 6 ^ n - 15 * (2 ^ n - 2) - 6
然后在和之前的结果一减就可以了
// 因为最后的数很大，不得不祭出大杀器unsigned long long
one[i] = one[i - 1] + 4 * two[i - 1] + (unsigned long long)pow((double)6, i - 2) - (unsigned long long)pow((double)2, i - 2);
two[i] = 2 * one[i - 1] + 4 * two[i - 1] + (unsigned long long)pow((double)2, i - 1) - 2;
lock[i] = 2 * one[i] + 4 * two[i];
alllock[i] = (unsigned long long)pow((double)6, i) - 15 * (unsigned long long)pow((double)2, i) + 24;
unsigned long long temp = alllock[i] - lock[i];然而即使使用了大杀器，最后一个还是越界了，但是既然他已经把最后的结果给你了，干脆直接输出（滑稽
1466 计算直线的交点数
平面上有n条直线，且无三线共点，问这些直线能有多少种不同交点数。
比如,如果n=2,则可能的交点数量为0(平行)或者1(不平行)。
分析
一道dp题，然而要想出状态真的好难…我一开始完全无从下手…
设dp[i][j]为有i个锁孔的时候，j个交点数可不可能存在，为0的时候不可能，为1的时候可能
当d[m][n]为1的时候，如果有r条平行线，那么相对于d[m][n]有d[i][(i - r) r + j]也为1，也就是多出了r条平行线就多出(i - r) r个交点，每个平行线都与其他所有相交
我一开始是考虑有多组平行线，然而这样就要开N维数组，这种方法的话还是很巧妙的，忽视了平行线的组数，每次哦度是相对前一组再多加一组，可能和之前的一样，也可能不一样。
综上，一共有三层循环：
- i从0～n得到每个直线数对应的最终情况
- r从0到i循环表示平行边的个数
- k从0到可能最大的数，也就是n为20的时候n * (n - 1) / 2的值进行循环来得到所有交点数
而输出的时候就之用循环到n * (n - 1) / 2，不用到20对应的最大值。.
贴一份代码
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <map>
#include <vector>
#include <set>
#include <stack>
#include <queue>
using namespace std;
#define INF 0x3fffffff
const int maxn = 10005;
int main()
{
int dp[25][195];
memset(dp, 0, sizeof(dp));
for (int i = 0; i <= 20; ++i)
{
dp[i][0] = 1;
for (int j = 0; j <= i; ++j)
{
for (int k = 0; k <= 190; ++k)
if (dp[j][k] == 1)
dp[i][(i - j) * j + k] = 1;
}
}
int n;
while (~scanf("%d", &n))
{
for (int i = 0; i <= n * (n - 1) / 2; ++i)
{
if (dp[n][i] == 1)
{
if (i != 0)
printf(" ");
printf("%d", i);
}
}
printf("\n");
}
return 0;
}最后
递推难起来真的是叫妈都没用了…动态规划则是一直都感觉不太通…好久没做手生了…