August 2015 – Page 2

POJ 3090 Visible Lattice Points

August 22, 20152015-08-22hahaschoolLeave a comment

题意

给出了一个1001×1001的点阵，和查询q，你要求出从(0,0)点到(q,q)点有多少种不同的点到原点的斜率（也就是题目中所说的“可见”），原点到原点不算。

思路

很直接的就可以想到算出所有的点到原点的斜率，预处理出答案，我们的做法是：从原点开始，一圈一圈地向外扩张，对于每个点都计算一边斜率，然后确认该斜率是否出现过，没出现过的话，当前圈上的点到原点的不同的斜率个数+1，这样求出每一圈的数目，最后我们再求一个前缀和就好了。

时间很理想，是O(n^2*log(n))的，然而POJ上超时了。我拿到ideone上测速，是700ms，可以过的，可能是评测机不在状态吧ˊ_>ˋ。补救的方法就是打了个表，反正数据也很少。

然而这个题的精髓并不是这么水过去的，这个题其实是一个包装过了的法雷级数(Wikipedia::法里数列可能需要科学上网)，如果试着一圈圈地写一下斜率，就会发现每一圈正好满足分子和分母互质的特性，每一圈的个数其实是欧拉函数值，整个答案是欧拉函数前缀和。所以我们就有了O(n)，的处理方法，详细的可以看这个题POJ 2478 Farey Sequence。

明明是刚做过的题居然都没有反应过来看来我真的是太迟钝了呢。

代码(暴力解法)

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>

using namespace std;

struct Fac{
    int up;
    int down;
    int gcd(int a,int b){
        if (b == 0) {
            return a;
        }
        return gcd(b, a%b);
    }
    void reduce(){
        int _gcd = gcd(up, down);
        up /= _gcd;
        down /= _gcd;
    }
    friend bool operator < (Fac a,Fac b){
        if(a.up == b.up){
            return a.down < b.down;
        }else
            return a.up < b.up;
    }
};

Fac tg(int x,int y){
    Fac ret;
    ret.up = y;
    ret.down = x;
    ret.reduce();
    return ret;
}

set<Fac> vis;
int ans[1001];

void get_ans(){
    for (int i = 1; i <= 1000; i++) {
        int x = 0, y = i;
        for (x = 0; x <= i; x++) {
            Fac _tg = tg(x, y);
            if (!vis.count(_tg)) {
                vis.insert(_tg);
                ans[i]++;
            }
        }
        x = i;
        for (y = i-1; y >= 0; y--) {
            Fac _tg = tg(x, y);
            if (!vis.count(_tg)) {
                vis.insert(_tg);
                ans[i]++;
            }
        }
        ans[i] += ans[i-1];
    }
}

