• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

CodeforcesRound#449[C/A.Nephrengivesariddle][D/B.ItheaPlaysWithChtholly]

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

PROBLEM C/A. Nephren gives a riddle

  http://codeforces.com/contest/896/problem/A

  codeforces 896a 897c

  预第i个串的长度,由于k最大1e18,所以超过1e18的长度直接标记为无限大,不用计算

  然后递归搜索即可

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

using namespace std;

typedef long long ll;

const ll INF=3e18;
const ll M=1e4+44;
const ll N=1e5+44;

char f0[M]={"What are you doing at the end of the world? Are you busy? Will you save us?"};
char s1[M]={"What are you doing while sending \""};
char s2[M]={"\"? Are you busy? Will you send \""};
char s3[M]={"\"?"};
ll lf0,ls1,ls2,ls3;
ll q;
ll len[N];

char solve(ll n,ll k)
{
	if(n==0)
		return f0[k-1];
	if(k<=ls1)
		return s1[k-1];
	k-=ls1;
	if(k<=len[n-1])
		return solve(n-1,k);
	k-=len[n-1];
	if(k<=ls2)
		return s2[k-1];
	k-=ls2;
	if(k<=len[n-1])
		return solve(n-1,k);
	k-=len[n-1];
	return s3[k-1];
}

int main()
{
	ll n,k;
	lf0=strlen(f0);
	ls1=strlen(s1);
	ls2=strlen(s2);
	ls3=strlen(s3);
	len[0]=lf0;
	for(ll i=1;i<=100000;i++)
		len[i]=3e18;
	for(ll i=1;i<=100000;i++)
	{
		len[i]=len[i-1]*2+ls1+ls2+ls3;
		if(len[i]>1e18)
			break;
	}
	scanf("%I64d",&q);
	while(q--)
	{
		scanf("%I64d%I64d",&n,&k);
		if(k>len[n])
			cout<<".";
		else cout<<solve(n,k);
	}
	return 0;
}

  

 

 

PROBLEM D/B. Ithea Plays With Chtholly

  http://codeforces.com/contest/896/problem/B

  codeforces 986b 897d

  从第一个位置开始维持一个从左到右不下降的序列,记为左序列;从左右一个位置开始维持一个从右到左不上升的序列,记为右序列

  取中间值midpi=c/2,每次取到一个数,如果这个数小于等于midpi,放入左边的序列,并且维持左序列从左到右不下降;

  如果这个数大于midpi,放入右序列,并且维持右序列从右到左不上升。

  相遇即是成功

  这样最坏情况不超过题目要求

 

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

using namespace std;

const int M=1e3+44;

int n,m,c,num,midpi;
int mp[M];
int s[M],li1,li2,ri1,ri2,flagli,flagri;

bool check()
{
//	for(int j=1;j<=n;j++)
//		cout<<s[j]<<' ';
//	cout<<endl;
	for(int i=1;i<=n;i++)
		if(s[i]==-1)
			return false;
	for(int i=1;i<n;i++)
		if(s[i]>s[i+1])
			return false;
//	cout<<"true"<<endl;
	return true;
}

void xf()
{
	fflush(stdout);
	scanf("%d",&num);
}

bool answer(int ans)
{
	printf("%d\n",ans);
	s[ans]=num;
	if(check())
	{
		fflush(stdout);
		return true;
	}
	else
	{
		fflush(stdout);
		scanf("%d",&num);
		return false;
	}
}

void init()
{
	int a,b,pi=0;
	a=c/n; b=c%n;
	for(int i=1;i<=b;i++)
		for(int j=1;j<=a+1;j++)
			mp[++pi]=i;
	for(int i=b+1;i<=n;i++)
		for(int j=1;j<=a;j++)
			mp[++pi]=i;
}

void solve()
{
//	init();
	memset(s,-1,sizeof(s));
	int flag;
	midpi=c/2;
	li1=1; li2=n/2; ri1=li2+1; ri2=n;
	flagli=flagri=0;
	for(int i=1;i<=m;i++)
	{
//		cout<<"id:"<<i<<endl;
		if(num<=midpi)
		{
			for(int j=li1;j<=ri2;j++)
				if(s[j]==-1 || s[j]>num)
					if(answer(j))
						return ;
					else break;
		}
		else
		{
			for(int j=ri2;j>=li1;j--)
				if(s[j]==-1 || s[j]<num)
					if(answer(j))
						return ;
					else break;
		}
	}
}

int main()
{
	scanf("%d%d%d",&n,&m,&c);
	xf();
	solve();
	return 0;
}


/*

3 12 7
4
5


*/

  

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
[转](.NETCoreC#)AESEncryption发布时间:2022-07-13
下一篇:
c#原子操作发布时间:2022-07-13
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap