首页 > 代码库 > codeforces 461C

codeforces 461C

2024-07-20 15:45:56   219人阅读

这题说的是 给了一张长方形的纸 1*n 然后可以按照不同的做法去折这个纸张 他有两种操作，操作1 给了一个pi 点 然后将左边的纸往右边折，第2种操作是给了一个L 和 R 然后计算出 L和R 之间的纸如果 切成单位长度有多少块, 开一个标记数组记录方向然后枚举将每位的值复制到相对应的地方，然后用树状数组不断地去维护，记得如果切的点在目前的最左区间和最右区间的二分一靠右的地方那么记得折的变成右边方向记得记录一下，然后再同样的用树状数组去维护

#include <iostream>#include <cstdio>#include <string.h>using namespace std;const int MAX_N = 100005;int C[MAX_N],n;int lowbit(int x){  return x&(-x);}int sum(int x){    int ans =0;    while(x>0){        ans+= C[x];        x-=lowbit(x);    }   return ans;}void add(int x, int d){    while(x<=n){         C[x]+=d;         x+=lowbit(x);    }}int main(){       int q,L,R,turn=0;       scanf("%d%d",&n,&q);      R = n,L=0;       for(int i=1 ; i<=n; i++)         add(i,1);       for(int cc=0 ; cc< q; ++cc){           int op,a,b;           scanf("%d",&op);           if(op==1){              scanf("%d",&a);              int Len = R -L;              if( ( a>Len/2 && turn==0 ) ){                    int LEN = Len-a;                    a = R-LEN;                  for(int loc = 1; loc <= LEN; ++loc ){                       int E = sum( a+loc ) - sum(a+loc-1);                       add(a-loc+1,E);                  }                  turn=1;                  R = a;                  continue;              }              if( (a<=Len/2 &&turn == 1 ) ){                   int LEN = a;                   a = R - LEN;                  for(int loc =1 ;loc <= LEN; ++loc){                      int E = sum(a+loc) -sum(a+loc-1);                      add(a-loc+1,E);                  }                  R=a;                  continue;              }              if( (a>(Len/2)&& turn==1)){                   int LEN = Len - a;                    a = L+LEN;                   for(int loc =0; loc < LEN ; ++loc){                        int E = sum( a - loc ) -sum(a-loc-1);                        add(a+loc+1,E);                   }                   L=a;                   turn=0;                   continue;              }              if(a<=Len/2 && turn == 0 ){                   int LEN = a;                   a=L+a;                   for(int loc =0 ; loc <LEN; ++ loc){                        int E = sum(a-loc) -sum(a-loc -1);                        add(a+loc+1,E);                   }                  L=a;                  continue;              }           }else{               scanf("%d%d",&a,&b);                int ans;               if(turn==0){                ans = sum(L+b)-sum(L+a);               }else {                  ans = sum(R-a) -sum(R-b);               }               printf("%d\n",ans);           }        }       return 0;}
View Code

 

codeforces 461C


联系
我们