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

[UVa 10635]Prince and Princess

这个名字真有童话风味哎……

直接LCS肯定会TLE。注意每个序列都是不重复序列,所以可以将A映射到[tex][1,p+1][/tex],然后再把B映射一下(有的可能A里面没有?反正既然A里没有就和LCS没关系了),就相当于求B的LIS。LIS可以在[tex]O(nlogn)[/tex]时间内完成。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=62510;
#define CL_ARR(x,v) memset(x,v,sizeof(x))

int B[maxn];
int Hash[maxn];
int d[maxn],g[maxn];
int main(){
    int T,n,p,q,x;
    register int i,ans,k,Case=0;
    scanf("%d",&T);
    while(T--){
        Case++;
        scanf("%d%d%d",&n,&p,&q);
        CL_ARR(Hash,0);
        for(i=1;i<=(p+1);i++){
            scanf("%d",&x);
            Hash[x]=i;
        }
        for(i=1;i<=(q+1);i++){
            scanf("%d",&x);
            B[i]=Hash[x];
        }
        CL_ARR(g,0x7f);
        ans=0;
        for(i=1;i<=(q+1);i++){
            k=lower_bound(g+1,g+2+q,B[i])-g;
            d[i]=k;
            g[k]=B[i];
            ans=max(ans,d[i]);
        }
        printf("Case %d: %d\n",Case,ans);
    }
    return 0;
}

[BZOJ 1511]Periods of Words

很妙的一道题啊。

这个题可以先求一遍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语言

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