学步园

C、D、E

C:

每段类似X00000000...的数（X表示非零数字）如果X左边整段数字连起来都没有这段数字大的话，那么左边整段+当前这段就必须作为一个数字，要不然左边整段不可能在当前这段前面，程序到这里就可以结束了。否则，左边整段可以继续分解。对于非零的一整段，可以第一个数连第二个数字一直连起来，答案是这段的长度。除非这段在最开头，且第一个数字小于第二个数字，那么前两个数字必须作为一个数，答案是长度-1。

code：

#include <algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <string>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
using namespace std;

#define N  100010
#define ll long long
#define ALL(x)     x.begin(),x.end()
#define CLR(x,a)   memset(x,a,sizeof(x))
#define mp	make_pair
#define fir first
#define sec second
typedef pair<int,int> PI;
const int    INF=0x3fffffff;
const int    MOD=1000000007;
/*----------------code-----------------*/

char s[N];

int solve(int begin,int end){
	if(end<begin) return 0;
	if(begin==0){
		if(end==begin) return 1;
		if(s[begin]>=s[begin+1]) return end-begin+1;
		return end-begin;
	}
	return end-begin+1;
}

bool check(int begin,int end,int _begin,int _end){
	if(end<0) return true;
	if(end-begin<_end-_begin) return false;
	if(end-begin>_end-_begin) return true;
	if(s[begin]>=s[_begin]) return true;
	return false;
}

int main(){
	scanf("%s",s);
	int n=strlen(s),end=n-1,ans=0;
	for(int i=n-1;i>=0;i--){
		if(s[i]=='0'){
			ans+=solve(i+1,end);
			int t=i;
			while(i>=0 && s[i]=='0') i--;	
		   	if(!check(0,i-1,i,t)){
				ans++;
				end=-1;
				break;
			}else{
				ans++;
			}
			end=i-1;
		}
	}
	ans+=solve(0,end);
	printf("%d",ans);
	return 0;
}

D:

看错题意，一直把arc （u,v）理解成存在路径u到v，虽然我准确翻译了“arc”的意思，但是当时就是糊涂。。。然后就不会做了。这里的意思就是存在有向边u->v。

枚举中心点v。

1.每个点都必须有一条指向v的边和从v指向该点的边，统计点v的出入度下就知道这里缺几条边了。

2.因为每个点需要出度2，入度2，再去掉和v连着的两条边，那么只需要出度1，入度1。想象一下，把一个点拆成两个，一个“出点”，一个“入点”。只有从“出点”有 有向边指向“入点”。那么这就是个“二分图”，而我们现在只需要出度1，入度1，所以一个“出点”匹配一个“入点”。做一下二分图最大匹配，就知道最多能保留几条边，多余的边删掉。实际操作的时候不需要真的拆点。

3.删完多余边之后，还有一些点不满足出度1，入度1，还需要再补边。

上面3个步骤需要的操作次数，就是点v为中心点的时候的最小操作次数。

code：

#include <algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <string>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
using namespace std;

#define N  512
#define ll long long
#define ALL(x)     x.begin(),x.end()
#define CLR(x,a)   memset(x,a,sizeof(x))
#define mp    make_pair
#define fir first
#define sec second
typedef pair<int,int> PI;
const int    INF=0x3fffffff;
const int    MOD=1000000007;
/*----------------code-----------------*/
int n,m,in[N],out[N],match[N];
bool g[N][N],vis[N];

bool augment(int v,int u){
	for(int i=1;i<=n;i++){
		if(i==v || !g[u][i] || vis[i]) continue;
		vis[i]=true;
		if(match[i]==-1 || augment(v,match[i])){
			match[i]=u;
			return true;
		}
	}
	return false;
}

int hungary(int v){
	int ans=0;
	CLR(match,-1);
	for(int i=1;i<=n;i++) if(v!=i){
		CLR(vis,0);
	   	if(augment(v,i)) ans++;
	}
	return ans;
}

