Posted Inspiring Learning / Competitive Programming

动态规划1

笔记

最优子结构：子结构最优，全局一定最优
无后效性：各个决策部分单独存在，不会相互影响

  1. 确定状态
    • 维度从低往高试
  2. 确定转移方程
    • 每一个状态的决策
    • 初始值
    • 边界问题
  3. 是否可以降低维度或其他优化

最大子串和

题意：给你一个有正有负的序列，求一个=子串（连续的一段），使其和最大！
样例输入： -5 6 -1 5 4 -7
样例输出： 14

状态：f[i]表示前i个数的最大子串和，每个状态只有两种决策：1. 与前面构成一个子串 2. 单独成为一个子串的开头
转移方程: f[i]=max(f[i−1]+a[i],a[i])f[i]=max(f[i−1]+a[i],a[i])

不相交的两个子串的最大和

给你一个有正有负的序列，求两个不重叠的子串，使其和最大！

方法一

两个不重叠的子串中间一定有一个分界点，我们可以枚举这个分界点，分别求出这个点左边的最大子串和以及右边的最大子串和

方法二

定义状态f[i][j]为前i个数组成了j个子串的最大值，当前状态下有两种选择，一种是与前面组成子串，一种是单独成为一个子串，但是需要枚举这个数前面的串的结尾在哪里
状态转移方程为f[i][j]=max(f[i−1][j]+a[i],f[k][j−1]+a[i],0<k<if[i][j]=max(f[i−1][j]+a[i],f[k][j−1]+a[i],0<k<i​
优化：可以用前缀和维护k维度，算出前k个数的最大和

最大子矩形

在一个矩阵中找到一个子矩阵，该子矩阵和最大！！输出最大和即可。

从暴力的角度考虑，这道题需要枚举矩形的两个顶点，也就是O(n^4)
我们可以只枚举两个顶点的行坐标，即找到这个矩形的高度所在的位置，然后把每一列的数之和求出来当做一个数，可以提前求出每一列前缀和，也就转化成了求最大子串和。

最长公共子序列

给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。
最长公共子序列:公共子序列中长度最长的子序列。
给定两个序列X={x1,x2,…,xm}和Y={y1,y2,…, yn}，找出X和Y的一个最长公共子序列。

状态：f[i][j]表示X的前i位与Y的前j位最长公共子序列的长度
转移方程：

1
2
3
4
5
6
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
{
    if(X[i]==Y[j]) f[i][j]=f[i-1][j-1]+1;
    else f[i][j]=max(f[i-1][j],f[i][j-1]);
}

回文词

回文词是一种对称的字符串——也就是说，一个回文词，从左到右读和从右到左读得到的结果是一样的。任意给定一个字符串，通过插入若干字符，都可以变成一个回文词。你的任务是写一个程序，求出将给定字符串变成回文词所需插入的最少字符数。比如字符串“Ab3bd”，在插入两个字符后可以变成一个回文词（“dAb3bAd”或“Adb3bdA”）。然而，插入两个以下的字符无法使它变成一个回文词。
给出一个字符串求出使其变为回文串需要插入的最少字符数。

思路：需要添加的字符的长度为原字符串的总长度减去现有的回文串长度，所以只要求出原字符串的回文串的长度就可以解决了
回文串的定义是正串与反串一样，那么正串与反串的最长公共子序列长度就是回文串的长度
为什么不是最长公共子串长度？* 在添加字符的时候可以在任意位置插入，所以不必要求连续。所以如果只能从左右两边加入，那么就是最长公共子串长度*

乘积最大

设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。
如：有一个数字串：312， 当N=3，K=1时会有以下两种分法： 1） 312=36 2） 312=62
这时，符合题目要求的结果是：31*2=62

状态：f[i][j]表示前i位使用k个乘号的最大乘积
决策：

  1. 这个数与前面的数组成更大的数，需要枚举这个数的起点
  2. 单独成为一个新数

*在算乘积的时候可以先算出前缀‘乘’*
转移方程:

1
2
3
4
5
6
7
8
9
10
11
for(int i=1;i<=n;i++)
    muti[i]*=muti[i-1]*a[i];
muti[0]=1;

for(int i=1;i<=n;i++)
for(int j=1;j<=k;j++)
{
    f[i][j]=f[i-1][j-1]*a[i];
    for(int k=1;k<i;k++)
        f[i][j]=f[k][j-1]*(muti[i]/muti[k-1]);
}
Posted Inspiring Learning / Competitive Programming

2018/12/8模拟赛

终于有一次能在考场上打出正解的模拟赛

连线游戏

题目

连线游戏（lines.cpp）
文件输入输出
时间限制：1s
空间限制：256M

【题目描述】
Farmer John最近发明了一个游戏，来考验自命不凡的贝茜。游戏开始的时候，FJ会给贝茜一块画着N (2 <= N <= 200)个不重合的点的木板，其中第i个点的横、纵坐标分别为X_i和Y_i (-1,000 <= X_i <=1,000； -1,000 <= Y_i <= 1,000)。
贝茜可以选两个点画一条过它们的直线，当且仅当平面上不存在与画出直线平行的直线。游戏结束时贝茜的得分，就是她画出的直线的总条数。为了在游戏中胜出，贝茜找到了你，希望你帮她计算一下最大可能得分。

【输入格式】
第1行: 输入1个正整数：N
第2..N+1行: 第i+1行用2个用空格隔开的整数X_i、Y_i，描述了点i的坐标

【输入样例】(lines.in):
4
-1 1
-2 0
0 0
1 1

【输出格式】
第1行: 输出1个整数，表示贝茜的最大得分，即她能画出的互不平行的直线数

【输出样例】 (lines.out):
4

【输出说明】

贝茜能画出以下4种斜率的直线：-1，0，1/3以及1。

思路

  • 枚举两两构成直线的k值，如果k值不存在，则ans++。

遇到的坑

  • 要考虑精度问题，考试的时候写了1e-5，结果炸了，改成1e-7就对了，甚至不加精度判断都能AC
  • 特判分母为0的情况，本来以为Inf是无限大，所有Inf表示的都是一个意思，但实际炸了……
    ###AC代码
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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int N=210;
int x[N],y[N],n;
double ans[N*N];

int main()
{	
	freopen("lines.in","r",stdin);
	freopen("lines.out","w",stdout);
	
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&x[i],&y[i]);
	
	int cnt=0;
	for(int i=1;i<=n;i++)
	for(int j=i+1;j<=n;j++)
	{
		double sta;
		if(x[i]-x[j]==0) sta=0x3f3f3f3f;
		else sta=1.0*(y[i]-y[j])/(x[i]-x[j]);
		
		bool flag=1;
		for(int k=1;k<=cnt;k++)
		{
			if(ans[k]-sta<=1e-10 && ans[k]-sta>=-1e-10)
			{
				flag=0;
				break;	
			} 
		}
		if(flag) ans[++cnt]=sta;//printf("%lf\n",sta);
	}
	printf("%d\n",cnt);
	return 0; 
}

独木桥

题目

【问题描述】
战争已经进入到紧要时刻。你是运输小队长，正在率领运输部队向前线运送物资。运输任务像做题一样无聊。你希望找些刺激，于是命令你的士兵们到前方的一座独木桥上欣赏风景，而你留在桥下欣赏士兵们。士兵们十分愤怒，因为这座独木桥十分狭窄，只能容纳一个人通过。假如有两个人相向而行在桥上相遇，那么他们两人将无法绕过对方，只能由一个人回头下桥，让另一个人先通过。但是，可以有多个人同时呆在同一个位置。
突然，你收到从指挥部发来的信息，敌军的轰炸机正朝着你所在的独木桥飞来！为了安全，你的部队必须撤下独木桥。独木桥的长度为L，士兵们只能呆在坐标为整数的位置，所有士兵的速度都为1，当一个士兵某一时刻来到了坐标为0或L+1的位置时，他就离开了独木桥。
每个士兵都有一个初始面对的方向，他们会以匀速朝着这个方向行走，中途不会自己改变方向。但是，如果两个士兵面对面相遇，他们无法彼此通过对方，于是就分别转身，继续行走。转身不需要任何时间。
由于先前的愤怒，你已不能控制你的士兵。甚至，你连每个士兵初始面对的方向都不知道。因此，你想要知道你的部队最少需要多少时间就可能全部撤离独木桥。另外，总部也在安排阻拦敌人的进攻，因此你还需要知道你的部队最多需要多少时间才能全部撤离独木桥。

【输入文件】
第一行：一个整数L，表示独木桥的长度。桥上的坐标为1..L
第二行：一个整数N，表示初始时留在桥上士兵的数目。
第三行：有N个整数，分别表示每个士兵的初始坐标。初始时，没有两个士兵在同一坐标。

【输出文件】只有一行，输出两个整数，分别表示部队撤离独木桥的最小时间和最大时间。两个整数用一个空格分开。

【样例输入】
4
2
1 3

【样例输出】
2 4

【数据规模及约定】
N≤L≤1000

思路

两个人遇见并分别掉头与两个人继续往前走是等价的，因为人与人之间不存在差异。

每个士兵只有两种选择，向左或向右

最大值就是每个士兵的最长选择的集合中的最大值

最小值就是每个士兵的最短选择的集合中的最大值

遇到的坑

  • 最外一层都是max，满足木桶原理

AC代码

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 <algorithm>
#include <cstring>
using namespace std;

int l,n,ans1,ans2;//max,min

int main()
{
	freopen("bridge.in","r",stdin);
	freopen("bridge.out","w",stdout);
	
	scanf("%d%d",&l,&n);
	while(n--)
	{
		int x;
		scanf("%d",&x);
		ans1=max(ans1,min(x,l-x+1));//min
		ans2=max(ans2,max(x,l-x+1));//max
	}
	printf("%d %d\n",ans1,ans2);
	return 0;
}

俄罗斯方块

最水的一道题，直接模拟，分七种情况，细心一点就好了

AC代码

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int N=110;
int mp[N],c,p,ans;

int main()
{
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
	
	scanf("%d%d",&c,&p);
	for(int i=1;i<=c;i++)
		scanf("%d",&mp[i]);

	if(p==1)
	{
		for(int i=1;i<=c-3;i++)
			if(mp[i]==mp[i+1] && mp[i+1]==mp[i+2] && mp[i+2]==mp[i+3]) ans++;
		printf("%d\n",c+ans);
		return 0;
	}
	if(p==2)
	{
		for(int i=1;i<=c-1;i++)
			if(mp[i]==mp[i+1]) ans++;
		printf("%d\n",ans);
		return 0;
	}
	if(p==3)
	{
		for(int i=1;i<=c-2;i++)
			if(mp[i]==mp[i+1] && mp[i+1]==mp[i+2]-1) ans++;
		for(int i=1;i<=c-1;i++)
			if(mp[i]==mp[i+1]+1) ans++;
		printf("%d\n",ans);
		return 0;
	}
	if(p==4)
	{
		for(int i=1;i<=c-2;i++)
			if(mp[i]==mp[i+1]+1 && mp[i+1]==mp[i+2]) ans++;
		for(int i=1;i<=c-1;i++)
			if(mp[i]==mp[i+1]-1) ans++;
		printf("%d\n",ans);
		return 0;
	}
	if(p==5)
	{
		for(int i=1;i<=c-2;i++)
			if(mp[i]==mp[i+1] && mp[i+1]==mp[i+2]) ans++;
		for(int i=1;i<=c-1;i++)
			if(mp[i]==mp[i+1]-1) ans++;
		for(int i=1;i<=c-1;i++)
			if(mp[i]==mp[i+1]+1) ans++;
		for(int i=1;i<=c-2;i++)
			if(mp[i]==mp[i+1]+1 && mp[i]==mp[i+2]) ans++;
		printf("%d\n",ans);
		return 0;
	}
	if(p==6)
	{
		for(int i=1;i<=c-2;i++)
			if(mp[i]==mp[i+1] && mp[i+1]==mp[i+2]) ans++;
		for(int i=1;i<=c-1;i++)
			if(mp[i]==mp[i+1]) ans++; 
		for(int i=1;i<=c-2;i++)
			if(mp[i]==mp[i+1]-1 && mp[i+1]==mp[i+2]) ans++;
		for(int i=1;i<=c-1;i++)
			if(mp[i]==mp[i+1]+2) ans++; 
		printf("%d\n",ans);
		return 0;
	}
	if(p==7)
	{
		for(int i=1;i<=c-2;i++)
			if(mp[i]==mp[i+1] && mp[i+1]==mp[i+2]) ans++;
		for(int i=1;i<=c-1;i++)
			if(mp[i]==mp[i+1]) ans++; 
		for(int i=1;i<=c-2;i++)
			if(mp[i]==mp[i+1] && mp[i+1]==mp[i+2]+1) ans++;
		for(int i=1;i<=c-1;i++)
			if(mp[i]==mp[i+1]-2) ans++; 
		printf("%d\n",ans);
		return 0;
	}
	return 0;
}

/*
5 7
2 0 3 1 2
*/
汉诺塔问题
Posted Inspiring Learning / Competitive Programming

汉诺塔问题

题面

相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘(如下图)。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。

自己汉诺塔问题晕了很久，但搜索写多了至少也有一些通悟

不妨假设：

  • 当只有

    1
    1个盘子

    时

    1. 把盘子从A直接移到C

  • 当只有

    1
    2个盘子

    时

    1. 将上面的盘子从A移动到B
    2. 将下面的盘子从A移动到C
    3. 将B上的盘子从B移动到C

  • 当有

    1
    3个盘子

    时

    1. 将上面的盘子从A移动到C
    2. 将中间的盘子从A移动到B
    3. 将C上的盘子从C移动到B
    4. 将下面的盘子从A移动到C
    5. 将B上面的盘子从B移到A
    6. 将B上的盘子从B移到C
    7. 将A上的盘子从A移到C

可以发现当有3个盘子时，中间就会转化成2个盘子的情况，2个盘子最后就会转化成1个盘子的情况，显然可采用递归的方法

思路

把n-1个盘子移到B，再把最下面的盘子移到C，再把B上的n-1个盘子移到C

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
#include <iostream>
#include <cstdio>
using namespace std;

int ans,n;

void dfs(int x,int a,int b,int c)// num from  trans   end
{
    if(x==1)
    {
        printf("move from %d to %d\n",a,c);
        ans++;
     	return;   
    }
    dfs(x-1,a,c,b);
    printf("move from %d to %d\n",a,c);
    ans++;
    dfs(x-1,b,a,c);
}

int main()
{
    scanf("%d",&n);
    dfs(n,1,2,3);
    printf("need %d steps\n",ans);
	return 0;
}

自己遇到的坑

  • a,b,c三个柱子没有搞清楚，递归函数里到底四个参数分别代表什么要搞清楚

其他一些……

  • f[n]=f[n-1]*2+1

    本次的次数就等于把n-1个盘子移动了两回，加上剩下的最大的盘子移动的一次

Posted Inspiring Learning / Competitive Programming

滑动窗口

思路：单调队列

以求最小值为例

  • 在读取每一个数 ai 的过程中，判断队尾的数是否大于ai,如果大于则证明队尾的数已经没有意义了，因为***它已经不可能成为现在及以后所有窗口内的最小值***，不妨弹出，重复以上操作，直到ai小于队尾的数，再把ai放到队尾
  • 当现在的长度已经达到窗口的长度时，每一次都会输出最小值，因为队列是单调递减的，第一个数一定是现在窗口内最小的数，直接输出
  • 在队尾添加的过程中，***要始终保证队列里的数都在窗口内***，当区间长度大于窗口长度时，要从队首弹出

自己遇到的坑

  • ***队列内存储的是这个数的位置，不是这个数的大小***，大小通过数组类似映射表示

  • *要考虑好整个过程的先后顺序*

    1. 先确保队列内的数都在范围内
    2. 把所有比ai小的队尾数依次弹出
    3. 将ai入队
    4. 如果达到滑动窗口范围，输出值

  • *两个数的编号相减加1代表该闭区间的长度*

  • 当算完最小值时队列不一定是空的，要先清空队列

C++ STL 双端队列 deque

q.push_back: 从后端加入 q.pop_back: 从后端弹出
从前端就是front
q.clear: 清空队列
q.size(): 读取队列的长度，但是好像类型不是int，只能用来判断数组是否为空

AC代码

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
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;

const int N=1e6+5;
int a[N];
deque<int> q;

int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    
//	q.push_back(1);
    //minn
    for(int i=1;i<=n;i++)
    {
        if(q.size() && i-k>=q.front()) q.pop_front();
        while(q.size() && a[i]<=a[q.back()]) q.pop_back();
        q.push_back(i);
        if(i>=k) printf("%d ",a[q.front()]);
    }
    
//	return 0;
    printf("\n");
    q.clear();
//	q.push_back(1);
    //maxn
    for(int i=1;i<=n;i++)
    {
        if(q.size() && i-k>=q.front()) q.pop_front();
        while(q.size() && a[i]>=a[q.back()]) q.pop_back();
        q.push_back(i);
        if(i>=k) printf("%d ",a[q.front()]);
    }
    
    return 0;
}
Follow

Links

follow.it

Recents

Categories

Archives

Tags

AI5
Beijing1
Berkeley1
Chicago2
Chinese New Year1
Chrome1
F13
Halloween1
Kentucky1
Microsoft10
Seattle8
Simulation1
Stanford1
Surface1
TOEFL1
Thanksgiving1
algorithm1
application2
birthday1
break2
class2
coding1
column1
competition13
cooking4
data structures1
debate1
event1
exam5
exercise3
family1
final1
flight1
food2
friend1
friends2
hangout1
history1
holiday2
log2
movie9
museum1
neural network2
newspaper1
note7
presentation3
product1
project2
python3
sports1
summer1
teamwork2
travel16
tutorial6
update3
video1
×