danihao123

搜索

音乐播放器

RSS

RSS Link

计数器

29170

[BZOJ 1511]Periods of Words

2016年9月15日 17:59 | Comments(0) | Category:题解 | Tags:

很妙的一道题啊。

这个题可以先求一遍KMP的失配函数,然后对于每个失配函数沿着失配边往前一直走(不能走到0)。然后对于每个前缀[tex]i[/tex],答案就是[tex]i-f[i][/tex](要求[tex]f[i][/tex]不为0,反之无解)。

为什么这样可以呢?

首先建议大家看一下Matrix67关于KMP的解释。对于一个前缀,如果整个弄上去肯定不行。所以说需要前面和后面重叠一个字串,这个子串是不考虑的。当然,我们希望在这个被删除的子串最短辣。

代码:

/**************************************************************
    Problem: 1511
    User: danihao123
    Language: C++
    Result: Accepted
    Time:148 ms
    Memory:5704 kb
****************************************************************/
 
#include <cstdio>
const int maxn=1000005;
 
char buf[maxn];
int f[maxn];
int main(){
    register int i,j;
    register long long ans=0;
    int n;
    scanf("%d%s",&n,buf);
    f[0]=f[1]=0;
    for(i=1;i<n;i++){
        j=f[i];
        while(j && buf[i]!=buf[j])
            j=f[j];
        f[i+1]=(buf[i]==buf[j]?j+1:0);
    }
    for(i=2;i<=n;i++){
        if(f[i]){
            while(f[f[i]]){
                f[i]=f[f[i]];
            }
        }
    }
    for(i=1;i<=n;i++){
        if(f[i]){
            ans+=i-f[i];
        }
    }
    printf("%lld\n",ans);
    return 0;
}

[BZOJ 2081]Beads

2016年9月12日 22:09 | Comments(0) | Category:题解 | Tags:

Hash第一题……

这个题直接枚举串长Hash判断即可。不过,注意读题。

感觉Hash挺简单的。还有就是我用了wyy的生日做Hash种子辣!

代码:

/**************************************************************
    Problem: 2081
    User: danihao123
    Language: C++
    Result: Accepted
    Time:5636 ms
    Memory:10904 kb
****************************************************************/
 
#include <cstdio>
#include <set>
#include <vector>
using namespace std;
typedef unsigned long long ull;
const int maxn=200005;
const ull x=200261;
ull s[maxn];
ull sufHash[maxn],preHash[maxn],x_pow[maxn];
int n;
inline void InitHash(){
    register int i;
    for(i=n;i>=1;i--){
        sufHash[i]=s[i]+sufHash[i+1]*x;
    }
    for(i=1;i<=n;i++){
        preHash[i]=s[i]+preHash[i-1]*x;
    }
    x_pow[0]=1;
    for(i=1;i<=n;i++){
        x_pow[i]=x*x_pow[i-1];
    }
}
inline ull Hash(int i,int L){
    return sufHash[i]-x_pow[L]*sufHash[i+L];
}
inline ull FilpHash(int i,int L){
    return preHash[i+L-1]-x_pow[L]*preHash[i-1];
}
 
set<ull> S;
vector<int> AnsList;
int tot=0;
inline void Check(int k){
    register int i,ans=0;
    register ull h;
    S.clear();
    for(i=1;(i+k-1)<=n;i+=k){
        h=Hash(i,k)*FilpHash(i,k);
        if(!S.count(h)){
            S.insert(h);
            ans++;
        }
    }
    if(ans>tot){
        tot=ans;
        AnsList.clear();
        AnsList.push_back(k);
    }else{
        if(ans==tot)
            AnsList.push_back(k);
    }
}
 
int main(){
    register int i,ans=0,maxv=0,cnt,temp;
    bool flag;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%llu",&s[i]);
    InitHash();
    for(i=1;i<=n;i++){
        Check(i);
    }
    printf("%d %d\n",tot,AnsList.size());
    flag=false;
    for(i=0;i<AnsList.size();i++){
        if(flag)
            putchar(' ');
        flag=true;
        printf("%d",AnsList[i]);
    }
    putchar('\n');
    return 0;
}

[BZOJ 1520]Szk-Schools

2016年9月04日 15:53 | Comments(0) | Category:题解 | Tags:

这个是二分图最小权完美匹配啦……不过我还是写的费用流。

不过注意一定要判断是否有完美匹配。

代码:

