DLUT onsite【线段树+数学+dp专场有木有!!!】[改](D + F)(zju 3542 + zju 3544)

虽然是用了10小时来打5小时的比赛,但也弱爆了。神马都不会啊。
A zoj 3539
搜索+字符串,连暴力都不会写
B zoj 3540
竟然是矩形并!!!。。不过就算是“矩形并”,也不会写。。线段树神马的,都不会哇。。
C zoj 3541
好巧妙好经典的N^2DP,我不会啊。
D zoj 3542
纯模拟。。。善用cctype和%x
代码:
#include <iostream>
#include 
<cstdio>
#include 
<cstring>
#include 
<string>
#include 
<cstdlib>
#include 
<cctype>
#include 
<map>
#include 
<set>
#include 
<bitset>
#include 
<vector>
#include 
<algorithm>
#include 
<cmath>
#define PB push_back
using namespace std;
const int inf = ~0u >> 1;
const double eps = 1e-8;
const double pi = acos(-1.0);
int sgn(double x)
{
    
return fabs(x) < eps ? 0:x < -eps?-1:1;
}
char str[5000];
int main()
{
    
while(cin.getline(str,5000))
    {
        
int l = strlen(str);
        
int i = 0;
        
char opt[20];
        
int cnt = 0;
        
while(1)
        {
            
char row[5];
            sprintf(row,
"%x",i);
            
for(int j = 0;j < 4 - strlen(row);j++)
                putchar(
'0');
            printf(
"%s: ",row);
            
bool mark = true;
            
for(int j = 0;j < 16;j++)
            {
                opt[j] 
= mark?str[i]:-1;
                i
++;
                
if(i == l)
                    mark 
= false;
            }
            
for(int j = 0;j < 16;j++)
            {
                
if(opt[j] != -1)
                    printf(
"%x",opt[j]);
                
else
                    printf(
"  ");
                
if(j%2)
                    printf(
" ");
            }
            
for(int j = 0;j < 16;j++)
            {
                
if(opt[j] == -1)
                    
break;
                
if(islower(opt[j]))
                    opt[j] 
= toupper(opt[j]);
                
else if(isupper(opt[j]))
                    opt[j] 
= tolower(opt[j]);
                printf(
"%c",opt[j]);
            }
            puts(
"");
            
if(!mark)
                
break;
        }
    }
}
E zoj 3543
N^2 dp,claire大神想了个神做法N^3,结果TLE了,哈哈~
F zoj 3544
200棵线段树,O(q * n * log(m)),ykwd大神去玩了,结果线段树部分没人敲了,不会啊。
shi哥说有O(n*m)的做法,不会啊。
shi哥的路径压缩的方法场上想到了,不会敲;到现在也不会敲。拿stl企图骗过去,果断TLE。好紧啊。
历时3天,终于AC了。链表路径压缩,orz。果断就是并查集的写法。
题解:
正着做就是裸体有lazy tag的线段树,竟然在zoj上可以过,太orz了。
刷板报什么的,有这样一个性质,后面的涂色不会被前面的覆盖,果断倒着做。
倒着做也可以某种线段树,不需要重复覆盖的,应该会比正着做要快。
(ps,既然正着做倒着做在zoj上都能过,为啥10.2的时候就只有那么点人过了F?不解)
说一下正解吧,太orz shi哥了。
我只想到了路径压缩,没有想到shi哥的并查集式路径压缩。(好像路径压缩就是在并查集里才常用的吧?我这个蒟蒻为毛没想到?!)

既然是不会重复覆盖,那么只要把已经覆盖过的删除了就好了,再覆盖的时候对删除的跳过去就行。这样最多删除O(m*n)次。
但是怎样快速查找呢?就是并查集的做法了,并查集路径压缩之后的复杂度在整数范围内最大为O(5)。
本题中的并查集:
删除[l,r]区间:
1.假如起始点未被删除过,那么就从这个点开始逐次删除,并统计删除的点数,返回删除的点数即可。
删除的过程中,记得将刚刚被删除的点的skip域指向本次删除区间的左端点。
2.假如起始点已经被删除过,那么就找这个点的skip域,直到找到一个可删除节点或者到本段的段尾为止(m)。
而接下来逐次删除的时候,删完的点的skip应该指向这个新的节点。
记得查找的时候,附带路径压缩,并查集的路径压缩各位大神肯定都会写吧?
删完了一个区间之后,把区间开始删除的点的skip域指向最后的点(不在本次删除范围内的可删除节点或者段末)。
牢记:路径压缩的时候是把所有儿子都指向父亲。
最后更新“最后节点“的时候,是将删除区间的起始点指向最后节点(根)。

