Shen Huang's Blog
0%

Posted on Edited on

基本知识

洛毕达法则(L’Hospital)法则，是在一定条件下通过分子分母分别求导再求极限来确定未定式值的方法。
设

  • (1)当x→a时，函数f(x)及F(x)都趋于零；
  • (2)在点a的去心邻域内，f’(x)及F’(x)都存在且$ F’(x) \ne 0 $；
  • (3)当x→a时$ lim_{x \to a}\frac{f’(x)}{F’(x)} $存在(或为无穷大)，那么x→a时又设
    (1)当x→∞时，函数f(x)及F(x)都趋于零；
    (2)当|x|>N时f’(x)及F’(x)都存在，且$ F’(x) \ne 0 $；
    (3)当x→∞时 $ lim_{x \to \infty}\frac{f’(x)}{F’(x)} $ 存在(或为无穷大)，那么
    x→∞时

举例1

求解 的值

举例2

求解 的值

首先注意到 然后通过化简得

最终得到

得到答案为0

Posted on Edited on

前言

如何在wordpress下面使用jetpack的Markdown，因为这里面的Markdown语法和普通略有不同（少了一些功能），现整理如下

Markdown语法

强调

  • 斜体使用*斜体*或者_斜体_
  • 加粗使用*加粗*或者__加粗__进行加粗
  • 水平线在一行输入三个或者以上的————,*
  • 删除线用两个波浪线括起来~删除线~

链接

  • 行内链接 link 使用[link](http://example.com)
  • 引用链接 ：
    Some text with a link and
    another link.
    举例如下：
Some text with [a link][1] and
another [link][2].

[1]: http://example.com/
[2]: http://example.org/

列表

  • 在行首使用 *Item或者 _Item
  • 数字列表在行首使用 1\. Item
    1. 混合列表使用 * 1\. Item

引用

Example

在行首使用 >或者 > > 即可

代码

  • 行内代码 ‘Example’ 使用单引号'Example'
  • 代码块 使用Code即可Code
  • 相应代码高亮使用
1
2
3
#button {
   border: none;
}

使用举例：

1
2
3
#button {
    border: none;
}

Posted on Edited on

欢迎使用WordPress。这是系统自动生成的演示文章。编辑或者删除它，然后开始您的博客！

Posted on Edited on

youtube视频链接: https://www.youtube.com/watch?v=XVrZs-0lfcg

https://www.youtube.com/watch?v=XVrZs-0lfcg

在这个视频里，他介绍了EnPlug怎么颠覆传统数字电视广告，以及展现了怎么才能使用EnPlug平台来开发一个应用，并且EnPlug可以很方便地通过SDK进行开发，以及可以让人在各种设备上运行展示他的软件。

Our SDK helps you engage with more people. Develop a custom Enplug app to showcase something you’ve already built or start from scratch. Either way, we make it easy.

这个是他们的主页上所说，的确，现在的数字广告屏幕，一方面是广告主不能自己控制内容，酒店或者超市不能按照自己的意愿订制广告播放内容，另一方面，受众也无法与广告进行互动，只能被动的收看屏幕内容。Enplug要提供的就是一种全新的互动数字电视广告屏幕。

看srt文件麻烦，写了一个python提取字幕的文字。

# -*- coding: utf-8 -*-
f = open("[1504120596] How I Build open platforms on Android.srt")             
f2 = open("t.txt","w")
line = f.readline()
cnt = 0
f2.write('nhello boy!')
while line:
    cnt = cnt + 1
    if cnt % 5 == 3:
        f2.write(str(line))
    line = f.readline()

f.close()
f2.close()

Posted on Edited on

班级红旗团支部需要刷微博数量，任务交到我头上，每天哔哔今天50条微博刷完了吗？

动手写了个自动刷微博机，放在Cubieboard上跑，省事又不费电，付一下最终成果图

刷微博成果

首先是Cubieboard上刷一个系统，这个很简单，一般小型化的linux就够用了。我是用的Lubuntu，当然你也可以使用其他的

装上python，一般linux下都有python2.7

sudo apt-get install python

然后是在新浪微博上获取开发者权限，最小的那种就够刷微博用了。取得APP_KEY，和APP_SECRET。

然后通过调用它的API进行发微博，基本30分钟一条新浪是不会封你的。否则会提示频率超过限制。

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
33
34
35
36
37
38
import weibo
APP_KEY = '3461922802'
APP_SECRET = '629a53dc7b5db5bdfce4cc5a543da44a'
CALL_BACK = 'https://api.weibo.com/oauth2/default.html'
import time
import datetime

def run():
        f = open("in.txt")
        line = f.readlines()
        client = weibo.APIClient(APP_KEY, APP_SECRET, CALL_BACK)
        auth_url = client.get_authorize_url()
        print "auth_url : " + auth_url
        code = raw_input("input the retured code : ")
        r = client.request_access_token(code)
        client.set_access_token(r.access_token, r.expires_in)

        while True:
            print "Ready! Do you want to send a new weibo?(y/n)"
            choice = raw_input()
            if choice == 'y' or choice == 'Y':
                #content = raw_input('input the your new weibo content : ')
                for i in range(1,5000):                            
                    j = i % 20
                    content = line[j]
                    client.statuses.update.post(status=content)
                    #+str(datetime.datetime.now()))
                    print "Send succesfully!"
                    time.sleep(1800)

                break;
                #else:
                #    print "Error! Empty content!"
            if choice == 'n' or choice == 'N':
                 break

