[POJ 1200]Crazy Search

很容易想到哈希+set判重的方法,但好像会T吧……

那么就要直接开哈希表了,但是哈希函数会很大,怎么办呢?

我们看到还有一个NK啊……这样就有一个行之有效的方法了:将字符串里的字符映射到[tex][0,NK-1][/tex],然后就可以开哈希表了……

代码:

#include <cstdio>
#include <cstring>
const int maxn=16000005;
int length,k;
bool P[maxn];
unsigned int hash[maxn],x_pow[maxn];
unsigned int ns[maxn];
void InitHash(){
	register int i;
	for(i=length;i>=1;i--)
		hash[i]=ns[i]+hash[i+1]*k;
	x_pow[0]=1;
	for(i=1;i<=length;i++)
		x_pow[i]=x_pow[i-1]*k;
}
unsigned int Hash(int i,int L){
	return hash[i]-x_pow[L]*hash[i+L];
}
char s[maxn];
int a[128];
int main(){
	int n;
	register int i,j=0,ans=0;
	scanf("%d%d",&n,&k);
	scanf("%s",s);
	length=strlen(s);
	for(i=0;i<length;i++){
		if(!a[s[i]]){
			a[s[i]]=j++;
		}
		if(j==k)
			break;
	}
	for(i=1;i<=length;i++){
		ns[i]=a[s[i-1]];
	}
	InitHash();
	for(i=1;i<=(length-n+1);i++){
		j=Hash(i,n);
		if(!P[j]){
			P[j]=true;
			ans++;
		}
	}
	printf("%d\n",ans);
	return 0;
}

[BZOJ 1468]Tree

点分治第一题……

这个也就是最经典的那个点分治问题了吧……参照qzc大爷的论文吧。

代码:

/**************************************************************
    Problem: 1468
    User: danihao123
    Language: C++
    Result: Accepted
    Time:816 ms
    Memory:2736 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 40005;
const int maxm = maxn * 2;
struct Edge {
    Edge *next;
    int to, dist;
};
Edge pool[maxm];
int graph_cnt;
Edge *first[maxn];
inline void clear_graph() {
    graph_cnt = 0;
    memset(first, 0, sizeof first);
}
inline void add_edge(int u, int v, int d) {
    Edge *e = &pool[graph_cnt++];
    e->next = first[u];
    first[u] = e;
    e->to = v;
    e->dist = d;
}
 
int k;
int calc(vector<int>& V) {
    int size = V.size();
    int rc = size - 1;
    int ans = 0;
    if(size <= 1){
        return 0;
    }
    for(int i = 0; i < size; i++) {
        while(i < rc && V[i] + V[rc] > k) {
            rc--;
        }
        if(i == rc) {
            break;
        }
        ans += rc - i;
    }
    return ans;
}
bool vis[maxn];
int siz[maxn];
void gen_siz(int x, int fa) {
    siz[x] = 1;
    for(Edge *e = first[x]; e; e = e->next) {
        int v = e->to;
        if(!vis[v] && v != fa) {
            gen_siz(v, x);
            siz[x] += siz[v];
        }
    }
}
int now_root, best_root;
void gen_best_root(int x, int fa) {
    bool OK = siz[x]*2 >= siz[now_root];
    for(Edge *e = first[x]; e; e = e->next) {
        int v = e->to;
        if(!vis[v] && v != fa) {
            gen_best_root(v, x);
            OK = OK && (siz[v]*2 <= siz[now_root]);
        }
    }
    if(OK) {
        best_root = x;
    }
}
void add_to_V(int x, int fa, int d, vector<int>& V) {
    V.push_back(d);
    for(Edge *e = first[x]; e; e = e->next) {
        int v = e->to;
        if(!vis[v] && v != fa) {
            add_to_V(v, x, d + e->dist, V);
        }
    }
}
int divide(int x) {
    gen_siz(x, 0);
    now_root = x;
    gen_best_root(x, 0);
    x = best_root;
    vis[x] = true;
    vector<int> V, CV;
    int ans = 0;
    for(Edge *e = first[x]; e; e = e->next) {
        int v = e->to;
        if(vis[v]) {
            continue;
        }
        CV.clear();
        add_to_V(v, x, e->dist, CV);
        sort(CV.begin(), CV.end());
        ans -= calc(CV);
        for(int i = 0; i < CV.size(); i++) {
            V.push_back(CV[i]);
        }
    }
    V.push_back(0);
    sort(V.begin(), V.end());
    ans += calc(V);
    for(Edge *e = first[x]; e; e = e->next) {
        int v = e->to;
        if(vis[v]) {
            continue;
        }
        ans += divide(v);
    }
    return ans;
}
 
int main() {
    int n;
    scanf("%d", &n);
    clear_graph();
    for(int i = 1; i <= (n - 1); i++) {
        int u, v, d;
        scanf("%d%d%d", &u, &v, &d);
        add_edge(u, v, d);
        add_edge(v, u, d);
    }
    scanf("%d", &k);
    printf("%d\n", divide(1));
    return 0;
}

[BZOJ 1051]受欢迎的牛

Tarjan缩点第一题……

很容易想到找出度为0的点(当且仅当这样的点有一个时有解),但是在有环图上这个方法会失效。

处理方法是,用Tarjan的强联通分量算法求出所有SCC,然后把每个SCC缩成一个点,然后再在缩点之后的图上求解即可(这个图是DAG。原因很简单,要是有环还能接着缩)。

代码:

/**************************************************************
    Problem: 1051
    User: danihao123
    Language: C++
    Result: Accepted
    Time:72 ms
    Memory:1692 kb
****************************************************************/
 
