[NKU]sweet @ Google && TopCoder && CodeForces

  BlogJava :: 首页 :: 联系 :: 聚合  :: 管理
  33 Posts :: 1 Stories :: 15 Comments :: 0 Trackbacks
难得做一场五小时的比赛……本以为这比赛,前两个小时做完水题就该手手睡了……没想到做完了五小时……不错不错……

题目传送门

刚上来必然是看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]>1continue;
16                 if (i == 0continue;
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->= viPHead ->= 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<&& 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 *= 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 *= 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 *= 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大概……

总之,第一次写块状链表,过了……心情舒畅啊……

posted on 2011-02-06 10:19 sweetsc 阅读(779) 评论(4)  编辑  收藏

Feedback

# re: World Finals Warmup I @UVA [块状链表] 2011-02-07 12:01 rujialiu
er...H是我出的教学题。标程用的splay,块状链表也可以。直接用STL的vector实现就可以了,程序不到2k,速度不受影响(uva上0.3秒左右,取的size=1000)。  回复  更多评论
  

# re: World Finals Warmup I @UVA [块状链表] 2011-02-07 14:45 [NKU]sweet
@rujialiu
Orz rujialiu老师……受教了  回复  更多评论
  

# re: World Finals Warmup I @UVA [块状链表] 2011-03-22 16:36 。。。
怎么可能这么麻烦。。。你在想什么。。。。。  回复  更多评论
  

# re: World Finals Warmup I @UVA [块状链表] 2011-03-22 16:41 。。。
@。。。
我说的是01那题。。。  回复  更多评论
  


只有注册用户登录后才能发表评论。


网站导航: