Category: Tricks

背景

今天写了一道POI的题目，血wa
要到了数据以后发现，这货需要SPJ才能测
于是研习了一下fopen、fscanf和fprintf的用法

用法

先定义一个文件指针（我不知道这货叫什么 QwQ）

FILE *data;

之后把这个文件指针指向我们需要的文件：

data = fopen("input.in","r");

然后I/O操作的时候指定一下用哪个文件指针即可：

fscanf(data,"%d",&n);
fprintf(data,"%d",n);

优越性

freopen是重定向全局的输入输出
但因为有些时候我们需要同时对多个文件进行I/O操作
所以就需要用fopen + fscanf + fprintf辣！

我之前一直是用.bat文件进行对拍，代码如下:

@echo off
:rep
echo running SJ.exe
SJ.exe > 11input.in
echo running bc.exe
bc.exe < 11input.in > 12bc.out
echo running me.exe
me.exe < 11input.in > 12me.out
fc 12me.out 12bc.out > nul
if not errorlevel 1 goto rep

但有一个我很想实现的功能：对拍时显示运行时间
于是今天考试的时候折腾了一下，搞出了下面这个东西：

#include<iostream>
#include<cstdio>
#include<ctime>
#include<cstdlib>
#include<windows.h>
using namespace std;

int main(){
	time_t a,b;
	while (true) {
		system("SJ.exe > 11input.in");
		
		a = clock();
		system("bc.exe < 11input.in > 12bc.out");
		b = clock(); printf("bc.exe cost %dms\n",b-a); 
		
		a = clock();
		system("me.exe < 11input.in > 12me.out");
		b = clock(); printf("me.exe cost %dms\n",b-a); 
		
		int tmp = system("fc 12bc.out 12me.out > result.txt");
		if (tmp == 1) system("taskkill /F /IM check.exe");
		cout<<endl<<endl;
	}
	return 0;
}

主要是应用了clock()和system()函数
要背住的东西也只有：”taskkill /F /IM check.exe”
运行效果如下：

感觉很不错，用了多少时间一目了然
因为调用了system()所以时间不是特别准，需要减去20ms的样子

近日，有幸看到一点黑科技，是一些函数：

— Built-in Function: int __builtin_popcount (unsigned int x)
Returns the number of 1-bits in x.
返回‘1’的个数。

— Built-in Function: int __builtin_ffs (unsigned int x)
Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero.
返回右起第一个‘1’的位置。

对于这些函数，他们全是O(1)的
不仅如此，你还会发现你不包含任何库都可以编译通过
而且你会发现，它们也不是宏 QAQ
是不是感觉很神奇？

经过多方查证，这些是GCC编译器提供的函数
换一句话来，这些下划线函数NOI系列赛可以用QAQ
参见：https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
该系列的其他函数，可以在上面的网址全部查到

最后附上据说是 __builtin_popcount 的源码：

int count(unsigned u){
	u = (u & 0x55555555) + ((u >> 1) & 0x55555555);
    u = (u & 0x33333333) + ((u >> 2) & 0x33333333);
    u = (u & 0x0F0F0F0F) + ((u >> 4) & 0x0F0F0F0F);
    u = (u & 0x00FF00FF) + ((u >> 8) & 0x00FF00FF);
    u = (u & 0x0000FFFF) + ((u >> 16) & 0x0000FFFF);
    return u;
}

众所周知，DFS可能会爆系统栈。
当然手写栈可以解决这个问题，但是我不会QAQ
但昨天%原教的代码，发现DFS，可以用一个“BFS + while() + 当前弧” 给优雅地替换掉
例如：

void DFS(int w, int f){
	l[w] = ++tot; dep[w] = dep[f]+1;
	for (int i=head[w];i;i=nxt[i])
		if (to[i] != f) DFS(to[i], w);
	r[w] = tot; fa[w][0] = f;
}

就可以用一下代码给完美替代：

inline void BFS(){
	BUF[1] = 1; dep[1] = 1;
	for (int fro=1,bak=1;bak<=fro;bak++){
		int w = BUF[bak];
		for (int i=head[w];i;i=nxt[i]){
			if (!dep[to[i]]) dep[to[i]] = dep[w]+1,
			fa[to[i]][0] = w, BUF[++fro] = to[i];
		}
	}
}

inline void DFS(){
	for (int i=1;i<=n;i++) now[i] = head[i];
	int w = 1; tot = 1;
	while (w) {
		if (!now[w]) {
			r[w] = tot;
			w = fa[w][0];
		} else {
			if (!l[w]) l[w] = ++tot;
			int tmp = to[now[w]]; now[w] = nxt[now[w]];
			if (dep[tmp] != dep[w]+1) continue;
			else w = tmp;
		}
	}
}

代码虽然长一点，但是可以接受，链剖也是可以搞的
至于空间代价，这个只是多了一个当前弧的数组
至于时间代价，有图有真相：

众所周知，HDU等搭建在windows下的OJ系统栈小得一逼，所以我们得手动扩栈……..
其实平时比赛，如果递归爆栈了，也是可以用这个特殊技能水一水的：

G++: 
int size = 256 << 20; // 256MB  
char *p = (char*)malloc(size) + size;  
__asm__("movl %0, %%esp\n" :: "r"(p)); 

C++: 
#pragma comment(linker, "/STACK:102400000,102400000")    

当然，如果会写手工栈，那也是极好的，然而我不会QAQ

———— 2016.8.28 更新 ————-
在BZOJ这种linux平台下，好像上面的扩栈方法不管用
于是我们可以添加如下代码：

const int main_stack=16;
char my_stack[128<<20];//À©Îª128MB
int main()
{
	__asm__("movl %%esp, (%%eax);\n"::"a"(my_stack):"memory");
	__asm__("movl %%eax, %%esp;\n"::"a"(my_stack+sizeof(my_stack)-main_stack):"%esp");
	my_main();
	__asm__("movl (%%eax), %%esp;\n"::"a"(my_stack):"%esp");
	return 0;
}

然后把原来的 int main() 改成 int my_main() 即可

—————————— UPD 2017.7.3 ——————————
在g++的编译命令里加入-Wl,--stack=536870912也可以开栈