#include <cstdio>
#include <stack>
#include <algorithm>
using namespace std;
const int maxn=10005,maxm=50005;
int first[maxn];
int next[maxm],to[maxm];
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 pre[maxn],low[maxn],sccno[maxn],sccsiz[maxn];
stack<int> S;
int dfs_clk=0,scc_cnt=0;
void dfs(int x){
    dfs_clk++;
    pre[x]=low[x]=dfs_clk;
    S.push(x);
    int i,u;
    for(i=first[x];i;i=next[i]){
        u=to[i];
        if(!pre[u]){
            dfs(u);
            low[x]=min(low[x],low[u]);
        }else{
            if(!sccno[u])
                low[x]=min(low[x],pre[u]);
        }
    }
    if(low[x]==pre[x]){
        scc_cnt++;
        sccsiz[scc_cnt]=0;
        while(true){
            u=S.top();
            S.pop();
            sccno[u]=scc_cnt;
            sccsiz[scc_cnt]++;
            if(u==x)
                break;
        }
    }
}
int n;
inline void Tarjan(){
    register int i;
    for(i=1;i<=n;i++)
        if(!pre[i])
            dfs(i);
}
 
bool Out[maxn];
int main(){
    int m,u,v;
    register int i,j,ans=0;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d",&u,&v);
        AddEdge(u,v);
    }
    Tarjan();
    for(i=1;i<=n;i++){
        for(j=first[i];j;j=next[j]){
            u=to[j];
            if(sccno[i]!=sccno[u])
                Out[sccno[i]]=true;
        }
    }
    for(i=1;i<=scc_cnt;i++){
        if(!Out[i]){
            if(ans){
                ans=0;
                break;
            }
            ans=sccsiz[i];
        }
    }
    if(n==1)
        ans=0;
    printf("%d\n",ans);
    return 0;
}

[CodeVS 1217]借教室

很容易想到线段树水过。

很可惜,这样估计也就70分。

然后这个问题是符合单调性的……可以二分答案哒。不过怎么判定?

不知道诸位还记得差分序列?记得就好,用差分序列的方法维护即可。

等等,我怎么感觉你这个做法是[tex]O(nlogn)[/tex]的,能过?

推荐一个行之有效的优化:注意一下每一次修改都是在之前的基础上反悔或前进几次,所以就可以直接在原基础上修改差分序列辣~这样效率是很高滴~

代码:

#include <cstdio>
const int maxn=1e6+5;
typedef long long ll;
ll A[maxn];
int l[maxn],r[maxn];
ll d[maxn];
ll C[maxn];
int n,m,last=0;
bool Check(int x){
    register int i,cnt=0;
    if(x>last)
        for(i=last+1;i<=x;i++){
            C[l[i]]+=d[i];
            C[r[i]+1]-=d[i];
        }
    if(x<last)
        for(i=x+1;i<=last;i++){
            C[l[i]]-=d[i];
            C[r[i]+1]+=d[i];
        }
    last=x;
    for(i=1;i<=n;i++){
        cnt+=C[i];
        if(cnt>A[i])
            return false;
    }
    return true;
}

int main(){
    register int i,L,M,R;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%lld",&A[i]);
    }
    for(i=1;i<=m;i++){
        scanf("%lld%d%d",&d[i],&l[i],&r[i]);
    }
    L=1;
    R=m+1;
    while(L<R){
        M=L+(R-L)/2;
        if(Check(M)){
            L=M+1;
        }else{
            R=M;
        }
    }
    if(L==m+1)
        puts("0");
    else
        printf("-1\n%d\n",L);
    return 0;
}

[POJ 2446]Chessboard

很容易看出是二分图最大匹配,可是怎么建图呢……