/**************************************************************
    Problem: 1520
    User: danihao123
    Language: C++
    Result: Accepted
    Time:2016 ms
    Memory:5004 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=410;
namespace MCMF{
    struct Edge{
        int u,v,cap,flow,cost;
    };
    vector<Edge> edges;
    vector<int> G[maxn];
    int m;
    inline void AddEdge(int u,int v,int cap,int cost){
        edges.push_back((Edge){u,v,cap,0,cost});
        edges.push_back((Edge){v,u,0,0,-cost});
        m=edges.size();
        G[u].push_back(m-2);
        G[v].push_back(m-1);
    }
    inline void ClearGraph(){
        register int i;
        edges.clear();
        for(i=0;i<maxn;i++)
            G[i].clear();
    }
    int a[maxn];
    bool inQueue[maxn];
    int d[maxn],p[maxn];
    bool BellmanFord(int s,int t,int& flow,long long& cost){
        register int i,u;
        queue<int> Q;
        memset(d,0x7f,sizeof(d));
        memset(inQueue,0,sizeof(inQueue));
        d[s]=0;
        inQueue[s]=true;
        p[s]=0;
        a[s]=0x7f7f7f7f;
        Q.push(s);
        while(!Q.empty()){
            u=Q.front();
            Q.pop();
            inQueue[u]=false;
            for(i=0;i<G[u].size();i++){
                Edge& e=edges[G[u][i]];
                if(e.cap>e.flow && d[e.v]>d[u]+e.cost){
                    d[e.v]=d[u]+e.cost;
                    p[e.v]=G[u][i];
                    a[e.v]=min(a[u],e.cap-e.flow);
                    if(!inQueue[e.v]){
                        Q.push(e.v);
                        inQueue[e.v]=true;
                    }
                }
            }
        }
        if(d[t]==0x7f7f7f7f)
            return false;
        flow+=a[t];
        cost+=((long long)d[t])*((long long)a[t]);
        for(u=t;u!=s;u=edges[p[u]].u){
            edges[p[u]].flow+=a[t];
            edges[p[u]^1].flow-=a[t];
        }
        return true;
    }
    long long MincostMaxflow(int s,int t,int& flow){
        register long long ans=0;
        while(BellmanFord(s,t,flow,ans));
        return ans;
    }
};
int main(){
    int n,m,a,b,k;
    register int i,j,cost,flow=0;
    register long long ans;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d%d%d%d",&m,&a,&b,&k);
        for(j=a;j<=b;j++){
            cost=k*abs(j-m);
            MCMF::AddEdge(i,j+n,1,cost);
        }
    }
    for(i=1;i<=n;i++)
        MCMF::AddEdge(0,i,1,0);
    for(i=n+1;i<=2*n;i++)
        MCMF::AddEdge(i,2*n+1,1,0);
    ans=MCMF::MincostMaxflow(0,2*n+1,flow);
    if(flow<n)
        puts("NIE");
    else
        printf("%lld\n",ans);
    return 0;
}

[BZOJ 3831]Little Bird

2016年8月12日 20:23 | Comments(0) | Category:题解 | Tags:

单调队列水体……然而我这蒟蒻仍然WA一墙

这个题本质是一个动态规划,然后我们发现取区间递推最小值这个任务可以交给单调队列君来做~不过优先级似乎是一个问题……

优先级直接按照递推值来搞即可,递推值一样的话才按照高度比。因为就算递推值比较小但高度会带来额外影响,也不过是1,这样撑死也不会使答案更差

但凡是单调队列的题,都会有神秘细节,这题也不例外……顺便说一下这题不要傻乎乎的用pair

代码:

/**************************************************************
    Problem: 3831
    User: danihao123
    Language: C++
    Result: Accepted
    Time:11596 ms
    Memory:16228 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
#include <queue>
#include <deque>
using namespace std;
const int maxn=1e6+1;
int D[maxn],f[maxn];
bool d_cmp(int x,int y){
    if(f[x]==f[y])
        return D[x]<D[y];
    else
        return f[x]>f[y];
}
struct DQueue{
    deque<int> D;
    queue<int> Q;
    void push(int x){
        Q.push(x);
        while(!D.empty() && d_cmp(D.back(),x))
            D.pop_back();
        D.push_back(x);
    }
    int top(){
        return D.front();
    }
    void pop(){
        if(D.front()==Q.front())
            D.pop_front();
        Q.pop();
    }
    int size(){
        return Q.size();
    }
    void clear(){
        while(!Q.empty())
            Q.pop();
        D.clear();
    }
};
DQueue hhh;
int main(){
    register int i,temp,ans;
    int n,Q,k;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&D[i]);
    scanf("%d",&Q);
    while(Q--){
        scanf("%d",&k);
        hhh.push(1);
        f[1]=0;
        for(i=2;i<=n;i++){
            while(hhh.size()>k)
                hhh.pop();
            temp=hhh.top();
            f[i]=f[temp]+(D[temp]<=D[i]);
            hhh.push(i);
        }
        printf("%d\n",f[n]);
        hhh.clear();
    }
    return 0;
}

[BZOJ 3524]Couriers

2016年2月12日 13:02 | Comments(0) | Category:题解 | Tags:

这道题有了主席树,就是裸题了……

只要用主席树维护出现次数,然后二分求解即可

但是!数组一定要开大,开大,再开大,重要的事情说三遍!

代码: