难得做一场五小时的比赛……本以为这比赛，前两个小时做完水题就该手手睡了……没想到做完了五小时……不错不错……
题目传送门
刚上来必然是看A题……A题乍一看有想法，实际上加上那个序之后比较恶心……想了五六分钟不看了……
接下来发现C题是水的，过之……
然后发现H题似乎可做，题意是：给你一个字符串，包含0，1和？，把？调整成01，使最大连续0 或 连续 1长度最小，求这个长度……
最大XXX最小，第一反应必然是二分……但是这个判定贪心并不见得好使
比如：
AA？AA，如果判定答案3，刚开始扫到了AA，此时还剩一个，下一个字符是？，涉及讨论，而且不太好办……
于是要讨论就干脆讨论个清楚……
首先判断答案为1的情况：答案为1的充要条件是串为01010101……或者101010101…O(N)扫一遍直接验证就行
当然要注意逻辑，譬如？？？？这种也得考虑周全……
我写的比较恶心……现在想想应该写两个小自动机走一趟就判出来了……
1 bool check1(){
2 bool haveOdd1 = 0;
3 bool haveOdd0 = 0;
4 bool haveEven1 = 0;
5 bool haveEven0 = 0;
6 for (int i = 0;i<len;i++){
7 if (i % 2 == 1){
8 if (str[i] == '1') haveOdd1 = 1;
9 if (str[i] == '0') haveOdd0 = 1;
10 } else {
11 if (str[i] == '1') haveEven1 = 1;
12 if (str[i] == '0') haveEven0 = 1;
13 }
14 }
15 if (haveOdd1 && haveOdd0) return 0;
16 if (haveEven1 && haveEven0) return 0;
17 if (!haveOdd1 && !haveOdd0) return 1;
18 if (!haveEven1 && !haveEven0) return 1;
19 if (haveOdd1 && haveEven0) return 1;
20 if (haveOdd0 && haveEven1) return 1;
21 return 0;
22 }
23
然后我们知道了答案>=2，就好办了……
如果连续？的长度=2
情况1：A??A -> ABBA，可无视
情况2：A??B -> ABAB，可无视
如果>2：
A(n个?) =AB(n-1)个？
大概就可以归纳证明连续？的长度>=2都可以通过构造来忽略……
接下来，只有一个？的情况：
A?A -> ABA ，可无视
A?B -> 找两边长度较小的那个，变过去……
?A……或者 ……A?：这种贴边的可以无视……
1 memset(size,0,sizeof(size));
2 memset(block,0,sizeof(block));
3 for (int i = 0 , j = 0;i<len ; i = j){
4 while (str[i]==str[j])
5 j++;
6 for (int k = i;k<j;k++){
7 block[k]=i;
8 }
9 size[i] = j - i;
10 }
11 for (int i = 0 , j = 0;i<len ; i = j){
12 while (str[i]==str[j])
13 j++;
14 if (str[i] == '?'){
15 if (size[i]>1) continue;
16 if (i == 0) continue;
17 if (j == len) continue;
18 if (str[i-1] == str[j]) continue;
19 if (size[block[i-1]]<=size[block[j]]) size[block[i-1]]++;
20 else size[block[j]]++;
21 }
22 }
23 int ans = 2;
24 for (int i = 0;i<len;i++){
25 if (str[i]=='?') continue;
26 if (size[i]>ans) ans = size[i];
27 }
写的时候SB了……WA了几次……
接下来发现没啥题可开，只能做H……
H题意就是给一个序列1，2，3……N，每次取出区间[L,R]，倒序接在序列的最后，若干操作后，求序列现在啥样了……
估计有大神会用线段树搞定，反正我不会……
我们知道，用数组可以O（1）的快速访问区间L,R，但是要花费O（N）的时间去移动……
用链表可以O（1）的移动，但是要找区间[L,R]可就O（N）了……
早就听说块状链表的概念……在链表里存储一个小数组，一般来讲数组大小=SQRT（N），这样相当于链表节点数也是SQRT（N），于是各种操作都是O（SQRT（N））了……
说着容易，写起来就恶心了……
首先，定义struct……这是里面的小数组……
1 const int MSIZE = 500;
2 struct vi {
3 int data[MSIZE];
4 int l;
5 int r;
6 void push_back(int i){
7 data[r++] = i;
8 }
9 int pop_back(){
10 return data[--r];
11 }
12 int pop_front(){
13 return data[l++];
14 }
15 int size(){
16 return r-l;
17 }
18 };
好吧……我承认从前这个地方是typedef vector<int> vi;
然后是块状链表的节点……其中rev是标记里面的东西是否倒序
1 struct node {
2 vi *data;
3 bool rev;
4 node *next;
5 node(vi *D=NULL,bool R=0,node *N=NULL){
6 data=D;
7 rev=R;
8 next=N;
9 }
10 };
11
为了提高效率，后来手写了new……
1 const int FULLSIZE = 800;
2 node nPool[FULLSIZE+10];
3 node *nPHead = nPool;
4 vi viPool[FULLSIZE+10];
5 vi *viPHead = viPool;
6 inline bool full (){
7 return nPHead - nPool > FULLSIZE || viPHead - viPool >FULLSIZE;
8 }
9
10 inline node *newNode(vi *D=NULL,bool R=0,node *N=NULL){
11 nPHead->data = D;
12 nPHead->rev = R;
13 nPHead->next = N;
14 return nPHead++;
15 }
16 inline vi *newVi(){
17 viPHead->l = viPHead ->r = 0;
18 return viPHead++;
19 }
接下来先写几个好写的过程……这是用一个数组构造块状链表的函数
1 void build(int arr[]){
2 nPHead = nPool;
3 viPHead = viPool;
4 head = tail = newNode (newVi(),0,NULL);
5 for (int i = 0;i < n;){
6 for (int cnt = 0; i<n && cnt <MSIZE ; i++,cnt++){
7 tail->data->push_back(arr[i]);
8 }
9 if (i < n)
10 tail = tail->next = newNode (newVi(),0,NULL);
11 }
12 }
这是把块状链表里的东西全部放进一个临时数组里的函数
1 void flush(int arr[]){
2 int s = 0;
3 for (node *i=head;i;i=i->next){
4 if (i->rev) {
5 for (int j=i->data->r-1;j>=i->data->l;j--)
6 arr[s++]=(*i->data).data[j];
7 } else {
8 for (int j=i->data->l;j<i->data->r;j++)
9 arr[s++]=(*i->data).data[j];
10 }
11 }
12 }
这是把一个节点里面的数组前size个取出来，把该节点一分为二的函数……
1 node *split(node *now,int size){
2 vi *tmp = newVi();
3 if (now->rev){
4 for (int i = 0;i<size;i++){
5 tmp->push_back(now->data->pop_back());
6 }
7 } else {
8 for (int i = 0;i<size;i++){
9 tmp->push_back(now->data->pop_front());
10 }
11 }
12 now->next = newNode(now->data,now->rev,now->next);
13 now->rev = 0;
14 now->data = tmp;
15 if (now == tail) tail = now->next;
16 return now;
17 }
好……进入主体……
1 void work(int l,int r){
2 // flp : lp's father
3 node *flp = NULL;
4 // lp : 指向区间左边的指针
5 node *lp = NULL;
6 // rp : 指向区间右边的指针
7 node *rp = NULL;
8 // [lp ，rp]是闭区间
9
10 //定位 lp ， 确定 flp
11 for (node *i = head ; i!=NULL;i=i->next){
12 if (l == 0) {
13 lp = i;
14 break;
15 } else if (l < i->data->size()) {
16 i = split(i,l);
17 flp = i;
18 lp = i->next;
19 break;
20 } else {
21 flp = i;
22 l -= i->data->size();
23 }
24 }
25
26 //定位 rp
27 for (node *i = head ; i!=NULL;i=i->next){
28 if (r == i->data->size()) {
29 rp = i;
30 break;
31 } else if (r <i->data->size()) {
32 i = split(i,r);
33 rp = i;
34 break;
35 } else r-=i->data->size();
36 }
37 // rpn = rp -> next
38 node *rpn = rp->next;
39
40 // 把 lp 
rp 的一段取出来放进TMP数组里
41 // 然后将每个节点标记成反序，指针反过来接着
42 static node* tmp[100010];
43 int tsize;
44 tsize = 0;
45 for (node *i = lp; ;i = i->next){
46 i->rev = !i->rev;
47 tmp[tsize++] = i;
48 if (i == rp) break;
49 }
50 for (int i = tsize-1; i>0 ; i--){
51 tmp[i]->next = tmp[i-1];
52 }
53 tmp[0]->next = NULL;
54
55 // 讨论如何接回原链表
56 // 原链表构造：head -> …… -> flp -> lp -> …… -> rp -> rpn -> …… ->tail
57 if (flp == NULL && rpn == NULL){
58 // 翻转整个链表的情况，修正 head 和 tail
59 // 原：lp（head） -> …… -> rp （tail）
60 // 新：rp（head） -> …… -> lp （tail）
61 head = rp;
62 tail = lp;
63 return ;
64 }
65 if (flp == NULL) {
66 //区间包含表头的情况
67 //原：lp(head) -> …… -> rp -> rpn -> …… ->tail
68 //新：rpn -> …… ->tail -> rp -> . ->lp
69 head = rpn;
70 tail->next = rp;
71 tail = lp;
72 return ;
73 }
74 if (rpn == NULL) {
75 //区间包含链表尾部的情况
76 //原：head -> …… -> flp -> lp -> …… -> rp （tail）
77 //新：head -> ->flp -> rp -> -> lp
78 flp->next = rp;
79 tail = lp;
80 return;
81 }
82 // 一般情况
83 // 原链表构造：head -> …… -> flp -> lp -> …… -> rp -> rpn -> …… ->tail
84 // 新构造：head -> …… -> flp -> rpn -> …… ->tail -> rp -> …… -> lp
85 flp->next = rpn;
86 tail->next = rp;
87 tail = lp;
88 }
总而言之，四个函数（构造，输出，分裂节点，取区间翻转接在后面）都搞定了，但是一直TLE……
手写了若干随机数据后发现，问题在于链表的长度……
按照我的写法，每次操作，假如说区间L，R，给L定位时，如果L恰好在某节点中，该节点下标范围[A,B]，则分成两块[A,L-1] ,[L,B]然后 返回[L,B]那个指针……给R定位时也是同样……这导致每次操作都会增加两个链表节点……
从前提交的版本，按照图论之类的经验，设定的FULLSIZE比较大，尽管不用手动回收内存（回收内存：flush一次，build一次，O(N)），减小了O(N)执行的次数……但是带来的问题就是块状链表会退化成普通的链表……
现在发到日志的版本，通过多次实验，设定了一个较小的FULLSIZE = 800……过了……
Time = 0.600MS大概……
总之，第一次写块状链表，过了……心情舒畅啊……