Educational Codeforces Round 22 真·辣鸡题?


最近码力严重下降,只能通过不断刷题康复式训练……

最近计划将注意力放到Codeforces上来……


A:模拟

题目大意:某小同学一共要写N道题,每道题都需要A[i]时间完成。OJ只在l[i]~r[i]时间(有多段时间)内开放提交,提交不占用时间且一次性可以提交多道题。问至少需要多少时间才能提交完所有题。

喜闻乐见的A……

我们直接累加所有的时间,最终得到的就是一个总和。我们只需要在这个时间之后OJ最早开放的时候提交所有题目就可以了。

不过并没有1A......还是特判方式出现了问题(lll¬ω¬)注意在每次获得一个 区间的时候先判断这段区间内是否能够提交,我当时太困写的是if(tot>=inl&&tot<=inr) printf("%d",tot); 于是就出现了一系列的问题……如果总和小于这段区间的左端点我们就在左端点提交就好了,在判断能否提交的时候跟左端点一点关系其实也没有……

#include <cstdio>
int max(int tx,int ty){return tx<ty?ty:tx;}
int n,m,inl,inr,tot;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&inl);
		tot+=inl;
	}
	scanf("%d",&m);
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d",&inl,&inr);
		if(tot<=inr)
		{
			printf("%d",max(tot,inl));
			return 0;
		}
	}
	printf("-1");
	return 0;
}

 


B:模拟

题目大意:对于常量x,y,变量a,b(非负整数),问[l,r]区间内最长的满足所有整数i!=x^a+y^b的子区间中最长的长度。

B也是很有意思的……最开始看到数据范围0<=l,r,x,y<=10^18还以为是数论果断放弃……果然23:00答题脑子抽风几率比较大……

我们发现即便对于最大的r=10^18,最小的(有多组解的)x=2,也最多只可能有不到100个,两个的话最多可能搭配也只有10000种不到……直接枚举就好了= =

但是10^18的最大变量大小使得情况极度复杂:

  1. 中间变量和全局变量必须全是long long!(CF第六个点)(别问我咋知道的)
  2. 在我们枚举的时候必须要找到所有的x^a满足其<=r+1。但是x可能是long long范围内的,如果我们暴力乘一下然后进行判断的话可能乘这个操作也没法完成。如果乘的时候爆ll的话自然就会RE。解决方案就是我们用需要滴答的最大值除一下此时得到的乘方值,判断一下需不需要(可不可以)再去乘一下,使指数+1了。(CF第16(x),17(y)个点)(别问我为啥知道的如此清楚)
  3. 记得在不可达的集合里面加入l-1和r+1,这样的话直接枚举每一段区间(排序后枚举每两个相邻的不可达元素)就可以了。(CF第15个点)

最后我们就得到喜闻乐见的答案了……

#include <cstdio>
#include <algorithm>
using namespace std;
long long ans,x,y,l,r,cannot[100100],tmp[1100];
int main()
{
	scanf("%lld%lld%lld%lld",&x,&y,&l,&r);
	long long val=1;
	while(val<=r+1)
	{
		tmp[++tmp[0]]=val;
		if(double((r+1)/val)<x) break;
		val*=x;
	}
	val=1;
	while(val<=r+1)
	{
		for(int i=1;i<=tmp[0];++i)
		{
			long long res=val+tmp[i];
			if(res<=r+1) cannot[++cannot[0]]=res;
		}
		if(double((r+1)/val)<y) break;
		val*=y;
	}
	cannot[++cannot[0]]=l-1;
	cannot[++cannot[0]]=r+1;
	sort(cannot+1,cannot+cannot[0]+1);
	for(int i=1;i<cannot[0];++i)
		if(cannot[i]>=l-1&&cannot[i+1]<=r+1)
		{
			ans=max(ans,cannot[i+1]-cannot[i]-1);
		}
	printf("%lld",ans);
	return 0;
}

C:树上问题

