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

[CodeVS 3729]飞扬的小鸟

论如何把一个完全背包出的高大上……

这个题啊……细节特别多……

首先,不建议开滚动数组,细节处理就会疯。

然后呢……真的不太好说了……还是看代码吧(尽管代码还是有明显的滚动数组痕迹)。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=10005,maxm=1005;
const int INF=0x7f7f7f7f;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)

int GZ[maxn][2];
bool haveGZ[maxn];
int A[maxn][2];
int d[maxn][maxm];
int main(){
    int n,m,k,temp;
    register int i,j,v,now,pre,ans=INF,cnt;
    scanf("%d%d%d",&n,&m,&k);
    cnt=k;
    REP(i,n){
        scanf("%d%d",&A[i][0],&A[i][1]);
    }
    for(i=0;i<=n;i++){
        GZ[i][0]=0;
        GZ[i][1]=m+1;
    }
    REP_B(i,k){
        scanf("%d",&temp);
        haveGZ[temp]=true;
        scanf("%d%d",&GZ[temp][0],&GZ[temp][1]);
    }
    memset(d,0x7f,sizeof(d));
    memset(d[0],0,sizeof(d[0]));
    d[0][0]=INF;
    REP_B(i,n){
        now=i;
        pre=i-1;
        d[now][0]=INF;
        int& X=A[i-1][0];
        int& Y=A[i-1][1];
        REP_B(j,m){
            if(j-X>0 && d[pre][j-X]<INF)
                d[now][j]=min(d[now][j],d[pre][j-X]+1);
            if(j-X>0 && d[now][j-X]<INF)
                d[now][j]=min(d[now][j],d[now][j-X]+1);
            if(j==m)
                for(v=j-X;v<=m;v++){
                    if(d[pre][v]<INF)
                        d[now][j]=min(d[now][j],d[pre][v]+1);
                    if(d[now][v]<INF)
                        d[now][j]=min(d[now][j],d[now][v]+1);
                }
        }
        for(j=GZ[i][0]+1;j<GZ[i][1];j++){
            if(j+Y<=m && d[pre][j+Y]<INF)
                d[now][j]=min(d[now][j],d[pre][j+Y]);
        }
        if(haveGZ[i]){
            REP_B(j,GZ[i][0])
                if(d[now][j]<INF){
                    d[now][j]=INF;
                }
            for(j=GZ[i][1];j<=m;j++)
                if(d[now][j]<INF){
                    d[now][j]=INF;
                }
        }
    }
    for(i=n;i>=1;i--){
        for(j=m;j>=1;j--){
            ans=min(ans,d[i][j]);
        }
        if(ans<INF)
            break;
        if(haveGZ[i])
            cnt--;
    }
    if(cnt==k){
        printf("1\n%d\n",ans);
    }else{
        printf("0\n%d\n",cnt);
    }
    return 0;
}

[CodeVS 1378]选课

上古CTSC提……竟然只是树形背包DP……

树形背包DP可以使用左儿子右兄弟法进行优化。这样的话每个点只需要考虑要选不选自己,摊派给兄弟多少,摊派给儿子多少。不过至于这样为何有很大的优化效果,可以参考完全背包的优化方法进行理解。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=305;
#define CL_ARR(x,v) memset(x,v,sizeof(x))
int lc[maxn],rb[maxn],W[maxn];
inline void Insert(int x,int y,int w){
    rb[y]=lc[x];
    lc[x]=y;
    W[y]=w;
}

int d[maxn][maxn];
int dp(int x,int k){
    if(x==-1 || k<=0)
        return 0;
    if(d[x][k]>=0)
        return d[x][k];
    int i;
    int& ans=d[x][k];
    ans=dp(rb[x],k);
    for(i=0;i<k;i++){
        ans=max(ans,W[x]+dp(lc[x],i)+dp(rb[x],k-i-1));
    }
    return ans;
}

int main(){
    register int i;
    int n,m,x,w;
    scanf("%d%d",&n,&m);
    CL_ARR(lc,-1);
    CL_ARR(rb,-1);
    for(i=1;i<=n;i++){
        scanf("%d%d",&x,&w);
        Insert(x,i,w);
    }
    CL_ARR(d,-1);
    printf("%d\n",dp(0,m+1));
    return 0;
}

