首页 > 代码库 > Codeforces Round #263 (Div. 1) C. Appleman and a Sheet of Paper
Codeforces Round #263 (Div. 1) C. Appleman and a Sheet of Paper
题目地址:http://codeforces.com/contest/461/problem/C
题目大意:见原题。
算法分析:启发式暴力,每次把短的纸带折到长的纸带中,在全局记一个rev标记。注意细节。
Code:
#include <cstdio> #include <algorithm> #define N 100000 using namespace std; bool rev; int n,q,beg=1,end,typ,p,l,r,bit[N+10]; inline void add(int x,int y){ for (;x<=n;x+=x&-x) bit[x]+=y; } inline int query(int x){ int res=0; for (;x;x-=x&-x) res+=bit[x]; return res; } int main(){ scanf("%d%d",&n,&q); for (int i=1;i<=n;++i) add(i,1); end=n; for (int i=1;i<=q;++i){ scanf("%d",&typ); if (typ==1){ scanf("%d",&p); if (p<=(end-beg+1)/2) if (rev){ p=end-p; for (int j=end;j>p;--j) add(2*p-j+1,query(j)-query(j-1)); end=p; } else{ p+=beg-1; for (int j=beg;j<=p;++j) add(2*p-j+1,query(j)-query(j-1)); beg=p+1; } else{ if (rev){ p=end-p; for (int j=beg;j<=p;++j) add(2*p-j+1,query(j)-query(j-1)); beg=p+1; } else{ p+=beg-1; for (int j=end;j>p;--j) add(2*p-j+1,query(j)-query(j-1)); end=p; } rev^=1; } } else{ scanf("%d%d",&l,&r); if (rev) l=end-l,r=end-r;else l+=beg-1,r+=beg-1; if (l>r) swap(l,r); printf("%d\n",query(r)-query(l)); } //<debug> /*puts(""); for (int j=beg;j<=end;++j) printf("--");puts(""); for (int j=beg;j<=end;++j) printf("%d ",query(j)-query(j-1));puts(""); for (int j=beg;j<=end;++j) printf("--");puts(""); printf("BEGIN @ %d END @ %d REV %s\n",beg,end,rev?"Y":"N"); puts("");*/ //</debug> } return 0; }
By Charlie Pan
Aug 27,2014
Codeforces Round #263 (Div. 1) C. Appleman and a Sheet of Paper
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。