danihao123

搜索

音乐播放器

RSS

RSS Link

计数器

26243

[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 1212]L语言

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

这个感觉本质上和那个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;
}

[POJ 2784]Buy or Build

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

啊这题竟然在POJ上有……

枚举套餐子集是肯定的啦,但接下来呢?有的同学或许会想直接Kruskal求MST。但是估计会T。

有一个很有效的优化:先求一遍不加套餐的MST,然后接下来每次求MST的时候都只考虑这[tex]n-1[/tex]条边,这样就很快了。

需要注意的是,这[tex]n-1[/tex]以外的边就算加入了套餐也不会被考虑。因为无论加不加套餐,这些更大的边所能连接的连通分量总是可以被以前更小的边连接,所以这条边无论如何也不会被考虑啦……

代码写起来容易让人崩溃……所以说这个题很能锻炼代码能力和Debug能力。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=1005,maxq=8;
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 Cost[maxq];
vector<int> V[maxq];
struct Edge{
	int u,v,d;
	bool operator <(const Edge& x) const{
		return d<x.d;
	}
};
vector<Edge> bj;
vector<Edge> E;
vector<Edge> garbage;
int MST(int cnt,vector<Edge>& E,vector<Edge>& to){
	if(!cnt)
		return 0;
	register int i,ans=0;
	to.clear();
	for(i=0;i<E.size();i++){
		if(!is_same(E[i].u,E[i].v)){
			union_set(E[i].u,E[i].v);
			ans+=E[i].d;
			to.push_back(E[i]);
			if(!(--cnt))
				break;
		}
	}
	return ans;
}

int zb[maxn][2];
inline int EucSqr(int x,int y){
	int t1=zb[x][0]-zb[y][0],t2=zb[x][1]-zb[y][1];
	t1*=t1;
	t2*=t2;
	return t1+t2;
}
int main(){
	int T,q,num,u;
	register int i,j,k,cnt,temp,ans;
	scanf("%d%d",&n,&q);
	for(i=0;i<q;i++){
		scanf("%d%d",&num,&Cost[i]);
		V[i].clear();
		while(num--){
			scanf("%d",&u);
			V[i].push_back(u);
		}
	}
	for(i=1;i<=n;i++){
		scanf("%d%d",&zb[i][0],&zb[i][1]);
	}
	for(i=1;i<=n;i++)
		for(j=i+1;j<=n;j++){
			bj.push_back((Edge){i,j,EucSqr(i,j)});
		}
	init_set();
	sort(bj.begin(),bj.end());
	ans=MST(n-1,bj,E);
	for(i=0;i<(1<<q);i++){
		init_set();
		temp=0;
		cnt=n-1;
		for(j=0;j<q;j++)
			if(i&(1<<j)){
				temp+=Cost[j];
				for(k=1;k<V[j].size();k++){
					if(!is_same(V[j][k],V[j][0])){
						union_set(V[j][k],V[j][0]);
						cnt--;
					}
				}
			}
		ans=min(ans,temp+MST(cnt,E,garbage));
	}
	printf("%d\n",ans);
	return 0;
}

[LA 3942]Remember the Word

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

Trie第一题……

首先,容我吐槽一下UVa这个OJ,速度特别感人(同学们可以实践一下)。

这个题最容易想到的是[tex]O(n^2)[/tex]的DP——对于[tex]S[i\ldots n][/tex],枚举其前缀查是否为单词,然后转移。但是啊……对于[tex]n\le 300000[/tex]这种方法肯定会T飞。

然后我们可以考虑使用Trie优化DP。对于每个[tex]S[i\ldots n][/tex],在前缀树中查找之,就能找到所有可以作为其前缀的单词。由于每个单词最大长度也只是100,所以查找会很快辣~

代码:

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn=300005;
const int maxW=4005,maxL=105;
const int MOD=20071027;
#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))

int n;
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];
int d[maxn];
int main(){
	register int i,j,Case=0;
	int m;
	while(scanf("%s%d",Text,&m)==2){
		Case++;
		n=strlen(Text);
		Trie::InitTrie();
		REP_B(i,m){
			scanf("%s",buf);
			len[i]=strlen(buf);
			Trie::Insert(buf,i);
		}
		d[n]=1;
		DREP(i,n){
			d[i]=0;
			Trie::Query(Text+i,n-i);
			REP(j,AnsList.size()){
				d[i]=(d[i]+d[i+len[AnsList[j]]])%MOD;
			}
		}
		printf("Case %d: %d\n",Case,d[0]);
	}
	return 0;
}