if __name__ == "__main__":
    run()
#社会主义核心价值观#社会主义核心价值体系是兴国之魂，是社会主义先进文化的精髓，决定着中国特色社会主义发展方向。
#社会主义核心价值观#一个民族的发展兴旺，离不开进步的核心价值观引领方向；一个国家的团结和睦，离不开统一的核心价值观凝聚共识;一种文化的自信自强，离不开先进的核心价值观提供支撑。
#社会主义核心价值观#积极培育和践行社会主义核心价值观，对于巩固全党全民团结奋斗的共同思想基础，对于集聚实现中华民族伟大复兴中国梦的强大正能量，具有重要现实意义和深远历史意义。增强文化软实力，需要培育核心价值观。
#社会主义核心价值观#中国优秀传统文化的丰富哲学思想、人文精神、教化思想、道德理念等，可以为人们认识和改造世界提供有益启迪，可以为治国理政提供有益启示。对传统文化中适合于调理社会关系和鼓励人们向上向善的内容，我们要结合时代条件加以继承和发扬，赋予其新的涵义。
#社会主义核心价值观#为在广大妇女和家庭中积极培育和践行社会主义核心价值观，推进家庭道德文明建设工作。日前，建宁县妇女联合会隆重召开“最美家庭”表彰会。会上，建宁县公安局城关派出所民警饶建龙家庭荣获“最美家庭”荣誉称号并受到表彰。
#社会主义核心价值观#【传承中华优秀文化要躬耕践行从小做起】传承文化，从小做起，要以德为本。以德为本不仅是几千年来中国社会的道德评价标准，也是中华民族朴素的为人之道。对于少年儿童来说，强基固本尤为重要。
#社会主义核心价值观#【富强，民主，文明，和谐】富强即国富民强，是社会主义现代化国家经济建设的应然状态，是中华民族梦寐以求的美好夙愿，也是国家繁荣昌盛、人民幸福安康的物质基础。国富民强，是祖国和个人共同奋斗的目标。
#社会主义核心价值观#社会主义核心价值体系的特征 主导性。社会主义核心价值体系追求中国特色社会主义共同理想弘扬民族精神和时代精神，倡导社会主义荣辱观，集中反映了当代社会最基本的价值取向和行为准则，具有明确的主导性。社会主义核心价值体系具有主导性的内在根据在于它的先进性。
#社会主义核心价值观# 践行社会主义核心价值观，是全面深化改革开放，适应当今我国发展趋势的又一次精神力量提升。
#社会主义核心价值观#【树立崇高的信念，坚定自己的理想】在时代的机遇和挑战面前，把握时代的脉搏，跟上时代的步伐，在变革中完成自己角色的转换，为国家的发展、社会的进步作出自己应有的贡献
#社会主义核心价值观#社会主义核心价值观是社会主义核心价值体系的内核，体现社会主义核心价值体系的根本性质和基本特征，反映社会主义核心价值体系的丰富内涵和实践要求，是社会主义核心价值体系的高度凝练和集中表达。
#社会主义核心价值观#“学习是文明传承之途、人生成长之梯、政党巩固之基、国家兴盛之要”，习近平同志从四个不同层面强调学习的重要性，阐释我们为什么要重视学习的原因。学习是中国共产党人战胜艰难的法宝。
#社会主义核心价值观#习近平同志曾经引用联合国教科文组织埃德加·富尔先生的预言说明学习的重要性：“未来的文盲，不再是不识字的人，而是没有学会怎样学习的人。”
#社会主义核心价值观#以人为本，就是以最广大人民根本利益为本，尊重人民主体地位，发挥人民首创精神，保障人民各项权益，不断满足人民日益增长的物质文化需要，不断提高人民思想道德素质和科学文化素质，做到发展为了人民、发展依靠人民、发展成果由人民共享，促进人的全面发展。
#社会主义核心价值观#共同富裕，就是把发展作为党和国家的第一要务，坚持以经济建设为中心，坚持走改革开放之路，坚持聚精会神搞建设、一心一意谋发展，不断解放和发展社会生产力，不断改善人民生活，实现以人为本、全面协调可持续的科学发展，实现先富带后富，最终达到共同富裕。
#社会主义核心价值观#民主法治，就是坚持党的领导、人民当家作主和依法治国的有机统一，保证人民依法实行民主选举、民主决策、民主管理、民主监督，不断健全民主制度、丰富民主形式、拓宽民主渠道、扩大公民有序政治参与，坚持法律面前人人平等，树立社会主义法制权威，建设社会主义法治国家。
#社会主义核心价值观#公平正义，就是坚持公民在法律面前一律平等，尊重和保障人权，依法保证公民权利和自由，保证全体社会成员平等参与、平等发展，保证权力在阳光下运行，社会各方面利益关系得到妥善协调，人民内部矛盾和其他社会矛盾得到正确处理，发展的成果惠及全体人民。
#社会主义核心价值观#团结和谐，就是在中国特色社会主义共同理想的基础上加强全党的团结、党和人民的团结，努力造成又有集中又有民主、又有纪律又有自由、又有统一意志又有个人心情舒畅、生动活泼的政治局面。
#社会主义核心价值观#开放包容，就是坚持解放思想、实事求是、与时俱进，坚持面向现代化、面向世界、面向未来，既继承优良传统，又紧跟时代前进步伐，既虚心学习借鉴人类创造的一切文明成果，又自觉维护国家、民族的利益和尊严，既尊重差异、包容多样。
#社会主义核心价值观#共同富裕，就是把发展作为党和国家的第一要务，坚持以经济建设为中心，坚持走改革开放之路，坚持聚精会神搞建设、一心一意谋发展，不断解放和发展社会生产力，不断改善人民生活，实现以人为本、全面协调可持续的科学发展，最终达到共同富裕。

　

