難得做一場五小時的比賽……本以為這比賽，前兩個小時做完水題就該手手睡了……沒想到做完了五小時……不錯不錯……
題目傳送門
剛上來必然是看A題……A題乍一看有想法，實際上加上那個序之后比較惡心……想了五六分鐘不看了……
接下來發(fā)現(xiàn)C題是水的，過之……
然后發(fā)現(xiàn)H題似乎可做，題意是：給你一個字符串，包含0，1和？，把？調整成01，使最大連續(xù)0 或 連續(xù) 1長度最小，求這個長度……
最大XXX最小，第一反應必然是二分……但是這個判定貪心并不見得好使
比如：
AA？AA，如果判定答案3，剛開始掃到了AA，此時還剩一個，下一個字符是？，涉及討論，而且不太好辦……
于是要討論就干脆討論個清楚……
首先判斷答案為1的情況：答案為1的充要條件是串為01010101……或者101010101…O(N)掃一遍直接驗證就行
當然要注意邏輯，譬如？？？？這種也得考慮周全……
我寫的比較惡心……現(xià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，就好辦了……
如果連續(xù)？的長度=2
情況1：A??A -> ABBA，可無視
情況2：A??B -> ABAB，可無視
如果>2：
A(n個?) =AB(n-1)個？
大概就可以歸納證明連續(xù)？的長度>=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了幾次……
接下來發(fā)現(xiàn)沒啥題可開，只能做H……
H題意就是給一個序列1，2，3……N，每次取出區(qū)間[L,R]，倒序接在序列的最后，若干操作后，求序列現(xiàn)在啥樣了……
估計有大神會用線段樹搞定，反正我不會……
我們知道，用數(shù)組可以O（1）的快速訪問區(qū)間L,R，但是要花費O（N）的時間去移動……
用鏈表可以O（1）的移動，但是要找區(qū)間[L,R]可就O（N）了……
早就聽說塊狀鏈表的概念……在鏈表里存儲一個小數(shù)組，一般來講數(shù)組大小=SQRT（N），這樣相當于鏈表節(jié)點數(shù)也是SQRT（N），于是各種操作都是O（SQRT（N））了……
說著容易，寫起來就惡心了……
首先，定義struct……這是里面的小數(shù)組……
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;
然后是塊狀鏈表的節(jié)點……其中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 }
接下來先寫幾個好寫的過程……這是用一個數(shù)組構造塊狀鏈表的函數(shù)
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 }
這是把塊狀鏈表里的東西全部放進一個臨時數(shù)組里的函數(shù)
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 }
這是把一個節(jié)點里面的數(shù)組前size個取出來，把該節(jié)點一分為二的函數(shù)……
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 : 指向區(qū)間左邊的指針
5 node *lp = NULL;
6 // rp : 指向區(qū)間右邊的指針
7 node *rp = NULL;
8 // [lp ，rp]是閉區(qū)間
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數(shù)組里
41 // 然后將每個節(jié)點標記成反序，指針反過來接著
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 //區(qū)間包含表頭的情況
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 //區(qū)間包含鏈表尾部的情況
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 }
總而言之，四個函數(shù)（構造，輸出，分裂節(jié)點，取區(qū)間翻轉接在后面）都搞定了，但是一直TLE……
手寫了若干隨機數(shù)據(jù)后發(fā)現(xiàn)，問題在于鏈表的長度……
按照我的寫法，每次操作，假如說區(qū)間L，R，給L定位時，如果L恰好在某節(jié)點中，該節(jié)點下標范圍[A,B]，則分成兩塊[A,L-1] ,[L,B]然后 返回[L,B]那個指針……給R定位時也是同樣……這導致每次操作都會增加兩個鏈表節(jié)點……
從前提交的版本，按照圖論之類的經(jīng)驗，設定的FULLSIZE比較大，盡管不用手動回收內存（回收內存：flush一次，build一次，O(N)），減小了O(N)執(zhí)行的次數(shù)……但是帶來的問題就是塊狀鏈表會退化成普通的鏈表……
現(xiàn)在發(fā)到日志的版本，通過多次實驗，設定了一個較小的FULLSIZE = 800……過了……
Time = 0.600MS大概……
總之，第一次寫塊狀鏈表，過了……心情舒暢啊……