[洛谷 P1637]三元上升子序列

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

这个明显是用树状数组进行统计……然而是树状数组统计第一题……so sad

答案很有可能就超int,建议开long long(反正我这么做了)。

代码:

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=30005;
int n;
struct BIT{
    int C[maxn];
    inline int lowbit(int x){
        return x&-x;
    }
    inline void Add(int p,int v){
        while(p<=n){
            C[p]+=v;
            p+=lowbit(p);
        }
    }
    inline int Sum(int x){
        register int ans=0;
        while(x>0){
            ans+=C[x];
            x-=lowbit(x);
        }
        return ans;
    }
    inline int Query(int l,int r){
        return Sum(r)-Sum(l-1);
    }
};

BIT T1,T2;
int A[maxn],A2[maxn];
int siz;
inline void InitLsh(){
    register int i;
    sort(A2+1,A2+n+1);
    siz=unique(A2+1,A2+n+1)-A2-1;
}
inline int GetLsh(int i){
    return lower_bound(A2+1,A2+siz+1,A[i])-A2;
}

int main(){
    register int i,left,right,temp;
    register long long ans=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d",&A[i]);
        A2[i]=A[i];
    }
    InitLsh();
    for(i=1;i<=n;i++){
        T2.Add(GetLsh(i),1);
    }
    for(i=1;i<=n;i++){
        temp=GetLsh(i);
        T2.Add(temp,-1);
        left=T1.Sum(temp-1);
        right=T2.Query(temp+1,siz);
        ans+=((long long)left)*((long long)right);
        T1.Add(temp,1);
    }
    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 2118]墨墨的等式

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

论如何把数论乱搞和图论乱搞出在一起……

这个题由于要求[tex]x\ge 0[/tex],所以不能gcd乱搞。我们可以先取[tex]\{a_n\}[/tex]的最小值[tex]p[/tex](忽略为0的情况,为啥取最小值待会再说),对方程两边模[tex]p[/tex]。然后对于任何能使某个同余方程成立的[tex]\{x_n\}[/tex],将其中所有[tex]x_i[/tex]同时加任意个[tex]p[/tex],同余方程都成立。

取模后,[tex]B\in Z_p[/tex],所以说只要对于[tex]Z_p[/tex]中的每个数找出最小的一组合法解即能推出其他解(所以说,剩余系越少效率越高,这也就要求取的[tex]a_i[/tex]要小)。不过这个最小的一组合法解怎么找?

我们先找出任意一个合法[tex]B[/tex](比如说0吧),然后尝试加上[tex]a_i[/tex],就可以推出其他[tex]B\in Z_p[/tex]的最小解。这个应用当然是需要最短路辣。

求出来的最短路,表示的是取最小解时的[tex]B[/tex]。这样的话就可以推出某个前缀区间中合法[tex]B[/tex]的个数(能加多少[tex]p[/tex],就有多少个,注意不要忽略加0个的情况),并且答案符合区间减法,最后做差分即可。

注意忽略[tex]a_i=0[/tex]的情况(相当于不存在)。

代码:

/**************************************************************
    Problem: 2118
    User: danihao123
    Language: C++
    Result: Accepted
    Time:1952 ms
    Memory:5508 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#ifdef DEBUG
#include <cassert>
#endif
using namespace std;
typedef long long ll;
const int maxn=15;
const ll INF=0x7f7f7f7f7f7f7f7f;
ll A[maxn];
bool inQueue[500005];
ll d[500005];
int n;
ll minv;
inline void SPFA(){
    register int i,u,to;
    queue<int> Q;
    memset(d,0x7f,sizeof(d));
    d[0]=0;
    Q.push(0);
    inQueue[0]=true;
    #ifdef DEBUG
    assert(d[1]==INF);
    #endif
    while(!Q.empty()){
        u=Q.front();
        Q.pop();
        inQueue[u]=false;
        for(i=1;i<=n;i++){
            to=(u+A[i])%minv;
            if(d[u]<INF && d[u]+A[i]<d[to]){
                d[to]=d[u]+A[i];
                if(!inQueue[to]){
                    Q.push(to);
                    inQueue[to]=true;
                }
            }
        }
    }
}
 
inline ll Calc(ll x){
    register ll ans=0;
    register int i=0;
    for(i=0;i<minv;i++)
        if(d[i]<=x)
            ans+=(x-d[i])/minv+1;
    return ans;
}
 
int main(){
    ll l,r;
    register int i;
    scanf("%d%lld%lld",&n,&l,&r);
    minv=0x7fffffff;
    for(i=1;i<=n;i++){
        scanf("%d",&A[i]);
        if(!A[i]){
            i--;
            n--;
            continue;
        }
        minv=min(minv,A[i]);
    }
    SPFA();
    printf("%lld\n",Calc(r)-Calc(l-1));
    return 0;
}


[CodeVS 1098]均分纸牌

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

很妙的一个贪心啊……

根据题意,易求平均值。然后每个数减去平均值表示这个数和平均数的“差异”。然后呢?如果每个数的差异值不为0,就直接摊给下一堆。

这种做法最大的精髓在于,即使差异值为负,也能摊给下一堆,从而避免了各种复杂操作。

代码:

#include <iostream>
using namespace std;
const int maxn=105;
int A[maxn];
int main(){
	register int i,sum=0,ans=0;
	int n;
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	for(i=1;i<=n;i++){
		cin>>A[i];
		sum+=A[i];
	}
	sum/=n;
	for(i=1;i<=n;i++){
		A[i]-=sum;
	}
	for(i=1;i<=n;i++){
		if(A[i]!=0){
			ans++;
			A[i+1]+=A[i];
			A[i]=0;
		}
	}
	cout<<ans<<endl;
	return 0;
}

[UOJ 19]寻找道路

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

这个题难就难在,别说重边自环,就是简单有向环,也会让DFS爆炸。所以考虑BFS。

但……BFS怎么判断其他点到[tex]t[/tex]的联通?

方法是,把边都反过来!这样BFS一遍就可以判联通了。

然后接下来BFS最短路就简单了,注意一些特判。

代码:

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn=10005,maxm=400005;
#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];
bool rev[maxm];
int graph_tot=0;
inline void AddEdge(int u,int v,bool reverse=false){
    graph_tot++;
    next[graph_tot]=first[u];
    first[u]=graph_tot;
    to[graph_tot]=v;
    rev[graph_tot]=reverse;
}

int s,t;
bool vis[maxn];
bool LT[maxn];
bool bfs_1(){
    register int i,u;
    memset(vis,0,sizeof(vis));
    queue<int> Q;
    Q.push(t);
    vis[t]=true;
    LT[t]=true;
    while(!Q.empty()){
        u=Q.front();
        Q.pop();
        GRAPH_REP(i,u){
            if(rev[i] && !vis[to[i]]){
                LT[to[i]]=true;
                Q.push(to[i]);
                vis[to[i]]=true;
            }
        }
    }
    return LT[s];
}

int dep[maxn];
int bfs_2(){
    register int i,u;
    bool Allow;
    memset(vis,0,sizeof(vis));
    queue<int> Q;
    Q.push(s);
    vis[s]=true;
    dep[s]=0;
    while(!Q.empty()){
        u=Q.front();
        Q.pop();
        Allow=true;
        GRAPH_REP(i,u){
            if(!rev[i] && !LT[to[i]]){
                Allow=false;
                break;
            }
        }
        if(!Allow)
            continue;
        GRAPH_REP(i,u){
            if(!rev[i] && !vis[to[i]]){
                dep[to[i]]=dep[u]+1;
                Q.push(to[i]);
                vis[to[i]]=true;
            }
        }
    }
    return vis[t]?dep[t]:-1;
}

int main(){
    int n,m,u,v;
    register int i;
    scanf("%d%d",&n,&m);
    REP(i,m){
        scanf("%d%d",&u,&v);
        AddEdge(u,v);
        AddEdge(v,u,true);
    }
    scanf("%d%d",&s,&t);
    if(!bfs_1()){
        puts("-1");
    }else{
        printf("%d\n",bfs_2());
    }
    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;
}