因为我们是朋友，所以你可以使用我的文字，但请注明出处：http://alwa.info

Posted on Edited on

问题1

四月一日快到了，Vayko想了个愚人的好办法——送礼物。嘿嘿，不要想的太好，这礼物可没那么简单，Vayko为了愚人，准备了一堆盒子，其中有一个盒子里面装了礼物。盒子里面可以再放零个或者多个盒子。假设放礼物的盒子里不再放其他盒子。

输入

((((B)()))())

(B)

输出

4

1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <cstdio>
#include <stack>
#include <cstring>
using namespace std;
int main(int argc, char const *argv[])
{
    char c[1111];
    while (~scanf("%s", c)){
        stack <int> st;
        while (!st.empty()) st.pop();
        for (int i = 0; i < strlen(c); i ++){
            if (c[i] == '('){
                st.push(1);
            }else if (c[i] == ')'){
                st.pop();
            }else {
                printf("%dn", st.size());
                break;
            }
        }
    }
    return 0;
}

栈的定义

栈和队列一个先进后出，一个先进先出。 堆栈（英语：stack），也可直接称栈。它的特殊之处在于只能允许在链结串列或阵列的一端（称为堆栈顶端指标，英语：top）进行加入资料（英语：push）和输出资料（英语：pop）的运算。另外堆叠也可以用一维阵列或连结串列的形式来完成。 由于堆栈数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作。 堆叠数据结构使用两种基本操作：推入（push）和弹出（pop）： 推入：将数据放入堆栈的顶端（阵列形式或串列形式），堆栈顶端top指标加一。 弹出：将顶端数据资料输出（回传），堆栈顶端资料减一。

- stack<INT</span> s；定义一个INT类型的栈s，也可以定义结构体的类型的。 </span>

- s.empty()判断栈是否是空的，是空的就返回真，不然就是假，所以这个是常常用在if和while里面。 </span>

- s.top()返回栈顶元素，a=s.top()的话那么a就被赋值成栈顶元素了，只是返回，但不改变栈里面的内容，也就是没有删除栈顶元素。</span>

- s.pop()用来删除栈顶元素的，没有返回值，不能对空栈使用。 </span>-</span>

s.size()返回栈里面有多少元素，就是用来确定栈里面的元素数量的。

- s.push()进栈的函数，s.push(a)。</span>

队列定义

队列（queue），是先进先出（FIFO, First-In-First-Out）的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端（称为rear）进行插入操作，在前端（称为front）进行删除操作。 队列的操作方式和堆栈类似，唯一的区别在于队列只允许新数据在后端进行添加。

- queue<INT</span> q;这里的INT和栈一样的。</span>

- q.empty(); q.pop(); q.size(); q.push(); </span>

- q.back(); q.front();这两个是队列的的返回方式，back是返回的队尾的元素，front是返回的队首的元素。</span>

手动实现一下栈和队列（数组或者链表）

问题2

某部队进行新兵队列训练，将新兵从一开始按顺序依次编号，并排成一行横队，训练的规则如下：从头开始一至二报数，凡报到二的出列，剩下的向小序号方向靠拢，再从头开始进行一至三报数，凡报到三的出列，剩下的向小序号方向靠拢，继续从头开始进行一至二报数。。。，以后从头开始轮流进行一至二报数、一至三报数直到剩下的人数不超过三人为止。

输入 </span>

2

20

40

输出 </span>

1 7 19

1 19 37

Posted on Edited on

给集训队14级的孩子稍微讲点算法入入门，真不希望每年集训队的孩子都这么弱。

问题1

LCS: 给出两个子序列A和B，求长度最大的公共子序列。 比如： 1,5,2,6,8,7 2,3,5,6,9,8,4 最长为5,6,8（另一个解2,6,8）

问题2

