天天看点
返回

【KpmCup#0 省选模拟赛】题解

【题目地址】点击打开链接

【分析们】

【T-1】

很明显的差分约束系统，判负环。

但是裸的要超时，我们注意到一个负环必定在一个强连通分量中。于是我们先求出SCC，再判负环。

只需要判断入队次数大于sqrt(N)即可，虽然这样是有反例的，但大多数数据是能过的。

【T-2】

斜率优化dp

我们可以得到一个dp方程：

            f[i]=min{f[j]+sigma(b[k]*(i-k))}+A[i]     j+1<=k&&k<=i-1

=>     f[i]=min{f[j]+i*(S1[i-1]-S1[j])-(S2[i-1]-S2[j])}+A[i]    S1[i]=sigma(B[1..i])   S2[i]=sigma(B[1..i]*(1..i))

val[j]=f[j]+i*(S1[i-1]-S1[j])-(S2[i-1]-S2[j])

设j,k为i的两个决策，设j<k。val[j]-val[k]<0,则j比k优。

        val[j]-val[k]=f[j]-f[k]+i*(S1[k]-S1[j])+S2[j]-S2[k]<0

=>    (f[k]-f[j]+S2[k]-S2[j])/(S1[k]-S1[j])>i

由于i单调递增，所以可以斜率优化。

【T-3】

最小割

我们这样建图：

1.S向每个种子连一条容量为ai的边

2.每个种子向T连一条容量为bi的边

每个方案拆为u，v两个点。

3.S向u连一条容量为c1i的边

4.v向T连一条容量为c2i的边

5.u向需要的种子连一条容量为INF的边

6.需要的种子向v连一条容量为INF的边

正确性是显然的

【T-4】

官方题解用了AC自动机，其实一个Trie就可以了。

我们将每个串倒序插入一个Trie树中，那么某个串的kpm串就一定在它的子树中。

我们再遍历Trie树，用后序遍历来将树转换为序列。

然后就变成了静态区间k大问题，可持久化线段树（主席树）即可。

有一点需要注意，同样的串可能会有重复，所以需要在Trie树上加个链表。

【代码们】

【T-1】

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define rrep(i,b,a) for(int i=(b);i>=(a);--i)
#define pf printf
#define sf scanf
#define p_b push_back
#define INF (~0U>>3)
#define MAXN 10010
#define MAXM 20010

struct edge{
	int v,w;
	edge* next;
}*head[2][MAXN],Edge[2][MAXM];
int N,M,totEdge,Scc;
int anc[MAXN];
int sz[MAXN];
int dis[MAXN];
int inqueue[MAXN];
int val[MAXN];
bool vis[MAXN];
bool hadspfa[MAXN];
vector <int> vec;

void Read(int& x){
	char tt=getchar();
	while(tt<'0'||'9'<tt) tt=getchar();
	for(x=0;'0'<=tt&&tt<='9';x=(x<<1)+(x<<3)+tt-'0',tt=getchar());
}

void Addedge(int u,int v,int w){
	Edge[0][totEdge].v=v;
	Edge[0][totEdge].w=w;
	Edge[0][totEdge].next=head[0][u];
	head[0][u]=&Edge[0][totEdge];
	
	Edge[1][totEdge].v=u;
	Edge[1][totEdge].next=head[1][v];
	head[1][v]=&Edge[1][totEdge++];
}

void Init(){
	Read(N);
	Read(M);
	int p,u,v,w;
	rep(i,1,M){
		Read(p);
		Read(u);
		Read(v);
		if(p==1){
			Read(w);
			Addedge(u,v,-w);
		}
		else if(p==2){
			Read(w);
			Addedge(v,u,w);
		}
		else{
			Addedge(u,v,0);
			Addedge(v,u,0);
		}
	}
}

void Dfs1(int u){
	vis[u]=true;
	for(edge* p=head[0][u];p!=NULL;p=p->next)
	    if(!vis[p->v])
	        Dfs1(p->v);
	vec.p_b(u);
}

void Dfs2(int u){
	vis[u]=false;
	sz[Scc]++;
	anc[u]=Scc;
	for(edge* p=head[1][u];p!=NULL;p=p->next)
	    if(vis[p->v])
	        Dfs2(p->v);
}

bool Spfa(int u){
	queue <int> Q;
	int n=ceil(sqrt(sz[anc[u]]));
	int fa=anc[u];
	Q.push(u);
	dis[u]=0;inqueue[u]=true;val[u]++;
	while(!Q.empty()){
		u=Q.front();Q.pop();
		inqueue[u]=false;
		for(edge* p=head[0][u];p!=NULL;p=p->next){
			if(anc[p->v]!=fa) continue;
			if(dis[p->v]>dis[u]+p->w){
				dis[p->v]=dis[u]+p->w;
				if(!inqueue[p->v]){
					inqueue[p->v]=true;
					val[p->v]++;
					Q.push(p->v);
					if(val[p->v]>n) return false;
				}
			}
		}
	}
	return true;
}