题目大意:一个树,小A最开始在1号root节点,小B最开始在x号节点,小B先开始走,目的是远离小A,小A后走,目的是追上小B。每一步两人可以走到相邻的节点或在原地等着。问最长多少次之后A可以追上B.

我们讨论两种情况。x一定在1下面,所以一定是1点的A向下一个劲的走,不可能停下吧= =此时B也绝对不会往上走去迎接A吧= =最终的结果一定是B到角落里了(最底层)没法走了,等着A来吃= =所以他一定会想办法逃到深度尽可能大的地方。此时可能的最大的时间就是B逃到最深处,此时的答案就是树的深度x2。(这就是我第一次提交的答案,WA在第8个点)

但是我们想,B一个劲往下走当然不一定时间最长,因为D所在子树不应顶就是最深的。所以B还能怎么做?他只能向上迎一下A(也是很不情愿的)。易知B可以达到最多小于x所在深度/2这一深度,再走就会和A碰上。我们想如果此时我们对于向上走的某一时刻调头向下,是不是就可能进入新的子树了?而且因为A还是没有改变路线,最终的时间就是A最终和B相遇的深度x2.

所以我们进行两次DFS.第一次标记depth,同时确定每一个点的父亲(类似并查集)之后再进行一次DFS目的是求出A正常访问B的路径上的点如果不走这条访问路径可能达到的最大深度。之后我们求出所有可以调头向下的点的最大深度,之后求最大值就结束了。

代码是比赛时写的比较丑见谅。

#include <bits/stdc++.h>
using namespace std;
queue<int> q;
int ans,cnt,n,x,inx,iny,depth[200010],deepest[200010],to[400010],nex[400010],head[200010];
bool onroute[200010];
void addedge(int tx,int ty)
{
	to[++cnt]=ty,nex[cnt]=head[tx],head[tx]=cnt;
	to[++cnt]=tx,nex[cnt]=head[ty],head[ty]=cnt;
	return;	
}
void dfs(int pos,int from,int deep)
{
	depth[pos]=deep;
	for(int i=head[pos];i;i=nex[i])
		if(to[i]!=from)
			dfs(to[i],pos,deep+1);
	return;
}
void dfsb(int pos,int from,int deep)
{
	deepest[pos]=1;
	for(int i=head[pos];i;i=nex[i])
		if(to[i]!=from)
		{
			dfsb(to[i],pos,deep+1);
			if(!onroute[to[i]]||onroute[pos]) deepest[pos]=max(deepest[pos],deepest[to[i]]+1);
		}
	return;
}
bool seekpoint(int pos,int from)
{
	if(depth[pos]>depth[x]) return false; 
	if(pos==x) return true;
	int tmp=false;
	for(int i=head[pos];i;i=nex[i])
		if(to[i]!=from&&seekpoint(to[i],pos))
		{
			tmp=true;
			break;
		}
	if(tmp) onroute[pos]=true;
	if(tmp&&depth[pos]>(depth[x]>>1)) q.push(pos);
	return tmp;
}
int main()
{
	scanf("%d%d",&n,&x);
	for(int i=1;i<n;++i) scanf("%d%d",&inx,&iny),addedge(inx,iny);
	dfs(1,0,0);
	seekpoint(1,0);
	dfsb(1,0,0);
	q.push(x);
	while(!q.empty())
	{
		int tmp=q.front();
		q.pop();
		ans=max(ans,(deepest[tmp]+depth[tmp]-1)<<1);
	}
	printf("%d",ans);
	return 0;
}

D:奥♂妙重重DP

题目大意:给你一个序列,请求出它的两个子序列,使得:1.他们没有交集。2.他们的每两个相邻元素之间的差=1或者差的绝对值为7的倍数。

奥妙重重的DP......已经弃疗看题解可是我还没看懂……再说再说QwQ


E,F Ongoing,敬请期待!

声明:TonyZhao's Home|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - Educational Codeforces Round 22 真·辣鸡题?


不骗了,不骗了。
A Simple OIer fighting tooth and nail.