int solve(int v){
	int vEdges=in[v]+out[v]-g[v][v];
	int ans=2*n-1-vEdges;
	int Max=hungary(v);
	ans+=m-vEdges-Max;
	ans+=n-1-Max;
	return ans;
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		g[x][y]=true;
		in[y]++, out[x]++;
	}
	int ans=INF;
	for(int v=1;v<=n;v++)
		ans=min(ans,solve(v));
	printf("%d\n",ans);
	return 0;
}

E:

题目的意思其实就是每次会移除你选的这段连续区间里最小的数字，而且给的n个数是不重复的。

如果区间[l,r]内最小的数不在b[]里，显然w=r-l+1，然后移除掉这个最小数。

如果在b[]里，设它的位置是pos，那么我们只能去区间[l,pos-1]和[pos+1,r]里继续寻找答案了。

用线段树维护区间最小值，最小值的位置，以及移除操作和统计区间还剩多少个数。

最多n-k次移除操作，复杂度O((n-k)log(n))。

code：

#include <algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <string>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
using namespace std;

#define N  1000100
#define ll long long
#define ALL(x)     x.begin(),x.end()
#define CLR(x,a)   memset(x,a,sizeof(x))
#define mp    make_pair
#define fir first
#define sec second
typedef pair<int,int> PI;
const int    INF=0x3fffffff;
const int    MOD=1000000007;
/*----------------code-----------------*/
int n,m;
bool vis[N];

class segTree{
#define lson (rt<<1)
#define rson (rt<<1|1)
private:
	struct segment{
		int l,r,sum,min;
	}seg[N<<2];
public:
	void pushup(int rt){
		seg[rt].min=min(seg[lson].min,seg[rson].min);
		seg[rt].sum=seg[lson].sum+seg[rson].sum;
	}

	void build(int l,int r,int rt){
		seg[rt].l=l, seg[rt].r=r;
		if(l==r){
			scanf("%d",&seg[rt].min);
			seg[rt].sum=1;
			return ;
		}
		int mid=(seg[rt].l+seg[rt].r)>>1;
		build(l,mid,lson);
		build(mid+1,r,rson);
		pushup(rt);
	}

	int remove(int val,int L,int R,int rt){
		if(seg[rt].l==seg[rt].r){
			if(seg[rt].min!=val) return 0;
			seg[rt].min=INF;
			seg[rt].sum=0;
			return seg[rt].l;
		}
		int pos=0;
		if(L<=seg[rt].l && seg[rt].r<=R){
			if(seg[lson].min==val) pos=remove(val,L,R,lson);
			else if(seg[rson].min==val) pos=remove(val,L,R,rson);
		}else{
			int mid=(seg[rt].l+seg[rt].r)>>1;
			if(L<=mid) pos+=remove(val,L,R,lson);
			if(mid<R) pos+=remove(val,L,R,rson);
		}
		pushup(rt);
		return pos;
	}

	int getSum(int L,int R,int rt){
		if(L<=seg[rt].l && seg[rt].r<=R) return seg[rt].sum;
		int mid=(seg[rt].l+seg[rt].r)>>1,sum=0;
		if(L<=mid) sum+=getSum(L,R,lson);
		if(mid<R) sum+=getSum(L,R,rson);
		return sum;
	}

	int getMin(int L,int R,int rt){
		if(L<=seg[rt].l && seg[rt].r<=R) return seg[rt].min;
		int mid=(seg[rt].l+seg[rt].r)>>1,Min=INF;
		if(L<=mid) Min=min(Min,getMin(L,R,lson));
		if(mid<R) Min=min(Min,getMin(L,R,rson));
		return Min;
	}
}T;

ll solve(int l,int r){
	if(r<l) return 0;
	ll ans=0;
	int val,len=T.getSum(l,r,1);
	if(len==0) return 0;
	while( len && !vis[(val=T.getMin(l,r,1))] ){
		ans+=len--;
		T.remove(val,l,r,1);
	}
	int pos=T.remove(val,l,r,1);
	return ans+solve(l,pos-1)+solve(pos+1,r);
}

int main(){
	scanf("%d%d",&n,&m);
	T.build(1,n,1);
	for(int i=0;i<m;i++){
		int x;
		scanf("%d",&x);
		vis[x]=true;
	}	
	printf("%I64d\n",solve(1,n));
	return 0;
}