以上说得很乱,画图解释就是:
这是naive的并查集,a exists in (l,r],a -> l,l -> (r+1)。
路径压缩的时候,l1 -> l2 -> l3 -> r => l1 -> r ,l2 -> r , l3 -> r。
关键代码在51~69行。(因为带了行号,所以复制不方便了哈。。)

数据结构神马的太神奇了。
代码如下:
  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <string>
  5 #include <cstdlib>
  6 #include <cctype>
  7 #include <map>
  8 #include <set>
  9 #include <bitset>
 10 #include <vector>
 11 #include <algorithm>
 12 #include <cmath>
 13 #define PB push_back
 14 #define sqr(x) ((x) * (x))
 15 using namespace std;
 16 const int inf = ~0u >> 1;
 17 const double eps = 1e-8;
 18 const double pi = acos(-1.0);
 19 int sgn(double x)
 20 {
 21     return fabs(x) < eps ? 0:x < -eps?-1:1;
 22 }
 23 #define maxn 205
 24 #define maxm 50005
 25 int n,m,q;
 26 inline int ab(int x)
 27 {
 28     return x >= 0?x:-x;
 29 }
 30 struct method
 31 {
 32     int type;
 33     int cnt;
 34     int in[7];
 35 }mth[maxm];
 36 int ans[10];
 37 struct skiplist
 38 {
 39     int skip[maxm];
 40     bool tr[maxm];
 41     void init(int m)
 42     {
 43         fill(tr,tr + m,1);
 44     }
 45     int jump(int pos)
 46     {
 47         if(pos >= m)
 48             return m;
 49         return tr[pos]?pos:skip[pos] = jump(skip[pos]);
 50     }
 51     int erase(int l,int r)
 52     {
 53         int now = jump(l),pos = now;//
 54         int num = 0;
 55         while(pos <= r)
 56         {
 57             if(tr[pos])
 58             {
 59                 tr[pos] = false;
 60                 skip[pos] = now;
 61                 pos++;
 62                 num++;
 63             }
 64             else
 65                 pos = jump(pos);
 66         }
 67         skip[now] = pos;
 68         return num;
 69     }
 70 }skip[maxn];
 71 void gao(int row,int le,int ri,int co)
 72 {
 73     ans[co] += skip[row].erase(le,ri);
 74 }
 75 int main()
 76 {
 77     while(scanf("%d %d %d",&n,&m,&q) == 3)
 78     {
 79         for(int i = 0;i < n;i++)
 80             skip[i].init(m);
 81         memset(ans,0,sizeof(ans));
 82         for(int i = 0;i < q;i++)
 83         {
 84             char opt[20];
 85             int a[10];
 86             scanf("%s",opt);
 87             switch(opt[0])
 88             {
 89                 case 'C':
 90                     mth[i].type = 1;
 91                     mth[i].cnt = 4;
 92                     break;
 93                 case 'D':
 94                     mth[i].type = 2;
 95                     mth[i].cnt = 4;
 96                     break;
 97                 case 'R':
 98                     mth[i].type = 3;
 99                     mth[i].cnt = 5;
100                     break;
101                 case 'T':
102                     mth[i].type = 4;
103                     mth[i].cnt = 4;
104                     break;
105             }
106             for(int j = 0;j < mth[i].cnt;j++)
107                 scanf("%d",&mth[i].in[j]);
108         }
109         for(int i = q - 1;i >= 0;i--)
110         {
111             int hi,lo,le,ri,c,cnt = mth[i].cnt,type = mth[i].type;
112             int in[10];
113             for(int j = 0;j < cnt;j++)
114                 in[j] = mth[i].in[j];
115             c = in[cnt-1];
116             if(mth[i].type == 1)
117             {
118                 hi = max(0,in[0- in[2]);
119                 lo = min(n - 1,in[0+ in[2]);
120                 for(int j = hi;j <= lo;j++)
121                 {
122                     int offset = floor(sqrt(sqr(in[2]) - sqr(j - in[0])));
123                     le = max(0,in[1- offset);
124                     ri = min(m - 1,in[1+ offset);
125                     gao(j,le,ri,c);
126                 }
127             }
128             else if(mth[i].type == 2)
129             {
130                 hi = max(0,in[0- in[2]);
131                 lo = min(n - 1,in[0+ in[2]);
132                 for(int j = hi;j <= lo;j++)
133                 {
134                     int offset = in[2- ab(j - in[0]);
135                     le = max(0,in[1- offset);
136                     ri = min(m - 1,in[1+ offset);
137                     gao(j,le,ri,c);
138                 }
139             }
140             else if(mth[i].type == 3)
141             {
142                 hi = in[0];
143                 lo = min(n - 1,in[0+ in[2- 1);
144                 for(int j = hi;j <= lo;j++)
145                 {
146                     le = in[1];
147                     ri = min(m - 1,in[1+ in[3- 1);
148                     gao(j,le,ri,c);
149                 }
150             }
151             else
152             {
153                 hi = in[0];
154                 lo = min(n - 1,in[0+ in[2/ 2);
155                 for(int j = hi;j <= lo;j++)
156                 {
157                     int offset = (in[2- (j - in[0]) * 2/ 2;
158                     le = max(0,in[1- offset);
159                     ri = min(m - 1,in[1+ offset);
160                     gao(j,le,ri,c);
161                 }
162             }
163         }
164         for(int i = 1;i <= 9;i++)
165             printf("%d%c",ans[i],i==9?'\n':' ');
166     }
167 }
168 

G zoj 3445
状态dp+ac自动机,orz ykwd大神。
H zoj 3546
因为有凹多边形的存在,我只能想到N!的做法。这,旋转路径规划?怎么想起了昨晚的rujia几何场的最后一题,谁更难真不好说。
I zoj 3547
四次方和公式+暴力容斥,orz claire_大神
J zoj 3548
推个式子再dp,式子推出来了,dp没人做,弱爆了。
推完式子剩下的就是二分图匹配。。。这场竟然有图论,我tmd竟然没看出来。弱爆了。

弱爆了弱爆了。

posted on 2011-10-02 17:27 BUPT-[aswmtjdsj] @ Penalty 阅读(1352) 评论(4)  编辑 收藏 引用 所属分类: ZOJ Solution Report

评论

# re: DLUT onsite【线段树+数学+dp专场有木有!!!】 2011-10-03 15:50 teoy

3544的线段树OJ上开的下么?
  回复  更多评论   

# re: DLUT onsite【线段树+数学+dp专场有木有!!!】 2011-10-03 23:12 BUPT-[aswmtjdsj] @ Penalty

@teoy
给了256M。。不过一般的线段树真心难搞。没看到5%的ac率么。。。还是果断线性做法吧。。  回复  更多评论   

# re: DLUT onsite【线段树+数学+dp专场有木有!!!】[改](D + F)(zju 3542 + zju 3544) 2011-10-04 22:40 ch

在zoj上空间够吗? 总是MLE啊,线段树和并查集刚好差了几倍的空间  回复  更多评论   

# re: DLUT onsite【线段树+数学+dp专场有木有!!!】[改](D + F)(zju 3542 + zju 3544) 2011-10-04 22:49 BUPT-[aswmtjdsj] @ Penalty

@ch
zoj给了256M。。。
并查集是200*50000*(4+1)+50000*10左右的字节,约50M的空间。
线段树是200*50000*4(一般4倍)*4*域的数量。4倍的话,可以开一个域,如果用short可以开俩域~
话说可以过这题的线段树不会写,不知道该开几个域的飘走~  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年10月>
2526272829301
2345678
9101112131415
16171819202122
23242526272829
303112345

导航

统计

常用链接

留言簿(1)

随笔分类(150)

随笔档案(71)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