danihao123

搜索

音乐播放器

RSS

RSS Link

计数器

29173

[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;
}

[UOJ 16]联合权值

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

这个题的关键啊……就在于那个中间点。

我们可以枚举中间点,然后进行统计。

至于最大联合权值,直接找中间点相邻点中最大权值和次大权值的积的最大值。至于联合权值之和,可以推出这样一个式子([tex]x[/tex]与中间点相邻,其中[tex]s[/tex]是所有和中间点相邻的点的权值和):

[tex]\Sigma x\mul (s-x)[/tex]

这就好弄多了。

代码:

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=2*1e5+5;
const int maxm=maxn*2,MOD=10007;
#define REP(i,n) for(i=1;i<=(n);i++)
#define GRAPH_REP(i,u) for(i=first[u];i;i=next[i])
int first[maxn];
int next[maxm],to[maxm];
int graph_tot=0;
inline void AddEdge(int u,int v){
    graph_tot++;
    next[graph_tot]=first[u];
    first[u]=graph_tot;
    to[graph_tot]=v;
}

// int pow_mod(int a,int b){
//     if(!b){
//         return 1;
//     }
//     int x=pow_mod(a,b>>1);
//     long long ans=(((long long)x)*((long long)x))%MOD;
//     if(1&b)
//         ans=ans*(a%MOD)%MOD;
//     return (int)ans;
// }
int d[maxn];
int main(){
    int n,u,v,temp,temp2;
    register int i,j,ans1=0,ans2=0,sum,maxv,smax;
    scanf("%d",&n);
    REP(i,n-1){
        scanf("%d%d",&u,&v);
        AddEdge(u,v);
        AddEdge(v,u);
    }
    REP(i,n){
        scanf("%d",&d[i]);
    }
    REP(i,n){
        sum=maxv=smax=0;
        GRAPH_REP(j,i){
            temp=to[j];
            sum=(d[temp]%MOD+sum)%MOD;
            if(d[temp]>maxv){
                smax=maxv;
                maxv=d[temp];
            }else{
                if(d[temp]>smax)
                    smax=d[temp];
            }
        }
        ans1=max(ans1,maxv*smax);
        temp2=0;
        GRAPH_REP(j,i){
            temp=to[j];
            temp2=(temp2+(d[temp]%MOD)*((sum-(d[temp]%MOD)+MOD)%MOD)%MOD)%MOD;
        }
        ans2=(ans2+temp2)%MOD;
    }
    printf("%d %d\n",ans1,ans2);
    return 0;
}

[BZOJ 2054]疯狂的馒头

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

秒,秒啊……

很容易想到线段树,但是在[tex]N=10^6,M=10^7[/tex]的情况下,线段树肯定会TLE。

考虑修改,我们可以发现真正影响一个馒头颜色的只是作用于此馒头上的最后一个操作。可以考虑倒序枚举操作,然后暴力修改。但是如此暴力修改的话可能覆盖了实际时间线较晚的操作……

考虑并查集!每个节点修改完后将其父亲改为下一个点,这样的话被修改的地方就可以轻松跳过了。

注意一个细节,第[tex]N[/tex]个馒头被染色后,其父亲会被修改为[tex]N+1[/tex],所以说并查集实际上要开[tex]N+1[/tex]!

代码:

/**************************************************************
    Problem: 2054
    User: danihao123
    Language: C++
    Result: Accepted
    Time:2476 ms
    Memory:39796 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=1000005;
int Color[maxn];
int P[maxn];
int n;
int find_set(int x){
    if(P[x]==x)
        return x;
    else
        return P[x]=find_set(P[x]);
}
inline void init_set(){
    register int i;
    for(i=1;i<=(n+1);i++)
        P[i]=i;
}
int buf[20];
inline void PutInt(int x){
    register int i,p=0;
    if(x==0){
        buf[p++]=0;
    }else{
        while(x){
            buf[p++]=x%10;
            x/=10;
        }
    }
    for(i=p-1;i>=0;i--)
        putchar(buf[i]+'0');
    putchar('\n');
}
int main(){
    int m,p,q;
    register int i,j,l,r,k=0;
    bool OK=false;
    scanf("%d%d%d%d",&n,&m,&p,&q);
    init_set();
    for(i=m;i>=1;i--){
        l=(((i%n)*(p%n))%n+q%n)%n+1;
        r=(((i%n)*(q%n))%n+p%n)%n+1;
        if(l>r)
            swap(l,r);
        for(j=find_set(l);j<=r;j=find_set(j)){
            Color[j]=i;
            P[j]=j+1;
            k++;
            if(k==n){
                OK=true;
                break;
            }
        }
        if(OK)
            break;
    }
    for(i=1;i<=n;i++)
        PutInt(Color[i]);
    return 0;
}