G. 在大学里安排座位是否搞错了什么[BNUZ-TI节ACM新生网络赛]

G. 在大学里安排座位是否搞错了什么

• 本题本准备卡暴力的，但是因为考虑java选手减小了数据。因此本题暴力可解。
• 考察：滑动窗口，双向队列
• 滑动窗口可以将嵌套的循环问题，转换为单循环问题，降低时间复杂度。

• 本题思路：

  将题目归纳得：给出一个长为n的字符串，有两个操作，操作二是读取第x位的字符串。操作一是翻转包括x的之后m个字符。

  对于操作一来说，大量的遍历是很容易TLE的，所以最好的选择是不翻转字符串，而是利用一个flag判断当前要从子串的哪端读取 来模拟翻转，这样可以在大数据的情况下极大的减少时间复杂度。

  因此可以新创建一个环形队列或者双向队列来储存子串。如图

  

  当读取到被反转的那段字符串时先判断flag的值，再从新的数组读取相对位置的字符。

  又因为题中有保证x1<=x2<=x3<=….<=n-m+1，因此就是持续向右的滑动，滑动的操作也是将此时子串的 “左端” 取出插入到相应位置，然后取值插入子串相应的”右端“

• 下面是滑动窗口的举例（最开始的flag为0），演示这里使用的是环形队列

  

  

  

  

  

一血：星澈(1701010075)

标程：

• 算法：

  #include<bits/stdc++.h>
  using namespace std;
  
  const int maxn = 1e6 + 500;
  
  int n,m,q,swq,now;
  
  char s[maxn],str[maxn];
  
  int main(){
      int count = 1;
      while(~scanf("%d %d %d",&n,&m,&q)){
          swq = 0;
          now = 0;
          
          deque<char>dq;
          scanf("%s",str);
          strcpy(s+1,str);
          
          cout<<"Case #"<<count++<<":"<<endl;
          
          for(int i=1;i<=m;i++){
              
              dq.push_back(str[i-1]);
          }
          now=1;
                  
          for(int i=1;i<=q;i++){
              int op,id;scanf("%d%d",&op,&id);
              if(op==2){
                  if(id<now||id>now+m-1)putchar(s[id]);
                  else{
                      id-=now;
                      if(swq)putchar(dq[m-1-id]);
                      else putchar(dq[id]);
                  }
              }
              else{
                  while(now<id){
                      if(swq){
                          s[now]=dq.back();
                          dq.pop_back();
                          dq.push_front(str[now+m-1]);
                      }
                      else{
                          s[now]=dq.front();
                          dq.pop_front();
                          dq.push_back(str[now+m-1]);
                      }
                      now++;
          //                for(auto x:dq)cout<<x<<" ";puts("");
                  }
                  swq^=1;
              }
          }
          cout<<endl;
      }
  }

• 暴力：

  #include<stdio.h>
  #include<iostream>
  #include<string.h>
  #include<vector>
  #include<algorithm>
  
  using namespace std;
  
  int main() {
      ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
      int n,m,q,cas=1,op,pos;
      char ch[1000005];
      while(cin >> n >> m >> q) {
          cin >> ch;
          vector<char> v;
          for(int i=0; i<strlen(ch); i++) {
              v.push_back(ch[i]);
          }
          printf("Case #%d:\n",cas++);
          for(int i=0; i<q; i++) {
              cin >> op >> pos;
              if(op==2) {
                  printf("%c",v[pos-1]);
              } else {
                  reverse(v.begin()+pos-1,v.begin()+pos+m-1);
              }
          }
          puts("");
  
      }
  }