Zhao70's Blog

发表于 | 分类于

至今没有填上的坑

动归

  • 完全背包
  • 多重背包
  • 最长递增子序列(导弹拦截)

数论

  • 康托展开

想要再挖的坑

  • 欧拉回路
  • 二叉树的层序遍历和生成
  • 复习DFS, BFS， 多做几道题
  • 复习最短路
  • 李欣健学长出的DP题
  • 蓝桥的相关资料和视频
  • 蓝桥往届试题
Zhao70's Blog

发表于 | 分类于

题目描述

题目链接: POJ3624
很经典的01背包问题，不累述了。

理解

01背包问题本身代码并不复杂，很难理解的是状态的转移，引用Tanky Woo的一句话

首先说下动态规划，动态规划这东西就和递归一样，只能找局部关系，若想全部列出来，是很难的，比如汉诺塔。你可以说先把除最后一层的其他所有层都移动到2，再把最后一层移动到3，最后再把其余的从2移动到3，这是一个直观的关系，但是想列举出来是很难的，也许当层数n=3时还可以模拟下，再大一些就不可能了，所以，诸如递归，动态规划之类的，不能细想，只能找局部关系。

使用01背包问题这类简单的问题来学习动态规划是新手友好的。

其次，对于01背包进行一维数组的优化，以及和完全背包问题及其一维数组优化的对比， 能够更好的理解状态这个概念。

原始版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
for(int i = 1; i <= nItem; i++)
{
    for(int j = 1; j <= nWeight; j++)
    {
        //如果不选一件物品有两种可能：
        //1. 装不下
        //2. 不想装
        if(j < weight[i])
            dp[i][j] = dp[i - 1][j];
        else{
            //注意此处max函数中dp数组无论拿还是不拿都是从[i - 1]的状态转移而来的
            //[i - 1]保证此处为01背包问题
            //即保证每个物品只有一个
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
        }
    }
}

使用一维数据进行优化

当nItem比较小(例如在1000以内)时，使用二维数组是可以使用的，但当nItem偏大(n为10000)时， 使用二维数组时不可行的， 所以学会使用一维数组是必须的。

1
2
3
4
5
6
7
8
9
10
11
12
13
  for(int i = 1; i <= nItem; i++)
  {
//此处的j为逆序
//说明每次计算得出的dp[j]都是从nItem - 1转移(保证每件物品只选一次)而来的
//完全背包与这个有微小的区别
//即从nItem转移而来的(每件物品可选任意次)
      for(int j = nWeight; j >= 1; j--)
      {
          if(weight[i] > j)
              continue;
          dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
      }
  }

参考链接

Tanky Woo’s Blog
DD大牛的背包九讲
北大动归相关课件

本人文笔略拙，觉得本文晦涩难懂可参考以上大牛的相关文档。

Zhao70's Blog

发表于

函数声明

1
2
#include <algorithm>
bool next_permutation( iterator start, iterator end );

The next_permutation() function attempts to transform the given range of elements [start,end) into the next lexicographically greater permutation of elements. If it succeeds, it returns true, otherwise, it returns false.

我的代码

github

Zhao70's Blog

发表于 | 分类于

原理

令 h(0) = 1, h(1) = 1, catalan数满足
h(n)= h(0)×h(n-1)+h(1)×h(n-2) + … + h(n-1)×h(0) (n>=2)

通项公式

h(n) = C(2n, n) / (n + 1) = (2n)! / ((n + 1)! × n!)

##应用

括号化

n组括号的合法运算式的个数

如((())) ()(()) ()()() (())() (()())

出栈次序

感觉此应用和括号化类似。
省去不表，详情见上篇博文。

构建二叉树和满二叉树

h(n)表示n个节点构建二叉树的方案数
h(n)表示2n + 1个节点构建**满二叉树的方案数

凸多边形的划分

在一个凸多边形中，通过若干条互不相交的对角线，把这个多边形划分成了若干个三角形。任务是键盘上输入凸多边形的边数n，求不同划分的方案数f（n）。

