DFS不让用数组的后果~~

背景：

今天有一道题是这样的
小明要看电视，给出今天的节目列表，问最多可以完整观看多少个节目，节目时间均为整点
输入：总共节目数 节目1开始时间 节目1结束时间 节目2开始时间 节目2结束时间
例：2 1 3 5 10
限时1000ms

显然应该使用DFS暴搜的一道题
关键是。。。老师说不让用数组。

那么问题来了：

1. 如何存储目前的搜索状态
2. 如何存储节目列表

该怎么办呢？ 于是开始用各种阴招：

1. 利用bitmap表示24个小时，绕开数组
2. 由于每一层的节目时间是相同的，那么可以通过巧妙设置栈，解决存储问题

其实之前还想了：

• 每一层做一个dispatcher（需要vector）
• 将任务拆解成小的task或者coroutine，然后用异步实现（需要socket）
• 暴力多线程
• fork
• 写临时文件
• 把数据写回到stdin

解释：

• gcc和vc都支持inline函数和寄存器传参，在x86 x64 armv7 aarch64架构上可以保证用三个寄存器传递参数，从而使每一个函数建立的栈帧不会被破坏。
• 递归调用handler，并且handler中没有类似于alloca的动态栈分配，每一次调用的函数建立的栈帧完全相同，进而可以一步一步改写调用堆栈上所有函数的a和b。
• 我的dfs算法中任一确定层的a b是固定的，因此每次handler执行到同一深度的时候，都会访问到相同的a和b。

该代码在x64 gcc -O0，x64 gcc -O3，x86 vc Release编译选项下均通过。

理论上只要处理器模型相似，并且编译器不像vc Debug下默认设置一样在每个函数起始处将局部变量清除，该代码均可正常运行。

两排notUsed是为了孤立出a和b，防止被意外覆写。

（PS：实际上这个思路类似于UAF，搞pwn的童鞋应该会明白哒）

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <stddef.h>

#ifdef __GNUC__
#define REGPARM __attribute__((regparm(3))) 
#else
#define REGPARM __fastcall
#endif

#ifdef __GNUC__
#define PLEASE_INLINE __attribute__((always_inline))
#else
#define PLEASE_INLINE inline
#endif

PLEASE_INLINE char getBit(int bitmap,int pos){
	return (bitmap &amp; (1 &lt;&lt; pos)) ? 1 : 0;
}

PLEASE_INLINE int hasBitOverlap(int bitmap1,int bitmap2){
	int i;
	for(i = 0;i &lt; 32;i++){
		if( getBit(bitmap1,i) == 1 &amp;&amp; 1 == getBit(bitmap2,i)){
			return 1;
		}
	}
	return 0;
}

PLEASE_INLINE int genBit(int a, int b){
	int i,ret = 0;
	for(i = a; i&lt; b; i++){
		ret |= (1 &lt;&lt; i);
	}
	return ret;
}

int oriDepth = 0;
int *pa = 0;
int *pb = 0;
int hasRead = 0;

int REGPARM handler(int maxDepth, int curTimeTable,int curK){
	int notUsed1, notUsed2, notUsed3, notUsed4, notUsed5, notUsed6, notUsed7, notUsed8, notUsed9, notUsed10;
	int a, b, i, ret1, ret2;
	int _notUsed1, _notUsed2, _notUsed3, _notUsed4, _notUsed5, _notUsed6, _notUsed7, _notUsed8, _notUsed9, _notUsed10;

	if (maxDepth == 0) {
		if (!hasRead) {
			ptrdiff_t pdiffa = pa - &amp;a;
			ptrdiff_t pdiffb = pb - &amp;b;
			int *cura = pa, *curb = pb;
			for (i = 0; i &lt; oriDepth; i++) { scanf("%d", cura); scanf("%d", curb); cura += pdiffa; curb += pdiffb; } hasRead = 1; } return curK; } pa = &amp;a; pb = &amp;b; ret1 = handler(maxDepth - 1, curTimeTable, curK); a = *&amp;a; b = *&amp;b; genBit(a,b); if(hasBitOverlap(curTimeTable,genBit(a,b))){ return ret1; } else{ ret2 = handler(maxDepth - 1, curTimeTable | genBit(a,b), curK + 1); return ret1 &gt; ret2 ? ret1 : ret2;
	}
}

int main(){
	int n,i,a,b, lastFound = -1;
	scanf("%d",&amp;n);

	oriDepth = n;
	printf("%d",handler(n, 0, 0));
	return 0;
}

附：当时提交的版本（部分使用数组）：

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

char getBit(int bitmap,int pos){
	return (bitmap & (1 << pos)) ? 1 : 0;
}

int hasBitOverlap(int bitmap1,int bitmap2){
	int i;
	for(i = 0;i < 32;i++){
		if( getBit(bitmap1,i) == 1 && 1 == getBit(bitmap2,i)){
			return 1;
		}
	}
	return 0;
}

int genBit(int a, int b){
	int i,ret = 0;
	for(i = a; i< b; i++){
		ret |= (1 << i);
	}
	return ret;
}

int *programList = 0;

int inputHelperA(int curDepth){
	return programList[curDepth * 2];
}

int inputHelperB(int curDepth){
	return programList[curDepth * 2 + 1];
}

int handler(int maxDepth, int curTimeTable,int curK){
	int a, b,ret1,ret2;

	if(maxDepth == 0)
		return curK;
	
	a = inputHelperA(maxDepth);
	b = inputHelperB(maxDepth);
	genBit(a,b);
	if(hasBitOverlap(curTimeTable,genBit(a,b))){
		return handler(maxDepth - 1, curTimeTable, curK);
	}
	else{
		ret1 = handler(maxDepth - 1, curTimeTable, curK);
		ret2 = handler(maxDepth - 1, curTimeTable | genBit(a,b), curK + 1);
		return ret1 > ret2 ? ret1 : ret2;
	}
}

int main(){
	int n,i,a,b, lastFound = -1;
	scanf("%d",&n);
	programList = (int *)malloc((n+1) * 2 * sizeof(int));
	for(i = n; i > 0; i--){
		scanf("%d%d", &a,&b);
		programList[2 * i] = a;
		programList[2 * i + 1] = b;
	}
	printf("%d",handler(n, 0, 0));
	return 0;
}