[CodeVS 1154]能量项链

环状DP填坑辣……

这个就是把矩阵连乘出到了环上。很容易想到的方法是枚举断点断环成链,当成简单的矩阵连乘做,不过这样的时间复杂度为[tex]O(n^4)[/tex],有点慢。我们可以直接把序列复制一份放到原序列后面,然后当成矩阵连乘做,这样的话时间复杂度仅为[tex]O(n^3)[/tex],挺优秀的。

代码:

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=205;
long long d[maxn][maxn];
long long e[maxn];
int main(){
    register int i,j,k;
    register long long temp,ans=0;
    int n;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%lld",&e[i]);
        e[i+n]=e[i];
    }
    for(j=2;j<2*n;j++)
        for(i=j-1;i>=1 && (j-i+1)<=n;i--){
            for(k=i;k<j;k++){
                temp=d[i][k]+d[k+1][j]+e[i]*e[k+1]*e[j+1];
                d[i][j]=max(d[i][j],temp);
            }
            ans=max(ans,d[i][j]);
        }
    printf("%lld\n",ans);
    return 0;
}

[CodeVS 1098]均分纸牌

很妙的一个贪心啊……

根据题意,易求平均值。然后每个数减去平均值表示这个数和平均数的“差异”。然后呢?如果每个数的差异值不为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;
}

[CodeVS 4416]FFF团卧底的后宫

差分约束又一题……也是水体……唯一难度在于两种符号。

不过这题有个坑点,无解(有负环)输出-1,答案无限大(不连通)输出-2,但……原题没说,望大家注意。

代码:

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
#define REP(i,n) for(i=1;i<=(n);i++)
const int maxn=1001,maxm=10002;
int first[maxn];
int next[maxm],to[maxm],dist[maxm];
int tot=0;
inline void Add_Edge(int u,int v,int d){
	tot++;
	next[tot]=first[u];
	first[u]=tot;
	to[tot]=v;
	dist[tot]=d;
}

int d[maxn];
int cnt[maxn];
bool inQueue[maxn];
int n;
int SPFA(){
	queue<int> Q;
	register int i,u;
	memset(d,0x7f,sizeof(d));
	d[n]=0;
	Q.push(n);
	inQueue[n]=true;
	while(!Q.empty()){
		u=Q.front();
		Q.pop();
		inQueue[u]=false;
		for(i=first[u];i;i=next[i]){
			if(d[u]<0x7f7f7f7f && d[to[i]]>d[u]+dist[i]){
				d[to[i]]=d[u]+dist[i];
				if(!inQueue[to[i]]){
					Q.push(to[i]);
					inQueue[to[i]]=true;
					cnt[to[i]]++;
					if(cnt[to[i]]>n)
					    return -1;
				}
			}
		}
	}
	if(d[1]==0x7f7f7f7f)
	    return -2;
	return d[1];
}
int main(){
	int m,k,u,v,d;
	register int i;
	scanf("%d%d%d",&n,&m,&k);
	REP(i,m){
		scanf("%d%d%d",&u,&v,&d);
		Add_Edge(v,u,d);
	}
	REP(i,k){
		scanf("%d%d%d",&u,&v,&d);
		Add_Edge(u,v,-d);
	}
	printf("%d\n",SPFA());
	return 0;
}

[BZOJ 1050]旅行/[CodeVS 1001]舒适的路线

这两个题是一样的啊……

让路径上最大值最小当然要玩瓶颈路,瓶颈路需要MST,然后Kruskal求MST时最小边不是不可控的!也就是说我们可以控制最小边,从而求出符合要求的生成树,然后凿出瓶颈路。

所以我们可以直接枚举最小边,然后Kruskal求生成树,之后求瓶颈路。至于是否有解,第一遍Kruskal(第一遍求的其实是MST)之后看看是否联通即可。

不过这个题求瓶颈路个人建议用BFS而不是DFS,且不谈BFS效率高还不易炸堆栈段(尽管这个题没有炸堆栈段的隐患),DFS本身细节就很多,容易错。

代码:

/**************************************************************
    Problem: 1050
    User: danihao123
    Language: C++
    Result: Accepted
    Time:3588 ms
    Memory:1172 kb
****************************************************************/
 
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <utility>
#include <bitset>
#include <vector>
#include <queue>
using namespace std;
const int maxn=501,maxm=10001;
#define REP(i,n) for(i=0;i<(n);i++)
#define REPB(i,n) for(i=1;i<=(n);i++)
#define CUS_REP(i,u,v) for(i=(u);i<(v);i++)
#define REP_G(i,u) for(i=first[u];i;i=next[i])
#define CL_ARR(x,v) memset(x,v,sizeof(x))
typedef pair<int,int> pii;
int n;
int S,T;
 
// Graph
int first[maxn];
int next[maxm],to[maxm],dist[maxm];
int G_cnt=0;
inline void Add_Edge(int u,int v,int d){
    G_cnt++;
    next[G_cnt]=first[u];
    first[u]=G_cnt;
    to[G_cnt]=v;
    dist[G_cnt]=d;
}
inline void Clear_Graph(){
    CL_ARR(first,0);
    CL_ARR(next,0);
    CL_ARR(to,0);
    CL_ARR(dist,0);
    G_cnt=0;
}
 
// BFS
bitset<maxn> vis;
struct Node{
    int x,maxv,minv;
};
pii BFS(){
    register int a,b,i;
    queue<Node> Q;
    Node tt;
    Q.push((Node){S,-1,0x7fffffff});
    vis[S]=true;
    while(!Q.empty()){
        tt=Q.front();
        Q.pop();
        if(tt.x==T)
            return make_pair(tt.maxv,tt.minv);
        REP_G(i,tt.x){
            if(!vis[to[i]]){
                vis[to[i]]=true;
                Q.push((Node){to[i],max(tt.maxv,dist[i]),min(tt.minv,dist[i])});
            }
        }
    }
}
 
// BINGCHA Set
int p[maxn],rank[maxn];
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);
}
inline void init_set(){
    register int i;
    for(i=1;i<=n;i++)
        p[i]=i;
    CL_ARR(rank,0);
}
 
// MST
struct Edge{
    int u,v,d;
    bool operator <(const Edge& x) const{
        return d<x.d;
    }
};
vector<Edge> E;
bool OK=false;
pii ans;
void MST(int x){
    register int i,a,b,cnt=0;
    pii que;
    register double jia,yi;
    Clear_Graph();
    init_set();
    CUS_REP(i,x,E.size()){
        if(!is_same(E[i].u,E[i].v)){
            Add_Edge(E[i].u,E[i].v,E[i].d);
            Add_Edge(E[i].v,E[i].u,E[i].d);
            cnt++;
            union_set(E[i].u,E[i].v);
            if(cnt==n-1)
                break;
        }
    }
    if(is_same(S,T)){
        OK=true;
    }else{
        return;
    }
    vis.reset();
    que=BFS();
    a=que.first;
    b=que.second;
    jia=((double)a)/((double)b);
    yi=(double(ans.first))/(double(ans.second));
    if(jia<yi){
        ans.first=a;
        ans.second=b;
    }
}
 
int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}
 