参考链接

百度百科

维基百科

Zhao70's Blog

发表于

题目描述

我们把n个元素的出栈个数的记为f(n), 那么对于1,2,3, 我们很容易得出：

f(1) = 1     //即 1
f(2) = 2     //即 12、21
f(3) = 5     //即 123、132、213、321、231

然后我们来考虑f(4), 我们给4个元素编号为a,b,c,d, 那么考虑：元素a只可能出现在1号位置，2号位置，3号位置和4号位置(很容易理解，一共就4个位置，比如abcd,元素a就在1号位置)。

方法一

  1. 如果元素a在1号位置，那么只可能a进栈，马上出栈，此时还剩元素b、c、d等待操作，就是子问题f(3)；
  2. 如果元素a在2号位置，那么一定有一个元素比a先出栈，即有f(1)种可能顺序（只能是b），还剩c、d，即f(2)，根据乘法原理，一共的顺序个数为f(1) * f(2)；
  3. 如果元素a在3号位置，那么一定有两个元素比1先出栈，即有f(2)种可能顺序（只能是b、c），还剩d，即f(1)，根据乘法原理，一共的顺序个数为f(2) * f(1)；
  4. 如果元素a在4号位置，那么一定是a先进栈，最后出栈，那么元素b、c、d的出栈顺序即是此小问题的解，即 f(3)；

结合所有情况，即

= f(3) + f(2) * f(1) + f(1) * f(2) + f(3);```为了规整化，我们定义f(0) = 1；于是f(4)可以重新写为：```f(4) = f(0)*f(3) + f(1)*f(2) + f(2) * f(1) + f(3)*f(0)```
1
2
然后我们推广到n，推广思路和n=4时完全一样，于是我们可以得到：```f(n) = f(0)*f(n-1) + f(1)*f(n-2) + ... + f(n-1)*f(0)

方法二

递推式满足Catalan数 h(n) = C(2n, n) / (n + 1)

//(n = 0,1,2,…) h(0)=1,h(1)=1

补充

C(m, n) = m! / (n! * (m - n)!)

Zhao70's Blog

发表于 | 分类于

题目链接 Uva11388

题目大意

已知两个数的最大公约数(GCD)和最小公倍数(LCM), 求两个数字, 要求第一个数字最小， 第二个数字最大

解题思路

1
2
3
4
5
6
7
由GCD和LCD的性质得，
LCM * GCD == a * b,
a = xG;
b = yG;
L / G == x * y;
若L % G != 0; 则说明 x * y 中存在小数 即无解
若有解， 最小为G 另一个为L

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
using namespace std;
int gcd(int, int);
int lcm(int, int);
int main()
{
    int nTest;
    cin >> nTest;
    while(nTest)
    {
        int G, L;
        cin >> G >> L;
        if(L % G != 0)
        {
            cout << -1 << endl;
            nTest--;
            continue;
        }
        cout << G << " " << L << endl;
        nTest--;
    }
    return 0;
}
int gcd(int a, int b)
{
    while(b ^= a ^= b ^= a %= b);
    return b;
}
int lcm(int a, int b)
{
    return (a * b) / gcd(a, b);
}
Zhao70's Blog

发表于

GCD最大公约数

概念

最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。

求法

1
2
3
4
5
unsigned int gcd(unsigned int a,unsigned int b)
{
    while(b^=a^=b^=a%=b);//注意此处分号
    return a;
}

LCM最小公倍数

概念

几个数共有的倍数叫做这几个数的公倍数，其中除0以外最小的一个公倍数，叫做这几个数的最小公倍数。

求法

1
2
3
4
5
6
7
int LCM(int a,int b)
{
	int temp_lcm;
	 //最小公倍数等于两数之积除以最大公约数
	temp_lcm = a * b /GCD(a,b);
	return temp_lcm;
}
Zhao70's Blog

发表于 | 分类于

题目