现有现金cash，和n种钱币，每种钱币有ni个，价值为di，求各种钱币组成的不超过cash的最大钱数…….

思路：二进制拆分转化为01背包

几何概念

  • 矢量是什么
  • 矢量加减法
  • 矢量叉积

- 矢量的概念： </span>　　

如果一条线段的端点是有次序之分的，我们把这种线段成为有向线段(directed segment)。如果有向线段p1p2的起点p1在坐标原点，我们可以把它称为矢量(vector)p2。

- 矢量加减法： </span>　　

设二维矢量P = ( x1, y1 )，Q = ( x2 , y2 )，则矢量加法定义为： P + Q = ( x1 + x2 , y1 + y2 )，同样的，矢量减法定义为： P - Q = ( x1 - x2 , y1 - y2 )。显然有性质 P + Q = Q + P，P - Q = - ( Q - P )。

- 矢量叉积： </span>　　

计算矢量叉积是与直线和线段相关算法的核心部分。设矢量P = ( x1, y1 )，Q = ( x2, y2 )，则矢量叉积定义为由(0,0)、p1、p2和p1+p2所组成的平行四边形的带符号的面积，即：P × Q = x1_y2 - x2_</span>y1，其结果是一个标量。显然有性质 P × Q = - ( Q × P ) 和 P × ( - Q ) = - ( P × Q )。</span> 　　

叉积的一个非常重要性质是可以通过它的符号判断两矢量相互之间的顺逆时针关系：

　　若 P × Q > 0 , 则P在Q的顺时针方向。

　　若 P × Q < 0 , 则P在Q的逆时针方向。

　　若 P × Q = 0 , 则P与Q共线，但可能同向也可能反向。

　　折线段的拐向判断：

　　折线段的拐向判断方法可以直接由矢量叉积的性质推出。对于有公共端点的线段p0p1和p1p2，通过计算(p2 - p0) × (p1 - p0)的符号便可以确定折线段的拐向：

　　若(p2 - p0) × (p1 - p0) > 0,则p0p1在p1点拐向右侧后得到p1p2。

　　若(p2 - p0) × (p1 - p0) < 0,则p0p1在p1点拐向左侧后得到p1p2。

　　若(p2 - p0) × (p1 - p0) = 0,则p0、p1、p2三点共线。

可解决问题

## - 判断点在线段上
## - 判断两线段是否相交 POJ 1066 POJ 1269 POJ 3304
## - 判断线段和直线是否相交
## - 判断矩形是否包含点 POJ 1410
## - 判断线段、折线、多边形是否在矩形中
## - 多边形面积 POJ 1654 POJ 3373
## - 判定点在多边形内 POJ 2318 POJ 2398
## - 凸包求法 （Andrew算法） POJ 1113 POJ 2187 POJ 1228

Posted on Edited on

自己圈的一场比赛,没想到这场等于有三道搜索,A题dfs,B题bfs+dfs,I题记忆化dfs,也是醉了

A题:

不要考虑什么先把能放的放下,反而导致编码复杂度非常高,因为只有15点,直接搜,把这个点作为中心点枚举四个方向就行.一点剪枝都不需要.

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
char s[220][220];
int ma[222][222];
int now[222][222];
#define maxn 101
struct Node{
    int x,y;
}p[maxn];
int pnum;
int tmpans;

void dfs(int id,int step,bool flag){
    if (id == pnum){
        for (int i = 0; i < pnum; i ++){
            if (now[p[i].x][p[i].y] == 0){
                return;
            }
        }
        tmpans = min(tmpans,step);
        return ;
    }
    int x = p[id].x, y = p[id].y;
    int t1 = now[x][y],t2 = now[x][y + 1], t3 = now[x - 1][y], t4 = now[x][y - 1],t5 = now[x + 1][y];
    if (ma[x][y] == 1 && ma[x - 1][y] != 0 && ma[x][y + 1] != 0){
        if (t1 == 1 && t2 == 1 && t3 == 1){
        }else {
            now[x][y] = 1;
            now[x][y + 1] = 1;
            now[x - 1][y] = 1;
            dfs(id + 1,step + 1, flag);
            now[x][y] = t1;
            now[x][y + 1] = t2;
            now[x - 1][y] = t3;

        }
    }
    if (!flag && ma[x][y] == 1 && ma[x - 1][y] != 0 && ma[x][y - 1] != 0){
        if (t1 == 1 && t3 == 1 && t4 == 1){
        }else {
            now[x][y] = 1;
            now[x][y - 1] = 1;
            now[x - 1][y] = 1;
            dfs(id + 1,step + 1, 1);
            now[x][y] = t1;
            now[x][y - 1] = t4;
            now[x - 1][y] = t3;

        }
    }
    if (!flag && ma[x][y] == 1 && ma[x + 1][y] != 0 && ma[x][y + 1] != 0){
        if (t1 == 1 && t5 == 1 && t2 == 1){
        }else {
            now[x][y] = 1;
            now[x][y + 1] = 1;
            now[x + 1][y] = 1;
            dfs(id + 1,step + 1, 1);
            now[x][y] = t1;
            now[x][y + 1] = t2;
            now[x + 1][y] = t5;

        }
    }
    if (!flag && ma[x][y] == 1 && ma[x + 1][y] != 0 && ma[x][y - 1] != 0){
        if (t1 == 1 && t4 == 1 && t5 == 1){
        }else {
            now[x][y] = 1;
            now[x][y - 1] = 1;
            now[x + 1][y] = 1;
            dfs(id + 1,step + 1, flag);
            now[x][y] = t1;
            now[x][y - 1] = t4;
            now[x + 1][y] = t5;

        }
    }
    dfs(id + 1,step, flag);
}

