标签：二分

codeforces 123 D. String　（后缀数组+两次二分得到区间＋rmq）

题目链接

题意：定义一个函数F．．

For exampe: F(babbabbababbab, babb) = 6. The list of pairs is as follows:

(1, 4), (4, 7), (9, 12)

Its continuous sequences are:

  • (1, 4)

  • (4, 7)

  • (9, 12)

  • (1, 4), (4, 7)

  • (4, 7), (9, 12)

  • (1, 4), (4, 7), (9, 12)

    erfen

．
erfen
题目描述得很烂．．看例子把．．大概就是：如果字符串y在字符串x中出现n次，那么F(x,y)=n*(n+1)/2

现在给一个字符串，求所有的F(s,x)的和，x为字符串的所有不相同的子串．

 

思路：由于刚刚写了一个求一个字符串所有不同子串个数的题目．．．于是就想到了后缀数组．．．

写完之后观察height[i]．如果把height[i]看成底在x轴上的第i个矩形的高的话，n就是一段连续的矩形的长度．

 

然后．．．暴力会tle 48

题解说单调栈．．．但是单调栈之后还要线段树or并查集？　（by 羊神）

．．．不会啊orz

最后用了二分+rmp过掉的

大概就是两次二分得到一个矩形的区间，和whust2016 #1的那道题有点像．

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
 
 
 
/* ***********************************************
Author :111qqz
Created Time :2016年08月01日 星期一 04时57分01秒
File Name :code/cf/problem/123d.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <stack>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=1E5+7;
int n,sa[N],rk[N],t[N],t2[N],cnt[N];
int height[N];
char s[N];
int cmp( int *r , int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];}
void getSa( int n,int m)
{
    int *x = t;
    int *y = t2;
    ms(cnt,0);
    for ( int i = 0 ; i  < n ; i++) cnt[x[i]=s[i]]++;
    for ( int i = 1 ; i < m ; i++) cnt[i] +=cnt[i-1];
    for ( int i = n-1 ; i >= 0 ; i--) sa[--cnt[x[i]]] = i ;
    for ( int k = 1 ; k <= n ; k <<=1)
    {
        int p = 0 ;
        for ( int i = n-k ; i < n;  i++) y[p++] = i;
        for  ( int i = 0 ; i < n ; i++) if (sa[i]>=k) y[p++] = sa[i]-k;
        ms(cnt,0);
        for ( int i = 0 ; i <n ; i++) cnt[x[y[i]]]++;
        for ( int i = 0 ; i < m ; i++) cnt[i] +=cnt[i-1];
        for ( int i = n-1 ; i >= 0 ; i--) sa[--cnt[x[y[i]]]] = y[i];
        swap(x,y);
        p = 1;
        x[sa[0]] = 0 ;
        for ( int i = 1 ;i  <n ; i++)
            x[sa[i]] = cmp(y,sa[i-1],sa[i],k)?p-1:p++;
        if (p>=n) break;
        m = p;
    }
}
void getHeight( int n)
{
    int k = 0 ;
    for ( int i = 0 ; i < n ; i++) rk[sa[i]] = i ;
    height[0] =  0 ;
    for ( int  i = 0 ; i < n ; i++)
    {
        if (rk[i]==0) continue;
        if (k) k--;
        int j = sa[rk[i]-1];
        while (s[i+k]==s[j+k]) k++;
        height[rk[i]] = k;
    }
}
int getSuffix( char s[])
{
    int len =  strlen(s);
    int up = 0 ;
    for ( int i = 0 ; i < len ; i++)
    {
        int  val = s[i];
        up = max(up,val);
    }
    s[len++]='$';
    getSa(len,up+1);
    getHeight(len);
    return len;
}
LL cal( LL x)
{
    return x*(x+1)/2LL;
}
LL solve2(int n)
{
         for ( int i = 0 ; i < n ; i++) cout<<i<<" "<<height[i]<<endl;
    ms(cnt,0);
    int up = 0 ;
    for ( int i = 1 ; i < n;  i++) cnt[height[i]]++,up=max(up,height[i]);
    for ( int i = up-1 ; i >= 0 ; i--) cnt[i] = cnt[i]+cnt[i+1];
    LL res = 0LL ;
    for ( int i = 0 ; i <= up ; i++)
        res = res + cal(1LL*cnt[i]);
    return res;
}
/*
stack<int>stk;
int l[N],r[N];
bool visl[N],visr[N];
 
LL solve ( LL n)  //单调栈
{
    LL res = n*(n-1LL)/2LL;
    int up = 0 ;abaabaabaaba
    for ( int i = 1 ; i < n; i++) up = max(height[i],up);
//   for ( int i = 1 ; i <= n ; i++) cout<<"i:"<<i<<" height[i]:"<<height[i]<<endl;
    height[0] = -1;
    height[n+1] = -1 ; //单调队列的哨兵
    stk.push(0);
    int x;
    for ( int i = 1 ; i <= n; i++)
    {
        for (x=stk.top();height[x]>=height[i];x=stk.top()) stk.pop();
        l[i] = x+1;
        stk.push(i);
//        cout<<"i:"<<i<<endl;
    }
    while (!stk.empty()) stk.pop() ; stk.push(n+1);
    for ( int i  = n ; i >=1 ; i--)
    {
        for (x=stk.top() ; height[x]>=height[i] ; x = stk.top()) stk.pop();
        r[i] = x-1;
        stk.push(i);
    }
  //  for ( int i = 1 ; i <= n ; i++)
//        cout<<"i:"<<i<<" l[i]:"<<l[i]<<" r[i]:"<<r[i]<<" height[i]:"<<height[i]<<" "<<(r[i]-l[i]+1)*height[i]<<endl;
//    int mxh = 0 ;
    ms(visl,false);
    ms(visr,false);
    int mxh = 0 ;
    int more =1;
    for ( int i = 1 ;i  <= n ; i++)
    {
        if (height[i]==0)
        {
            mxh = 0 ;
            continue;
        }
        if (visr[r[i]]&&visl[l[i]])
        {
            mxh = 0 ;
            continue;
        }
            if (i>1&&height[i-1]<height[i]) more = height[i]-height[i-1];
            if (i<n&&height[i+1]<height[i]) more = min(more,height[i]-height[i+1]);
            res = res + cal((r[i]-l[i]+1))*(more);
            mxh = max(mxh,height[i]);
            visr[r[i]] = true;
            visl[l[i]] = true;
//            cout<<"i:"<<i<<" res:"<<res<<endl;
        
      }
        
    return res;
}  */
 
