LA 4670

Type:AC自动机

题意

给你一堆子串和一个主串

问你在主串中出现次数最多的子串有哪些,最后结果按字典序排列

Code

#include<bits/stdc++.h>
using namespace std;

const int maxn=11000;
const int maxm=152;
const int maxt=1e6+6;

int T,N,tot_len;
char str[maxm][80],tot[maxt];

struct AC_AutoMaton{
    static const int sigma_size=26;

    int ch[maxn][sigma_size];

    int f[maxn];

    int cnt[maxn],val[maxn];
    bool vis[maxn][sigma_size];

    int siz,root,max_time;

    vector<string> ans;

    int newNode(){
        for(int i=0;i<sigma_size;++i){
            ch[siz][i]=0;
        }
        for(int i=0;i<sigma_size;++i){
            vis[siz][i]=false;
        }
        f[siz]=val[siz]=0;
        return siz++;
    }

    void init(){
        ans.clear();
        for(int i=0;i<maxn;++i) val[i]=cnt[i]=0;
        siz=0;root=0;max_time=0;
        newNode();
    }

    int ord(char c){
        if(isupper(c))
            c=tolower(c);
        return (int)(c-'a');
    }

    void insert(char *s,int v){
        int u=root,n=strlen(s);
        for(int i=0;i<n;++i){
            int c=ord(s[i]);
            if(!ch[u][c]) ch[u][c]=newNode();
            u=ch[u][c];
       }
       val[u]=v;
    }

    void getFail(){
        queue<int> Q;
        Q.push(root);
        while(!Q.empty()){
            int k=Q.front();
            Q.pop();
            for(int c=0;c<sigma_size;++c){
                if(ch[k][c]){
                    f[ch[k][c]]=k?ch[f[k]][c]:0;
                    Q.push(ch[k][c]);
                }
                else ch[k][c]=ch[f[k]][c];
            }
        }
    }

    void Find(char *s){
        int u=0,n=tot_len;
        for(int i=0;i<n;++i){
            int c=ord(s[i]);
            ///下面这句加不加都一样
            //while(u && !ch[u][c]) u=f[u];
            u=ch[u][c];

            int p=u;
            //cout<<i<<"  "<<u<<": "<<c<<endl;
            ///while是用来判断子串的.这道题不需要加
            while(p && val[p]){
                if(!vis[p][c]){
                    cnt[val[p]]++;
                    max_time=max(cnt[val[p]],max_time);
                    p=f[p];
                    vis[p][c]=true;
                }
            }
        }
    }

    void print(){
        printf("%d\n",max_time);
        for(int i=1;i<=N;++i){
            if(cnt[i]==max_time){
                ans.push_back(str[i]);
            }
        }
        sort(ans.begin(),ans.end());
        for(int i=0;i<ans.size();++i){
            cout<<ans[i]<<endl;
        }
    }
}aho;

int main(){
    while(~scanf("%d",&N) && N){
        aho.init();
        for(int i=1;i<=N;++i){
            scanf("%s",str[i]);
            aho.insert(str[i],i);
        }
        getchar();
        aho.getFail();
        tot_len=0;
        //scanf("%[^\n]",str);
        gets(tot);
        tot_len=strlen(tot);
        //cout<<tot_len<<endl;
        aho.Find(tot);
        aho.print();
    }
    return 0;
}

POJ 1961

Link

https://vjudge.net/problem/UVALive-3026

Type: KMP-Next数组

题意

给你一个字符串,输出这个字符串中所有的周期子串最后一个字符的下标和周期长度

题解

前置

关于Next数组

(1) Next数组记录的是如果当前字符不匹配,跳到哪个字符进行再次匹配.

(2) j=Next[k]表示第 j 个字符和第 k 个字符一样.

(3) j=Next[k]表示前 j 个字符和后 j 个字符一样

即 1~j-1 和 k-j+1~k 这两个子串相等

正文

即我们求出该字符串的Next数组后我们可以判断当前 (i-Next[i]) 是否能被 i 整除.