// I/O优化
inline int readint(){
    char c=getchar();
    register int x=0;
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
int main(){
    int m;
    register int i,u,v,d;
    n=readint();
    m=readint();
    REP(i,m){
        u=readint();
        v=readint();
        d=readint();
        E.push_back((Edge){u,v,d});
    }
    S=readint();
    T=readint();
    sort(E.begin(),E.end());
    ans.first=0x7fffffff;
    ans.second=1;
    REP(i,m){
        MST(i);
        if(!OK){
            if(!i){
                puts("IMPOSSIBLE");
                return 0;
            }else{
                break;
            }
        }
    }
    d=gcd(ans.first,ans.second);
    ans.first/=d;
    ans.second/=d;
    if(ans.second==1)
        printf("%d\n",ans.first);
    else
        printf("%d/%d\n",ans.first,ans.second);
    return 0;
}

[CodeVS 3269]混合背包

哎……现在才敢说真正会背包DP……

这个题可以分成三类问题分别处理,然后用一个一维数组一起递推。

0-1背包和完全背包都很简单。多重背包直接递推的话复杂度很高,可以考虑单调队列优化……然而窝太弱……不过还是用了

代码:

#include <cstdio>
#include <algorithm>
#include <queue>
#include <deque>
using namespace std;
const int maxn=201,maxv=200001;
struct DQueue{
    deque<int> D;
    queue<int> Q;
    void push(int x){
        Q.push(x);
        while(!D.empty() && x>D.back())
            D.pop_back();
        D.push_back(x);
    }
    int top(){
        return D.front();
    }
    void pop(){
        if(D.front()==Q.front())
            D.pop_front();
        Q.pop();
    }
    int size(){
        return Q.size();
    }
    void clear(){
        while(!Q.empty())
            Q.pop();
        D.clear();
    }
};
int d[maxv];
int v;
void pack(int V,int W,int c){
	register int i,j,m;
	if(c==1){
		for(i=v;i>=V;i--)
			d[i]=max(d[i],d[i-V]+W);
	}else{
		if(c==-1){
			for(i=V;i<=v;i++)
				d[i]=max(d[i],d[i-V]+W);
		}else{
			c=min(c,v/V);
			for(i=0;i<V;i++){
				m=(v-i)/V;
				DQueue Q;
				for(j=0;j<=m;j++){
					if(Q.size()==c+1)
						Q.pop();
					Q.push(d[j*V+i]-j*W);
					d[j*V+i]=Q.top()+j*W;
				}
			}
		}
	}
}
int main(){
	register int i;
	int n,x,y,z;
	scanf("%d%d",&n,&v);
	for(i=1;i<=n;i++){
		scanf("%d%d%d",&x,&y,&z);
		pack(x,y,z);
	}
	printf("%d\n",d[v]);
	return 0;
}

[CodeVS 1044]拦截导弹

第一问很显然是最长不升子序列,直接DP即可。

第二问咋整?暴力?网络流?

其实就是最长不降子序列。具体证明嘛……自己找吧。

代码:

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=22;
int d[maxn],f[maxn];
int A[maxn];
int main(){
    int n;
    register int i,j,ans=0;
    for(n=1;;n++)
        if(scanf("%d",&A[n])!=1)
            break;
    n--;
    for(i=1;i<=n;i++){
        d[i]=1;
        for(j=i-1;j>=1;j--)
            if(A[j]>=A[i])
                d[i]=max(d[i],d[j]+1);
        ans=max(ans,d[i]);
    }
    printf("%d\n",ans);
    ans=0;
    for(i=1;i<=n;i++){
        f[i]=1;
        for(j=i-1;j>=1;j--)
            if(A[j]<=A[i])
                f[i]=max(f[i],f[j]+1);
        ans=max(ans,f[i]);
    }
    printf("%d\n",ans);
    return 0;
}

[CodeVS 3168]抄书问题 3

二分答案处女作,嗯……

这题没啥好说的……二分答案+贪心判定。注意最后输出的时候不能一味贪心,否则区间数可能小于k!

代码:

#include <cstdio>
#include <utility>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=1000001;
int n;
ll A[maxn];
bool hf(int k,int x){
    register int i,d=1;
    register ll ans=0;
    for(i=1;i<=n;i++){
        if(ans+A[i]>x){
            d++;
            ans=A[i];
        }else{
            ans+=A[i];
        }
    }
    return d<=k;
}
vector<pii> as;
void print(int k,int x){
    register int i,kr=k,l=n,r=n;
    register ll cnt=0;
    for(i=n;i>=1;i--){
        if(cnt+A[i]>x || i<kr){
            l=i+1;
            kr--;
            as.push_back(make_pair(l,r));
            cnt=A[i];
            l=i;
            r=i;
        }else{
            l=i;
            cnt+=A[i];
        }
    }
    as.push_back(make_pair(l,r));
    for(i=as.size()-1;i>=0;i--)
        printf("%d %d\n",as[i].first,as[i].second);
}
int main(){
    register int i,k;
    register ll L=-1,R=0,M;
    scanf("%d%d",&n,&k);
    for(i=1;i<=n;i++){
        scanf("%lld",&A[i]);
        R+=A[i];
        L=max(L,A[i]);
    }
    if(R<=1)
        R=2;
    while(R>L){
        M=L+(R-L)/2;
        if(hf(k,M))
            R=M;
        else
            L=M+1;
    }
    print(k,L);
    return 0;
}