博客

【校内测】千纸鹤

题目

原题来自：CF

解题思路

其实暴力模拟操作是有70的

但是我当时懒得想，然后没打。。。

翻折次数越多，长度就会越多

要解决的就是如果对折点超过长度的一半，时间花费太多

可以转变为翻转后再翻折，那折的长度就变短了

打标价是否翻转了，确定当前的翻折点

PS 数组存的是区间，而不是坐标，例x=3，那么应该是将3翻到4那

程序

#include<iostream>
#include<cstring> 
#include<cstdio>
using namespace std;
int n,m,op,x,k,l,r,fla,a[10000100];
int main()
{
	freopen("paper.in","r",stdin);
	freopen("paper.out","w",stdout);
	scanf("%d%d",&n,&m);
	r=n;
    for (int i=0;i<n;i++) a[i]=1;
	for (int i=1;i<=m;i++) 
	{
		scanf("%d%d",&op,&x);
		if (op) 
		{
		   if (fla) x=r-l-x-1;
		   printf("%d\n",a[l+x]);
		   continue;
	    }
	    else {
	       if (fla) x=r-l-x;
	       if (x*2>r-l)
	       {
	       	  fla=1;  //标记翻转
	       	  for (int i=0;i<r-l-x;i++)
	       	      a[l+x-i-1]+=a[l+x+i];  //从右往左折
	       	  r=l+x;
		   }
		   else 
		   {
		   	  fla=0;  //没有翻转，去标记
		      for (int i=0;i<x;i++)
		          a[l+x+i]+=a[l+x-i-1];
			  l=l+x;
		   }
	    }
	}
	return 0;
}