即 i%(i-Next[i]) 是否等于0.

i-Next[i]为该子串的长度,如果可以整除则证明该子串为循环节,循环节长度为 i-Next[i] ,循环次数为 i/(i-Next[i]).

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000+10;
char ts[maxn];
int n,kase=1;
int Next[maxn];
void getNext(){
    int j=0,k=-1;
    Next[0]=-1;
    while(j<n){
        if(k==-1 || ts[j]==ts[k]) Next[++j]=++k;
        else k=Next[k];
    }
}
void print(){
    for(int i=1;i<=n;++i){
        cout<<Next[i]<<" ";
    }
    cout<<endl;
}

int main(){
    while(~scanf("%d",&n)){
        if(!n)break;
        scanf("%s",ts);
        getNext();
        //print();
        printf("Test case #%d\n",kase++);
        for(int i=2;i<=n;++i){
            if(Next[i]<=0) continue;
            if(i%(i-Next[i])==0){
                printf("%d %d\n",i,i/(i-Next[i]));
            }
        }
        printf("\n");
        getchar();
    }
    return 0;
}

LA 3882

【Link】

And Then There Was One

【题解】

假设问题是从n个人编号分别为0…n-1,取第k个,

则第k个人编号为k-1的淘汰,剩下的编号为 0,1,2,3…k-2,k,k+1,k+2…

此时因为从刚刚淘汰那个人的下一个开始数起,因此重新编号

把k号设置为0,则

k 0

k+1 1

0 n-k

1 n-k+1

假设已经求得了n-1个人情况下的最终胜利者保存在f[n-1]中,则毫无疑问,该胜利者还原到原来的真正编号即为 (f[n-1]+k)%n (因为第二轮重新编号的时候,相当于把每个人的编号都减了k,因此重新+k即可恢复到原来编号)。由此,我们可以想象,当最终只剩下一个人的时候,该人即为胜利者,此时重新编号,因为只有一个人,所以此时f[1]=0

这样f[2]=(f[1]+k)%2,这样就可以求出最终胜利者在2个人的时候的情况下的编号,由递推公式f[n]=(f[n-1]+k)%n,可递推到最初编号序列中该胜利者的编号。

因此用这个方法,只需一遍On的扫描,即可求出最终答案

不过该题要求编号从1开始,只要把f[n]+1即可,同时,该题指定了第一个要删除的人必须为编号为m的人,其实也不难,求出f[n]之后,把原本编号为0的位置移到跟m只相距k的位置即可实现第一次删除的编号为m。所以最终 ans=(f[n]+1+m-k);

当然因为m-k可能为负数,导致整个ans为负,这样其实最后+n即可解决。

【Code】

LA 3882.cpp

#include<bits/stdc++.h>
using namespace std;
const int maxn=10000+10;
int f[maxn];
int main(){
    int n,k,m;
    while(scanf("%d%d%d",&n,&k,&m)==3 && n){
        ///最后一次变换只有一个点,所以最终点设为0
        ///每次去掉一个点以后重新编号,所以%i
        ///从底向上的方法
        f[1]=0;
        for(int i=2;i<=n;++i)f[i]=(f[i-1]+k)%i;
        ///因为是从0编号,而题目要求从1编号,所以+1
        ///因为从0开始,而题目要求从m开始删除第k个
        ///所以第一次删除的下标应该是f[n]-k=第一次的起始下标
        ///0-k+m+1=真正的起始坐标,因为第一次需要将m设为0,从m开始重新编号
        int ans=(m-k+1+f[n])%n;
        ///因为m-k+1可能小于0,所以m-k+1+f[n]也可能小于0
        if(ans<=0) ans+=n;
        printf("%d\n",ans);
    }
    return 0;
}

 

LA 3902

【Link】

Network

【题解】

可将网络看成一棵树,将初始的VOD看做该树的根.距离该根k的叶节点可以忽略不计.其余的叶子结点记录在nodes数组表内,nodes[i]代表深度为i的叶子结点表.covered代表该叶子结点是第i个叶子结点是否可以使用VOD.gr代表邻接表.

