We are apologize for the inconvenience but you need to download
more modern browser in order to be able to browse our page

Download Safari
Download Safari
Download Chrome
Download Chrome
Download Firefox
Download Firefox
Download IE 10+
Download IE 10+

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;
}