HCTF-Douglas-Peuker 笔记

Author: Dik1s@0xFA.club

HCTF的一道PPC,计算的规则很好懂。

把每个运算符都考虑成单独的,分别做先后运算,如下:

((15+3)*8)-7
(15+(3*8))-7
15+((3*8)-7)
15+(3*(8-7))
((15+3)*(8-7)) //+ - *
((15+3)*(8-7)) //- + *

最后将这些所有式子求出的值相加得到最终结果。

输入形式如下:

6[2,5,10,9,3,34]++*-* 

代码需感谢小学弟和大哥的支持。

代码如下:

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
#define INF 0x3fffffff
#define maxn 1000

typedef long long LL;
const LL MOD = 1e9+7;

LL A[maxn], C[maxn][maxn];
char op[maxn];
LL dp[maxn][maxn];

int main(int nnnnn,char* args[])
{
	int n;char ch;
	A[0] = 1;
	for(int i=1; i<=maxn-10; i++)
		A[i] = (A[i-1] * i)%MOD;
		//A内存放阶乘地址
	C[0][0] = 1;//规定排列组合C00=1
	for(int i=1; i<=maxn-10; i++)
	{
		C[i][0] = 1;
		for(int j=1; j<=i; j++)
			C[i][j] = (C[i-1][j-1] + C[i-1][j])%MOD;
	}//计算出排列组合的数,供下方调用。
	stringstream ss(args[1]);
	ss >> n >> ch;
	//n为数据的个数
	{
		memset(dp, 0, sizeof(dp));
		for(int i=1; i<=n; i++)
			ss >> dp[i][i] >> ch;
			//dp[i][i]此时为其中数据,如4[3,8,11,4]*++   d[1][1]=3  d[2][2]=8  以此类推
		ss >> op+1;
		//op内储存符号地址
		for(int L=2; L <= n; L++)
		{
			for(int i=1; i+L-1 <= n; i++)
			{
				int j = i + L - 1;
				dp[i][j] = 0;
				for(int k=i; k<j; k++)
				{
					LL t;
					if(op[k] == '*'){
					t = (dp[i][k]*dp[k+1][j])%MOD;
					}
					if(op[k] == '+'){
					t = (dp[i][k]*A[j-k-1]+dp[k+1][j]*A[k-i])%MOD;
					}
					if(op[k] == '-'){
					t = (dp[i][k]*A[j-k-1]-dp[k+1][j]*A[k-i])%MOD;
					}
					dp[i][j] = (dp[i][j]+t*C[j-i-1][k-i])%MOD;
				}
			}
		}
		printf("%lld\n", (dp[1][n]+MOD)%MOD );
	}
	return 0;
}

这段代码很有意思,所以总结学习一下。

原本按照计算规则老老实实的写代码的话需要计算的次数为n(n为数据的个数)的阶乘次。那么当计算数据较多的时候将会需要很多的时间。不能够符合题目的要求。

但是这段代码巧妙的减少了时间复杂度。

下面是总结:

-------------------
|        |        |
-------------------
| n个符号| m个符号 |    
0        k        p

如上图所示,我们假设有一个式子,在其中随机选取一个符号,作为K。K的左边有n个符号,k的右边有m个符号。

现在假设:

n=2
m=3 那么:

n将有两种情况,这两种情况求出的值我们分别记为a,b。
m将有六种情况,这六种情况我们分别记为A,B,C,D,E,F.

当k为+或者-时,最后的结果为:

	 |-A  =a1                       |-A =b1
	 |-B  =a2                       |-B =b2
	 |-C  =a3                       |-C =b3
    a(+-)|-D  =a4                  b(+-)|-D =b4 
	 |-E  =a5                       |-E =b5
	 |-F  =a6                       |-F =b6

最终的结果为:

sum = a1+a2+a3+a4+a5+a6+b1+b2+b3+b4+b5+b6
等同于
sum = (a+A)+(a+B)+...+(a+F)+(b+A)+(b+B)+...(b+F)

那么里面一共有个a和b在最后处理的时候相加了

也就是

sum = a*A[3](+-)(A+B+C+D+E+F)+b*A[3](+-)(A+B+C+D+E+F)    

这也就意味着,k的左边也就是n这一边最后处理的数据为:

(a+b)*A[m]   

也就是左边按照规则处理完以后的数据乘以右边数据数量的阶乘,以此类推右边也是这个样子。

那么最后的结果就是:

dp[n]*A[m](+-)dp[m]*A[n]
dp[n]为左边n个符号处理以后的结果,dp[m]为右边m个符号处理以后的结果.A为阶乘

当k为*时