最优选择放置服务器的方法是选择距离主机最远(k)的那个服务器上安装VOD即可.

【Code】

LA 3902.cpp

#include<bits/stdc++.h>
using namespace std;

const int maxn=1000+10;
vector<int> gr[maxn],nodes[maxn];
int n,s,k,fa[maxn];
bool covered[maxn];

///无根树转有根树,计算fa数组,根据深度把--叶子节点--插入nodes表中
///u当前节点下标,f,当前节点父节点下标,d深度.
void dfs(int u,int f,int d){
    fa[u]=f;
    int nc=gr[u].size();
    ///距离根节点k距离以内的叶子结点不用记录
    if(nc==1 && d>k) nodes[d].push_back(u);
    for(int i=0;i<nc;++i){
        int v=gr[u][i];
        if(v!=f)dfs(v,u,d+1);
    }
}

void dfs2(int u,int f,int d){
    covered[u]=true;
    int nc=gr[u].size();
    for(int i=0;i<nc;++i){
        int v=gr[u][i];
        if(v!=f&&d<k)dfs2(v,u,d+1);///只覆盖到新服务器不超过k的结点 ///v!=f => 如果从f访问到u,那么就不能再从u回访f.深搜嘛.一路莽到底.
    }
}

int solve(){
    int ans=0;
    memset(covered,0,sizeof(covered));
    for(int d=n-1;d>k;--d){
        for(int i=0;i<nodes[d].size();++i){
            int u=nodes[d][i];
            if(covered[u])continue;///不考虑已经覆盖的点

            int v=u;
            for(int j=0;j<k;++j)v=fa[v];///找到相邻k级祖先,不可能有-1,因为之前已经把离根k的节点忽略了
            dfs2(v,-1,0);///在结点v设置服务器,然后通过对该服务器深搜
                         ///找到所有的叶子结点
            ans++;
        }
    }
    return ans;
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d",&n,&s,&k);///节点数,初始VOD服务器的编号和k
        for(int i=1;i<=n;++i){gr[i].clear();nodes[i].clear();}
        for(int i=0;i<n-1;++i){
            int a,b;
            scanf("%d%d",&a,&b);
            gr[a].push_back(b);
            gr[b].push_back(a);
        }
        dfs(s,-1,0);
        printf("%d\n",solve());
    }
    return 0;
}

LA 3401

【Link】

Colored Cubes,Tokyo 2005,LA 3401

【题解】

思路题,模拟题

先预处理处所有旋转可能.然后通过固定第一个立方体,用于处理出的表来旋转剩下的n-1个立方体.dfs解决,然后对每种旋转情况进行check.更新ans.

【预处理代码及处理结果】

LA 3401旋转情况.cpp

#include<bits/stdc++.h>
using namespace std;

int Dleft[]={4,0,2,3,5,1};
int up[]={2,1,5,0,4,3};

//旋转
void rot(int* T,int* p){
    int q[6];
    memcpy(q,p,sizeof(q));
    for(int i=0;i<6;++i){
        p[i]=T[q[i]];
    }
}

void enumerate_permutations(){
    int p0[6]={0,1,2,3,4,5};
    printf("int dice24[24][6] = {\n");
    for(int i=0;i<6;++i){
        int p[6];
        memcpy(p,p0,sizeof(p0));
        if(i==0) rot(up,p);
        if(i==1) {rot(Dleft,p); rot(up,p);}
        if(i==3) {rot(up,p);rot(up,p);}
        if(i==4) {rot(Dleft,p);rot(Dleft,p);rot(Dleft,p);rot(up,p);}
        if(i==5) {rot(Dleft,p);rot(Dleft,p);rot(up,p);}
        for(int i=0;i<4;++i){
            printf("{%d,%d,%d,%d,%d,%d},\n",p[0],p[1],p[2],p[3],p[4],p[5]);
            rot(Dleft,p);
        }
    }
    printf("};\n");
}

