天天看点
返回

CF-Education 72(Div.2) A(二分) B(思维+公式) C(思维+暴力) D(思维+DFS染色) E(思维+线段树合并)A. Creating a Character（二分）B. Zmei Gorynich（思维+公式）C. The Number Of Good Substrings（思维+暴力）D. Coloring Edges（思维+DFS染色）E. Sum Queries?（思维+线段树合并）

Contest:https://codeforces.com/contest/1217

这场比赛。。一言难尽。。不出所料的掉惨了QAQ

那天比较困，8点多就睡觉了，半夜正睡觉着，神仙叫我起来打CF了(22：30)，一脸懵逼着就下床报名，然后开始准备，甚至脸都没洗，坐在电脑前发呆。。然后就自闭了QAQ

DE补的也是很艰难(都看了题解才会的QAQ)(F到现在都不会写。感觉好难，就放弃了)

A. Creating a Character（二分）

题目链接：https://codeforces.com/contest/1217/problem/A

题目大意：给出n个人，每个人有m个自由属性点，初始力量和智力属性。把所有自由属性点都分发完，有多少种方法能够使最后的力量属性>智力属性。

思路：总共m+1种分法，我们由于分到的属性按顺序使单调的，所以我直接一个二分就好了。确定分给力量的属性点mid，则智力的就是m-mid，找到第一个（力量+mid）>（智力+m-mid），后面的就都是了。

虽然很轻松就过了，但是我当时已经有不好的预感了，但由于已经交了一发了。。就只好硬着头皮打下去了。。

ACCode：

int main(){
	int T;scanf("%d",&T);
	while(T--){
		ll s,i,e;scanf("%lld%lld%lld",&s,&i,&e);
		ll l=0,r=e,mid;
		while(l<=r){
			mid=(l+r)>>1;
			if(s+mid<=i+(e-mid)) l=mid+1;
			else r=mid-1;
		}
		if(l<=e) printf("%lld\n",e-l+1);
		else printf("0\n");
	}
}

B. Zmei Gorynich（思维+公式）

题目链接：https://codeforces.com/contest/1217/problem/B

题目大意：T组测试数据，每组一条蛇，一开始有x个头，有n种攻击方法。每种攻击方法会先砍掉di个头，但是如果还有头，就会又长出hi个头。判断最少的砍击次数，如果砍不死，就输出-1.同一种砍头方法可以重复使用。

思路：当时看完这道题后，瞬间想到青蛙跳井的问题(跳d高，滑h高)。想到，第二题也稳了，估计掉分不会太惨，但由于脑子混沌+眼瞎，就被卡了。。

我们判断第一次会不会被砍死，判断一下会不会被砍死，最后就是判断多少次了。

我们首先选出砍掉头最多的一组i，容易得出：mxd+k*Cut[i]>=x。这里的mxd就是最多一次砍多少个头，Cut[i]就是最多一组砍多少个头。由于k砍的次数 只能是整数，所以记得+1.

很轻松的推完了公式，自信提交，WA4.。。(WTF??!!)一脸蒙蔽，一直怀疑是式子推错了。。结果是特判输出-1写成输出0了。卡了我40多分钟QAQ。。。结果心态爆炸，就上床继续睡觉了QAQ。。

ACCode：

struct Node{
	int d,h,cut;
};
Node A[MAXN];
 
int Cmp1(Node a,Node b){
	return a.d>b.d;
}
int Cmp2(Node a,Node b){
	return a.cut>b.cut;
}
int main(){
	int T;scanf("%d",&T);
	while(T--){
		int n,x;scanf("%d%d",&n,&x);
		for(int i=1;i<=n;++i){
			scanf("%d%d",&A[i].d,&A[i].h);
			A[i].cut=A[i].d-A[i].h;
		}sort(A+1,A+1+n,Cmp1);//选出最大的 
		int mxd=A[1].d;
		if(A[1].d>=x){
			printf("1\n");continue;
		}
		sort(A+1,A+1+n,Cmp2);//选出最好砍的 
		if(A[1].cut<=0){//必定不会砍掉 
			printf("-1\n");continue;
		}
		int k=(x-mxd)/A[1].cut;
		int ans=k;
		if((x-mxd)%A[1].cut==0){//正好k次+最后一次跳出去了跳出去 
			ans++;
		}
		else{
			ans+=2;
		}
		printf("%d\n",ans);
	}
}

C. The Number Of Good Substrings（思维+暴力）