void Solve(){
	rep(i,1,N)
	    if(!vis[i])
	        Dfs1(i);
	rrep(i,N-1,0)
	    if(vis[vec[i]]){
	    	Scc++;
	    	Dfs2(vec[i]);
	    }
	
	rep(i,1,N) dis[i]=INF;
	rep(i,1,N)
	    if(!hadspfa[anc[i]]){
	    	hadspfa[anc[i]]=true;
	    	if(!Spfa(i)){
	    		puts("No");
	    		return;
	    	}
	    }
	puts("Yes");
}

int main(){
	Init();
	Solve();
	return 0;
}

【T-2】

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <deque>

using namespace std;

#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define rrep(i,b,a) for(int i=(b);i>=(a);--i)
#define pf printf
#define sf scanf
#define p_b push_back
#define p_f push_front
#define pp_b pop_back
#define pp_f pop_front
#define INF (~0U>>3)
#define ll long long
#define MAXN 1000010

int N;
ll S1[MAXN];
ll S2[MAXN];
ll f[MAXN];

template <class T>
void Read(T& x){
	char tt=getchar();
	while(tt<'0'||'9'<tt) tt=getchar();
	for(x=0;'0'<=tt&&tt<='9';x=(x<<1)+(x<<3)+tt-'0',tt=getchar());
}

void Init(){
	Read(N);
	rep(i,1,N) Read(f[i]);
	rep(i,1,N){
		ll tmp;
	    Read(tmp);
	    S1[i]=S1[i-1]+tmp;
	    S2[i]=S2[i-1]+tmp*i;
	}
}

ll K(int j,int k){
	return (f[k]-f[j]+S2[k]-S2[j]);
}

ll L(int j,int k){
	return (S1[k]-S1[j]);
}

ll Val(int i,int j){
	return f[j]+i*(S1[i-1]-S1[j])-(S2[i-1]-S2[j]);
}

void Solve(){
	deque <int> Dq;
	f[0]=0;
	Dq.p_b(0);
	int n=1;
	rep(i,1,N){
		while(n>=2&&K(Dq[0],Dq[1])<=i*L(Dq[0],Dq[1])){
		    Dq.pp_f();
			n--;
		}
		f[i]+=Val(i,Dq[0]);
		while(n>=2&&
		    K(Dq[n-2],Dq[n-1])*L(Dq[n-1],i)
			>=
			K(Dq[n-1],i)*L(Dq[n-2],Dq[n-1])){
		    Dq.pp_b();
			n--;
		}
		Dq.p_b(i);
		n++;
	}
	cout<<f[N]<<endl;
}

int main(){
	Init();
	Solve();
	return 0;
}

【T-3】

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <deque>

using namespace std;

#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define rrep(i,b,a) for(int i=(b);i>=(a);--i)
#define pf printf
#define sf scanf
#define p_b push_back
#define INF (~0U>>3)
#define ll long long
#define MAXN 5010
#define MAXM 2000010

struct edge{
	int v,c;
	edge* next;
	edge* opt;
}*head[MAXN],Edge[MAXM];
int N,M;
int S,T;
int idx;
int ans;
int dis[MAXN];
int vd[MAXN];
int A[MAXN];
int B[MAXN];

void Read(int& x){
	char tt=getchar();
	while(tt<'0'||'9'<tt) tt=getchar();
	for(x=0;'0'<=tt&&tt<='9';x=(x<<1)+(x<<3)+tt-'0',tt=getchar());
}

void Addedge(int u,int v,int c){
	idx++;
	Edge[idx].v=v;
	Edge[idx].c=c;
	Edge[idx].next=head[u];
	Edge[idx].opt=Edge+idx+1;
	head[u]=Edge+idx;
	
	idx++;
	Edge[idx].v=u;
	Edge[idx].c=0;
	Edge[idx].next=head[v];
	Edge[idx].opt=Edge+idx-1;
	head[v]=Edge+idx;
}

int Sap(int u,int flow){
	if(u==T) return flow;
	int delta=0;
	for(edge* p=head[u];p!=NULL;p=p->next){
		int v=p->v;
		if(p->c>0&&dis[u]==dis[v]+1){
			int tmp=Sap(v,min(flow-delta,p->c));
			p->c-=tmp;
			p->opt->c+=tmp;
			delta+=tmp;
			if(delta==flow) return delta;
		}
	}
	if(dis[S]>T) return delta;
	if(!(--vd[dis[u]])) dis[S]=T+1;
	vd[++dis[u]]++;
	return delta;
}

void Init(){
	Read(N);
	rep(i,1,N) Read(A[i]),ans+=A[i];
	rep(i,1,N) Read(B[i]),ans+=B[i];
	Read(M);
	S=0;T=N+(M<<1)+1;
	
	rep(i,1,N){
	    Addedge(S,i,A[i]);
		Addedge(i,T,B[i]);
	}
	
	rep(i,1,M){
		int k,c1,c2,tmp;
		Read(k);
		Read(c1);
		Read(c2);
		ans+=c1+c2;
		Addedge(S,i+N,c1);
		Addedge(i+N+M,T,c2);
		rep(j,1,k){
			Read(tmp);
			Addedge(i+N,tmp,INF);
			Addedge(tmp,i+N+M,INF);
		}
	}
}