int main(){
    freopen("3401.txt","w",stdout);
    enumerate_permutations();
    return 0;
}

处理结果:

int dice24[24][6] = {
{2,1,5,0,4,3},
{2,0,1,4,5,3},
{2,4,0,5,1,3},
{2,5,4,1,0,3},
{4,2,5,0,3,1},
{5,2,1,4,3,0},
{1,2,0,5,3,4},
{0,2,4,1,3,5},
{0,1,2,3,4,5},
{4,0,2,3,5,1},
{5,4,2,3,1,0},
{1,5,2,3,0,4},
{5,1,3,2,4,0},
{1,0,3,2,5,4},
{0,4,3,2,1,5},
{4,5,3,2,0,1},
{1,3,5,0,2,4},
{0,3,1,4,2,5},
{4,3,0,5,2,1},
{5,3,4,1,2,0},
{3,4,5,0,1,2},
{3,5,1,4,0,2},
{3,1,0,5,4,2},
{3,0,4,1,5,2},
};

【题解代码】

LA 3401.cpp

#include<bits/stdc++.h>
using namespace std;
///旋转情况表
int dice24[24][6] = {
{2,1,5,0,4,3},
{2,0,1,4,5,3},
{2,4,0,5,1,3},
{2,5,4,1,0,3},
{4,2,5,0,3,1},
{5,2,1,4,3,0},
{1,2,0,5,3,4},
{0,2,4,1,3,5},
{0,1,2,3,4,5},
{4,0,2,3,5,1},
{5,4,2,3,1,0},
{1,5,2,3,0,4},
{5,1,3,2,4,0},
{1,0,3,2,5,4},
{0,4,3,2,1,5},
{4,5,3,2,0,1},
{1,3,5,0,2,4},
{0,3,1,4,2,5},
{4,3,0,5,2,1},
{5,3,4,1,2,0},
{3,4,5,0,1,2},
{3,5,1,4,0,2},
{3,1,0,5,4,2},
{3,0,4,1,5,2},
};


const int maxn=4;//最大立方体数
///
///立方体数,第i个立方体原始涂色,dfs后得到的答案
///
int n,dice[maxn][6],ans;

///
///借用vector判断改颜色是否已存在,并借第一个立方体的
///涂颜色的顺序(下标)来决定每个颜色的下标是多少.
///进而确定其他立方体的颜色下标
///
vector names;
int ID(const char* name){
    string s(name);
    int n=names.size();
    for(int i=0;i<n;++i)
        if(names[i]==s) return i;//已存在
    names.push_back(s);
    return n;//不存在,加入后返回
}

///每个立方体的旋转方式和旋转后各个面的颜色
int r[maxn],color[maxn][6];

///每次dfs到n个立方体后,判断所需旋转次数
///然后更新ans
void check(){
    ///对于每个立方体按r[i]旋转
    for(int i=0;i<n;++i)
        for(int j=0;j<6;++j) color[i][dice24[r[i]][j]]=dice[i][j];

    int tot=0;///需要重新涂色的面数
    for(int j=0;j<6;++j){///考虑每个面
        int cnt[maxn*6];///每个面颜色出现的次数
        memset(cnt,0,sizeof(cnt));
        int maxface=0;
        ///记录每个面最多的颜色
        for(int i=0;i<n;++i)
            maxface=max(maxface,++cnt[color[i][j]]);
        tot+=n-maxface;///第j面的最少重涂次数
    }
    ans=min(tot,ans);
}

///把每个面都旋转,旋转不计次数,所以直接判断是否旋转后每个面完全相等即可
void dfs(int d){
    if(d==n) check();
    else{
        for(int i=0;i<24;++i){
            r[d]=i;
            dfs(d+1);
        }
    }
}