int dp[N][30]; // for rmq;
void rmq_init( int n)
{
    for ( int i = 1 ; i <= n ; i++) dp[i][0] = height[i];
 
    for ( int j = 1 ; (1<<j) <= n ; j++)
        for ( int i = 1 ; i + (1<<j) - 1 <= n ; i++)
            dp[i][j] = min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
int rmq( int l,int r)
{
    if (l>r) swap(l,r);
    int k = 0 ;
    while (1<<(k+1)<=r-l+1) k++;
    int res = min(dp[l][k],dp[r-(1<<k)+1][k]);
    return res;
 
}
 
LL solve( LL len)
{
    rmq_init(len);
    LL ans = len*(len+1)/2;
 
//   for ( int i = 1 ; i <= len ; i++) cout<<i<<" :"<<height[i]<<endl;
    for ( int i = 1 ; i <= len ; i++)
    {
        int l = 0 ,r = i ;
        while (r>l+1)
        {
            int mid = (l+r)/2;
            if (rmq(mid,i-1)>=height[i]) r = mid;
            else l = mid;
        }
        int L = i,R= len+1;
        while (R>L+1)
        {
            int mid = (L+R) / 2;
            if (rmq(i+1,mid)>height[i]) L = mid;
            else R = mid;
        }
//        cout<<"i:"<<height[i]<<"L:"<<L<<" r:"<<r<<" ans:"<<ans<<endl;
        ans +=1LL*height[i]*(L-i+1)*(i-r+1);
    }
    return ans;
}
int main()
{
        #ifndef  ONLINE_JUDGE
        freopen("code/in.txt","r",stdin);
  #endif
        scanf("%s",s);
        int len = getSuffix(s);
//        cout<<"len:"<<len-1<<endl;
        LL ans = solve(len-1);
        printf("%lld\n",ans);
  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}
 
 
 
 

bc #77 ||hdu 5652 India and China Origins (图的动态连通性问题，并查集or 二分+bfs验证连通性)

题目链接
题意：没图不好描述，有中文题面中文题面，直接看吧。
思路：据说这道题有三种做法。 当时比赛一种都不会。

先说一种：做法是把格子看成点，可以到达的相邻格子之间看成有边相连，然后倒过来用并查集判断无向图的连通性。具体做法是：先统计初始所有空的位置，然后把所有要增加的山都加上（先统计空的位置是因为山之后要去掉，而去掉以后要得到该点的标号），然后将把所有空的点以及china(设标号为n*m+1)点,和india(设标号为n*m+2) 点通过并查集来合并..可以从上往下从左往右，每次只需要判断上面的点和左边的点是否有空，如果有就用并查集合并。 china点和india点特殊搞就好。

然后判断india和china是否联通，如果是则输出-1.否则从最后添加的山开始移除，每次移除一座山，添加四个方向能添加的边（注意这里不要忘记如果改点在第0行或者第n-1行还要添加和china或者india的边）

然后移除后询问india和china是否联通 （root(china)==root(india)?）

如果时间i联通了，而i+1没有联通，说明时间i是两国最早的失去联系的时间。

 

第一次做这种题目，这种题目的一般做法都是倒过来做。貌似还有一个二分删除的山+bfs判断连通性的。。。？ 窝再搞搞看。
update :二分+bfs判断连通性。其实这个思路更常规。。做法就是字面意思。注意无解的判断即可。

 

并查集解法：

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
 
 
 
/* ***********************************************
Author :111qqz
Created Time :2016年03月27日 星期日 20时11分02秒
File Name :code/bc/#77/1003.cpp
************************************************ */
 
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
 
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=505;
char maze[N][N];
int f[N*N];
int n,m;
int q;
int p[N][N];
int china;
int india;
struct node
{
    int x,y;
    int id;
 
}shan[N*N],kong[N*N];
 
int root ( int x)
{
    if (x!=f[x]) f[x] = root (f[x]);
    return f[x];
}
 
void merge( int x,int y)
{
    int rx = root (x);
    int ry = root (y);
//    cout<<"rx::"<<rx<<"   ry::"<<ry<<endl;
    if (rx!=ry)
    {
        f[rx] = ry ;
//        f[ry] = rx;
    }
}
 
void addegg( int x,int y)
{
    if (x-1>=0&&maze[x-1][y]=='0') merge(p[x][y],p[x-1][y]);
    if (x+1<n&&maze[x+1][y]=='0') merge(p[x][y],p[x+1][y]);
    if (y-1>=0&&maze[x][y-1]=='0') merge(p[x][y],p[x][y-1]);
    if (y+1<m&&maze[x][y+1]=='0') merge(p[x][y],p[x][y+1]);
 
    if (x==0) merge(p[x][y],china);  //一开始忘记更新边缘的山被移除后，点和china以及india的边了。
    if (x==n-1) merge(p[x][y],india);
}
int main()
{
        #ifndef  ONLINE_JUDGE
        freopen("code/in.txt","r",stdin);
  #endif
 
        int T;
        cin>>T;
        while (T--)
        {
            scanf("%d %d",&n,&m);
            for ( int i = 0 ; i < n ; i++) scanf("%s",maze[i]);
 
            scanf("%d",&q);
            for ( int i = 1 ; i <= q ; i++)
            {
                int x,y;
                scanf("%d %d",&x,&y);
                shan[i].x = x;
                shan[i].y = y;
                shan[i].id = i;
//                maze[x][y] = '1';  //先统计空位。
            }
 
            int cnt = 0 ;
            ms(p,-1);
            for ( int i = 0 ; i  < n ; i++)
            {
                for ( int j = 0 ; j < m;  j++)
                {
                    if (maze[i][j]=='0')
                    {
                        cnt++;
                        kong[cnt].x = i ;
                        kong[cnt].y = j;
                        kong[cnt].id = i;
                        p[i][j] = cnt;
                    }
                }
            }
 
            for ( int i  = 1 ; i <= q ; i ++)
            {
                int x = shan[i].x;
                int y = shan[i].y;
                maze[x][y]='1';
            }
            //check kong...ok!
            //for ( int i = 1 ; i  <= cnt ; i++) cout<<"kong:"<<kong[i].x<<" "<<kong[i].y<<endl;
 
                china = n*m+1;
                india = n*m+2;
            for ( int i = 0 ; i <= n*m+2 ; i++) f[i] =  i;
        //    f[china] = china;
          //  f[india] = india;
         //   cout<<"china:"<<china<<endl;
           // cout<<"india:"<<india<<endl;
            for ( int j = 0 ; j  < m ; j++)
            {
                if (maze[0][j]=='0')
                {  
                    merge(china,p[0][j]);
                }
                if (maze[n-1][j]=='0')
                {
                    merge(india,p[n-1][j]);
                }
            }
 
            for ( int i = 0 ;i < n ; i++)
            {
                for ( int j = 0 ; j < m ; j ++)
                {
                    if (maze[i][j]=='1') continue;
                    if (maze[i-1][j]=='0') merge(p[i-1][j],p[i][j]);
                    if (maze[i][j-1]=='0') merge(p[i][j-1],p[i][j]);
                }
            }
 
            if (root(china)==root(india))
            {
                puts("-1");
                continue;
            }
 
            for ( int i = q ; i >= 1 ; i--)
            {
                int x = shan[i].x;
                int y = shan[i].y;
 
                maze[x][y] = '0';
                addegg(x,y);
                if (root(china)==root(india))
                {
                    printf("%d\n",i);
                    break;
                }
            }
        }
 
  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}
 
 
 
 

二分+bfs判断连通性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
 
 
 
/* ***********************************************
Author :111qqz
Created Time :2016年03月28日 星期一 21时12分05秒
File Name :code/hdu/5652.cpp
************************************************ */
 
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
 
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=501;
char maze[N][N];
int n,m;
int q;
bool vis[N][N];
 
struct node
{
    int x,y;
 
    bool ok ()
    {
        if (x>=0&&x<n&&y>=0&&y<m&&!vis[x][y]) return true;
        return false;
    }
}shan[250005];
 
 
int check( int id)
{
    
    for ( int i = 0 ; i < n ; i++)
    {
        for ( int j = 0 ; j < m ; j ++)
        {
            if (maze[i][j]=='1') vis[i][j] = true;
                else vis[i][j] = false;
        }
    }
 
    for ( int i = 1 ; i <= id ; i++)
    {
        int x = shan[i].x;
        int y = shan[i].y;
        vis[x][y] = true;
    }
 
    queue<node>q;
    for ( int j = 0 ; j  < m ; j++)
    {
        
        if (!vis[0][j])
        {
            node tmp;
            tmp.x = 0;
            tmp.y = j;
            q.push(tmp);
        }
    }
 
    while (!q.empty())
    {
        node pre = q.front();q.pop();
        if (pre.x==n-1) return 1;
        for ( int i = 0 ; i < 4 ; i++)
        {
            node nxt;
            nxt.x = pre.x + dx4[i];
            nxt.y = pre.y + dy4[i];
            if (nxt.ok())
            {
                vis[nxt.x][nxt.y] = true;
                q.push(nxt);
                
            }
        }
    }
    return 0;
}
 
int bin()
{
    int l = 1 ;
    int r = q ;
    int mid;
    while (l<=r)
    {
        mid = (l+r)/2;
        if (check(mid))
            l = mid + 1;
        else r = mid -1;
    }
    if (l>q) return -1;
    return l;
}
int main()
{
        #ifndef  ONLINE_JUDGE
        freopen("code/in.txt","r",stdin);
  #endif
 
        int T;
        cin>>T;
        while (T--)
        {
            scanf("%d%d",&n,&m);
            for ( int i = 0 ; i  < n;  i++) scanf("%s",maze[i]);
            scanf("%d",&q);
            for ( int i = 1 ; i <= q ; i ++) scanf("%d %d",&shan[i].x,&shan[i].y);
            int ans = bin();
            printf("%d\n",ans);
        }
 
  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}