那些严重拖慢做题进度的题以及遇到的坑4

Author Avatar
patrickcty 2月 23, 2017

那些严重拖慢做题进度的题以及遇到的坑4

杭电207X && 208X

A1 = ?

有如下方程：Ai = (Ai-1 + Ai+1)/2 - Ci (i = 1, 2, 3, …. n).
若给出A0, An+1, 和 C1, C2, …..Cn.
请编程计算A1 = ?

分析：

这是一个数学问题，然而这个递推却很坑爹，Ai与Ai-1和Ai-2都有关，然而初始条件却要你求A1，看了解答之后才知道怎么做…自己高中数学功力还是一般般啊…

以下来源于网上

因为：Ai=(Ai-1+Ai+1)/2 - Ci,
A1=(A0 +A2 )/2 - C1;
A2=(A1 + A3)/2 - C2 , …
=> A1+A2 = (A0+A2+A1+A3)/2 - (C1+C2)
=> A1+A2 = A0+A3 - 2(C1+C2)
同理可得：
A1+A1 = A0+A2 - 2(C1)
A1+A2 = A0+A3 - 2(C1+C2)
A1+A3 = A0+A4 - 2(C1+C2+C3)
A1+A4 = A0+A5 - 2(C1+C2+C3+C4)
…
A1+An = A0+An+1 - 2(C1+C2+…+Cn)
—————————————————– 左右求和
(n+1)A1+(A2+A3+…+An) = nA0 +(A2+A3+…+An) + An+1 - 2(nC1+(n-1)C2+…+2Cn-1+Cn)

=> (n+1)A1 = nA0 + An+1 - 2(nC1+(n-1)C2+…+2Cn-1+Cn)

=> A1 = [nA0 + An+1 - 2(nC1+(n-1)C2+…+2Cn-1+Cn)]/(n+1)

这个解法的巧妙之处就在于多项相加的时候，两边都有A2～An，而多出来的A1和An+1正好是要求的和知道的，于是就可以直接写出答案。然而要发现规律不难但是要想到把它们加起来就有点难了…

选课时间

又到了选课的时间了，xhd看着选课表发呆，为了想让下一学期好过点，他想知道学n个学分共有多少组合。你来帮帮他吧。（xhd认为一样学分的课没区别）

分析：

这一题一看就觉得应该是一个动态规划，但是不是求最优，而是求数量最多，于是就有些懵逼了。

先上代码吧

for (int i = 0; i < k; ++i)
        {
            // 每次输入新课的时候循环
            int a, b;
            scanf("%d %d", &a, &b);

            // 对于每门课，都有相当于一个背包
            for (int m = n; m >= 1; --m)
            {
                for (int l = 1; l <= b; ++l)
                {
                    // 不同的是只要新装进去就加上种类
                    // 好难想到
                    // 这个种类真的不好想
                    if (m - l * a >= 0)
                        d[m] += d[m - l * a];
                }
            }
        }

分析：

因为正好是输入的每门课，所以就直接跟着课来循环，就不用等输入完之后再进入循环。
对于每门课，可以看作是一个背包，背包容量为n也就是总学分数。这时候就还是要从容量为n到1进行一个循环，里面的循环就是对课程的数量，到这里还是和0-1背包是一样的，下面就是重点了

如果还能装得下，那么就在之前的基础上加上了加进去的数量对应的种类，也就是说如果学分为m，则d[m]是基于d[m-1]到d[0]所有的情况。
这是这个的一个难点，也是和平常的动态规划不一样的地方。

找单词

假设有x1个字母A， x2个字母B,….. x26个字母Z，同时假设字母A的价值为1，字母B的价值为2,….. 字母Z的价值为26。那么，对于给定的字母，可以找到多少价值<=50的单词呢？单词的价值就是组成一个单词的所有字母的价值之和，比如，单词ACM的价值是1+3+14=18，单词HDU的价值是8+4+21=33。(组成的单词与排列顺序无关，比如ACM与CMA认为是同一个单词）。

分析：

这是一道和上面几乎一样的踢，但是由于一些坑爹的原因，运行结果一直都是错的…

还是先上代码

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include <algorithm>
#include <map>

using namespace std;

const int maxn = 30;
int a[maxn];  // 每个字母出现的次数
int d[55];  // 最大种类

int main()
{
	int n;
	scanf("%d", &n);
	while(n--)
	{
        int cnt = 0;

        memset(d, 0, sizeof(d));
        d[0] = 1;
        for (int i = 1; i <= 26; ++i)
        {
            scanf("%d", &a[i]);
        }

        // 还是对于每个字母来循环
        for (int i = 1; i <= 26; ++i)
        {
            if (a[i] == 0)
                continue;
            // 这里是对于剩下的分数
            // 里面就几乎和上面一题完全一样了
            for (int j = 50; j >= i; --j)
            {
                for (int k = 1; k <= a[i]; ++k)
                {
                    if (j - i * k >= 0)
                        d[j] += d[j - i * k];
                }
            }
        }

        // 这个地方坑的我好惨...明明是50位的数组...我已开始只加了26位...
        for (int i = 1; i <= 50; ++i)
        {
            cnt += d[i];
        }
        printf("%d\n", cnt);
	}
	return 0;
}

和上面一题不同的是这一题在1~50这个范围内都可以，所以最后只用把结果加起来就可以了，比较坑爹的是，我一直以为d只有26位…所以结果一直秘制的小…

汉诺塔IV

还记得汉诺塔III吗？他的规则是这样的：不允许直接从最左(右)边移到最右(左)边(每次移动一定是移到中间杆或从中间移出)，也不允许大盘放到小盘的上面。xhd在想如果我们允许最大的盘子放到最上面会怎么样呢？（只允许最大的放在最上面）当然最后需要的结果是盘子从小到大排在最右边。

分析：

这个是在前一个汉诺塔的基础上来的，分三步走：

  1. 把n-1个移到中间去
  2. 把第n个移到中间再移到右边去
  3. 把n-1个移到右边去

最坑的是有一些隐藏的结论一直没发现：

  1. 把n个移到最右边相当于先移到中间，再移到右边，因为事实上每个块都是移到中间才能移到最右边的
  2. 把n个移到中间和把n个从中间移到旁边是一样的，对于单个的，都是一步到位
  3. 把n个移到右边相当于2*把n个移到中间，由1,2可以知道

所以者具体的结果其实就是汉诺塔3的a[n - 1] + 2

没发现规律的我被坑的好惨…

expand_less
Powered by Hexo
Theme - Material