int main(){
    int n,m;
    while (~scanf("%d%d", &n, &m) && (n + m)){
        memset(ma, -1, sizeof(ma));
        memset(now, -1, sizeof(now));
        for (int i = 0; i < n; i ++){
            scanf("%s",s[i]);
            for (int  j = 0; j < m; j ++){
                if (s[i][j] == '#'){
                    ma[i + 1][j + 1] = 0;
                    now[i + 1][j + 1] = -1;
                }else {
                    ma[i + 1][j + 1] = 1;
                    now[i + 1][j + 1] = 0;
                }
            }   
        }

        pnum = 0;
        tmpans = 999999;
        for (int i = 1; i <= n; i ++){
            for (int j = 1; j <= m; j ++){
                if (ma[i][j] == 1){
                    p[pnum].x = i;
                    p[pnum ++].y = j;
                }           
            }
        }
        dfs(0,0,0);
        printf("%dn",tmpans == 999999? -1 : tmpans);           
    }
    return 0;
}
B题:

先bfs找出所有的点对的距离然后存下来,然后dfs找出所有的序列.

C题:

只要找到[i][j]对应的四个点就行了.

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
33
34
35
36
37
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int a[33][33],b[33][33];
int main(){
    int n;
    while (~scanf("%d", &n) && n){
        for (int i = 0; i < n; i ++){
            for (int j = 0; j < n; j ++){
                scanf("%d", &a[i][j]);
            }
        }
        for (int i = 0; i < n; i ++){
            for (int j = 0; j < n; j ++){
                scanf("%d", &b[i][j]);
            }
        }
        int cnt[4] = {0,0,0,0};
        for (int i = 0; i < n; i ++){
            for (int j = 0; j < n; j ++){
                if (a[i][j] == b[i][j]) cnt[0] ++;
                if (a[i][j] == b[j][n - i - 1]) cnt[1] ++;
                if (a[i][j] == b[n - i - 1][n - j - 1]) cnt[2] ++;
                if (a[i][j] == b[n - j - 1][i]) cnt[3] ++;
            }
        }
        int ans = 0;
        for (int i = 0; i < 4; i ++){
            ans = max(ans, cnt[i]);
        }
        printf("%dn",ans);
    }
    return 0;
}
F题:

比较繁琐的模拟,就是要考虑这个点有没有气(旁边有没有空格了).要用并查集+map(set).

I题:

状态压缩DP+记忆化搜索

注意预处理所有的状态能得到的分数,A和B他们都是走最优策略可以一起考虑区别就是dp数组记录的时候的区别,要dfs的区别出来,一个是先手一个是后手

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

int num[33],bag[22][10];
int sc[1 << 21],b,g,s;
int dp[1 << 21];
void init(int maxStatus){
    //cout << g << endl;
    int tmp[20] = {0};
    memset(tmp, 0, sizeof(tmp));
    for (int i = 0; i < maxStatus; i ++){
        for (int j = 0; j < b; j ++){
            if (i & (1 << j)){
                for (int k = 1; k <= g; k ++){
                    tmp[k] += bag[j][k];
                }
            }
        }
        int ret = 0;
        for (int j = 1; j <= g; j ++){
        //  cout << tmp[j] << ' ' ;
            ret += tmp[j] / s;
            tmp[j] = 0;
        }
    //  cout <<g <<  i << ' ' << ret << endl;
        sc[i] = ret;

    }
}

int dfs(int stat, int remain){
    if (dp[stat] != -1) return dp[stat];
    int ntstat, cha, ret = 0;
    for (int i = 0; i < b; i ++){
        if ((stat & (1 << i)) == 0){
            ntstat = stat | (1 << i);
            cha = sc[ntstat] - sc[stat];
            if (cha){
                ret = max(ret, dfs(ntstat, remain - cha) + cha);
            }else {
                ret = max(ret, remain - dfs(ntstat, remain));
            }
        }
    }
    dp[stat] = ret;
    return ret;
}