void Bfs(){
	memset(dis,-1,sizeof dis);
	queue <int> Q;
	Q.push(T);dis[T]=0;
	while(!Q.empty()){
		int u=Q.front();Q.pop();
		for(edge* p=head[u];p;p=p->next)
		    if(dis[p->v]==-1){
		    	vd[dis[p->v]=dis[u]+1]++;
		    	Q.push(p->v);
		    }
	}
}

void Solve(){
	Bfs();
	while(dis[S]<=T) ans-=Sap(S,INF);
	cout<<ans<<endl;
}

int main(){
	Init();
	Solve();
	return 0;
}

【T-4】

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define rrep(i,b,a) for(int i=(b);i>=(a);--i)
#define INF (~0U>>3)
#define sf scanf
#define pf printf
#define MAXN 100010
#define MAXM 300010

struct link{
	int rank;
	link* next;
}PPol[MAXN],*NEw=PPol;

struct TrieNode{
    TrieNode* ch[26];
    int rank;
    link* next;
    link* last;
}*trie_root,pool[MAXM],*New=pool;

struct SegNode{
	#define node SegNode
    node* lc;
    node* rc;
    int sz;
}*root[MAXN],*null,Pool[MAXN*18],*NNew=Pool;

int N;
int label;
char S[MAXM];
int A[MAXN];
int l[MAXN];
int r[MAXN];

link* Get(int rank){
	NEw->rank=rank;
	return NEw++;
}

TrieNode* Get(){
    New->rank=0;
    return New++;
}

node* Get(node* lc,int sz,node* rc){
    NNew->lc=lc;
    NNew->sz=sz;
    NNew->rc=rc;
    return NNew++;
}

int Getstr(int rt=0){
    S[0]=getchar();
    #define check(a) (a>='a'&&a<='z')
    while(!check(S[0])) S[0]=getchar();
    for(S[++rt]=getchar();check(S[rt]);S[++rt]=getchar());
    return rt;
}

void Init(){
    trie_root=Get();
    sf("%d",&N);
    rep(i,1,N){
        int t=Getstr();
        TrieNode* p=trie_root;
        rrep(j,t-1,0){
            int tmp=S[j]-'a';
            if(!p->ch[tmp]) 
                p->ch[tmp]=Get();
            p=p->ch[tmp];
        }
        if(!p->rank) p->rank=i;
        else{
        	if(!p->next) p->next=p->last=Get(i);
        	else{
        		link* q=p->last;
        		q->next=Get(i);
        		p->last=q->next;
        	}
        }
    }
}

void Dfs(TrieNode* p,int sz=1){
    if(p->rank){
	    l[p->rank]=label+1;
	    if(p->next){
	    	link* q=p->next;
	    	sz++;
	    	l[q->rank]=label+1;
	    	while(q->next){
	    		q=q->next;
	    		l[q->rank]=label+1;
	    		sz++;
	    	}
	    }
	}
    rep(i,0,25)
        if(p->ch[i])
            Dfs(p->ch[i]);
    int tmp=label+sz;
    if(p->rank){
        A[++label]=p->rank;
        r[p->rank]=tmp;
        if(p->next){
        	link* q=p->next;
        	A[++label]=q->rank;
        	r[q->rank]=tmp;
        	while(q->next){
        		q=q->next;
        		A[++label]=q->rank;
        		r[q->rank]=tmp;
        	}
        }
    }
}

node* Insert(node* T,int id,int Left,int Right,int key){
    #define ls (id<<1),Left,Mid
    #define rs ((id<<1)|1),Mid+1,Right
    #define Mid ((Left+Right)>>1)
    if(Left==Right) return Get(T->lc,T->sz+1,T->rc);
    if(key<=Mid)
        return Get(Insert(T->lc,ls,key),T->sz+1,T->rc);
    else
        return Get(T->lc,T->sz+1,Insert(T->rc,rs,key));
}

int Select(node* a,node* b,int Left,int Right,int k){
    if(b->sz-a->sz<k) return -1;
    if(Left==Right) return Left;
    int t=b->lc->sz-a->lc->sz;
    if(k<=t)
        return Select(a->lc,b->lc,Left,Mid,k);
    else
        return Select(a->rc,b->rc,Mid+1,Right,k-t);
}

void Solve(){
    Dfs(trie_root);
    root[0]=null;
    rep(i,1,N) root[i]=Insert(root[i-1],1,1,N,A[i]);
    rep(i,1,N){
        int tmp;
        sf("%d",&tmp);
        pf("%d\n",Select(root[l[i]-1],root[r[i]],1,N,tmp));
    }
}

int main(){
    null=Get(0,0,0);
    null->lc=null;
    null->rc=null;
    Init();
    Solve();
    return 0;
}
算法题解--图论：SCC 算法题解--图论：网络流 算法题解--数据结构 算法题解--动态规划 算法题解--字符串 算法分析
上一篇: HDU 3639 Hawk-and-Chicken 强连通分量分解 + dfs
下一篇: #生活碎片记录ISFP地球生存指南#一条plog告别七月

继续阅读