int main(){
    while(scanf("%d",&n)==1&&n){
        names.clear();
        for(int i=0;i<n;++i){
            for(int j=0;j<6;++j){
                char name[30];
                scanf("%s",name);
                dice[i][j]=ID(name);
            }
        }
        ans=n*6;///上界,所有面都重涂的结果
        r[0]=0;///第一个立方体不旋转
        dfs(1);
        printf("%d\n",ans);
    }
    return 0;
}

LA 4329

【Link】

https://vjudge.net/problem/UVALive-4329

thought】

考虑对于每第i个人做裁判,1 ~ (i-1)中有sm[i]个比A[i]能力小的,(i+1) ~ N 中有sl[i]个比A[i]能力小的.

那么1 ~ (i-1)中有  (i-sm[i]-1)  个比A[i]能力大的,(i+1) ~ N 中有  (N-i-sl[i])  个比A[i]能力大的.

根据乘法原理 对于第i个人做裁判有 sl[i](i-sm[i]-1)+sm[i](N-i-sl[i]) 中比赛可能,因为每个人做裁判,所以最后结果为每个人做裁判的情况和.

考虑 T=119998+219997+319996+…+199981 爆int,故用long long 存.

【Type】

树状数组,lowbit()

【Code】

LA 4329.cpp

【溢出int测试】

LA 4329.cpp

 

LA 3029

【类型】

扫描线,悬线法

【题解】

蓝书P50

扫描方程的解释

我对代码的理解放在代码里了.

如果为满:left[i][j]=0,right[i][j]=n,up[i][j]=0,这里是为了下一行的比较做准备。可以模拟试一试。

【Code】

#include<algorithm>
#include<cstdio>
using namespace std;
const int maxn=1000;
int mat[maxn][maxn],up[maxn][maxn],left[maxn][maxn],right[maxn][maxn];
int readchar(){
    int a=getchar();
    while(a!=’F’ && a!=’R’) a=getchar();
    return a;
}
int main(){
    int T;
    scanf(“%d”,&T);
    while(T–){
        int m,n;
        scanf(“%d%d”,&m,&n);
        for(int i=0;i<m;++i)
            for(int j=0;j<n;++j){
                int ch=getchar();
                while(ch!=’F’ && ch!=’R’) ch=getchar();
                mat[i][j]=ch==’F’?0:1;
            }

        int ans=0;
        for(int i=0;i<m;++i){//从上到下逐行处理
            int lo=-1,ro=n;
            for(int j=0;j<n;++j)//从左向右处理
                if(mat[i][j]==1){left[i][j]=up[i][j]=0;lo=j;}
                else{
                    up[i][j]=i==0?1:up[i-1][j]+1;
                    //lo存的是左边界的下标,而不是到左边将诶有多少空地
                    //这里,每次遇到障碍(1)时,lo就等于j(重新开始计算左边界)
                    //然后,left[i][j]存的是当前矩阵的右边界
                    //这里是lo+1,而不是lo++,所以lo的值在碰到障碍前一直不变
                    //因为受到上一行的影响,所以需要在上一行和本行中选取一个最大
                    //下标的左边界.
                    left[i][j]=i==0?lo+1:max(left[i-1][j],lo+1);
                }
            for(int j=n-1;j>=0;–j)//从右往左扫描,维护right并更新答案
                if(mat[i][j]==1){right[i][j]=n;ro=j;}
                //为啥等于n捏???
                //为了使其下一行若是空格,作比较的时候,会发现上一行的下标一定是最大的
                //从而不影响下一行右边界的计算
                else{
                    right[i][j]=i==0?ro-1:min(right[i-1][j],ro-1);
                    ans=max(ans,up[i][j]*(right[i][j]-left[i][j]+1));
                }
        }
        printf(“%d\n”,ans*3);
    }
    return 0;
}

LA 3905

【类型】

区间扫描,  抽象成事件来做的区间扫描

【题解】

蓝书P45

另一个更详细的blog

代码中难懂的部分都已经注释了.

【Code】

#include<bits/stdc++.h>
using namespace std;