题目链接：https://codeforces.com/contest/1217/problem/C

题目大意：给出一个01字符串S判断有多少个好字串，好子串p的定义：p.lenth=子串p的二进制数。

思路：思路是学长告诉我的。。

由于最长是2e5，所以子串的长度最长<20所以我们可以枚举了，枚举右端点，枚举前20个，判断是否可以构成一个好子串。至于前面0的个数，可以使用前缀和来判断。恨自己脑子愚笨啊！！

ACCode：

int Pre[MAXN];
char S[MAXN];
 
int main(){
	int T;scanf("%d",&T);
	while(T--){
		scanf("%s",S+1);int len=strlen(S+1);
		for(int i=1;i<=len;++i){
			Pre[i]=Pre[i-1]+S[i]-'0';
		}
		int ans=0;
		for(int i=1;i<=len;++i){//枚举右端点 
			for(int j=i,siz=0,tmp=1;j>=i-20&&j>=1;--j){//从[i-20,i]的区间内有多少个符合条件的区间 
				if(S[j]=='1'){
					siz+=tmp;//[j,i]的大小 
					int pre=siz-(i-j+1);//前面pre个0 
					if(j-1>=pre&&Pre[j-1]-Pre[j-pre-1]==0){//[1,j)>=pre&&
						ans++;
					}
				}tmp<<=1;
			}
		}printf("%d\n",ans);
	}
}

D. Coloring Edges（思维+DFS染色）

题目链接：https://codeforces.com/contest/1217/problem/D

题目大意：给出一个有向图，n个点m条边，判断最少多少种颜色可以将这个图染色，规定一个环不能是一种颜色。

思路：有向图，环不能是一种颜色，所以答案只会在1和2之间。当时想的是从一个点开始，到另一个点结束，中间的边都是1，反着的边都是2.但是一直苦恼怎么判断反着的边。。

赛后看题解：第一次找到节点标记为1，同时该边染色1，退出该节点的DFS标记为2，那么当我们再次碰到一个被标记的节点后，如果该节点为1，说明还没有退出就又被找到了，存在环，则该边标记为2.若该边为2.说明推出后，其他的点能够再次访问到该节点但是是在上面的，所以边标记为1。

ACCode：

const int MAXN=5e3+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const ll MOD=1e4+7;
const double PI=acos(-1.0);
const double EPS=1.0e-8;
//unsigned register
// ios::sync_with_stdio(false)
 
 
struct Edge1{
	int v,id,nxt;
	Edge1(int _v=0,int _id=0,int _nxt=0){
		v=_v;id=_id;nxt=_nxt;
	}
};
Edge1 Edge[MAXN<<2];
int Head[MAXN],Ecnt;
int Col[MAXN],Ans[MAXN];
int flag;
int n,m;
 
void Intt(){
	clean(Head,-1);Ecnt=0;
	flag=0;
}
void AddEdge(int u,int v,int id){
	Edge[Ecnt]=Edge1(v,id,Head[u]);
	Head[u]=Ecnt++;
}
void DFS(int u){
	Col[u]=1;
	for(int i=Head[u];i+1;i=Edge[i].nxt){
		int v=Edge[i].v,id=Edge[i].id;
		if(Col[v]==0){
			DFS(v);
			Ans[id]=1;
		}
		else if(Col[v]==2) Ans[id]=1;
		else{
			Ans[id]=2;
			flag=1;
		}
	}Col[u]=2;
}
int main(){
	Intt();
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		int u,v;scanf("%d%d",&u,&v);
		AddEdge(u,v,i);
	}
	for(int i=1;i<=n;++i){
		if(Col[i]==0) DFS(i);
	}
	printf("%d\n",flag?2:1);
	for(int i=1;i<=m;++i) printf("%d ",Ans[i]);printf("\n");
}

E. Sum Queries?（思维+线段树合并）

题目链接：https://codeforces.com/contest/1217/problem/E

题目大意：给出n个元素组成的数组，有两种操作：1.将a[i]修改为val。2.查询[l,r]中的最小的不平衡元素。

不平衡元素定义：多个元素相加得到一个Sum，如果存在某一位，Sum有但是组成Sum的元素中对应位置没有相等的数字，那么就是不平衡的。

CF-Education 72(Div.2) A(二分) B(思维+公式) C(思维+暴力) D(思维+DFS染色) E(思维+线段树合并)A. Creating a Character（二分）B. Zmei Gorynich（思维+公式）C. The Number Of Good Substrings（思维+暴力）D. Coloring Edges（思维+DFS染色）E. Sum Queries?（思维+线段树合并）