我们可以考虑把一个点的横纵坐标相加,和为偶数者称之为偶数点,反之为奇数点。我们发现,每个骨牌都正好覆盖了一个奇数点和一个偶数点。于是乎就能把点分为两个集合了,建图就很方便了。

代码:

#include <cstdio>
#include <cstring>
const int maxn=35,maxm=520;
bool G[maxm][maxm];

// Hungray
int odd_cnt=0,even_cnt=0;
bool vis[maxm];
int GirlFriend[maxm];
bool DFS(int x){
    int i;
    for(i=1;i<=even_cnt;i++)
        if(G[x][i] && !vis[i]){
            vis[i]=true;
            if(!GirlFriend[i] || DFS(GirlFriend[i])){
                GirlFriend[i]=x;
                return true;
            }
        }
    return false;
}
inline int Hungray(){
    register int i,ans=0;
    for(i=1;i<=odd_cnt;i++){
        memset(vis,0,sizeof(vis));
        if(DFS(i))
            ans++;
    }
    return ans;
}

int n,m;
bool isHole[maxn][maxn];
int ct[maxn][maxn];
inline int AddPoint(int a,int b,int x,int y){
	if(ct[x][y])
		if(!isHole[x][y])
			G[ct[a][b]][ct[x][y]]=true;
}
int main(){
	int k,x,y;
	register int i,j,tot;
	scanf("%d%d%d",&m,&n,&k);
	tot=m*n-k;
	if(1&tot){
		puts("NO");
		return 0;
	}
	for(i=1;i<=k;i++){
		scanf("%d%d",&x,&y);
		isHole[y][x]=true;
	}
	for(i=1;i<=m;i++)
		for(j=1;j<=n;j++){
			if(isHole[i][j])
				continue;
			if(1&(i+j)){
				ct[i][j]=++odd_cnt;
			}else{
				ct[i][j]=++even_cnt;
			}
		}
	for(i=1;i<=m;i++)
		for(j=1;j<=n;j++){
			if(!isHole[i][j] && 1&(i+j)){
				AddPoint(i,j,i-1,j);
				AddPoint(i,j,i+1,j);
				AddPoint(i,j,i,j-1);
				AddPoint(i,j,i,j+1);
			}
		}
	if(Hungray()==(tot/2)){
		puts("YES");
	}else{
		puts("NO");
	}
	return 0;
}

[POJ 3723]Conscription

还是要注意读题(换言之,我英语很烂)……

这个题实际上要求求出一个最大生成森林。我们可以直接把边权造成负的,Kruskal一遍即可。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=10005;
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))

// DJSet
int p[maxn*2],rank[maxn*2];
int find_set(int x){
	if(p[x]==x)
		return x;
	else
		return p[x]=find_set(p[x]);
}
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);
}
int n;
inline void init_set(){
	register int i;
	REP_B(i,n){
		p[i]=i;
	}
	CL_ARR(rank,0);
}

struct Edge{
	int u,v,d;
	bool operator <(const Edge& x) const{
		return d<x.d;
	}
};
int m;
Edge E[50005];
#define EDGE_ALL(i) E[i].u,E[i].v
int MST(){
	register int i,ans=0,cnt=0;
	init_set();
	sort(E+1,E+1+m);
	REP_B(i,m){
		if(!is_same(EDGE_ALL(i))){
			union_set(EDGE_ALL(i));
			ans+=E[i].d;
			cnt++;
			if(cnt==n-1)
				break;
		}
	}
	return ans;
}

int main(){
	int T,N,M;
	register int i,ans;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d%d",&N,&M,&m);
		n=N+M;
		ans=10000*n;
		for(i=1;i<=m;i++){
			scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].d);
			E[i].u+=1;
			E[i].v+=1+N;
			E[i].d*=-1;
		}
		ans+=MST();
		printf("%d\n",ans);
	}
	return 0;
}

[POJ 2352]Stars

刚开始竟然还以为是强制离散化的二维Fenwick树……噫……注意读题。

这个题的坐标是按Y升序给出(Y相同则按X升序),所以说直接Fenwick树搞搞即可……

代码:

#include <cstdio>
const int maxn=15005,maxX=32010;
int C[maxX];
inline int lowbit(int x){
	return x&(-x);
}
inline void Add(int pos,int v){
	while(pos<=maxX){
		C[pos]+=v;
		pos+=lowbit(pos);
	}
}
inline int Sum(int x){
	register int res=0;
	while(x>0){
		res+=C[x];
		x-=lowbit(x);
	}
	return res;
}