int main(){
    while (~scanf("%d%d%d", &g, &b, &s)){
        if (g + b + s == 0) break;
        //cout << g << b << s << endl;
        memset(bag, 0, sizeof(bag));
        memset(num, 0, sizeof(num));
        memset(sc, 0, sizeof(sc));
        memset(dp, -1, sizeof(dp));
        int k,t;
        for (int i = 0; i < b; i ++){
            scanf("%d", &k);
            //cout << "k = " << k;
            for (int j = 0; j < k; j ++){
                scanf("%d", &t);
                bag[i][t] ++;
                num[t] ++;
                //cout << t ;
            }
            //cout << endl;
        }

        int sum = 0;
        for (int i = 1; i <= g; i ++){
            sum += num[i] / s;
        }
        int maxSt = 1 << b;
        //cout << "maxSt" << maxSt << endl;
        init(maxSt);
        dp[maxSt - 1] = 0;
        int ans = dfs(0, sum);
        //cout << sum << ' ' << ans << endl;
        printf("%dn", ans - (sum - ans));
    }
}

Posted on Edited on

lca问题主要有两种解法，一种是基于二分搜索的算法，一种是把问题转化为RMQ问题来解决的。

算法一:
1.首先假设求lca(u,v)的话，不妨设v的depth比较大，那么就是说v先向上走depth[v] - depth[u]步，这样depth[u] == depth[v]。
2.有一种可能就是现在u，v已经在一个点了，那就不用管了。否则的话，u和v每次同步的向上走一个步长，直到走到同一个点为止。

上面的算法都需要每次向上走一个步长，这个步长的确定类似于parent[u]，不过现在的变成了parent[k][u]，这个表示从u点开始向上走2^k步到达的点，比如说parent[0][u]就相当于u的父亲节点，parent[1][u]这个点就是parent[0][u]这个点再向上走一步，也就是parent[0][parent[0][u]]。
对于这个k，我们进行二分搜索复杂度在logn。首先得预处理出来pa数组。
这样这个算法的复杂度就出来了。预处理是O(nlogn)，而每次查询lca的复杂度是O(logn)。

一个大概的的板子:

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
33
34
35
36
37
38
39
40
41
42
43
44
vector <int> ve[maxn];
int root;
int pa[maxlog][maxn]; //向上走2^k步到达的节点（超过根设为-1）
int dep[maxn];  //节点深度，从0开始

void dfs(int u, int p, int d){
    pa[0][u] = p;
    dep[u] = d;
    for (int i = 0; i < ve[u].size(); i ++){
        if (ve[u][i] != p) dfs(ve[u][i], u, d + 1);
    }
}

void init(){
    //memset(pa, -1, sizeof(pa));
    //预处理出pa[0]和dep数组
    dfs(root, -1, 0);
    //预处理pa数组
    for (int k = 0; k + 1 < maxlog; k ++){
        for (int i = 1; i <= n; i ++){
            if (pa[k][i] < 0) pa[k + 1][i] = -1;
            else pa[k + 1][i] = pa[k][pa[k][i]];
        }
    }
}

int lca(int u, int v){
    //让u和v先到达同一深度
    if (dep[u] > dep[v]) swap(u, v);
    for (int k = 0; k < maxlog; k ++){
        if ((dep[v] - dep[u]) >> k & 1){
            v = pa[k][v];
        }
    }
    if (u == v) return u;
    //二分搜索计算lca
    for (int k = maxlog - 1; k >= 0; k --){
        if (pa[k][u] != pa[k][v]){
            u = pa[k][u];
            v = pa[k][v];
        }
    }   
    return pa[0][u];
}

算法二:
首先定义：LCA(u,v)就是访问u之后到访问v之前所经过的顶点中距离根最近的那个。

例题：

POJ 1470

题意：
求出所有的lca(u,v)后看每个点出现几次。

思路：
1.就是直接上板子的题目很简单。
2.关键是求root，要算每个点的入度，入度为0便是root

代码：

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
int n,m;
#define maxn 4010
#define maxlog 13
vector <int> ve[maxn];
int ans[maxn];
int ru[maxn];
int root;
int pa[maxlog][maxn];
int dep[maxn];
void dfs(int u, int p, int d){
    pa[0][u] = p;
    dep[u] = d;
    for (int i = 0; i < ve[u].size(); i ++){
        if (ve[u][i] != p) dfs(ve[u][i], u, d + 1);
    }
}
void init(){
    //memset(pa, -1, sizeof(pa));
    dfs(root, -1, 0);
    for (int k = 0; k + 1 < maxlog; k ++){
        for (int i = 1; i <= n; i ++){
            if (pa[k][i] < 0) pa[k + 1][i] = -1;
            else pa[k + 1][i] = pa[k][pa[k][i]];
        }
    }
}
int lca(int u, int v){
    if (dep[u] > dep[v]) swap(u, v);
    for (int k = 0; k < maxlog; k ++){
        if ((dep[v] - dep[u]) >> k & 1){
            v = pa[k][v];
        }
    }
    if (u == v) return u;
    //二分搜索计算lca
    for (int k = maxlog - 1; k >= 0; k --){
        if (pa[k][u] != pa[k][v]){
            u = pa[k][u];
            v = pa[k][v];
        }
    }   
    return pa[0][u];
}
int main(){
    while (~scanf("%d", &n)){
        memset(ans, 0, sizeof(ans));
        memset(ru, 0, sizeof(ru));
        int u,pnum,v;
        for (int i = 1; i <= n; i ++){
            scanf("%d:(%d)", &u, &pnum);
            ve[u].clear();
            for (int j = 0; j < pnum; j ++){
                scanf("%d", &v);
                ve[u].push_back(v);
                ru[v] ++;
            }
        }
        for (int i = 1; i <= n; i++){
            if (ru[i] == 0) {
                root = i;
                break;
            }
        }
        init();
        scanf("%d", &m);
        char c;
        for (int i = 0; i < m; i ++){
            while(~scanf("%c", &c)){
                if (c == '('){
                    scanf("%d %d)", &u, &v);
                    ans[lca(u,v)] ++; 
                    break;
                }
            }
        }
        for (int i = 1; i <= n; i ++){
            if (ans[i] > 0){
                printf("%d:%dn", i, ans[i]);
            }
        }
    }
    return 0;
}