如例子。红色的是存在，很明显第二个的第二位不存在，因此是不平衡的。

题解思路(直接看的题解)：很明显，如果存在多个元素的组合，那么必定存在2个元素的组合，如果两两组合都是平衡的话，必定整个序列是平衡的。因为a+b==c%10的话，必定有一个是0，因为进位的话会造成下一个数不平衡。如果多个元素不平衡，那么可以去掉除了不平衡位置的两个元素的另外的元素。

所以我们就可以将问题转化成求序列[l,r]种找2个元素使之不平衡。维护最多9位。因此维护9个数位。每个数位记录最小的该位置存在值的最小值。合并的时候，更新ans，枚举9个数位，取最小的值。

ACCode：

#include<stdlib.h>
#include<string.h>
#include<stdio.h>
#include<time.h>
#include<math.h>
// srand((unsigned)time(NULL));rand();
 
#include<map>
#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<bitset>
#include<string>
#include<fstream>
#include<iostream>
#include<algorithm>
 
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define clean(a,b) memset(a,b,sizeof(a))
using namespace std;
      
const int MAXN=2e5+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const ll MOD=1e9+7;
const double PI=acos(-1.0);
const double EPS=1.0e-8;
//unsigned register
// ios::sync_with_stdio(false)
 
struct SegTree{
	struct Node{
		int l,r;
		ll ans,mi[10];
		friend Node operator + (Node a,Node b){
			Node tmp;
			tmp.l=min(a.l,b.l);tmp.r=max(a.r,b.r);
			tmp.ans=min(a.ans,b.ans);
			for(int i=0;i<=9;++i){
				tmp.ans=min(tmp.ans,a.mi[i]+b.mi[i]);
				tmp.mi[i]=min(a.mi[i],b.mi[i]);
			}return tmp;
		}
	};
	Node Tree[MAXN<<2];
	
	void PushUp(int rt){
		Tree[rt]=Tree[rt<<1]+Tree[rt<<1|1];
	}
	void Build(int l,int r,int rt,ll A[]){
		Tree[rt].l=l;Tree[rt].r=r;
		if(l==r){
			Tree[rt].ans=INF64;
			for(ll i=0,j=1;i<=9;++i,j*=1ll*10){//第i位是否存在值 
				Tree[rt].mi[i]=A[l]/j%10?A[l]:INF64;
			}return ;
		}int mid=(l+r)>>1;
		Build(l,mid,rt<<1,A);Build(mid+1,r,rt<<1|1,A);
		PushUp(rt);
	}
	void Update(int pos,int val,int rt){
		if(Tree[rt].l==Tree[rt].r){
			Tree[rt].ans=INF64;
			for(ll i=0,j=1;i<=9;++i,j*=1ll*10){
				Tree[rt].mi[i]=val/j%10?val:INF64;
			}return ;
		}
		if(pos<=Tree[rt<<1].r) Update(pos,val,rt<<1);
		else Update(pos,val,rt<<1|1);
		PushUp(rt);
	}
	Node Query(int ql,int qr,int rt){
		if(ql<=Tree[rt].l&&Tree[rt].r<=qr) return Tree[rt];
		if(qr<=Tree[rt<<1].r) return Query(ql,qr,rt<<1);
		else if(ql>=Tree[rt<<1|1].l) return Query(ql,qr,rt<<1|1);
		else{
			return Query(ql,qr,rt<<1)+Query(ql,qr,rt<<1|1);
		}
	}
};
SegTree Seg;
ll A[MAXN];
int n,m;
 
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%lld",&A[i]);
	}Seg.Build(1,n,1,A);
	for(int i=1;i<=m;++i){
		int opt;scanf("%d",&opt);
		if(opt==1){//单点更新 
			int pos,val;scanf("%d%d",&pos,&val);
			Seg.Update(pos,val,1);
		}
		else{//区间查询 
			int l,r;scanf("%d%d",&l,&r);
			int ans=(MAXN<<2)-2;Seg.Tree[ans]=Seg.Query(l,r,1);
			printf("%lld\n",Seg.Tree[ans].ans==INF64?-1:Seg.Tree[ans].ans);
		}
	}
	
}
程序设计竞赛记录
上一篇: DFS序学习
下一篇: poj 1979（DFS）

继续阅读