int cnt[maxn];
int main(){
	register int i;
	int n,x,y;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d%d",&x,&y);
		x++;
		cnt[Sum(x)]++;
		Add(x,1);
	}
	for(i=0;i<n;i++){
		printf("%d\n",cnt[i]);
	}
	return 0;
}

[POJ 2406]Power Strings

循环节又一题……用KMP性质搞搞即可。

注意特判(好像是句废话),再就没啥了……

代码:

#include <cstdio>
#include <cstring>
const int maxn=1e6+5;
char P[maxn];
int f[maxn];
int main(){
	register int i,j,xhj,n;
	while(scanf("%s",P)){
		if(P[0]=='.')
			break;
		n=strlen(P);
		f[0]=f[1]=0;
		for(i=1;i<n;i++){
			j=f[i];
			while(j && P[j]!=P[i])
				j=f[j];
			f[i+1]=(P[j]==P[i]?j+1:0);
		}
		xhj=n-f[n];
		if(!(n%xhj)){
			printf("%d\n",n/xhj);
		}else{
			puts("1");
		}
	}
	return 0;
}

[UVa 11549]Calculator Conundrum

很有趣的一个题。

很明显,求出的结果一定会循环,形成一个环。然后呢?假如有一只乌龟和一只兔子在这个赛道上赛跑(同起点),兔子的速度是乌龟的两倍,那么最后兔子一定会“追上”乌龟,然后接下来的情况就是以前的循环了。

这种神奇的算法叫做Floyd判圈算法。话说还有一种Brent判圈算法……常数比它还要小。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
char buf[25];
int n;
inline ull next(ull x){
    register ull res=0;
    register int i,length;
    memset(buf,0,sizeof(buf));
    length=sprintf(buf,"%llu",x*x);
    length=min(length,n);
    for(i=0;i<length;i++){
        res=res*10+buf[i]-'0';
    }
    return res;
}
int main(){
    ull k1,k2,ans;
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%llu",&n,&k1);
        ans=k1;
        k2=k1;
        do{
            k1=next(k1);
            k2=next(k2);
            if(k2>ans)
                ans=k2;
            k2=next(k2);
            if(k2>ans)
                ans=k2;
        }while(k1!=k2);
        printf("%llu\n",ans);
    }
    return 0;
}

[BZOJ 3172]单词

首先……出题人语文不太好……估计和我这种语文很差的人还有差距……

这个提的意思是,给你若干个单词,输出每个单词在所有单词(而不是把所有单词连起来)中出现的次数。

然后肯定要AC自动机上失配函数搞一波辣……把BFS序倒过来搜,传递出现次数即可。还有这个题的数据范围好像也比给出的小很多……

代码:

/**************************************************************
    Problem: 3172
    User: danihao123
    Language: C++
    Result: Accepted
    Time:232 ms
    Memory:115080 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
const int maxn=205;
const int maxnode=1*1e6+5;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
int cnt[maxnode];
 
namespace ACAutomate{
    // Trie
    const int sigma_size=26;
    int Tree[maxnode][sigma_size];
    int siz;
    inline int idx(char c){
        return c-'a';
    }
    void InitAC(){
        siz=0;
        CL_ARR(Tree[0],0);
    }
    int Insert(char *s){
        register int i,n=strlen(s);
        register int u=0,c;
        REP(i,n){
            c=idx(s[i]);
            if(!Tree[u][c]){
                siz++;
                Tree[u][c]=siz;
                CL_ARR(Tree[siz],0);
            }
            u=Tree[u][c];
            cnt[u]++;
        }
        return u;
    }
    // AC Automate
    int f[maxnode];
    int Q[maxnode];
    void InitFail(){
        register int i,u,x,v,head=0,tail=0;
        f[0]=0;
        REP(i,sigma_size){
            u=Tree[0][i];
            if(u){
                f[u]=0;
                Q[tail++]=u;
            }
        }
        while(head<tail){
            u=Q[head];
            head++;
            REP(i,sigma_size){
                x=Tree[u][i];
                if(!x){
                    continue;
                }
                Q[tail++]=x;
                v=f[u];
                while(v && !Tree[v][i])
                    v=f[v];
                f[x]=Tree[v][i];
            }
        }
        for(i=tail-1;i>=0;i--)
            cnt[f[Q[i]]]+=cnt[Q[i]];
    }
};
 
char buf[maxnode];
int pos[maxn];
int main(){
    int n;
    register int i;
    scanf("%d",&n);
    ACAutomate::InitAC();
    REP_B(i,n){
        scanf("%s",buf);
        pos[i]=ACAutomate::Insert(buf);
    }
    ACAutomate::InitFail();
    REP_B(i,n){
        printf("%d\n",cnt[pos[i]]);
    }
    return 0;
}