标题：生物芯片
X博士正在研究一种生物芯片，其逻辑密集度、容量都远远高于普通的半导体芯片。
博士在芯片中设计了 n 个微型光源，每个光源操作一次就会改变其状态，即：点亮转为关闭，或关闭转为点亮。
这些光源的编号从 1 到 n，开始的时候所有光源都是关闭的。
博士计划在芯片上执行如下动作：
所有编号为2的倍数的光源操作一次，也就是把 2 4 6 8 … 等序号光源打开
所有编号为3的倍数的光源操作一次, 也就是对 3 6 9 … 等序号光源操作，注意此时6号光源又关闭了。
所有编号为4的倍数的光源操作一次。
…..
直到编号为 n 的倍数的光源操作一次。
X博士想知道：经过这些操作后，某个区间中的哪些光源是点亮的。
【输入格式】
3个用空格分开的整数：N L R (L<R<N<10^15) N表示光源数，L表示区间的左边界，R表示区间的右边界。
【输出格式】
输出1个整数，表示经过所有操作后，[L,R] 区间中有多少个光源是点亮的。
例如：
输入：
5 2 3
程序应该输出：
2
再例如：
输入：
10 3 6
程序应该输出：
3

思路

这道题如果用纯暴力肯定GG，涉及到了2个知识点

完全平方即用一个整数乘以自己例如11，22，3*3等，依此类推。若一个数能表示成某个整数的平方的形式，则称这个数为完全平方数。完全平方数是非负数，而一个完全平方数的根有两个。

一个正整数n是完全平方数的充分必要条件是n有奇数个因数（包括1和n本身）。

从 左边界的二次根号下 枚举 i 直到 i 的平方等于 右边界

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    long long nLight, left, right;
    cin >> nLight >> left >> right;
    long long ans = right - left + 1;
    for(long long i = sqrt(left); i * i <= right; i++)
    {
		//此处注意这个if, 若left进行开方运算后可能向下取整， 导致ans多自减1
        if(i * i >= left && i * i <= right)
            ans--;
    }
    cout << ans;
    return 0;
}
Zhao70's Blog

发表于

题目链接: Uva10474 Where is the Marble?

涉及的知识点

  • lower_bound

分析

典型的水题， lower_bound()返回的是一个有序的非递减数列第一个大于等于查询值的位置。

如果要在

1, 2, 2, 3, 3, 3, 4, 5, 7

找寻2, 则返回所在的位置，检查该位置的数值是否为2

找寻6, 返回7所在位置

我的代码

github

Zhao70's Blog

发表于 | 分类于

stringstream及其用法

包含在头文件 sstream 中

  1. 声明stringstream

    1
    stringstream ss;

  2. 给stringstream对象赋值

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    //可以在定义时赋值
    string s;
    cin >> s;
    stirngstream ss(s);
    //利用stringstream::str()进行赋值
    stringstream ss;
    ss.str("hello stringstream");
    //利用流
    string s;
    stringstream ss;
    cin >> s;
    ss <<　ｓ;

  3. stringstream的清空

    1
    2
    3
    stringstream ss;
    ss.str("");//right
    ss.clear; //error

std::lower_bound()和std::lower_bound()

ForwardIter lower_bound(ForwardIter first, ForwardIter last,const _Tp& val)算法返回一个非递减序列[first, last)中的第一个大于等于值val的位置。
ForwardIter upper_bound(ForwardIter first, ForwardIter last, const _Tp& val)算法返回一个非递减序列[first, last)中第一个大于val的位置。

1 2 2 3 4 4 4 5 6 7 9 9 10  
first       lower_bound(first, last, 4)       upper_bound(first, last, 4)         last 
1
2
//查找相应的值的位置
int loc = lower_bound(first, last, 4) - first;

不定长数组： vector()

若a是一个vector，可以用a.size( )读取它的大小，a.resize( )改变大小，a.push_back( )向尾部添加元素，a.pop_back( )删除最后一个元素

set()用法