int main(){
    get_ans();
    int caseCnt;
    scanf(" %d",&caseCnt);
    for (int d = 1; d <= caseCnt; d++) {
        int q;
        scanf(" %d",&q);
        printf("%d %d %d\n",d,q,ans[q]);
    }
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

using namespace std;

struct Fac{

int up;

int down;

int gcd(int a,int b){

if (b == 0) {

return a;

}

return gcd(b, a%b);

}

void reduce(){

int _gcd = gcd(up, down);

up /= _gcd;

down /= _gcd;

}

friend bool operator < (Fac a,Fac b){

if(a.up == b.up){

return a.down < b.down;

}else

return a.up < b.up;

}

};

Fac tg(int x,int y){

Fac ret;

ret.up = y;

ret.down = x;

ret.reduce();

return ret;

}

set<Fac> vis;

int ans[1001];

void get_ans(){

for (int i = 1; i <= 1000; i++) {

int x = 0, y = i;

for (x = 0; x <= i; x++) {

Fac _tg = tg(x, y);

if (!vis.count(_tg)) {

vis.insert(_tg);

ans[i]++;

}

x = i;

for (y = i-1; y >= 0; y--) {

Fac _tg = tg(x, y);

if (!vis.count(_tg)) {

vis.insert(_tg);

ans[i]++;

}

ans[i] += ans[i-1];

}

int main(){

get_ans();

int caseCnt;

scanf(" %d",&caseCnt);

for (int d = 1; d <= caseCnt; d++) {

int q;

scanf(" %d",&q);

printf("%d %d %d\n",d,q,ans[q]);

}

POJ 2478 Farey Sequence

August 21, 20152015-08-21hahaschoolOne Comment

题意

介绍性的问题，法雷级数(Wikipedia::法里數列可能需要科学上网)。

简单暴力，给出一个n，求出对于1～n中每一个数，有多少个小于等于他的数与他互质，把这些数量加在一起是多少，其实就是求欧拉函数的前缀和。

思路

欧拉函数有两种得到的方法，一是使用分解因子的方法，得到单个数的欧拉函数值，时间复杂度O(sqrt(n) * log(n))。如下：

//only for single number circumstances
long long s_phi(long long n)
{
    long long m=(long long)sqrt(n+0.5),ans=n;
    for(long long i=2;i<=m;i++)
    {
        if(n%i==0)
        {
            ans=ans/i*(i-1);
            while(n%i==0)n/=i;
        }
    }
    if(n>1)ans=ans/n*(n-1);
    return ans;
}

//only for single number circumstances

long long s_phi(long long n)

{

long long m=(long long)sqrt(n+0.5),ans=n;

for(long long i=2;i<=m;i++)

{

if(n%i==0)

{

ans=ans/i*(i-1);

while(n%i==0)n/=i;

}

if(n>1)ans=ans/n*(n-1);

return ans;

}

可以发现这样算的话如果只求一个数的欧拉函数还是不亏的，但是如果要求非常非常多的欧拉函数，时间就会爆炸，所以我们不可以在这个题用这种方法。

第二种方法是利用欧拉函数的若干性质：欧拉函数线性筛法详解(Lytning)，然后把素数的线性筛法和求欧拉函数结合到一起，如果要求非常多的欧拉函数，使用这种方法预处理是非常快的，而且还顺便求了素数，一石二鸟。

const int N = 1000000;
int n;
int phi[N+10],prime[N+10],tot,ans;//phi储存的是欧拉函数 prime按次序保存了全部的素数 mark是素数标记，false意味素，true意味合
bool mark[N+10];
void getphi()
{
    int i,j;
    phi[1]=1;
    for(i=2;i<=N;i++)//相当于分解质因式的逆过程
    {
        if(!mark[i])
        {
            prime[++tot]=i;//筛素数的时候首先会判断i是否是素数。
            phi[i]=i-1;//当 i 是素数时 phi[i]=i-1
        }
        for(j=1;j<=tot;j++)
        {
            if(i*prime[j]>N)  break;
            mark[i*prime[j]]=1;//确定i*prime[j]不是素数
            if(i%prime[j]==0)//接着我们会看prime[j]是否是i的约数
            {
                phi[i*prime[j]]=phi[i]*prime[j];break;
            }
            else  phi[i*prime[j]]=phi[i]*(prime[j]-1);//其实这里prime[j]-1就是phi[prime[j]]，利用了欧拉函数的积性
        }
    }
}

const int N = 1000000;

int n;

int phi[N+10],prime[N+10],tot,ans;//phi储存的是欧拉函数 prime按次序保存了全部的素数 mark是素数标记，false意味素，true意味合

bool mark[N+10];

void getphi()

{

int i,j;

phi[1]=1;

for(i=2;i<=N;i++)//相当于分解质因式的逆过程

{

if(!mark[i])

{

prime[++tot]=i;//筛素数的时候首先会判断i是否是素数。

phi[i]=i-1;//当 i 是素数时 phi[i]=i-1

}

for(j=1;j<=tot;j++)

{

if(i*prime[j]>N) break;

mark[i*prime[j]]=1;//确定i*prime[j]不是素数

if(i%prime[j]==0)//接着我们会看prime[j]是否是i的约数

{

phi[i*prime[j]]=phi[i]*prime[j];break;

}

else phi[i*prime[j]]=phi[i]*(prime[j]-1);//其实这里prime[j]-1就是phi[prime[j]]，利用了欧拉函数的积性

}

快速地得到欧拉函数值之后，前缀和什么的就是很简单的事情了。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>

using namespace std;

const int N = 1000000;
int n;
int phi[N+10],prime[N+10],tot,ans;//phi储存的是欧拉函数 prime按次序保存了全部的素数 mark是素数标记，false意味素，true意味合
bool mark[N+10];
void getphi()
{
    int i,j;
    phi[1]=1;
    for(i=2;i<=N;i++)//相当于分解质因式的逆过程
    {
        if(!mark[i])
        {
            prime[++tot]=i;//筛素数的时候首先会判断i是否是素数。
            phi[i]=i-1;//当 i 是素数时 phi[i]=i-1
        }
        for(j=1;j<=tot;j++)
        {
            if(i*prime[j]>N)  break;
            mark[i*prime[j]]=1;//确定i*prime[j]不是素数
            if(i%prime[j]==0)//接着我们会看prime[j]是否是i的约数
            {
                phi[i*prime[j]]=phi[i]*prime[j];break;
            }
            else  phi[i*prime[j]]=phi[i]*(prime[j]-1);//其实这里prime[j]-1就是phi[prime[j]]，利用了欧拉函数的积性
        }
    }
}

long long phisum[1000006];

int main(){
    getphi();
    for (int i = 2; i <= 1000000; i++) {
        phisum[i] = phi[i] + phisum[i-1];
    }
    int q;
    while (cin >> q && q) {
        cout << phisum[q] << endl;
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

using namespace std;

const int N = 1000000;

int n;

int phi[N+10],prime[N+10],tot,ans;//phi储存的是欧拉函数 prime按次序保存了全部的素数 mark是素数标记，false意味素，true意味合

bool mark[N+10];

void getphi()

{

int i,j;

phi[1]=1;

for(i=2;i<=N;i++)//相当于分解质因式的逆过程

{

if(!mark[i])

{

prime[++tot]=i;//筛素数的时候首先会判断i是否是素数。

phi[i]=i-1;//当 i 是素数时 phi[i]=i-1

}

for(j=1;j<=tot;j++)

{

if(i*prime[j]>N) break;

mark[i*prime[j]]=1;//确定i*prime[j]不是素数

if(i%prime[j]==0)//接着我们会看prime[j]是否是i的约数

{

phi[i*prime[j]]=phi[i]*prime[j];break;

}

else phi[i*prime[j]]=phi[i]*(prime[j]-1);//其实这里prime[j]-1就是phi[prime[j]]，利用了欧拉函数的积性

}

long long phisum[1000006];

int main(){

getphi();

for (int i = 2; i <= 1000000; i++) {

phisum[i] = phi[i] + phisum[i-1];

}

int q;

while (cin >> q && q) {

cout << phisum[q] << endl;

}

return 0;

}

SPOJ SUBLEX Lexicographical Substring Search

August 20, 20152015-08-20hahaschoolLeave a comment

题意

把一个字符串所有的不同的字串全拿出来，按字典序排序，第k小的字符串是什么样子的呢？

思路

字串问题当然是后缀自动机了。对于给出的字符串，建立一个后缀自动机，然后对后缀自动机对应的状态图进行一次拓扑排序，每个节点的深度就是节点上携带的mxn(当前状态对应的字串最长为多少位)。接下来我们从深度最大的节点开始往根部处理每一个节点，我们要求出的就是对于每个能走的边，所有接下来的以这条边对应的字母开头的字串数目，而节点上面存的是节点出边的边权之和。这样我们就得到了一个处理好的图，我们只要在这个图上面搜索，逼近k值就可以了。

因为SPOJ卡常数特别严重，所以拓扑排序要使用计数排序的方法，而且要开额外的数组纪录每一个节点所有的孩子来加快之后的搜索速度。

代码

//
//  SPOJ SUBLEX.cpp
//  playground
//
//  Created by Adam Chang on 2015/08/10.
//  Copyright © 2015年 Adam Chang. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>

using namespace std;

#define MAXN 90005

struct SAM_State{
    int mxn;
    int cnt;
    int id;
    SAM_State *to[26];
    SAM_State *parent;
    void init(int _mxn){
        mxn = _mxn;
        memset(to, NULL, sizeof(to));
        parent = NULL;
        cnt = 0;
        id = 0;
    }
} idx[2*MAXN];

int totalNode = 0;
int len = 0;
SAM_State *idx_sorted[2*MAXN];

SAM_State* SAM_Append(SAM_State *last,SAM_State *root,int ch){
    SAM_State *p = last;
    SAM_State *np = &idx[++totalNode];
    np -> mxn = p -> mxn + 1;
    while (p && p -> to[ch] == NULL) {
        p -> to[ch] = np;
        p = p -> parent;
    }
    if (p != NULL) {
        SAM_State *q = p -> to[ch];
        if (q -> mxn == p -> mxn + 1) {
            np -> parent = q;
        }else{
            SAM_State *nq = &idx[++totalNode];
            *nq = *q;
            nq -> mxn = p -> mxn + 1;
            q -> parent = nq;
            np -> parent = nq;
            while (p && p -> to[ch] == q) {
                p -> to[ch] = nq;
                p = p -> parent;
            }
        }
    }else{
        np -> parent = root;
    }
    last = np;
    return last;
}

void SAM_Init(int n){
    for (int i = 0; i <= n ; i++) {
        idx[i].init(0);
    }
    totalNode = 0;
}

SAM_State* SAM_Build(char* str){
    len = (int)strlen(str);
    SAM_Init(2*len);
    SAM_State *root = &idx[0];
    SAM_State *last = root;
    for (int i = 0; i < len; i++) {
        last = SAM_Append(last, root, str[i] - 'a');
    }
    return root;
}

int cnt[MAXN*2];
void SAM_Toposort(){
    for (int i = 0; i <= totalNode; i++) {
        idx[i].id = i;
        cnt[idx[i].mxn]++;
    }
    for (int i = 1; i <= len; i++) {
        cnt[i] += cnt[i-1];
    }
    for (int i = 0; i <= totalNode; i++) {
        idx_sorted[--cnt[idx[i].mxn]] = &idx[i];
    }
}

int childID[MAXN*2][26];
int childVal[MAXN*2][26];
char childCh[MAXN*2][26];
int childCnt[MAXN*2];
void SAM_Buildgraph(){
    for (int i = totalNode; i >= 0; i--) {
        SAM_State *cur = idx_sorted[i];
        int curid = cur -> id;
        for (int j = 0; j < 26; j++) {
            if (cur -> to[j] != NULL) {
                SAM_State *nxt = cur -> to[j];
                int nxtid = nxt -> id;
                childID[curid][childCnt[curid]] = nxtid;
                childVal[curid][childCnt[curid]] = nxt -> cnt + 1;
                childCh[curid][childCnt[curid]] = j + 'a';
                cur -> cnt += nxt -> cnt + 1;
                childCnt[curid]++;
            }
        }
    }
}

char ans[MAXN];
void get_ans(int k){
    int pos = 0;
    SAM_State *cur = &idx[0];
    while (k) {
        for (int i = 0; i < childCnt[cur -> id]; i++) {
            if (childVal[cur -> id][i] < k) {
                k -= childVal[cur -> id][i];
            }else {
                k--;
                ans[pos] = childCh[cur -> id][i];
                cur = &idx[childID[cur -> id][i]];
                pos++;
                break;
            }
        }
    }
    ans[pos] = '\0';
    puts(ans);
}

char a[MAXN];
int main(){
    scanf(" %s",a);
    SAM_Build(a);
    SAM_Toposort();
    SAM_Buildgraph();
    int q = 0;
    scanf(" %d",&q);
    for (int i = 1; i <= q; i++) {
        int k = 0;
        scanf(" %d",&k);
        get_ans(k);
    }
    return 0;
}

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

// SPOJ SUBLEX.cpp

// playground

// Created by Adam Chang on 2015/08/10.

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

using namespace std;

#define MAXN 90005

struct SAM_State{

int mxn;

int cnt;

int id;

SAM_State *to[26];

SAM_State *parent;

void init(int _mxn){

mxn = _mxn;

memset(to, NULL, sizeof(to));

parent = NULL;

cnt = 0;

id = 0;

}

} idx[2*MAXN];

int totalNode = 0;

int len = 0;

SAM_State *idx_sorted[2*MAXN];

SAM_State* SAM_Append(SAM_State *last,SAM_State *root,int ch){

SAM_State *p = last;

SAM_State *np = &idx[++totalNode];

np -> mxn = p -> mxn + 1;

while (p && p -> to[ch] == NULL) {

p -> to[ch] = np;

p = p -> parent;

}

if (p != NULL) {

SAM_State *q = p -> to[ch];

if (q -> mxn == p -> mxn + 1) {

np -> parent = q;

}else{

SAM_State *nq = &idx[++totalNode];

*nq = *q;

nq -> mxn = p -> mxn + 1;

q -> parent = nq;

np -> parent = nq;

while (p && p -> to[ch] == q) {

p -> to[ch] = nq;

p = p -> parent;

}

}else{

np -> parent = root;

}

last = np;

return last;

}

void SAM_Init(int n){

for (int i = 0; i <= n ; i++) {

idx[i].init(0);

}

totalNode = 0;

}

SAM_State* SAM_Build(char* str){

len = (int)strlen(str);

SAM_Init(2*len);

SAM_State *root = &idx[0];

SAM_State *last = root;

for (int i = 0; i < len; i++) {

last = SAM_Append(last, root, str[i] - 'a');

}

return root;

}

int cnt[MAXN*2];

void SAM_Toposort(){

for (int i = 0; i <= totalNode; i++) {

idx[i].id = i;

cnt[idx[i].mxn]++;

}

for (int i = 1; i <= len; i++) {

cnt[i] += cnt[i-1];

}

for (int i = 0; i <= totalNode; i++) {

idx_sorted[--cnt[idx[i].mxn]] = &idx[i];

}

int childID[MAXN*2][26];

int childVal[MAXN*2][26];

char childCh[MAXN*2][26];

int childCnt[MAXN*2];

void SAM_Buildgraph(){

for (int i = totalNode; i >= 0; i--) {

SAM_State *cur = idx_sorted[i];

int curid = cur -> id;

for (int j = 0; j < 26; j++) {

if (cur -> to[j] != NULL) {

SAM_State *nxt = cur -> to[j];

int nxtid = nxt -> id;

childID[curid][childCnt[curid]] = nxtid;

childVal[curid][childCnt[curid]] = nxt -> cnt + 1;

childCh[curid][childCnt[curid]] = j + 'a';

cur -> cnt += nxt -> cnt + 1;

childCnt[curid]++;

}

char ans[MAXN];

void get_ans(int k){

int pos = 0;

SAM_State *cur = &idx[0];

while (k) {

for (int i = 0; i < childCnt[cur -> id]; i++) {

if (childVal[cur -> id][i] < k) {

k -= childVal[cur -> id][i];

}else {

k--;

ans[pos] = childCh[cur -> id][i];

cur = &idx[childID[cur -> id][i]];

pos++;

break;

}

ans[pos] = '\0';

puts(ans);

}

char a[MAXN];

int main(){

scanf(" %s",a);

SAM_Build(a);

SAM_Toposort();

SAM_Buildgraph();

int q = 0;

scanf(" %d",&q);

for (int i = 1; i <= q; i++) {

int k = 0;

scanf(" %d",&k);

get_ans(k);

}

return 0;

}

POJ3352 Road Construction / POJ3177 Redundant Paths

August 20, 20152015-08-20hahaschoolLeave a comment

题意

给你一个联通图，问你最少要添加多少条边才能把这个图变成一个双联通图。

思路

非常经典的边双联通分量缩点问题。找出图中所有的边双联通分量，把这些分量各自收缩为一个点，节点之间若有边，一定是割边，这样就得到了一棵由边联通分量缩成的点和割边组成的树，把一个树变成双联通图要添加的最少边数是(r+1)/2其中r是这棵树的节点数量，这是一个蛮重要的结论。

找边联通分量的方法有好多，可以找到所有割边之后，对于每个点启动一次dfs，搜索中屏蔽掉所有割边，这样就可以收割所有的边双联通分量，也可以对于每个点直接启动一次tarjan算法，在函数返回的过程中，收割掉所有low值一样的节点就可以得到边双联通分量。这份代码使用的是后一种方案。

代码

两个题一个数据中有重边，一个没有，这份代码考虑了这个问题，所以连边都能顺利过，双倍经验。

//
//  POJ3552.cpp
//  playground
//
//  Copyright © 2015 Adam Chang. All rights reserved.
//

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <cmath>

using namespace std;

const int MAXN = 1005;

int n = 0, m = 0;
vector<int> to[MAXN];
vector<int> to2[MAXN];

void add_edge(int a, int b){
    to[a].push_back(b);
    to[b].push_back(a);
}

void add_edge2(int a, int b){
    to2[a].push_back(b);
    to2[b].push_back(a);
}


void remove_duplicate(vector<int> *to){
    for (int i = 1; i <= n; i++) {
        sort(to[i].begin(), to[i].end());
        to[i].erase(unique(to[i].begin(), to[i].end()), to[i].end());
    }
}

int sdcc_belong[MAXN];
stack<int> sdcc_stk;
int sdcc_dfn[MAXN];
int sdcc_low[MAXN];
vector<vector<int> > sdcc;
int sdcc_cnt = 0;

void sdcc_tarjan(int cur, int par){
    sdcc_dfn[cur] = sdcc_low[cur] = sdcc_cnt++;
    sdcc_stk.push(cur);
    for (int i = 0; i < to[cur].size(); i++) {
        int nxt = to[cur][i];
        if (nxt == par) {
            continue;
        }
        if (!sdcc_dfn[nxt]) {
            //如果对面点还没有进入过，那就进去
            sdcc_tarjan(nxt, cur);
            sdcc_low[cur] = min(sdcc_low[cur], sdcc_low[nxt]);
        }else {
            //如果对面点进去过，那么考虑是不是回边，如果是的话要更新当前节点low值
            sdcc_low[cur] = min(sdcc_low[cur], sdcc_dfn[nxt]);
        }
    }
    //我们这样处理问题不会受重边影响，因为我们考虑的中心是边联通分量内部的点而非外部的割点，这样我们只需要关心当前这个点及其联通部分是不是有指向之前的点的回边就可以，只要没有回边，就说明边双联通分量已经走完了，可以收割
    if (sdcc_low[cur] == sdcc_dfn[cur]) {
        //当前节点及其联通部分没有任何指向父亲部分的回边了，可以收割和当前节点连着的所有节点为一个双联通分量了
        //generate sdcc
        int last;
        sdcc.push_back(vector<int>());
        int sdccid = (int)sdcc.size();
        do{
            last = sdcc_stk.top();
            sdcc_stk.pop();
            sdcc[sdccid-1].push_back(last);
            sdcc_belong[last] = sdccid;
        }while (cur != last);
    }
}

void get_sdcc(){
    memset(sdcc_belong, 0, sizeof(sdcc_belong));
    while (!sdcc_stk.empty()) {
        sdcc_stk.pop();
    }
    memset(sdcc_dfn, 0, sizeof(sdcc_dfn));
    memset(sdcc_low, 0, sizeof(sdcc_low));
    sdcc.clear();
    sdcc_cnt = 0;

    for (int i = 1; i <= n; i++) {
        if (!sdcc_dfn[i]) {
            sdcc_tarjan(i,0);
        }
    }
}

int main(){
    scanf(" %d %d",&n, &m);
    for (int i = 1; i <= n; i++) {
        to[i].clear();
    }
    for (int i = 1; i <= m; i++) {
        int a = 0, b = 0;
        scanf(" %d %d",&a, &b);
        add_edge(a, b);
    }
    get_sdcc();
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < to[i].size(); j++) {
            if (sdcc_belong[to[i][j]] != sdcc_belong[i]) {
                add_edge2(sdcc_belong[to[i][j]], sdcc_belong[i]);
            }
        }
    }
    remove_duplicate(to2);
    int res = 0;
    for (int i = 1; i <= n; i++) {
        if (to2[i].size() == 1) {
            res++;
        }
    }
    cout << (res+1)/2 << endl;
    return 0;
}

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

// POJ3552.cpp

// playground

#include <iostream>

#include <iomanip>

#include <algorithm>

#include <queue>

#include <vector>

#include <set>

#include <stack>

#include <map>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <cmath>

using namespace std;

const int MAXN = 1005;

int n = 0, m = 0;

vector<int> to[MAXN];

vector<int> to2[MAXN];

void add_edge(int a, int b){

to[a].push_back(b);

to[b].push_back(a);

}

void add_edge2(int a, int b){

to2[a].push_back(b);

to2[b].push_back(a);

}

void remove_duplicate(vector<int> *to){

for (int i = 1; i <= n; i++) {

sort(to[i].begin(), to[i].end());

to[i].erase(unique(to[i].begin(), to[i].end()), to[i].end());

}

int sdcc_belong[MAXN];

stack<int> sdcc_stk;

int sdcc_dfn[MAXN];

int sdcc_low[MAXN];

vector<vector<int> > sdcc;

int sdcc_cnt = 0;

void sdcc_tarjan(int cur, int par){

sdcc_dfn[cur] = sdcc_low[cur] = sdcc_cnt++;

sdcc_stk.push(cur);

for (int i = 0; i < to[cur].size(); i++) {

int nxt = to[cur][i];

if (nxt == par) {

continue;

}

if (!sdcc_dfn[nxt]) {

//如果对面点还没有进入过，那就进去

sdcc_tarjan(nxt, cur);

sdcc_low[cur] = min(sdcc_low[cur], sdcc_low[nxt]);

}else {

//如果对面点进去过，那么考虑是不是回边，如果是的话要更新当前节点low值

sdcc_low[cur] = min(sdcc_low[cur], sdcc_dfn[nxt]);

}

//我们这样处理问题不会受重边影响，因为我们考虑的中心是边联通分量内部的点而非外部的割点，这样我们只需要关心当前这个点及其联通部分是不是有指向之前的点的回边就可以，只要没有回边，就说明边双联通分量已经走完了，可以收割

if (sdcc_low[cur] == sdcc_dfn[cur]) {

//当前节点及其联通部分没有任何指向父亲部分的回边了，可以收割和当前节点连着的所有节点为一个双联通分量了

//generate sdcc

int last;

sdcc.push_back(vector<int>());

int sdccid = (int)sdcc.size();

do{

last = sdcc_stk.top();

sdcc_stk.pop();

sdcc[sdccid-1].push_back(last);

sdcc_belong[last] = sdccid;

}while (cur != last);

}

void get_sdcc(){

memset(sdcc_belong, 0, sizeof(sdcc_belong));

while (!sdcc_stk.empty()) {

sdcc_stk.pop();

}

memset(sdcc_dfn, 0, sizeof(sdcc_dfn));

memset(sdcc_low, 0, sizeof(sdcc_low));

sdcc.clear();

sdcc_cnt = 0;

for (int i = 1; i <= n; i++) {

if (!sdcc_dfn[i]) {

sdcc_tarjan(i,0);

}

int main(){

scanf(" %d %d",&n, &m);

for (int i = 1; i <= n; i++) {

to[i].clear();

}

for (int i = 1; i <= m; i++) {

int a = 0, b = 0;

scanf(" %d %d",&a, &b);

add_edge(a, b);

}

get_sdcc();

for (int i = 1; i <= n; i++) {

for (int j = 0; j < to[i].size(); j++) {

if (sdcc_belong[to[i][j]] != sdcc_belong[i]) {

add_edge2(sdcc_belong[to[i][j]], sdcc_belong[i]);

}

remove_duplicate(to2);

int res = 0;

for (int i = 1; i <= n; i++) {

if (to2[i].size() == 1) {

res++;

}

cout << (res+1)/2 << endl;

return 0;

}

HDU4738 Caocao's Bridges

August 20, 20152015-08-20hahaschoolLeave a comment

题意

给出一个图，和一堆边，不保证没有重边，每一个边上携带者一个权值，现在问你能不能删去一条边，使图不再联通。可以的话删去权值最小的那条边，并且输出这个权值。

注意(坑点)

因为题意的特殊性，如果图本来就不联通，输出0.如果可以满足条件但最小的权值恰好是0，要输出1。

思路

删一个边把图裂开这种要求很明显就是找图的割边了。寻找割边是很典型的问题，应该使用tarjan算法，但是一定要注意重边对于找割边的影响(因为割边删掉后，图应该会裂开，但是如果有重边，删掉一条，还有一条，图显然不会裂开)，因此我们要对原来的方法稍作修改，首先是存图的方式，我们不能漏掉任意一条边，因此一个理想的方式就是链式前向星。链式前向星有一个很好用的特性，我们在创建无向边的时候实际上是创建了两条有向边，而这两条有向边在链式前向星的容器中的编号是相邻的，也就是说对于编号i的边i^1就是这条边对应的反向边，这样我们就可以非常方便地标记这条边是不是已经走过(vis_e[i] = vis_e[i^1] = true)。tarjan部分附带了注释。

代码

//
//  HDU4738.cpp
//  playground
//
//  Copyright (c) 2015 Adam Chang. All rights reserved.
//

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <cmath>

using namespace std;

#define MAXN 1005
#define MAXE 2000005

struct EDGE
{
    int u, v, w;
    int next;
};

int first[MAXN], rear;
EDGE edge[MAXE];

void init(int n)
{
    memset(first, -1, sizeof(first[0])*(n+1));
    rear = 0;
}

void insert(int tu, int tv, int tw)
{
    edge[rear].u = tu;
    edge[rear].v = tv;
    edge[rear].w = tw;
    edge[rear].next = first[tu];
    first[tu] = rear++;
    edge[rear].u = tv;
    edge[rear].v = tu;
    edge[rear].w = tw;
    edge[rear].next = first[tv];
    first[tv] = rear++;
}


int pre[MAXN], low[MAXN];
bool vis_e[MAXE];      //是否访问了边
bool is_bridge[MAXE];  //是否是桥
int dfs_clock;
int res = 909303;
void dfs(int cur)
{
    pre[cur] = low[cur] = ++dfs_clock;
    for(int i = first[cur]; ~i; i = edge[i].next)
    {
        //便利以当前点出发的所有边
        int tv = edge[i].v;
        if(!pre[tv])
        {
            //如果这条边连接着的节点还没有访问过，那就进到这个节点里面
            vis_e[i] = vis_e[i^1] = true;
            dfs(tv);
            low[cur] = min(low[cur], low[tv]);
            if(pre[cur] < low[tv]){
                //当前边连着的这个节点处理完毕了，如果发现这个节点的low值还是比当前节点大，说明这个节点及其联通部分没有指向已访问任何节点的回边，也就是说割开当前这条边，这个节点以及其联通的部分就和当前节点裂开了，这条边也就理所当然的是割边
                is_bridge[i] = is_bridge[i^1] = true;
                res = min(res,edge[i].w);//更新答案用的
            }
        }
        else
            if(pre[tv] < pre[cur] && !vis_e[i])
            {
                //这里是如果当前这条边是一条回边，那么就要更新当前节点的low值了
                vis_e[i] = vis_e[i^1] = true;
                low[cur] = min(low[cur], pre[tv]);
            }
    }
}

void find_bridge(int n)
{
    res = 909303;
    dfs_clock = 0;
    memset(pre, 0, sizeof(pre[0])*(n+1));
    memset(vis_e, 0, sizeof(vis_e[0])*rear);
    memset(is_bridge, 0, sizeof(is_bridge[0])*rear);
    dfs(1);
}

int main(){
    int n = 0,m = 0;
    while (scanf(" %d %d",&n,&m) != EOF) {
        if (n == 0 && m == 0) {
            break;
        }
        init(n);
        for (int i = 1; i <= m; i++) {
            int u = 0,v = 0,w = 0;
            scanf(" %d %d %d",&u,&v,&w);
            insert(u, v, w);
        }
        find_bridge(n);
        if (dfs_clock < n) {
            cout << 0 << endl;
        }else if (res == 909303) {
            cout << -1 << endl;
        }else if(res == 0){
            cout << 1 << endl;
        }else {
            cout << res << endl;
        }
    }
}

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

// HDU4738.cpp

// playground

#include <iostream>

#include <iomanip>

#include <algorithm>

#include <queue>

#include <vector>

#include <set>

#include <stack>

#include <map>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <cmath>

using namespace std;

#define MAXN 1005

#define MAXE 2000005

struct EDGE

{

int u, v, w;

int next;

};

int first[MAXN], rear;

EDGE edge[MAXE];

void init(int n)

{

memset(first, -1, sizeof(first[0])*(n+1));

rear = 0;

}

void insert(int tu, int tv, int tw)

{

edge[rear].u = tu;

edge[rear].v = tv;

edge[rear].w = tw;

edge[rear].next = first[tu];

first[tu] = rear++;

edge[rear].u = tv;

edge[rear].v = tu;

edge[rear].w = tw;

edge[rear].next = first[tv];

first[tv] = rear++;

}

int pre[MAXN], low[MAXN];

bool vis_e[MAXE]; //是否访问了边

bool is_bridge[MAXE]; //是否是桥

int dfs_clock;

int res = 909303;

void dfs(int cur)

{

pre[cur] = low[cur] = ++dfs_clock;

for(int i = first[cur]; ~i; i = edge[i].next)

{

//便利以当前点出发的所有边

int tv = edge[i].v;

if(!pre[tv])

{

//如果这条边连接着的节点还没有访问过，那就进到这个节点里面

vis_e[i] = vis_e[i^1] = true;

dfs(tv);

low[cur] = min(low[cur], low[tv]);

if(pre[cur] < low[tv]){

//当前边连着的这个节点处理完毕了，如果发现这个节点的low值还是比当前节点大，说明这个节点及其联通部分没有指向已访问任何节点的回边，也就是说割开当前这条边，这个节点以及其联通的部分就和当前节点裂开了，这条边也就理所当然的是割边

is_bridge[i] = is_bridge[i^1] = true;

res = min(res,edge[i].w);//更新答案用的

}

else

if(pre[tv] < pre[cur] && !vis_e[i])

{

//这里是如果当前这条边是一条回边，那么就要更新当前节点的low值了

vis_e[i] = vis_e[i^1] = true;

low[cur] = min(low[cur], pre[tv]);

}

void find_bridge(int n)

{

res = 909303;

dfs_clock = 0;

memset(pre, 0, sizeof(pre[0])*(n+1));

memset(vis_e, 0, sizeof(vis_e[0])*rear);

memset(is_bridge, 0, sizeof(is_bridge[0])*rear);

dfs(1);

}

int main(){

int n = 0,m = 0;

while (scanf(" %d %d",&n,&m) != EOF) {

if (n == 0 && m == 0) {

break;

}

init(n);

for (int i = 1; i <= m; i++) {

int u = 0,v = 0,w = 0;

scanf(" %d %d %d",&u,&v,&w);

insert(u, v, w);

}

find_bridge(n);

if (dfs_clock < n) {

cout << 0 << endl;

}else if (res == 909303) {

cout << -1 << endl;

}else if(res == 0){

cout << 1 << endl;

}else {

cout << res << endl;

}

HDU5396 / 15多校9-1 Expression

August 20, 20152015-08-20hahaschoolLeave a comment

题意

给出了一个算术表达式，表达式里面只会含有加减乘三种运算。我们每一次从中选取两个数字并执行这两个数字对应的运算，运算结果放回式子中继续进行运算，直到最后只剩下了一个数。让我们求的是每一种不同的选取方式所得到的结果的和。

注意

这个题没有做好的主要原因是没有领会到题目中关于不同的选取方式的定义，注意到题目中讲到只要有一轮选取的数字不一样，就视为不同。这句话的含义中有两个信息：一是允许重复，二是要分先后。

思路

最开始确实是没什么思路的，后来看了看board发现并不是特别难的题。于是尝试拆解问题，我们可以从算数式的一小段入手，以sample的1 + 4 * 6 – 8 * 3为例。

只考虑1 + 4部分，只有一种配置方法，就是(1 + 4);
考虑1 + 4 * 6部分，我们发现这一部分可以看成两种情况：1 + (4 * 6)和(1 + 4) * 6，在这里面我们已经考虑了1 + 4区段，而4 * 6区段只有一种配置。这样1 + 4 * 6这个区段就有两种配置了。
接下来考虑1 + 4 * 6 – 8区段，要想得到这个区段的全部情况，我们应该考虑：
1 + (4 * 6 – 8),1 + 4 * (6 – 8),(1 + 4) * 6 – 8,(1 + 4 * 6) – 8这些情况，其中(4 * 6 – 8)又可以看成考虑(4 * 6) – 8,4 * (6 – 8)这两种情况，而(1 + 4 * 6)的对应情况我们先前已经算好了。
最后，考虑1 + 4 * 6 – 8 * 3，顺着上面的思路来，就可以拆分成：
1 + (4 * 6 – 8 * 3),1 + 4 * (6 – 8 * 3),(1 + 4) * 6 – (8 * 3),(1 + 4 * 6) – 8 * 3,(1 + 4 * 6 – 8) * 3，接下来再去拆分这五种情况中的子情况。。。

如果比较敏感的话应该已经发现这就是典型的区间dp了，在推方程的时候，我们是将所有子情况的答案累加，得到当前情况的答案，但这还不够，还要注意每种情况，因为选择顺序的关系，会有多重副本，而这个副本的数量其实蛮好求，就是阶乘，而还要注意，我们在讨论当前情况的时候，是将整个等待处理的算式区段分成了（左区段）算子（分界点）算子（右区段）这样看待的，那么先后的问题又来了，我们不光左右区段的答案自身要乘上阶乘，最后整个结果还要乘上一个组合数，因为左右区段的操作又是分先后的。

以下引自官方题解，注意第2段第2行的dp[l][r]实际上是dp[l][k]。

代码

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <cmath>

using namespace std;

#define MODER 1000000007
#define MAXN 105
long long seq[MAXN];
long long fac[MAXN];
long long C[MAXN][MAXN];
string op;
int n = 0;

long long dp[MAXN][MAXN];

long long calc(char _op,long long a,long long b){
    if (_op == '+') {
        return a+b;
    }
    if (_op == '-') {
        return a-b;
    }
    if (_op == '*') {
        return a*b;
    }
    return 0;
}

void solve(){
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; i++) {
        dp[i][i] = seq[i];
    }
    for (int j = 1; j <= n; j++) {
        for (int i = j - 1; i >= 1; i--) {
            for (int k = i; k < j; k++) {
                if (op[k-1] == '*') {
                    dp[i][j] += calc(op[k-1], dp[i][k], dp[k+1][j])*(C[j-i-1][k-i]%MODER);
                    dp[i][j] %= MODER;
                }else{
                    dp[i][j] += calc(op[k-1], dp[i][k]*fac[j-k-1], dp[k+1][j]*fac[k-i])*(C[j-i-1][k-i]%MODER);
                    dp[i][j] %= MODER;
                }
                dp[i][j] %= MODER;
            }
        }
    }
    cout << (dp[1][n]+MODER)%MODER << endl;
}

int main(){
    fac[0] = 1;
    fac[1] = 1;
    for (int i = 2; i < MAXN; i++) {
        fac[i] = fac[i-1] * i;
        fac[i] %= MODER;
    }
    for (int i = 0; i < MAXN; i++) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; j++) {
            C[i][j] = (C[i-1][j-1] + C[i-1][j])%MODER;
        }
    }
    while (scanf(" %d",&n) != EOF) {
        for (int i = 1; i <= n; i++) {
            scanf(" %lld",&seq[i]);
        }
        cin >> op;
        solve();
    }
    return 0;
}

#include <iostream>

#include <iomanip>

#include <algorithm>

#include <queue>

#include <vector>

#include <set>

#include <stack>

#include <map>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <cmath>

using namespace std;

#define MODER 1000000007

#define MAXN 105

long long seq[MAXN];

long long fac[MAXN];

long long C[MAXN][MAXN];

string op;

int n = 0;

long long dp[MAXN][MAXN];

long long calc(char _op,long long a,long long b){

if (_op == '+') {

return a+b;

}

if (_op == '-') {

return a-b;

}

if (_op == '*') {

return a*b;

}

return 0;

}

void solve(){

memset(dp, 0, sizeof(dp));

for (int i = 1; i <= n; i++) {

dp[i][i] = seq[i];

}

for (int j = 1; j <= n; j++) {

for (int i = j - 1; i >= 1; i--) {

for (int k = i; k < j; k++) {

if (op[k-1] == '*') {

dp[i][j] += calc(op[k-1], dp[i][k], dp[k+1][j])*(C[j-i-1][k-i]%MODER);

dp[i][j] %= MODER;

}else{

dp[i][j] += calc(op[k-1], dp[i][k]*fac[j-k-1], dp[k+1][j]*fac[k-i])*(C[j-i-1][k-i]%MODER);

dp[i][j] %= MODER;

}

dp[i][j] %= MODER;

}

cout << (dp[1][n]+MODER)%MODER << endl;

}

int main(){

fac[0] = 1;

fac[1] = 1;

for (int i = 2; i < MAXN; i++) {

fac[i] = fac[i-1] * i;

fac[i] %= MODER;

}

for (int i = 0; i < MAXN; i++) {

C[i][0] = C[i][i] = 1;

for (int j = 1; j < i; j++) {

C[i][j] = (C[i-1][j-1] + C[i-1][j])%MODER;

}

while (scanf(" %d",&n) != EOF) {

for (int i = 1; i <= n; i++) {

scanf(" %lld",&seq[i]);

}

cin >> op;

solve();

}

return 0;

}

测试数据

97
42002488 796642576 700424534 492928793 184907764 938887713 107181410 792482963 116518857 549637047 48511747 856433446 590402464 673573447 69495247 203714018 787925377 850112031 375048938 271938638 802494129 158813597 264970784 798528530 490197704 767196026 415353101 689929144 369487202 500663908 925646045 947272745 114170350 422275395 246584468 426418550 579611856 152254016 594726322 728563727 288775478 565138043 680902891 876305510 191112081 452293970 492433812 225768745 679619541 994547367 982603691 15296092 603978680 788518145 465189078 210083862 284880628 329589000 399155372 591915435 797863137 618608585 376324991 227860486 120496725 572177678 329264566 227752653 18519150 658879074 140948055 480823355 695634904 724306259 441449688 256897368 85177480 128320040 41023787 381309904 286849451 367291277 211136278 290206582 349174511 816810643 807052002 541046992 896355733 423997911 637059027 125956299 890644270 192297197 195369584 799285045 466378517
*-+*-**-**+++*-+***+-+*---*--*-**--+*+-+-+*--*+-+*--*-+-+++-+--*-+-*-*++-*-**--+++*--*---++-*++*
100
325956497 703488203 24659275 111168319 30696633 867177774 567622896 185486419 730598881 883230119 563712961 180803964 584941667 42152595 815189025 948445222 884302629 466122431 388540473 372338423 752635513 450641548 639363964 357672619 825047257 242786661 924828610 870704848 270082303 123836441 184865109 256936904 141852852 53253274 127451487 980520417 371387947 159139226 594030471 989127423 368227302 520002431 426259211 996010421 453683913 296897751 30787432 117956896 228079495 691620926 472262826 67500912 817492577 585593640 200764240 553661751 385019596 415018760 607221075 359597740 879829661 611875418 72124927 645005443 360828306 807614336 631355051 144405553 577602237 307688494 780098694 145617805 554856951 119871777 577700931 735031691 442941868 914165376 161547196 986694552 589094296 393092926 299298515 27791972 528267970 281143872 40947478 656044098 203648506 270007357 395952343 102357150 867735114 759911266 233005045 225629783 216508671 965812522 867627947 54865288
+*+--*-*--+-+-+-**++**-*-*-+++*----*+-+-*-+--*-*++***--+--+--++*-*-+--+++--*--+**+**+-++++-++-+-+-*
90
956166081 237081354 516719910 457360421 651030602 297934201 515637975 519190273 54461470 788822420 279420737 34945495 176179851 783472901 692713303 659271374 203828810 406894617 768216502 461887911 221519925 409786328 934329140 306306033 329222655 272749566 919794473 709469627 302842176 528461835 946937241 537809932 810411833 899731345 234778231 117393561 254762040 126366265 546045205 14512569 569130426 607567456 203472523 734412701 828351711 918290891 334578733 149890177 382043196 169168053 245184636 511942620 100149911 315905467 115836107 692482046 906064513 661013850 824221946 293670720 80472372 90846392 220956727 408720330 754118436 945210308 859229672 853979780 968731675 852433305 908692551 199233651 11771210 317467451 856084951 49265992 825336724 452902485 164913224 679351928 304042220 847674906 821118447 182594926 694723853 291245530 803251413 540653332 592046149 142109566
++*---+*+**-++++***+*+-+*---+-+***--+-*-+++*+--*-*--**+***+--**-+-+-++*****------*+-++**-
98
465893828 289478394 637733884 308885867 438351788 735511445 307686150 260496183 824225502 905288458 256046492 786615060 148277488 673436291 27093667 401773414 1160361 980127483 369236180 639808765 442848666 282140241 285019731 91637988 737317728 162662493 733270777 918021327 953687807 211142407 579529297 24704404 541921193 680289260 117728749 103507124 79572674 561536575 15361202 98943187 967924857 691391009 194221889 323326354 951458576 315726744 858945948 955751157 648400730 61497384 961311423 784338729 294243201 890869562 522348152 691037449 323402334 682597630 973909177 717395005 95548247 21273692 917317409 131467669 249482841 728306708 443179802 60669811 107016161 656988680 561007944 172140657 89706235 52256148 475262929 286585935 470901312 299761485 692845276 902285286 173616886 630407007 687350996 982195399 356786913 761716439 746065586 615855955 988179377 213166205 714725937 33387759 271839281 110967052 14364116 148251161 502652519 90843729
-+-++-*+-+-++*---*+*+-**+**--*-+-*-*-+**+****+-+--*-*---++-*-**+-*+*+*****+--*-*-*++++**-*+*----+
90
350460548 683529871 618335624 301938708 443122496 740210529 608748989 773860075 674745679 22051422 3363717 987211125 7455042 150942802 582997451 291451956 853047743 431725539 36063965 916459186 38819334 344832685 905333497 1107506 975568033 430522271 161030190 197567954 895976561 296526280 570825600 567895344 214279060 533392121 265331207 871875814 43745873 576354855 463692349 974512750 403562709 549167732 828509064 696570071 722237507 802639046 991590202 959577397 340576026 62211977 989146740 14037103 635490010 76262658 676592780 771209273 144694401 589889441 374019705 794324052 631865159 951489016 543939718 848804382 598908343 454624051 191117102 551826494 15211257 347769268 242088328 821837708 735776787 734680412 604336524 27170997 995319171 131982742 84150036 813106575 43808331 416344584 422178259 871443637 216387827 398825027 345823744 111101361 155871499 780534153
**-*-++-*-**-*-+**++*-*-+--++-*-+*+-**+*+*-+--+-****++++--+--***-***+--*-*-**-+*+**+--*++
91
369083073 419494718 203958830 132372075 390802926 108536958 359364853 19500017 269482466 116851881 344733006 179976765 665095536 360566894 927223606 19745537 491617131 255871431 124073757 831691852 936168299 628337639 858503621 108450073 907654947 372031410 911623368 876473964 201368080 876278835 741544686 308383962 105473714 378332068 996785400 271362759 704071329 849695712 653933557 203390911 361151674 38280361 955354553 522170431 280173923 910896686 363582043 455411786 666760984 961246757 160430953 687453873 722283066 498568491 361164110 310314399 980345471 155440227 622193202 125958147 10507896 741345861 389880790 480072833 776884410 323432536 97991633 567659920 127960073 533577083 783345366 151218843 982868351 60821489 482093522 436596314 984998445 444073626 446463882 520127981 851250321 237935771 36254845 181834749 1892735 590141893 44183356 907397065 651309846 304020843 692801648
+--++--+-***+-*****-*+**-*-+-+-*-+---+-++**---*+*+++--*--+****-++-+*++*-+**--**---+*+++*-+
95
485961444 707318302 57064654 176495871 981660811 806591453 749245216 252359665 640407166 201588566 229199175 22221498 253223551 89060045 36553720 599810065 690462711 312436980 238112789 353747414 1235787 421192028 507582469 881355702 715088908 889803479 427807294 715763499 180319586 856082545 252088586 371033343 805019366 508584217 969333119 98454585 271605226 361453207 64747991 650332198 547814821 873131112 984499986 580710491 344613939 615329421 404282591 777196302 118410946 11963934 659717948 507303795 747209595 950367516 753045801 176048491 706920969 173638533 316930518 527337716 578840389 846842421 243743892 197032755 731614680 851429944 626387157 782585390 891983285 190702081 843662892 380320957 46341925 767604463 954225554 298117931 559555112 239118791 302671351 708956286 752167883 1322449 902538348 425160852 358281322 987326867 999028966 751278854 149097087 738185510 584755024 344857640 348462276 159402382 992435733
++*+*--+---*--+*+-+-+--*--+*-+*-***-++++-*++--**-*-++**+*--+---++-+*-+-*****--+*++-++---*+-*-*
90
708511031 580454884 227136142 315621694 816437399 199767158 386431313 686370110 238353452 139416588 779802144 608654642 467489163 831726446 177582404 378458251 337656406 254807945 342315402 863727928 286103825 511591671 575369197 838832647 507977204 814685639 337057684 773267625 341189200 866190414 207863050 394278149 453465048 441178914 35690319 69224577 296167130 849182168 708756333 283539732 546794320 603792560 38629336 734370168 392790933 10814704 666659334 849235982 691489146 328094362 607198396 698640135 10716951 828126963 375568154 828692719 823702322 575575625 918563014 375356521 475300605 659723582 175829677 963552591 888605399 232840649 634512826 82307505 912075233 92779504 653744096 592088094 742745064 820901033 815390368 483300366 543784186 724589233 156227853 913512225 19661415 753126660 567955191 261150273 594085718 547745500 853111654 352199308 705804090 799372957
+--*-*-----*-+---**+*-+*--++*--*+--+--**+***-*--*++-*+-+-***-+*+**+*-*-*-*-+--*---*+*+-++
96
745131348 132164682 53201627 902282100 874213989 356071088 989681045 309159690 969998164 250807468 224153864 637733574 414025807 534447052 239938263 651633817 668396919 458283193 843872939 159037502 11057109 236593972 429549911 851112401 704402304 78699305 238509846 404970270 39586946 9081814 306277267 3711244 564099019 968721766 710261919 586758441 982680786 401446643 500175322 213135781 877490352 453437567 329475656 806918548 853703984 114299540 88539338 160468731 669040349 957021960 49639602 535019049 141455628 719430169 270319732 619425002 947845400 586735438 752287536 216082851 802549300 311244799 445723663 870569122 283877780 655342789 300264268 954376549 311654858 144010011 396563887 901014044 266438208 32948491 722645416 381920087 782995709 50813474 604350127 112815107 314336714 409810162 881358330 733090236 875766857 841898841 821955077 972889196 454176407 564218854 438155439 767047250 355712741 832941005 456329031 419935147
**+++-*+---*-++*+++**++*-*+-*++*-**++*+*++-**+****-+++-+*-+--**-++++***+****+-**-*++--**+++*---
94
879208146 720194280 688588236 132151311 571754818 516340692 372196947 679358302 58621157 310946581 801039916 514131463 921434971 429834826 912359712 414935618 613718553 74440483 16817102 233159445 36718893 621052009 507311235 415092243 764745446 891797180 958065907 610573861 5726480 875130917 57458402 30582627 405021797 687280414 778490387 220908214 154543311 509544961 371751221 979852052 447958755 139043990 514555945 716641402 561306439 453747387 499366646 482768254 787975719 127490978 758930338 383071499 687188345 424770454 344217611 538347542 492161286 496179179 912925428 903636458 25400076 207749328 793144023 909837457 737624442 247805916 983546684 847258002 338263826 680076652 837407636 596231254 321433816 415494165 868192278 2043786 797470453 521067839 969135743 198743740 376254888 359629600 614277288 946583788 732320246 959854749 206526850 756861967 653066081 493501859 24106177 39504781 934132764 132575038
*---+--*-*+--+***+*-+*-+*-+--*****-----++*-+****-*-*--*+*++*+---**+*+*+*-+**+*+-*+*+-**--*+++

42002488 796642576 700424534 492928793 184907764 938887713 107181410 792482963 116518857 549637047 48511747 856433446 590402464 673573447 69495247 203714018 787925377 850112031 375048938 271938638 802494129 158813597 264970784 798528530 490197704 767196026 415353101 689929144 369487202 500663908 925646045 947272745 114170350 422275395 246584468 426418550 579611856 152254016 594726322 728563727 288775478 565138043 680902891 876305510 191112081 452293970 492433812 225768745 679619541 994547367 982603691 15296092 603978680 788518145 465189078 210083862 284880628 329589000 399155372 591915435 797863137 618608585 376324991 227860486 120496725 572177678 329264566 227752653 18519150 658879074 140948055 480823355 695634904 724306259 441449688 256897368 85177480 128320040 41023787 381309904 286849451 367291277 211136278 290206582 349174511 816810643 807052002 541046992 896355733 423997911 637059027 125956299 890644270 192297197 195369584 799285045 466378517

*-+*-**-**+++*-+***+-+*---*--*-**--+*+-+-+*--*+-+*--*-+-+++-+--*-+-*-*++-*-**--+++*--*---++-*++*

100

325956497 703488203 24659275 111168319 30696633 867177774 567622896 185486419 730598881 883230119 563712961 180803964 584941667 42152595 815189025 948445222 884302629 466122431 388540473 372338423 752635513 450641548 639363964 357672619 825047257 242786661 924828610 870704848 270082303 123836441 184865109 256936904 141852852 53253274 127451487 980520417 371387947 159139226 594030471 989127423 368227302 520002431 426259211 996010421 453683913 296897751 30787432 117956896 228079495 691620926 472262826 67500912 817492577 585593640 200764240 553661751 385019596 415018760 607221075 359597740 879829661 611875418 72124927 645005443 360828306 807614336 631355051 144405553 577602237 307688494 780098694 145617805 554856951 119871777 577700931 735031691 442941868 914165376 161547196 986694552 589094296 393092926 299298515 27791972 528267970 281143872 40947478 656044098 203648506 270007357 395952343 102357150 867735114 759911266 233005045 225629783 216508671 965812522 867627947 54865288

+*+--*-*--+-+-+-**++**-*-*-+++*----*+-+-*-+--*-*++***--+--+--++*-*-+--+++--*--+**+**+-++++-++-+-+-*

956166081 237081354 516719910 457360421 651030602 297934201 515637975 519190273 54461470 788822420 279420737 34945495 176179851 783472901 692713303 659271374 203828810 406894617 768216502 461887911 221519925 409786328 934329140 306306033 329222655 272749566 919794473 709469627 302842176 528461835 946937241 537809932 810411833 899731345 234778231 117393561 254762040 126366265 546045205 14512569 569130426 607567456 203472523 734412701 828351711 918290891 334578733 149890177 382043196 169168053 245184636 511942620 100149911 315905467 115836107 692482046 906064513 661013850 824221946 293670720 80472372 90846392 220956727 408720330 754118436 945210308 859229672 853979780 968731675 852433305 908692551 199233651 11771210 317467451 856084951 49265992 825336724 452902485 164913224 679351928 304042220 847674906 821118447 182594926 694723853 291245530 803251413 540653332 592046149 142109566

++*---+*+**-++++***+*+-+*---+-+***--+-*-+++*+--*-*--**+***+--**-+-+-++*****------*+-++**-

465893828 289478394 637733884 308885867 438351788 735511445 307686150 260496183 824225502 905288458 256046492 786615060 148277488 673436291 27093667 401773414 1160361 980127483 369236180 639808765 442848666 282140241 285019731 91637988 737317728 162662493 733270777 918021327 953687807 211142407 579529297 24704404 541921193 680289260 117728749 103507124 79572674 561536575 15361202 98943187 967924857 691391009 194221889 323326354 951458576 315726744 858945948 955751157 648400730 61497384 961311423 784338729 294243201 890869562 522348152 691037449 323402334 682597630 973909177 717395005 95548247 21273692 917317409 131467669 249482841 728306708 443179802 60669811 107016161 656988680 561007944 172140657 89706235 52256148 475262929 286585935 470901312 299761485 692845276 902285286 173616886 630407007 687350996 982195399 356786913 761716439 746065586 615855955 988179377 213166205 714725937 33387759 271839281 110967052 14364116 148251161 502652519 90843729

-+-++-*+-+-++*---*+*+-**+**--*-+-*-*-+**+****+-+--*-*---++-*-**+-*+*+*****+--*-*-*++++**-*+*----+

350460548 683529871 618335624 301938708 443122496 740210529 608748989 773860075 674745679 22051422 3363717 987211125 7455042 150942802 582997451 291451956 853047743 431725539 36063965 916459186 38819334 344832685 905333497 1107506 975568033 430522271 161030190 197567954 895976561 296526280 570825600 567895344 214279060 533392121 265331207 871875814 43745873 576354855 463692349 974512750 403562709 549167732 828509064 696570071 722237507 802639046 991590202 959577397 340576026 62211977 989146740 14037103 635490010 76262658 676592780 771209273 144694401 589889441 374019705 794324052 631865159 951489016 543939718 848804382 598908343 454624051 191117102 551826494 15211257 347769268 242088328 821837708 735776787 734680412 604336524 27170997 995319171 131982742 84150036 813106575 43808331 416344584 422178259 871443637 216387827 398825027 345823744 111101361 155871499 780534153

**-*-++-*-**-*-+**++*-*-+--++-*-+*+-**+*+*-+--+-****++++--+--***-***+--*-*-**-+*+**+--*++

369083073 419494718 203958830 132372075 390802926 108536958 359364853 19500017 269482466 116851881 344733006 179976765 665095536 360566894 927223606 19745537 491617131 255871431 124073757 831691852 936168299 628337639 858503621 108450073 907654947 372031410 911623368 876473964 201368080 876278835 741544686 308383962 105473714 378332068 996785400 271362759 704071329 849695712 653933557 203390911 361151674 38280361 955354553 522170431 280173923 910896686 363582043 455411786 666760984 961246757 160430953 687453873 722283066 498568491 361164110 310314399 980345471 155440227 622193202 125958147 10507896 741345861 389880790 480072833 776884410 323432536 97991633 567659920 127960073 533577083 783345366 151218843 982868351 60821489 482093522 436596314 984998445 444073626 446463882 520127981 851250321 237935771 36254845 181834749 1892735 590141893 44183356 907397065 651309846 304020843 692801648

+--++--+-***+-*****-*+**-*-+-+-*-+---+-++**---*+*+++--*--+****-++-+*++*-+**--**---+*+++*-+

485961444 707318302 57064654 176495871 981660811 806591453 749245216 252359665 640407166 201588566 229199175 22221498 253223551 89060045 36553720 599810065 690462711 312436980 238112789 353747414 1235787 421192028 507582469 881355702 715088908 889803479 427807294 715763499 180319586 856082545 252088586 371033343 805019366 508584217 969333119 98454585 271605226 361453207 64747991 650332198 547814821 873131112 984499986 580710491 344613939 615329421 404282591 777196302 118410946 11963934 659717948 507303795 747209595 950367516 753045801 176048491 706920969 173638533 316930518 527337716 578840389 846842421 243743892 197032755 731614680 851429944 626387157 782585390 891983285 190702081 843662892 380320957 46341925 767604463 954225554 298117931 559555112 239118791 302671351 708956286 752167883 1322449 902538348 425160852 358281322 987326867 999028966 751278854 149097087 738185510 584755024 344857640 348462276 159402382 992435733

++*+*--+---*--+*+-+-+--*--+*-+*-***-++++-*++--**-*-++**+*--+---++-+*-+-*****--+*++-++---*+-*-*

708511031 580454884 227136142 315621694 816437399 199767158 386431313 686370110 238353452 139416588 779802144 608654642 467489163 831726446 177582404 378458251 337656406 254807945 342315402 863727928 286103825 511591671 575369197 838832647 507977204 814685639 337057684 773267625 341189200 866190414 207863050 394278149 453465048 441178914 35690319 69224577 296167130 849182168 708756333 283539732 546794320 603792560 38629336 734370168 392790933 10814704 666659334 849235982 691489146 328094362 607198396 698640135 10716951 828126963 375568154 828692719 823702322 575575625 918563014 375356521 475300605 659723582 175829677 963552591 888605399 232840649 634512826 82307505 912075233 92779504 653744096 592088094 742745064 820901033 815390368 483300366 543784186 724589233 156227853 913512225 19661415 753126660 567955191 261150273 594085718 547745500 853111654 352199308 705804090 799372957

+--*-*-----*-+---**+*-+*--++*--*+--+--**+***-*--*++-*+-+-***-+*+**+*-*-*-*-+--*---*+*+-++

745131348 132164682 53201627 902282100 874213989 356071088 989681045 309159690 969998164 250807468 224153864 637733574 414025807 534447052 239938263 651633817 668396919 458283193 843872939 159037502 11057109 236593972 429549911 851112401 704402304 78699305 238509846 404970270 39586946 9081814 306277267 3711244 564099019 968721766 710261919 586758441 982680786 401446643 500175322 213135781 877490352 453437567 329475656 806918548 853703984 114299540 88539338 160468731 669040349 957021960 49639602 535019049 141455628 719430169 270319732 619425002 947845400 586735438 752287536 216082851 802549300 311244799 445723663 870569122 283877780 655342789 300264268 954376549 311654858 144010011 396563887 901014044 266438208 32948491 722645416 381920087 782995709 50813474 604350127 112815107 314336714 409810162 881358330 733090236 875766857 841898841 821955077 972889196 454176407 564218854 438155439 767047250 355712741 832941005 456329031 419935147

**+++-*+---*-++*+++**++*-*+-*++*-**++*+*++-**+****-+++-+*-+--**-++++***+****+-**-*++--**+++*---

879208146 720194280 688588236 132151311 571754818 516340692 372196947 679358302 58621157 310946581 801039916 514131463 921434971 429834826 912359712 414935618 613718553 74440483 16817102 233159445 36718893 621052009 507311235 415092243 764745446 891797180 958065907 610573861 5726480 875130917 57458402 30582627 405021797 687280414 778490387 220908214 154543311 509544961 371751221 979852052 447958755 139043990 514555945 716641402 561306439 453747387 499366646 482768254 787975719 127490978 758930338 383071499 687188345 424770454 344217611 538347542 492161286 496179179 912925428 903636458 25400076 207749328 793144023 909837457 737624442 247805916 983546684 847258002 338263826 680076652 837407636 596231254 321433816 415494165 868192278 2043786 797470453 521067839 969135743 198743740 376254888 359629600 614277288 946583788 732320246 959854749 206526850 756861967 653066081 493501859 24106177 39504781 934132764 132575038

*---+--*-*+--+***+*-+*-+*-+--*****-----++*-+****-*-*--*+*++*+---**+*+*+*-+**+*+-*+*+-**--*+++

302477149

455689444

197787710

802805207

652251842

492754358

934589866

940842836

821057755

931125012

SPOJ LCS Longest Common Substring

August 09, 20152015-08-09hahaschool2 Comments

［等待填坑］

//
//  SPOJ LCS.cpp
//  playground
//
//  Created by Adam Chang on 2015/08/08.
//  Copyright © 2015年 Adam Chang. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>

using namespace std;

struct SAM_State{
    int mxn;
    SAM_State *to[26];
    SAM_State *parent;
    SAM_State(int _mxn){
        mxn = _mxn;
        memset(to, 0, sizeof(to));
        parent = NULL;
    }
};

SAM_State* SAM_Append(SAM_State *last,SAM_State *root,int ch){
    SAM_State *p = last;
    SAM_State *np = new SAM_State(p -> mxn + 1);
    while (p && p -> to[ch] == NULL) {
        p -> to[ch] = np;
        p = p -> parent;
    }
    if (p != NULL) {
        SAM_State *q = p -> to[ch];
        if (q -> mxn == p -> mxn + 1) {
            np -> parent = q;
        }else{
            SAM_State *nq = new SAM_State(p -> mxn + 1);
            nq -> parent = q -> parent;
            q -> parent = nq;
            np -> parent = nq;
            memcpy(nq -> to, q -> to, sizeof(q -> to));
            while (p && p -> to[ch] == q) {
                p -> to[ch] = nq;
                p = p -> parent;
            }
        }
    }else{
        np -> parent = root;
    }
    last = np;
    return last;
}

SAM_State* SAM_Build(string str){
    SAM_State *root = new SAM_State(0);
    SAM_State *last = root;
    for (int i = 0; i < str.size(); i++) {
        last = SAM_Append(last, root, str[i] - 'a');
    }
    return root;
}


int main(){
    string a,b;
    cin >> a >> b;
    SAM_State *sam_root = SAM_Build(a);
    SAM_State *sam = sam_root;
    int ans = 0;
    int curcnt = 0;
    for (int i = 0; i < b.size(); i++) {
        if (sam -> to[b[i]-'a'] != NULL) {
            curcnt++;
            sam = sam -> to[b[i]-'a'];
        }else{
            ans = max(curcnt,ans);
            curcnt = 0;
            while (sam -> parent) {
                sam = sam -> parent;
                if (sam -> to[b[i]-'a'] != NULL) {
                    curcnt = sam->mxn+1;
                    sam = sam -> to[b[i]-'a'];
                    break;
                }
            }
        }
    }
    cout << max(curcnt,ans) << endl;
    return 0;
}

100

101

102

103

// SPOJ LCS.cpp

// playground

// Created by Adam Chang on 2015/08/08.

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

using namespace std;

struct SAM_State{

int mxn;

SAM_State *to[26];

SAM_State *parent;

SAM_State(int _mxn){

mxn = _mxn;

memset(to, 0, sizeof(to));

parent = NULL;

}

};

SAM_State* SAM_Append(SAM_State *last,SAM_State *root,int ch){

SAM_State *p = last;

SAM_State *np = new SAM_State(p -> mxn + 1);

while (p && p -> to[ch] == NULL) {

p -> to[ch] = np;

p = p -> parent;

}

if (p != NULL) {

SAM_State *q = p -> to[ch];

if (q -> mxn == p -> mxn + 1) {

np -> parent = q;

}else{

SAM_State *nq = new SAM_State(p -> mxn + 1);

nq -> parent = q -> parent;

q -> parent = nq;

np -> parent = nq;

memcpy(nq -> to, q -> to, sizeof(q -> to));

while (p && p -> to[ch] == q) {

p -> to[ch] = nq;

p = p -> parent;

}

}else{

np -> parent = root;

}

last = np;

return last;

}

SAM_State* SAM_Build(string str){

SAM_State *root = new SAM_State(0);

SAM_State *last = root;

for (int i = 0; i < str.size(); i++) {

last = SAM_Append(last, root, str[i] - 'a');

}

return root;

}

int main(){

string a,b;

cin >> a >> b;

SAM_State *sam_root = SAM_Build(a);

SAM_State *sam = sam_root;

int ans = 0;

int curcnt = 0;

for (int i = 0; i < b.size(); i++) {

if (sam -> to[b[i]-'a'] != NULL) {

curcnt++;

sam = sam -> to[b[i]-'a'];

}else{

ans = max(curcnt,ans);

curcnt = 0;

while (sam -> parent) {

sam = sam -> parent;

if (sam -> to[b[i]-'a'] != NULL) {

curcnt = sam->mxn+1;

sam = sam -> to[b[i]-'a'];

break;

}

cout << max(curcnt,ans) << endl;

return 0;

}

SPOJ LCS2 Longest Common Substring II

August 09, 20152015-08-09hahaschoolLeave a comment

［详细题解等待填坑］

SPOJ真是业界奇葩

//
//  SPOJ LCS2.cpp
//  playground
//
//  Created by Adam Chang on 2015/08/08.
//  Copyright © 2015年 Adam Chang. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>

using namespace std;

struct SAM_State{
    int mxn;
    int mi;
    int mx;
    SAM_State *to[26];
    SAM_State *parent;
    void init(int _mxn){
        mxn = _mxn;
        memset(to, NULL, sizeof(to));
        parent = NULL;
        mx = 0;
        mi = 909303;
    }
} idx[200005];

int totalNode = 0;
int mxmxn = 0;
SAM_State *idx_sorted[200005];

SAM_State* SAM_Append(SAM_State *last,SAM_State *root,int ch){
    SAM_State *p = last;
    SAM_State *np = &idx[++totalNode];
    np -> mxn = p -> mxn + 1;
    mxmxn = max(mxmxn, np -> mxn);
    while (p && p -> to[ch] == NULL) {
        p -> to[ch] = np;
        p = p -> parent;
    }
    if (p != NULL) {
        SAM_State *q = p -> to[ch];
        if (q -> mxn == p -> mxn + 1) {
            np -> parent = q;
        }else{
            SAM_State *nq = &idx[++totalNode];
            *nq = *q;
            nq -> mxn = p -> mxn + 1;
            q -> parent = nq;
            np -> parent = nq;
            while (p && p -> to[ch] == q) {
                p -> to[ch] = nq;
                p = p -> parent;
            }
        }
    }else{
        np -> parent = root;
    }
    last = np;
    return last;
}

void init(int n){
    for (int i = 0; i <= n ; i++) {
        idx[i].init(0);
    }
    totalNode = 0;
    mxmxn = 0;
}

SAM_State* SAM_Build(char* str){
    int len = (int)strlen(str);
    init(2*len);
    SAM_State *root = &idx[0];
    SAM_State *last = root;
    for (int i = 0; i < len; i++) {
        last = SAM_Append(last, root, str[i] - 'a');
    }
    return root;
}

int cnt[100005];
void toposort(){
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i <= totalNode; i++) {
        cnt[idx[i].mxn]++;
    }
    for (int i = 1; i <= mxmxn; i++) {
        cnt[i] += cnt[i-1];
    }
    for (int i = 0; i <= totalNode; i++) {
        idx_sorted[--cnt[idx[i].mxn]] = &idx[i];
    }
}



char a[100005];

int main(){
    scanf("%s",a);
    SAM_State *sam_root = SAM_Build(a);
    toposort();
    while (scanf("%s",a) != EOF) {
        int len = (int)strlen(a);
        SAM_State *sam = sam_root;
        int tmp = 0;
        for (int i = 0; i < len; i++) {
            if (sam -> to[a[i] - 'a'] != NULL) {
                tmp++;
                sam = sam -> to[a[i] - 'a'];
            }else{
                while (sam && sam -> to[a[i] - 'a'] == NULL) {
                    sam = sam -> parent;
                }
                if (sam == NULL) {
                    sam = sam_root;
                    tmp = 0;
                }else{
                    tmp = sam -> mxn + 1;
                    sam = sam -> to[a[i] - 'a'];
                }
            }
            sam -> mx = max(sam -> mx, tmp);
        }
        for (int j = totalNode; j >= 0; j--) {
            SAM_State *cur = idx_sorted[j];
            cur -> mi = min(cur -> mi, cur -> mx);
            if (cur -> parent != NULL) {
                cur -> parent -> mx = max(cur -> parent -> mx, cur -> mx);
                cur -> parent -> mx = min(cur -> parent -> mxn,cur -> parent -> mx);
            }
            cur -> mx = 0;
        }
    }
    int res = 0;
    for (int i = 0; i <= totalNode; i++) {
        res = max(idx[i].mi, res);
    }
    printf("%d\n",res);
    return 0;
}

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

// SPOJ LCS2.cpp

// playground

// Created by Adam Chang on 2015/08/08.

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

using namespace std;

struct SAM_State{

int mxn;

int mi;

int mx;

SAM_State *to[26];

SAM_State *parent;

void init(int _mxn){

mxn = _mxn;

memset(to, NULL, sizeof(to));

parent = NULL;

mx = 0;

mi = 909303;

}

} idx[200005];

int totalNode = 0;

int mxmxn = 0;

SAM_State *idx_sorted[200005];

SAM_State* SAM_Append(SAM_State *last,SAM_State *root,int ch){

SAM_State *p = last;

SAM_State *np = &idx[++totalNode];

np -> mxn = p -> mxn + 1;

mxmxn = max(mxmxn, np -> mxn);

while (p && p -> to[ch] == NULL) {

p -> to[ch] = np;

p = p -> parent;

}

if (p != NULL) {

SAM_State *q = p -> to[ch];

if (q -> mxn == p -> mxn + 1) {

np -> parent = q;

}else{

SAM_State *nq = &idx[++totalNode];

*nq = *q;

nq -> mxn = p -> mxn + 1;

q -> parent = nq;

np -> parent = nq;

while (p && p -> to[ch] == q) {

p -> to[ch] = nq;

p = p -> parent;

}

}else{

np -> parent = root;

}

last = np;

return last;

}

void init(int n){

for (int i = 0; i <= n ; i++) {

idx[i].init(0);

}

totalNode = 0;

mxmxn = 0;

}

SAM_State* SAM_Build(char* str){

int len = (int)strlen(str);

init(2*len);

SAM_State *root = &idx[0];

SAM_State *last = root;

for (int i = 0; i < len; i++) {

last = SAM_Append(last, root, str[i] - 'a');

}

return root;

}

int cnt[100005];

void toposort(){

memset(cnt, 0, sizeof(cnt));

for (int i = 0; i <= totalNode; i++) {

cnt[idx[i].mxn]++;

}

for (int i = 1; i <= mxmxn; i++) {

cnt[i] += cnt[i-1];

}

for (int i = 0; i <= totalNode; i++) {

idx_sorted[--cnt[idx[i].mxn]] = &idx[i];

}

char a[100005];

int main(){

scanf("%s",a);

SAM_State *sam_root = SAM_Build(a);

toposort();

while (scanf("%s",a) != EOF) {

int len = (int)strlen(a);

SAM_State *sam = sam_root;

int tmp = 0;

for (int i = 0; i < len; i++) {

if (sam -> to[a[i] - 'a'] != NULL) {

tmp++;

sam = sam -> to[a[i] - 'a'];

}else{

while (sam && sam -> to[a[i] - 'a'] == NULL) {

sam = sam -> parent;

}

if (sam == NULL) {

sam = sam_root;

tmp = 0;

}else{

tmp = sam -> mxn + 1;

sam = sam -> to[a[i] - 'a'];

}

sam -> mx = max(sam -> mx, tmp);

}

for (int j = totalNode; j >= 0; j--) {

SAM_State *cur = idx_sorted[j];

cur -> mi = min(cur -> mi, cur -> mx);

if (cur -> parent != NULL) {

cur -> parent -> mx = max(cur -> parent -> mx, cur -> mx);

cur -> parent -> mx = min(cur -> parent -> mxn,cur -> parent -> mx);

}

cur -> mx = 0;

}

int res = 0;

for (int i = 0; i <= totalNode; i++) {

res = max(idx[i].mi, res);

}

printf("%d\n",res);

return 0;

}

SPOJ SORTBIT Sorted bit squence

August 05, 20152015-08-05hahaschoolLeave a comment

［等待填坑］

//
//  SPOJ SORTBIT.cpp
//  playground
//
//  Created by Adam Chang on 2015/08/04.
//  Copyright © 2015年 Adam Chang. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>

using namespace std;

unsigned int cnt[33][33];//cnt[height][required num of 1]
void get_cnt(){
    cnt[0][0] = 1;
    cnt[1][0] = 1;
    cnt[1][1] = 1;
    for (int i = 2; i <= 32; i++) {
        cnt[i][0] = 1;
        for (int j = 1; j <= 32; j++) {
            cnt[i][j] = cnt[i-1][j] + cnt[i-1][j-1];
        }
    }
}

unsigned int count_to(unsigned int a, int k){
    unsigned int ret = 0;
    int hav = 0;
    for (int i = 31; i >= 0; i--) {
        if (a & (1U << (unsigned int)i)) {
            if (k >= hav) {
                ret += cnt[i][k - hav];
            }
            hav++;
        }
    }
    return ret;
}

unsigned int count_num(int lb, int rb, int k){
    unsigned int ret = 0;
    if (lb > rb) {
        swap(lb, rb);
    }
    unsigned int ulb = lb, urb = rb;
    if (lb * rb != 0) {
        if (lb > 0) {
            ret = count_to(urb+1,k) - count_to(ulb, k);
        }else {
            if (rb == -1) {
                ret = count_to(urb, k) - count_to(ulb, k);
                if (k == 32) {
                    ret++;
                }
            }else{
                ret = count_to(urb+1, k) - count_to(ulb, k);
            }
        }
    }else {
        if (lb == 0) {
            ret = count_to(urb+1, k);
        }else {
            ret = cnt[32][k] - count_to(ulb, k);
            if (k == 0) {
                ret++;
            }
        }
    }
    return ret;
}

int get_ans(int m, int n, long long k){
    if (m > n) {
        swap(m, n);
    }
    long long curcnt = 0;
    long long target = 0;
    int lasti = 0;
    for (int i = 0; i <= 32; i++) {
        lasti = i;
        curcnt += count_num(m, n, i);
        if (curcnt >= k) {
            target = count_num(m, n, i) - curcnt + k;
            break;
        }
    }
    int l = m, r = n, mid = l + (r - l)/2;
    while (l < r) {
        if (count_num(m, mid, lasti) < target) {
            l = mid + 1;
        }else {
            r = mid;
        }
        mid = l + (r - l)/2;
    }
    return mid;
}

int main(){
    get_cnt();
    int caseCnt = 0;
    cin >> caseCnt;
    while (caseCnt--) {
        int m = 0, n = 0, k = 0;
        cin >> m >> n >> k;
        cout << get_ans(m, n, k) << endl;
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

// SPOJ SORTBIT.cpp

// playground

// Created by Adam Chang on 2015/08/04.

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

using namespace std;

unsigned int cnt[33][33];//cnt[height][required num of 1]

void get_cnt(){

cnt[0][0] = 1;

cnt[1][0] = 1;

cnt[1][1] = 1;

for (int i = 2; i <= 32; i++) {

cnt[i][0] = 1;

for (int j = 1; j <= 32; j++) {

cnt[i][j] = cnt[i-1][j] + cnt[i-1][j-1];

}

unsigned int count_to(unsigned int a, int k){

unsigned int ret = 0;

int hav = 0;

for (int i = 31; i >= 0; i--) {

if (a & (1U << (unsigned int)i)) {

if (k >= hav) {

ret += cnt[i][k - hav];

}

hav++;

}

return ret;

}

unsigned int count_num(int lb, int rb, int k){

unsigned int ret = 0;

if (lb > rb) {

swap(lb, rb);

}

unsigned int ulb = lb, urb = rb;

if (lb * rb != 0) {

if (lb > 0) {

ret = count_to(urb+1,k) - count_to(ulb, k);

}else {

if (rb == -1) {

ret = count_to(urb, k) - count_to(ulb, k);

if (k == 32) {

ret++;

}

}else{

ret = count_to(urb+1, k) - count_to(ulb, k);

}

}else {

if (lb == 0) {

ret = count_to(urb+1, k);

}else {

ret = cnt[32][k] - count_to(ulb, k);

if (k == 0) {

ret++;

}

return ret;

}

int get_ans(int m, int n, long long k){

if (m > n) {

swap(m, n);

}

long long curcnt = 0;

long long target = 0;

int lasti = 0;

for (int i = 0; i <= 32; i++) {

lasti = i;

curcnt += count_num(m, n, i);

if (curcnt >= k) {

target = count_num(m, n, i) - curcnt + k;

break;

}

int l = m, r = n, mid = l + (r - l)/2;

while (l < r) {

if (count_num(m, mid, lasti) < target) {

l = mid + 1;

}else {

r = mid;

}

mid = l + (r - l)/2;

}

return mid;

}

int main(){

get_cnt();

int caseCnt = 0;

cin >> caseCnt;

while (caseCnt--) {

int m = 0, n = 0, k = 0;

cin >> m >> n >> k;

cout << get_ans(m, n, k) << endl;

}

return 0;

}

URAL 1057 Amount of Degrees

August 03, 20152015-08-03hahaschoolLeave a comment

［等待填坑中］

//
//  URAL 1057.cpp
//  playground
//
//  Created by Adam Chang on 2015/08/03.
//  Copyright © 2015年 Adam Chang. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>
#include <bitset>

using namespace std;

unsigned int x = 0, y = 0, k = 0, b = 0;

unsigned int dp[33][33];//dp[depth][request numbers of 1]
void get_dp(){
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    dp[1][0] = 1;
    dp[1][1] = 1;
    for (int i = 2; i <= 32; i++) {
        dp[i][0] = 1;
        for (int j = 1; j <= 32; j++) {
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
        }
    }
}

unsigned int get_ans(unsigned int a){
    unsigned int ret = 0;
    int hav = 0;
    for (int i = 31; i >= 0; i--) {
        if (a & (1 << i)) {
            if (k >= hav) {
                ret += dp[i][k-hav];
            }
            hav++;
        }
    }
    return ret;
}

bitset<32> b_to_bin(unsigned int n){
    vector<int> vec;
    while (n) {
        vec.push_back(n % b);
        n /= b;
    }
    bitset<32> bit;
    for (int i = 1; i <= vec.size(); i++) {
        if (vec[(int)vec.size() - i] == 1) {
            bit[(int)vec.size() - i] = 1;
        }else if(vec[(int)vec.size() - i] == 0){
            bit[(int)vec.size() - i] = 0;
        }else {
            for (int j = (int)vec.size() - i; j >= 0; j--) {
                bit[j] = 1;
            }
            break;
        }
    }
    return bit;
}

int main(){
    cin >> x >> y >> k >> b;
    get_dp();
    bitset<32> bitx(b_to_bin(x));
    bitset<32> bity(b_to_bin(y));
    cout << get_ans(bity.to_ulong()+1) - get_ans(bitx.to_ulong()) << endl;
    return 0;
}

// URAL 1057.cpp

// playground

// Created by Adam Chang on 2015/08/03.

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

#include <bitset>

using namespace std;

unsigned int x = 0, y = 0, k = 0, b = 0;

unsigned int dp[33][33];//dp[depth][request numbers of 1]

void get_dp(){

memset(dp, 0, sizeof(dp));

dp[0][0] = 1;

dp[1][0] = 1;

dp[1][1] = 1;

for (int i = 2; i <= 32; i++) {

dp[i][0] = 1;

for (int j = 1; j <= 32; j++) {

dp[i][j] = dp[i-1][j-1] + dp[i-1][j];

}

unsigned int get_ans(unsigned int a){

unsigned int ret = 0;

int hav = 0;

for (int i = 31; i >= 0; i--) {

if (a & (1 << i)) {

if (k >= hav) {

ret += dp[i][k-hav];

}

hav++;

}

return ret;

}

bitset<32> b_to_bin(unsigned int n){

vector<int> vec;

while (n) {

vec.push_back(n % b);

n /= b;

}

bitset<32> bit;

for (int i = 1; i <= vec.size(); i++) {

if (vec[(int)vec.size() - i] == 1) {

bit[(int)vec.size() - i] = 1;

}else if(vec[(int)vec.size() - i] == 0){

bit[(int)vec.size() - i] = 0;

}else {

for (int j = (int)vec.size() - i; j >= 0; j--) {

bit[j] = 1;

}

break;

}

return bit;

}

int main(){

cin >> x >> y >> k >> b;

get_dp();

bitset<32> bitx(b_to_bin(x));

bitset<32> bity(b_to_bin(y));

cout << get_ans(bity.to_ulong()+1) - get_ans(bitx.to_ulong()) << endl;

return 0;

}