警示后人 & hack 数据 & 数据生成器

声明：本贴所有内容来自本贴发布之前的所有帖，内容结合了作者自己踩的坑

前缀和后缀和要对 $0$ 取 $\max$
最大子列和不能为空，即不能对 $0$ 取 $\max$
修改和翻转操作中，在操作函数内操作，而不是打上标记延迟到 pushdown 中做
打翻转懒标记时不能暴力 pushup，应该交换前缀最大和与后缀最大和
RE 80pts，特判 $tot = 0$ 的情况
修改的懒标记不能以 0/-1 等值当作未操作，应该用一个不在数值范围内的数，例如 $10^9$
（FHQ-Treap）在操作函数中不要乱 pushup/pushdown，应在合并或分裂时进行
（FHQ-Treap）TLE 40pts，插入时不能一个一个插入，应一次分裂多次合并或先将要插入的数用 $O(n)$ 建树的方法构造成 Treap 再合并
（FHQ-Treap） $O(n)$ 建树后要 dfs 把正确的信息 pushup 上去
（FHQ-Treap 数组写法）注意 0 号节点的最大子列和答案应为极小值
（FHQ-Treap 数组写法）pushdown 时不要把数据放到 0 号节点了
（指针写法）pushdown/pushup 时注意判断空指针
MLE 10pts，关于删除子树：如果你 #2~#9 全是 MLE
10pts，关于最值：警钟撅烂,如果你10pts
（块状链表）块状链表的大小一定要严格控制在 $\sqrt{n} \sim 2\sqrt{n}$ ，警示后人
（内存回收）每次翻垃圾桶的时候都要记得初始化对应节点的全部信息，警示后人
（Splay 内存回收）TLE，在删除的时候回收空间，删除时先将要删除的序列的父节点的左儿子指向空，然后进行回收空间。
（FHQ-Treap）TLE，插入时先将所有待插入的数合并，再合并到原来的树中去。
（平衡树中有哨兵结点）WA 90pts，在查询答案时应将这两点的答案剔除，如果wa#3
告诫后人
（带旋转）关于这题的更新旋转标记顺序
最小值不要设置得过小例如 INT_MIN，最大值不要设置得过大，例如 INT_MAX

一些 hack 数据：

PLAIN

9 8
0 0 0 0 0 0 0 0 0 
GET-SUM 5 4
INSERT 8 3 1 1 1
GET-SUM 1 12

3 3
-1 2 3
INSERT 3 2 -2 3
INSERT 4 2 -1 2
MAX-SUM 3 5

4 4
1 1 1 1
MAKE-SAME 1 2 0
INSERT 0 3 1 1 1
GET-SUM 3 5

5 10
1 1 1 1 1
DELETE 2 4
INSERT 1 4 2 3 4 5
GET-SUM 3 3

10 7
7 12 7 7 6 5 11 9 18 7 
MAX-SUM 
INSERT 4 1 -13
REVERSE 10 2
MAKE-SAME 2 10 -6
INSERT 8 3 -20 10 -18
REVERSE 14 1
MAX-SUM 

5 3
0 0 0 0 0 
MAKE-SAME 2 4 0
REVERSE 4 2
GET-SUM 2 3

1 1
-1
MAX-SUM

一个数据生成器：

CPP

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <ctime>
using namespace std;
const int N=5,M=5,MAXN=10;
int fs(int x)
{
	if(rand()%2==0)
		return -x;
	else
		return x;
}
string chose[10];
int main(){
	freopen("in.in","w",stdout);
	chose[1]="INSERT";
	chose[2]="DELETE";
	chose[3]="MAKE-SAME";
	chose[4]="REVERSE";
	chose[5]="GET-SUM";
	chose[6]="MAX-SUM";
    srand(time(NULL));
    int n=N,m=M;
    printf("%d %d\n",n,m);
    for(int i=1;i<=n;i++){
        int x=rand()%10;
        printf("%d ",x);
    }
    puts(""); 
    for(int i=1,opt,v,x,k;i<=m;i++)
	{
		opt=rand()%6+1;
		if(!n)
		{
			if((opt%2)==0)
				opt=1;
			else
				opt=6;
		}
		cout<<chose[opt]<<" ";
		switch(opt)
		{
			case 1:
				v=rand()%(n+1);
				k=rand()%N+1;
				printf("%d %d",v,k);
				for(int i=1;i<=k;i++)
					printf(" %d",fs( rand()%(MAXN+1) ));
				puts("");
				n+=k; 
				break;
			case 2:
				v=rand()%n+1;
				k=rand()%(n-v+1)+1;
				printf("%d %d\n",v,k);
				n-=k;
				break;
			case 3:
				v=rand()%n+1;
				k=rand()%(n-v+1)+1;
				x=fs( rand()%(MAXN+1) );
				printf("%d %d %d\n",v,k,x);
				break;
			case 4:
				v=rand()%n+1;
				k=rand()%(n-v+1)+1;
				printf("%d %d\n",v,k);
				break;
			case 5:
				v=rand()%n+1;
				k=rand()%(n-v+1)+1;
				printf("%d %d\n",v,k);
				break;
			default:
				puts("");
				break;
		}
    }
    return 0;
}

警示后人 & hack 数据 & 数据生成器

讨论操作

回复

相关推荐

警示后人 & hack 数据 & 数据生成器