[BZOJ 2733][HNOI2012]永无乡

我这题竟然很早就做了……

求k小显然可以用平衡树。但是这个题还需要快速的合并平衡树,那就需要启发式合并了。

继续阅读

[BZOJ 1483][HNOI2009]梦幻布丁

做了很久了吧,但现在才写题解……(斜眼

首先记录一个起始的颜色段数,然后每种颜色都要用链表顺序记下该颜色有哪些点。然后合并的时候合并两个链表——最优策略显然是启发式合并。

但是,很多时候并不是把小链表的扔到大的里面的情况,而是恰好反过来的情况,如何处理?

这种时候,我们可以交换两个颜色的“真实身份”。合并的时候,把每个点当成它的“真实身份”处理即可。

继续阅读

[BZOJ 1009][HNOI2008]GT考试

好劲啊这题……

首先先想DP的做法,我们用[tex]p[i][j][/tex]表示若字符串已匹配前缀[tex][1,i][/tex],有多少种方案使得追加上一个数后匹配[tex][1,j][/tex],这个用KMP可以很方便的求出(事实上暴力也可以)

然后再来看DP的做法,转移方程大致是这样的:

[tex]d[i][j]=\Sigma_{k=0}^{m-1}(d[i-1][k]\times p[k][j])[/tex]

但是n非常大,这么做注定要TLE。

不过看这个转移方程,是不是和矩阵乘法的定义很像?是的。

我们可以用一个[tex]1\times m[/tex]的矩阵[tex]D[/tex]来表示某一个阶段的DP值,我们可以把[tex]p[/tex]组织成一个[tex]m\times m[/tex]矩阵[tex]P[/tex]。然后我们可以发现:

[tex]D_i\times P=D_{i+1}[/tex]

由于矩阵乘法满足结合律,所以:

[tex]D_n=D_0\times P^n[/tex]

很明显可以快速幂搞出来。

代码:

/**************************************************************
    Problem: 1009
    User: danihao123
    Language: C++
    Result: Accepted
    Time:80 ms
    Memory:820 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
typedef ull Matrix[22][22];
ull MOD;
#define REP(i,n) for(i=0;i<(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
#define CP_ARR(from,to) memcpy(to,from,sizeof(from))
 
inline void MatrixMul(Matrix A,Matrix B,int m,int n,int p,Matrix& res){
    register int i,j,k;
    Matrix C;
    CL_ARR(C,0);
    REP(i,m){
        REP(j,p){
            REP(k,n){
                C[i][j]=(C[i][j]+(A[i][k]*B[k][j])%MOD)%MOD;
            }
        }
    }
    CP_ARR(C,res);
}
void MatrixPow(Matrix A,int m,ull p,Matrix& res){
    Matrix a,temp;
    register int i;
    CL_ARR(a,0);
    memcpy(a,A,sizeof(a));
    CL_ARR(temp,0);
    REP(i,m){
        temp[i][i]=1;
    }
    while(p){
        if(1&p){
            MatrixMul(temp,a,m,m,m,temp);
        }
        p>>=1;
        MatrixMul(a,a,m,m,m,a);
    }
    CP_ARR(temp,res);
}
 
char buf[25];
int f[25];
int main(){
    register int i,u,j;
    register ull ret=0;
    ull n;
    int m;
    Matrix ans,P;
    scanf("%llu%d%llu",&n,&m,&MOD);
    scanf("%s",buf+1);
    CL_ARR(ans,0);
    ans[0][0]=1;
    CL_ARR(P,0);
    P[0][0]=9;P[0][1]=1;
    // f[0]=f[1]=0;
    for(i=1;i<m;i++){
        u=f[i];
        while(u && buf[u+1]!=buf[i+1]){
            u=f[u];
        }
        if(buf[u+1]==buf[i+1]){
            f[i+1]=u+1;
        }else{
            f[i+1]=0;
        }
        for(j=0;j<10;j++){
            u=i;
            while(u && buf[u+1]!=j+'0'){
                u=f[u];
            }
            if(buf[u+1]==j+'0'){
                P[i][u+1]=(P[i][u+1]+1)%MOD;
            }else{
                P[i][0]=(P[i][0]+1)%MOD;
            }
        }
    }
    MatrixPow(P,m,n,P);
    MatrixMul(ans,P,1,m,m,ans);
    for(i=0;i<m;i++){
        ret=(ret+ans[0][i])%MOD;
    }
    printf("%llu\n",ret);
    return 0;
}

[BZOJ 1212]L语言

这个感觉本质上和那个Remember a Word很像吧……

不过这个只是求最长可行前缀,递推即可。

代码:

/**************************************************************
    Problem: 1212
    User: danihao123
    Language: C++
    Result: Accepted
    Time:660 ms
    Memory:45072 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn=1048581;
const int maxW=4005,maxL=105;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define DREP(i,n) for(i=(n)-1;i>=0;i--)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
 
vector<int> AnsList;
namespace Trie{
    const int maxnode=400005;
    const int sigma_siz=26;
    int Tree[maxnode][sigma_siz];
    int val[maxnode];
    int siz;
    inline int idx(char c){
        return c-'a';
    }
    inline void InitTrie(){
        siz=0;
        val[0]=0;
        CL_ARR(Tree[0],0);
    }
    void Insert(char *s,int v){
        register int u=0,n=strlen(s);
        register int i,c;
        REP(i,n){
            c=idx(s[i]);
            if(!Tree[u][c]){
                siz++;
                Tree[u][c]=siz;
                val[siz]=0;
                CL_ARR(Tree[siz],0);
            }
            u=Tree[u][c];
        }
        val[u]=v;
    }
    void Query(char *s,int len){
        register int i,c,u=0;
        AnsList.clear();
        REP(i,len){
            if(!s[i])
                break;
            c=idx(s[i]);
            if(!Tree[u][c])
                break;
            u=Tree[u][c];
            if(val[u])
                AnsList.push_back(val[u]);
        }
    }
};
 
char Text[maxn];
int len[maxW];
char buf[maxL];
bool d[maxn];
int main(){
    int n,m;
    int length;
    register int i,j,k;
    bool flag;
    Trie::InitTrie();
    scanf("%d%d",&n,&m);
    REP_B(i,n){
        scanf("%s",buf);
        len[i]=strlen(buf);
        Trie::Insert(buf,i);
    }
    REP_B(i,m){
        scanf("%s",Text);
        length=strlen(Text);
        CL_ARR(d,0);
        d[0]=true;
        for(j=0;j<=length;j++){
            if(d[j]){
                Trie::Query(Text+j,length-j);
                REP(k,AnsList.size()){
                    d[j+len[AnsList[k]]]=true;
                }
            }
        }
        flag=false;
        for(j=length;j>=0;j--){
            if(d[j]){
                flag=true;
                printf("%d\n",j);
                break;
            }
        }
        if(!flag)
            puts("0");
    }
    return 0;
}

[BZOJ 1217]消防局的设立

很明显可以看出消防局距离为5的话最划算……然后贪心就行了,顺便注意下根节点处理

代码:

/**************************************************************
    Problem: 1217
    User: danihao123
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:844 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1010;
#define GRAPH_REP(i,u) for(i=first[u];i;i=next[i])
int first[maxn];
int next[maxn*2],to[maxn*2];
int graph_cnt=0;
inline void AddEdge(int u,int v){
    graph_cnt++;
    next[graph_cnt]=first[u];
    first[u]=graph_cnt;
    to[graph_cnt]=v;
}
 
int ans=0;
int d[maxn];
void dfs(int x,int fa=-1){
    int maxq=-maxn,minq=maxn;
    int i;
    GRAPH_REP(i,x)
        if(to[i]!=fa){
            dfs(to[i],x);
            maxq=max(maxq,d[to[i]]);
            minq=min(minq,d[to[i]]);
        }
    if(minq+maxq<=3)
        d[x]=minq+1;
    else
        d[x]=maxq+1;
    if(minq==maxn)
        d[x]=3;
    if(d[x]==5){
        ans++;
        d[x]=0;
    }else{
        if(fa==-1 && d[x]>2)
            ans++;
    }
}
 
int main(){
    int n,v;
    register int i;
    scanf("%d",&n);
    for(i=1;i<=(n-1);i++){
        scanf("%d",&v);
        AddEdge(i+1,v);
        AddEdge(v,i+1);
    }
    dfs(1);
    printf("%d\n",ans);
    return 0;
}

[BZOJ 1196]公路修建问题

挺简单的二分答案题……然而到现在才A

思路很明显,直接二分最终答案。那么判定如何做呢?

假设判定谓词为[tex]C(x)[/tex],那么我们首先考虑选白边。贪心加入边权小于[tex]x[/tex]的边(当然是否有必要就要用并查集判定了。并且这样就算加的超过了[tex]k[/tex]条也不会对答案造成影响)。然后白边加的不够[tex]k[/tex]谓词就是假了。

然后再考虑黑边,接下来的事情就很简单了。

代码:

/**************************************************************
    Problem: 1196
    User: danihao123
    Language: C++
    Result: Accepted
    Time:672 ms
    Memory:1212 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define REP(i,n) for(i=0;i<(n);i++)
#define RAP(i,n) for(i=1;i<=(n);i++)
const int maxn=10001,maxm=20001;
 
struct Edge{
    int u,v,d1,d2;
};
bool cmp1(const Edge& x,const Edge& y){
    return x.d1<y.d1;
}
bool cmp2(const Edge& x,const Edge& y){
    return x.d2<y.d2;
}
 
int n;
int p[maxn],rank[maxn];
int find_set(int x){
    if(p[x]==x)
        return x;
    else
        return p[x]=find_set(p[x]);
}
inline void link_set(int x,int y){
    if(rank[x]>rank[y]){
        p[y]=x;
    }else{
        p[x]=y;
        if(rank[x]==rank[y])
            rank[y]++;
    }
}
inline void union_set(int x,int y){
    link_set(find_set(x),find_set(y));
}
inline bool is_same(int x,int y){
    return find_set(x)==find_set(y);
}
inline void init_set(){
    register int i;
    for(i=1;i<=n;i++)
        p[i]=i;
    memset(rank,0,sizeof(rank));
}
 
int k,m;
Edge E[maxm];
inline bool check(int x){
    register int i,first_cnt=0,cnt=0;
    init_set();
    sort(E,E+m,cmp1);
    REP(i,m){
        if(E[i].d1>x){
            break;
        }else{
            if(!is_same(E[i].u,E[i].v)){
                first_cnt++;
                cnt++;
                union_set(E[i].u,E[i].v);
            }
        }
        if(cnt==n-1){
            return true;
        }
    }
    if(first_cnt<k)
        return false;
    sort(E,E+m,cmp2);
    REP(i,m){
        if(E[i].d2>x){
            break;
        }else{
            if(!is_same(E[i].u,E[i].v)){
                cnt++;
                union_set(E[i].u,E[i].v);
            }
        }
        if(cnt==n-1)
            return true;
    }
    return false;
}
int main(){
    register int i,L=1,M,R=0;
    scanf("%d%d%d",&n,&k,&m);
    m--;
    REP(i,m){
        scanf("%d%d%d%d",&E[i].u,&E[i].v,&E[i].d1,&E[i].d2);
        R=max(R,E[i].d1);
    }
    R++;
    while(L<R){
        M=L+(R-L)/2;
        if(check(M))
            R=M;
        else
            L=M+1;
    }
    printf("%d\n",L);
    return 0;
}

 

[BZOJ 1192]鬼谷子的钱袋

这题真是interesting极了!

建议先在纸上实践一下,然后你会发现问题的解就是n的二进制长度!

让我偷着乐一会

[要证明?我这先挖个坑]

代码:

继续阅读