sum = a1*a2*a3*a4*a5*a6*b1*b2*b3*b4*b5*b6
等同于:
sum = a*(A+B+C+D+E+F)+b*(A+B+C+D+E+F)

也就没有阶乘了。

好,思想讲完了,现在来分析代码。

输入啥的就不说了,注释里面已经有了,直接分析。

L表示的是当前循环计算的数据的个数,例如当L=2时,如下:

(15*8)+11+4 -> 15*(8+11)+4 -> 15*8+(11+4)

就只计算括号中的数据,并将计算结果储存在d[i][j]中

dp[i][j]表示的是从第i个数据计算到第j个数据的结果,如

dp[1][2]=15*8    dp[2][3]=8+11

dp[1][2]中1指的是第一个数据15,2指的是第二个数据8

当L=3时,如下:

|15*8+11|+4 -> 15*|8+11+4|

在计算 15*8+11 的时候,他不会再重新计算 15 x 88+11 会直接调用上次循环的结果dp[1][2]和dp[2][3]进行计算,最后得出来整个式子的结果。这个式子是第一个数据到第三个数据,那么就用dp[1][3]储存。以此类推,当处理四个数据时,调用前三个数据的结果。依次递归,所以空间需要很大,但是会大大的节约运算的时间。

最后考虑排列组合的问题。

dp[i][j] = (dp[i][j] + t * C[j-i-1][k-i])%MOD; //t是处理完当前K的值以后的结果

那么为什么要乘以C[j-i-1][k-i])呢。

还是那个例子:

15*8+11+4   

现在计算整个式子的值,当K在第二个+的地方。

处理完(15*8)+(11+4)以后的值为t,但是这个t只是一种情况。什么意思呢?

(15*8)+(11+4)

这个t的值是这个式子的值,没有错,但是它并没有考虑是先算乘号还是先算加号。

所以就需要考虑先算(15*8)还是先算(11+4)。现在我们只考虑符号。

这个式子一共有三个符号* + +,去除第二个加号已经是最低优先级运算符,已经确定是最后运算,所以不考虑。所以只有两个符号需要考虑。

这两个运算符需要考虑先后顺序,而且顺序又不能重叠,所以类似于排列组合。

如:

|A |B |
-------

现在有A,B两个位置可以填运算符。

K为已经确定为最低优先运算级的第二个加号,K的左边有一个运算符*,K的右边有一个运算符+,那么可以在A中填 * 号,那么B中只能够填+号了。当在A中填+号,那么B中也只能填 * 号。

所以填进去的方式有种。

好,现在假设有五个符号

 * + - + *

把K设置在- 号的位置。K的左边和K的右边计算结果已经计算出为t,即t为:

(data1 * data2 + data3 ) - (data4 + dadta5 *data6)

上述式子中在左边和右边分开考虑时候的一种情况。

那么当左右一起考虑的时候一共有几种情况呢?

去掉中间的K指定的符号还有四个符号,即还可以填四个符号,如下:

|A |B |C |D |
-------------

现把这四个符号用1,2,3,4表示:

*  +  +  *
1  2  3  4

那么因为K的左边和右边分开考虑计算(这一点已经在上面说啦~),那么1,2和3,4的先后顺序互不影响。也就是把1放进A把2放进D是一样的,因为他们中间的-号是最低优先级。

举个例子:

现在确定优先级为 1 3 2 4,这个时候的式子可以看做:

((data1 * data2) + data3)  - ((data4 + dadta5) *data6)

在确定优先级为 1 4 2 3,这个时候式子可以看做:

((data1 * data2) + data3)  - (data4 + (dadta5 *data6))

假如这四个式子按照这个顺序排,则一共有种组合,而且每种组合都在K的两边进行和K没有关系。

但是已经说了:

t = k的左边所有情况求出的最后的值 - k的右边所有情况求出的值

那么k的左边的所有情况,也就是 data1 x data2 + data3 的所有情况,包括:

((data1 * data2) + data3)
(data1 * (data2 + data3))

也就是种情况的和。

当时在四个符号排列的时候,计算K的左边和右边的值并不是左边或者右边计算出来的最后的值。只是左边或者右边所有情况中的一种情况。

所以最后的四个符号再加上K所指定的符号 - 一共五个符号排列计算最后的值的所有情况应该为种.

情况数再乘以t就是最后的值。

代入上述代码中,即一共就j-i-1个符号需要排列。k左边的符号有k-i个。

也就是

最后利用递归依次求出解并放置在dp数组中调用,直到L为n,循环结束输出最后一组值就是结果。

以上,欢迎指正教育 :)

Powered by 0xFA-Team
©Copyright 2014-2500 0xFA-Team