//0<x+a*t<w
//0<x+a*t<w,0<y+b*t<h,  t>0
//起始坐标:(x,y) 速度:(a,b)
//x横坐标运动范围(0-w) y纵坐标运动范围(0-h)
//题目给的公式 在时刻t坐标:p+tv=(x,y)+(t*a,t*b)
//然后根据这个范围求出出现在镜框的范围内的时间区间,开区间
//因为出现在镜框上不算进入射程.
void update(int x,int a,int w,double &L,double &R){
    if(a==0){
        if(x<=0 || x>=w) R=L-1;//无解,无法出现在镜框范围内
    }else if(a>0){
        L=max(L,-(double)x/a);
        R=min(R,(double)(w-x)/a);
    }else{
        L=max(L,(double)(w-x)/a);
        R=min(R,-(double)x/a);
    }
}

const int maxn=100000+10;
struct Event{
    double x;
    int type;//状态,0为右端点,1为左端点
    bool operator<(const Event &a)const{
        return x<a.x || (x==a.x && type>a.type);//先处理右端点
    }
}events[maxn*2];

int main(){
    int T;
    scanf(“%d”,&T);
    while(T–){
        int w,h,n,e=0;
        scanf(“%d%d%d”,&w,&h,&n);
        for(int i=0;i<n;++i){
            int x,y,a,b;
            scanf(“%d%d%d%d”,&x,&y,&a,&b);
            //0<x+a*t<w,0<y+b*t<h,  t>0
            double L=0,R=1e9;//先开一个无穷大的区间
            update(x,a,w,L,R);
            update(y,b,h,L,R);
            if(R>L){//只把有效可进入镜框的点加入区间
                events[e++]=(Event){L,0};
                events[e++]=(Event){R,1};
            }
        }
        //排序区间,可以画图看下.
        sort(events,events+e);
        int cnt=0,ans=0;
        for(int i=0;i<e;++i){
            if(events[i].type==0)
                cnt++,ans=max(ans,cnt);
            else cnt–;
        }
        printf(“%d\n”,ans);
    }
    return 0;
}

LA 3708

【题解】

蓝书P8

题意是原本n个墓碑均匀分布在一个周长为10000的圆周上,现在加入m个,如果要使得n+m个墓碑都均匀分布的话,那么原来的墓碑最少的移动总距离是多少。

因为加入m个之后m+n个墓碑的位置是固定的,要是移动距离最少必定会有一个墓碑不动,将圆周分成m+n段,分别标上0,1,2,3,4。。然后需要移动的墓碑坐标就是数轴上面的非整数点,两边的值靠近哪个就选哪个,之后再等比例扩大即可。

放大倍数:10000/(M+N)

原先N的坐标在放入M后的位置:
//设距离L
//i(10000/N)=L
//L/(10000/(M+N))=pos
//pos=i
(10000/N)/(10000/(M+N))
//pos=i*(M+N)/N

【Code】

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
int N,M;
int main(){
    while(scanf(“%d%d”,&N,&M)!=EOF) {
        double ans=0.0;
        for(int i=1;i<N;++i){
            double pos=(double)i/N*(N+M);
            //原先N的坐标在原来的位置是哪里
            //设距离L
            //i*(10000/N)=L
            //L/(10000/(M+N))=pos
            //pos=i*(10000/N)/(10000/(M+N))
            //pos=i*(M+N)/N
            ans+=fabs(pos-floor(pos+0.5))/(N+M);
            //floor()向下取整,这里等价于找两边距离最近
            //的那个点.
        }
        printf(“%.4lf\n”,ans*10000);  
    }
    return 0;
}

与上面题解同理(没那么奇葩的写法的Code)

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int main() {
    int n,m;
    while(~scanf("%d%d",&n,&m)) {
        double ans = 0;
        for(int i = 1;i < n;i++) {
            double pos = (double)i * (m + n) / n;
            ans += min(pos - (int)pos,(int)(pos + 1) - pos);
                        //取离两边距离最近的那个点
        }
        printf("%.4lf\n",ans * 10000 / (m + n));
    }
    return 0;
}