POJ 1986

题意：
求出lca(u,v)的同时算上这个路径上的len之和。

思路：
1.就是直接上板子的题目很简单，要加上一个dp[k][u]表示从u点向上走2^k的路径长度，这样处理的时候注意一点。
2.root随便设一个点不会改变路径的。

代码：

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
struct Info{
    int v,len;
    Info(int a,int b){
        v = a;
        len = b;
    }
};
#define maxn 100100
#define maxlogv 20
vector <Info> ve[maxn];
int n,m;
int pa[maxlogv][maxn];
int dep[maxn];
int dp[maxlogv][maxn];
void dfs(int u, int p, int d){
    pa[0][u] = p;
    dep[u] = d;
    for (int i = 0; i < ve[u].size(); i ++){
        if (ve[u][i].v != p){
            dp[0][ve[u][i].v] = ve[u][i].len;
            dfs(ve[u][i].v, u, d + 1);
        }
    }
}
void init(){
    memset(dp, 0, sizeof(dp));
    dfs(1, -1, 0);
    for (int k = 0; k + 1 < maxlogv; k ++){
        for (int v = 1; v <= n; v ++){
            if (pa[k][v] < 0) {
                pa[k + 1][v] = -1;
                dp[k + 1][v] = dp[k][v];
            }else {
                pa[k + 1][v] = pa[k][pa[k][v]];
                dp[k + 1][v] = dp[k][v] + dp[k][pa[k][v]];
            }
        }
    }
}
int lca(int u,int v){
    int ret = 0;
    if (dep[u] > dep[v]) swap(u, v);
    for (int k = 0; k < maxlogv; k ++){
        if ((dep[v] - dep[u]) >> k & 1){
            ret += dp[k][v];
            v = pa[k][v];
        }
    }
    if (u == v) return ret;
    for (int k = maxlogv; k >= 0; k --){
        if (pa[k][u] != pa[k][v]){
            ret += dp[k][u];
            ret += dp[k][v];
            u = pa[k][u];
            v = pa[k][v];
        }
    }
    //return pa[0][u];
    return ret + dp[0][u] + dp[0][v];
}
int main(){
    char s[100];
    int u,v,len;
    while (~scanf("%d%d", &n, &m)){
        for (int i = 1; i <= n; i ++){
            ve[i].clear();
        }
        for (int i = 1; i <= m; i ++){
            scanf("%d%d%d%s", &u, &v, &len, s);
            ve[u].push_back(Info(v,len));
            ve[v].push_back(Info(u,len));
        }
        init();
        int k;
        scanf("%d", &k);
        for (int i = 0; i < k; i ++){
            scanf("%d%d", &u, &v);
            printf("%dn", lca(u,v));
        }
    }
    return 0;
}

　

因为我们是朋友，所以你可以使用我的文字，但请注明出处：http://alwa.info

Posted on Edited on

先给出结论，然后给出几道例题

结论

如果一个动态规划方程能够用矩阵乘法来进行优化，那么必须满足：
  1. 状态必须是一维或者两维。超过两维的情况，可以通过把多维状态压缩到一维的方法降到两维（其实就是一个pre一个now表示i+1和i并没有降低状态数）
  2. 每个状态dp[i][j]必须满足只和dp[i-1][k]有关，并且这是一个线性关系。
  3. 转移矩阵需要都相同或者至少是循环出现的，才能使用快速幂来加速矩阵乘法。
  4. 假设第一维的大小是N，第二维的大小是M，那么矩阵乘法的时间复杂度为O(M^3logN)，而直接转移的复杂度至多是O(M^2N)，有时候甚至更小，通常只有M很小的时候并且N相当大的时候才会使用矩阵乘法，否则不值得。

POJ 3744 Scout YYF I

题意：

你在一条布满地雷的道路上，开始在坐标1。每次有概率P向前走一步，有概率1-P向前走两步。道中路某几个点上会有地雷，问你安全通过的概率。地雷数N<=10，坐标范围在100000000内。

dp的方程还是很好想的dp[i] = p * dp[i-1] + (1-p) * dp[i-2]，但是n比较大直接转移不行，考虑通过矩阵快速幂解决DP的转移方程。

代码：

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const ll mod = 1000000007ll;
int num[12];double p;
#define N 10
double Mat[N][N];
void product_mod(double a[][N], double b[][N], int n) {
    double c[N][N] = {};
    for ( int i=0; i<n; i++) {
        for ( int j=0; j<n; j++) {
            for ( int k=0; k<n; k++) {
                c[i][j] += a[i][k] * b[k][j];
            }
        }
    }
    for ( int i=0; i<n; i++) {
        for ( int j=0; j<n; j++) {
            a[i][j] = c[i][j];
        }
    }
}
//a ^ x % mod 
void power_mod(double a[][N], int x, int n) {
    memset(Mat, 0, sizeof(Mat));
    for ( int i=0; i<n; i++) Mat[i][i] = 1;
    while (x != 0) {
        if (x & 1) product_mod(Mat, a, n);
        product_mod(a, a, n);
        x >>= 1;
    }
}
double a[N][N];
int main(int argc, char const *argv[])
{
    int n;
    while (~scanf("%d%lf",&n, &p)){
        for (int i = 1; i <= n; i ++){
            scanf("%d", &num[i]);
        }
        sort(num + 1, num + n + 1);
        n = unique(num + 1, num + n + 1) - (num + 1);
        double ans = 1;
        num[0] = 0;
        for (int i = 1; i <= n; i ++){
            a[0][0] = p;a[0][1] = 1-p;
            a[1][0] = 1;a[1][1] = 0;
            power_mod(a,num[i] - num[i-1] - 1,2);
            ans *= (1 - Mat[0][0]);
            //cout << Mat[0][0] << &#39; &#39; << ans << endl;
        }
        printf("%.7fn",ans);
    }
    return 0;
}

HDU 2604 Queuing

题意：

求2个字母f和m构成的长度为m的序列中不含fmf以及fff的种数。

这题数据太水可以暴力，不过这个也是一个可以矩阵优化DP的题目。 

推出来的DP转移方程为dp[i] = dp[i-1] + dp[i-3] + dp[i-4] 

具体来说就是，当第i位为m的时候前i-1位只要满足条件就能实现了。当第i位为f的时候，就需要分情况讨论了，当第i-1位为m的时候，i-2不能为f，否则出现fmf的情况，那么就是说i-2必须是m，才能够实现，就是dp[i-3] * 1,（表示i-2位只能取m）。然后当第i-1位为f的时候，i-2也只能是m，并且i-3也只能是m，所以最后的几位是mmff，也就是这种情况的解为dp[i-4] * 1(表示i-3只能取一位，而且i-2，i-1都只有一种情况)。最终得出来dp[i] = dp[i-1] + dp[i-3] + dp[i-4]。 

而且这个还是一个线性转移，一维的考虑用矩阵进行转移 

| 1 0 1 1 |   |F[n-1]|   |F[n] | 

| 1 0 0 0 |   |F[n-2]|   |F[n-1]| 

| 0 1 0 0 | * |F[n-3]| = |F[n-2]| 

| 0 0 1 0 |   |F[n-4]|   |F[n-3]|

代码：

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
int num[12];
#define N 10
int Mat[N][N];
void product_mod(int a[][N], int b[][N], int n,int mod) {
    int c[N][N] = {};
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k ++) {
                c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % mod;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            a[i][j] = c[i][j];
        }
    }
}
//a ^ x % mod 
void power_mod(int a[][N], int x, int n, int mod) {
    memset(Mat, 0, sizeof(Mat));
    for (int i = 0; i < n; i ++) Mat[i][i] = 1;
    while (x != 0) {
        if (x & 1) product_mod(Mat, a, n, mod);
        product_mod(a, a, n, mod);
        x >>= 1;
    }
}
int A[N][N];
int main(int argc, char const *argv[])
{
    int n,m;
    while (~scanf("%d%d",&n, &m)){
        int mod = m;
        memset(A, 0, sizeof(A));
        A[0][0] = 1;A[0][2] = 1; A[0][3] = 1;
        A[1][0] = 1;A[2][1] = 1; A[3][2] = 1;
        num[1] = 2;
        num[2] = 4;
        num[3] = 6;
        num[4] = 9;
        if (n <= 4){
            printf("%dn", num[n] % mod);
        }else {
            //cout << "n = " << n << endl;
            power_mod(A, n - 4, 4, mod);
            //cout << a[0][0] << ' ' << a[0][1] << ' ' << a[0][2] << ' ' << a[0][3] << endl;
            int ans = Mat[0][0] * num[4] + Mat[0][1] * num[3] + Mat[0][2] * num[2] +
                Mat[0][3] * num[1];
            ans %= mod;
            printf("%dn", ans);
        }
    }
    return 0;
}

HDU 2294 Pendant</span>

差不多的转移方程，只是矩阵的大小有改变。

dp[i][j]=dp[i-1][j]*j+dp[i-1][j-1]*(k-j+1)   

dp[i][j]表示由j种不同的珠子组成长度为i的吊链的方法数

　

因为我们是朋友，所以你可以使用我的文字，但请注明出处：http://alwa.info