Tag: Bitmask

Manhattan Wiring

RegMs If Leave a comment

题目描述

There is a rectangular area containing $n \times m$ cells. Two cells are marked with “2”, and another two with “3”. Some cells are occupied by obstacles. You should connect the two “2”s and also the two “3”s with non-intersecting lines. Lines can run only vertically or horizontally connecting centers of cells without obstacles.
Lines cannot run on a cell with an obstacle. Only one line can run on a cell at most once. Hence, a line cannot intersect with the other line, nor with itself. Under these constraints, the total length of the two lines should be minimized. The length of a line is defined as the number of cell borders it passes. In particular, a line connecting cells sharing their border has length $1$.
Fig. 1(a) shows an example setting. Fig. 1(b) shows two lines satisfying the constraints above with minimum total length $18$.
Example

题意概述

给定一张$n \times m$的有障碍矩阵，其中恰有两个2和两个3，其余有些格子上有障碍。求分别连接两个2和两个3的两条不相交路径长度之和的最小值。
数据范围：$1 \le n, m \le 9$。

算法分析

插头DP，维护一排插头，令$f_{i, j, s}$表示处理到第$i$行第$j$列的格子且插头的状态为$s$时的最小值，根据当前格子的状态进行相应的转移。

代码

#include <cstdio>
#include <cstring>

void minify(short &a, short b) {
  a > b && (a = b);
}

static const int N = 11;
int rec[1 << 20];
short mp[N][N], f[2][N][1 << 20]; // 0 for no wire, 2 for wire 2, 3 for wire 3

int modify(int s, int p, int v) {
  return (s & ((1 << (p << 1)) - 1)) | (((s >> ((p + 1) << 1) << 2) + v) << (p << 1));
}

int query(int s, int p) {
  return s >> (p << 1) & 3;
}

int main() {
  int n, m, top = 0;
  for (int i = 0; i < 1 << 20; ++ i) {
    for (int j = 0; j < N; ++ j) if (query(i, j) == 1) goto illegal;
    rec[top ++] = i; illegal: ;
  }
  while (scanf("%d%d", &n, &m), n) {
    for (int i = 0; i < n; ++ i)
      for (int j = 0; j < m; ++ j) scanf("%hd", &mp[i][j]);
    int cur = 0; memset(f, 0x3f, sizeof f), f[cur][0][0] = 0;
    for (int i = 0; i < n; ++ i, cur ^= 1) {
      for (int j = 0; j < m; ++ j)
        for (int _ = 0, k = rec[0]; _ < top; k = rec[++ _])
          if (f[cur][j][k] < 10000) {
            int p = query(k, j), q = query(k, j + 1);
            if (mp[i][j] == 0) {
              if (! p && ! q)
                minify(f[cur][j + 1][k], f[cur][j][k]),
                minify(f[cur][j + 1][modify(modify(k, j, 2), j + 1, 2)], f[cur][j][k] + 1),
                minify(f[cur][j + 1][modify(modify(k, j, 3), j + 1, 3)], f[cur][j][k] + 1);
              else if (! p ^ ! q)
                minify(f[cur][j + 1][modify(modify(k, j, p + q), j + 1, 0)], f[cur][j][k] + 1),
                minify(f[cur][j + 1][modify(modify(k, j, 0), j + 1, p + q)], f[cur][j][k] + 1);
              else if (p && p == q)
                minify(f[cur][j + 1][modify(modify(k, j, 0), j + 1, 0)], f[cur][j][k] + 1);
            } else if (mp[i][j] == 1) {
              if (! p && ! q) minify(f[cur][j + 1][k], f[cur][j][k]); 
            } else {
              if (! p && ! q)
                minify(f[cur][j + 1][modify(k, j, mp[i][j])], f[cur][j][k] + 1),
                minify(f[cur][j + 1][modify(k, j + 1, mp[i][j])], f[cur][j][k] + 1);
              else if (p == mp[i][j] && ! q)
                minify(f[cur][j + 1][modify(k, j, 0)], f[cur][j][k] + 1);
              else if (! p && q == mp[i][j])
                minify(f[cur][j + 1][modify(k, j + 1, 0)], f[cur][j][k] + 1);
            }
          }
      for (int _ = 0, k = rec[0]; _ < top; k = rec[++ _])
        if (! query(k, m)) minify(f[cur ^ 1][0][k << 2 & (1 << ((m + 1) << 1)) - 1], f[cur][m][k]);
      for (int j = 0; j <= m; ++ j)
        for (int _ = 0, k = rec[0]; _ < top; k = rec[++ _]) f[cur][j][k] = 16000;
    }
    printf("%d\n", f[cur][0][0] < 10000 ? f[cur][0][0] - 2 : 0);
  }
  return 0;
}

Another Chocolate Maniac

RegMs If Leave a comment

题目描述

Bob really LOVES chocolate. He thinks he never gets enough. Imagine his joy when his parents told him that they would buy him many rectangular chocolate pieces for his birthday. A piece of chocolate is a $2 \times 1$ or $1 \times 2$ rectangle. Bob’s parents also bought him a nice birthday cake, which can be imagined as a matrix having $M$ rows and $N$ columns. Some positions on the cake are occupied by candles, the others are empty. Bob’s parents asked their son to place as many chocolate pieces as he can on the empty squares on the cake, in such a manner that no two chocolate pieces overlap. However, he would like to keep the chocolate pieces to himself. That’s why, he wants to place only a minimal amount of them on the cake and keep the rest. In order not to make Mon and Dad suspicious, Bob wants to place the chocolate pieces in such a way, that no other piece may be placed on the cake (that is, there won’t exist any two adjacent empty squares). Find the minimal number of pieces which need to be placed on the cake, so that they do not overlap and no extra piece may be added.

题意概述

给定一个$M \times N$的网格，其中有些格子是满的。要求用$2 \times 1$和$1 \times 2$两种方块填充空格子，使得不存在两个相邻的空格子。求至少需要多少方块。
数据范围：$1 \le M \le 70, \; 1 \le N \le 7$。

算法分析

令$f_{i, j, k}$表示处理到第$i$行，第$(i-1)$行的状态为$j$且第$i$行的状态为$k$的方案数。转移时要注意判断上下两行是否有相邻的空格子。

代码

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

using namespace std;

namespace std {
  template <typename T> void maxify(T &a, T b) { b > a && (a = b); }
  template <typename T> void minify(T &a, T b) { b < a && (a = b); }
}

struct IOManager {
  template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); }
  inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; }
  inline int read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); }
  template <typename T> inline IOManager operator > (T &x) { read(x); return *this; }
  template <typename T> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }
  inline void write(char c) { putchar(c); }
  inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); }
  template <typename T> inline IOManager operator < (T x) { write(x); return *this; }
} io;

struct Solver {
private:
  static const int N = 80;
  static const int M = 8;
  int n, m, f[2][1 << M][1 << M], mp[N];
  void input() {
    io > n > m;
    for (int i = 1; i <= n; ++ i)
      for (int j = 1; j <= m; ++ j) {
        char c; io > c, (mp[i] <<= 1) += c == '*';
      }
    mp[0] = mp[n + 1] = mp[n + 2] = (1 << m) - 1;
  }
  void init() { memset(f, 0x1f, sizeof f), f[0][mp[0]][mp[1]] = 0; }
  bool check(int s) {
    bool flag = false;
    for (int i = 0; i < m; s >>= 1, ++ i) {
      if (s & 1) flag = false;
      else { if (flag) return false; flag = true; }
    }
    return true;
  }
  void update(int x, int a, int b, int s, int val, int p) {
    if (check(b) && ! ((1 << m) - 1 - a & (1 << m) - 1 - b)) minify(f[x][b][s], val);
    for (int i = p; i < m; ++ i)
      if (! (b & 1 << i)) {
        if (! (s & 1 << i)) update(x, a, b | 1 << i, s | 1 << i, val + 1, i + 1);
        if (i && ! (b & 1 << i - 1)) update(x, a, b | 1 << i | 1 << i - 1, s, val + 1, i + 1);
      }
  }
  void process() {
    int cur = 0;
    for (int i = 1; i <= n + 1; cur ^= 1, ++ i) {
      memset(f[cur ^ 1], 0x1f, sizeof f[cur ^ 1]);
      for (int j = 0; j < 1 << m; ++ j)
        for (int k = 0; k < 1 << m; ++ k)
          if (f[cur][j][k] < 5e8) update(cur ^ 1, j, k, mp[i + 1], f[cur][j][k], 0);
    }
    io < f[cur][(1 << m) - 1][(1 << m) - 1] < '\n';
  }

public:
  void solve() { input(), init(), process(); }
} solver;

int main() {
  solver.solve();
  return 0;
}

Hardwood Floor

RegMs If Leave a comment

题目描述

The banquet hall of Computer Scientists’ Palace has a rectangular form of the size $M \times N$. It is necessary to lay hardwood floors in the hall. There are wood pieces of two forms:

  • rectangles ($2 \times 1$)
  • corners (squares $2 \times 2$ without one $1 \times 1$ square)

You have to determine $X$ – the number of ways to cover the banquet hall.
Remarks. The number of pieces is large enough. It is not allowed to leave empty places, or to cover any part of a surface twice, or to saw pieces.

题意概述

有一个$M \times N$的网格，要求用两种方块覆盖它，一种是$2 \times 1$的方块，一种是$2 \times 2$挖去$1 \times 1$的方块。方块可以旋转。求方案数。
数据范围：$1 \le M, N \le 9$。

算法分析

用$f_{i, j}$表示前$(i-1)$行都已填满且第$i$行的状态为$j$的方案数，转移时枚举$j$可以转移到的状态。暴力计算即可发现合法的转移不会太多。

代码

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

#define int long long

using namespace std;

struct IOManager {
  template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); }
  inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; }
  inline int read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); }
  template <typename T> inline IOManager operator > (T &x) { read(x); return *this; }
  template <typename T> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }
  inline void write(char c) { putchar(c); }
  inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); }
  template <typename T> inline IOManager operator < (T x) { write(x); return *this; }
} io;

struct Solver {
private:
  static const int N = 11;
  int n, m, f[N][1 << N];
  void input() { io > n > m; }
  void update(int x, int y, int s, int val, int p) {
    if (y == (1 << m) - 1) { f[x][s] += val; return; }
    for (int i = p; i < m; ++ i)
      if (! (y & 1 << i)) {
        if (! (s & 1 << i)) {
          update(x, y | 1 << i, s | 1 << i, val, i + 1);
          if (i && ! (s & 1 << i - 1)) update(x, y | 1 << i, s | 1 << i | 1 << i - 1, val, i + 1);
          if (i < m - 1 && ! (s & 1 << i + 1)) update(x, y | 1 << i, s | 1 << i | 1 << i + 1, val, i + 1);
        }
        if (i < m - 1 && ! (y & 1 << i + 1)) {
          update(x, y | 1 << i | 1 << i + 1, s, val, i + 2);
          if (! (s & 1 << i)) update(x, y | 1 << i | 1 << i + 1, s | 1 << i, val, i + 2);
          if (! (s & 1 << i + 1)) update(x, y | 1 << i | 1 << i + 1, s | 1 << i + 1, val, i + 2);
        }
      }
  }
  void process() {
    f[0][(1 << m) - 1] = 1;
    for (int i = 0; i <= n; ++ i)
      for (int j = 0; j < 1 << m; ++ j)
        if (f[i][j]) update(i + 1, j, 0, f[i][j], 0);
    io < f[n + 1][0] < '\n';
  }

public:
  void solve() { input(), process(); }
} solver;

signed main() {
  solver.solve();
  return 0;
}

Open the Brackets

RegMs If Leave a comment

题目描述

There is a syntactically correct boolean expression.
The definition of syntactically correct expression follows as:

  1. “a”, “b”, “c”, …, “j” are syntactically correct expressions.
  2. If A is a correct expression, then !A and (A) are correct expressions too.
  3. If A is a correct expression and B is a correct expression, then A||B, A&B, A<=>B, A=>B, A#B are syntactically correct expressions too.

Syntactically correct expression doesn’t contain spaces.
Small Latin letters are variables, ! denotes negation, || – disjunction, & – conjunction, <=> – equality, => – implication, # – excepting or.
Negation has the highest priority, conjunction has middle priority, and other operations have low priority. Brackets change the order of operations executing.
Two expressions are called identical if their values are the same in any values of variables.
Make the expression, which will be identical with given expression. New expression must be free of brackets.

题意概述

将一个逻辑表达式$s$转化成一个不包含括号的等价表达式$t$。保证$s$中变量的个数不超过$10$。
数据范围：$1 \le |s| \le 2048, \; 1 \le |t| \le 32768$。

算法分析

由于变量数不超过$10$，因此可以枚举每个变量的值，计算表达式的值，若为真，则在答案中加入这个状态（状态间用||隔开，变量间用&隔开）。如果最后答案为空，则直接输出!a&a。

代码

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

using namespace std;

struct Solver {
private:
  string s;
  void input() { cin >> s; }
  int len(char c) {
    switch (c) {
      case '!' : return 0;
      case '&' : return 0;
      case '|' : return 1;
      case '<' : return 2;
      case '=' : return 1;
      case '#' : return 0;
    }
  }
  int priority(char c) {
    switch (c) {
      case '!' : return 1;
      case '&' : return 2;
      case '|' : return 3;
      case '<' : return 3;
      case '=' : return 3;
      case '#' : return 3;
      case '(' : return 4;
    }
  }
  bool single(bool a, char c, bool b) {
    switch (c) {
      case '&' : return a && b;
      case '|' : return a || b;
      case '<' : return a == b;
      case '=' : return a || ! b;
      case '#' : return a ^ b;
    }
  }
  int match(string s, int p) {
    int cnt = 1;
    while (cnt) ++ p, cnt += (s[p] == '(') - (s[p] == ')');
    return p;
  }
  stack <char> symbol;
  stack <bool> number;
  void pop() {
    if (symbol.top() == '!') {
      symbol.pop(); bool p = number.top(); number.pop(), number.push(! p);
    } else {
      bool p = number.top(); number.pop();
      bool q = number.top(); number.pop();
      number.push(single(p, symbol.top(), q));
      symbol.pop();
    }
  }
  bool calc(string s) {
    for (int i = 0; i < s.length(); ++ i) {
      if (isdigit(s[i])) number.push(s[i] - '0');
      else if (s[i] == '(') symbol.push('(');
      else if (s[i] == ')') {
        while (symbol.top() != '(') pop();
        symbol.pop();
      } else {
        while (! symbol.empty() && priority(symbol.top()) <= priority(s[i])) pop();
        symbol.push(s[i]), i += len(s[i]);
      }
    }
    while (! symbol.empty()) pop();
    return number.top();
  }
  bool check(int p, string s) {
    for (int i = 0; i < s.length(); ++ i)
      if (isalpha(s[i])) s[i] = ((p & 1 << s[i] - 'a') > 0) + '0';
    return calc(s);
  }
  void process() {
    for (int i = 0; i + 1 < s.length(); ++ i)
      while (i + 1 < s.length() && s[i] == '!' && s[i + 1] == '!')
        s = s.substr(0, i) + s.substr(i + 2);
    string ans, sep;
    for (int i = 0; i < 1 << 10; ++ i)
      if (check(i, s)) {
        ans += sep, sep = "||";
        string s;
        for (int j = 0; j < 10; ++ j) {
          ans += s, s = "&";
          if (! (i & 1 << j)) ans += "!";
          ans += j + 'a';
        }
      }
    if (ans.length() == 0) ans = "!a&a";
    cout << ans << endl;
  }

public:
  void solve() { input(), process(); }
} solver;

int main() {
  solver.solve();
  return 0;
}

Arpa and a Game with Mojtaba

RegMs If Leave a comment

题目描述

Mojtaba and Arpa are playing a game. They have a list of $n$ numbers in the game.
In a player’s turn, he chooses a number $p^k$ (where $p$ is a prime number and $k$ is a positive integer) such that $p^k$ divides at least one number in the list. For each number in the list divisible by $p^k$, call it $x$, the player will delete $x$ and add ${x \over p^k}$ to the list. The player who can not make a valid choice of $p$ and $k$ loses.
Mojtaba starts the game and the players alternatively make moves. Determine which one of players will be the winner if both players play optimally.

算法分析

给定一个长度为$n$的序列，两人轮流进行操作，每次操作给定$p, k$，其中$p$是素数，$k$是正整数，将序列中所有能被$p^k$整除的数除以$p^k$（要求至少有一个数能被整除），不能进行操作的人算输。问在两人都采取最优策略的情况下，先手必胜还是后手必胜。
数据范围：$1 \le n \le 100, \; 1 \le a_i \le 10^9$。

算法分析

考虑某个质数$p$，它对其他质数不产生任何影响，因此可以分别处理每个质数。
设处理到的质数是$p$，我们计算出它在序列每个数中的最高次数，并储存在二进制数s中。那么在进行一次$p, k$操作后，s会被更新成(s>>k)|(s&((1<<(k-1))-1))。把s看成点，操作看成边，就构成了一张有向图。分别计算每个质数有向图的SG函数，异或起来，如果等于$0$则后手必胜，否则先手必胜。

代码

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

using namespace std;

namespace std {
  template <typename T>
  void maxify(T &a, T b) { b > a && (a = b); }
  template <typename T>
  void minify(T &a, T b) { b < a && (a = b); }
}

struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c; bool flag = false; x = 0;
    while (~ c && ! isdigit(c = getchar()) && c != '-') ;
    c == '-' && (flag = true, c = getchar());
    if (! ~ c) return false;
    while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return (flag && (x = -x), true);
  }
  inline bool read(char &c) {
    c = '\n';
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    return ~ c;
  }
  inline int read(char s[]) {
    char c; int len = 0;
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    if (! ~ c) return 0;
    while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
    return (s[len] = '\0', len);
  }
  template <typename T>
  inline IOManager operator > (T &x) {
    read(x); return *this;
  }
  template <typename T>
  inline void write(T x) {
    x < 0 && (putchar('-'), x = -x);
    x > 9 && (write(x / 10), true);
    putchar(x % 10 + '0');
  }
  inline void write(char c) {
    putchar(c);
  }
  inline void write(char s[]) {
    int pos = 0;
    while (s[pos] != '\0') putchar(s[pos ++]);
  }
  template <typename T>
  inline IOManager operator < (T x) {
    write(x); return *this;
  }
} io;

struct Solver {
private:
  static const int N = 100;
  int n, a[N + 1];
  map <int, int> sg, num;
  void input() {
    io > n;
    for (int i = 1; i <= n; ++ i) io > a[i];
  }
  void init() {
    for (int i = 1; i <= n; ++ i)
      if (a[i] > 1) {
        int q = sqrt(a[i]);
        for (int j = 2; j <= q; ++ j) {
          if (a[i] == 1) break;
          if (! (a[i] % j)) {
            int cnt = 0;
            while (! (a[i] % j)) a[i] /= j, ++ cnt;
            num[j] |= 1 << cnt - 1;
          }
        }
        if (a[i] > 1) num[a[i]] |= 1;
      }
  }
  int get_sg(int t) {
    if (! t) return 0;
    if (sg.count(t)) return sg[t];
    map <int, bool> vis;
    int p = t, cnt = 0;
    while (p) p >>= 1, ++ cnt;
    for (int i = 1; i <= cnt; ++ i)
      vis[get_sg((t >> i) | (t & (1 << i - 1) - 1))] = true;
    cnt = 0;
    while (vis[cnt]) ++ cnt;
    return sg[t] = cnt;
  }
  void process() {
    int ans = 0;
    for (map <int, int> :: iterator it = num.begin(); it != num.end(); ++ it) ans ^= get_sg(it->second);
    if (! ans) io < (char *) "Arpa\n";
    else io < (char *) "Mojtaba\n";
  }

public:
  void solve() {
    input(), init(), process();
  }
} solver;

int main() {
  solver.solve();
  return 0;
}

Paths in a Complete Binary Tree

RegMs If Leave a comment

题目描述

$T$ is a complete binary tree consisting of $n$ vertices. It means that exactly one vertex is a root, and each vertex is either a leaf (and doesn’t have children) or an inner node (and has exactly two children). All leaves of a complete binary tree have the same depth (distance from the root). So $n$ is a number such that $n+1$ is a power of $2$.
In the picture you can see a complete binary tree with $n=15$.
A Binary Tree
Vertices are numbered from $1$ to $n$ in a special recursive way: we recursively assign numbers to all vertices from the left subtree (if current vertex is not a leaf), then assign a number to the current vertex, and then recursively assign numbers to all vertices from the right subtree (if it exists). In the picture vertices are numbered exactly using this algorithm. It is clear that for each size of a complete binary tree exists exactly one way to give numbers to all vertices. This way of numbering is called symmetric.
You have to write a program that for given $n$ answers $q$ queries to the tree.
Each query consists of an integer number $u_i$ and a string $s_i$, where $u_i$ is the number of vertex, and $s_i$ represents the path starting from this vertex. String $s_i$ doesn’t contain any characters other than $L, R$ and $U$, which mean traverse to the left child, to the right child and to the parent, respectively. Characters from $s_i$ have to be processed from left to right, considering that $u_i$ is the vertex where the path starts. If it’s impossible to process a character (for example, to go to the left child of a leaf), then you have to skip it. The answer is the number of vertex where the path represented by $s_i$ ends.
For example, if $u_i=4$ and $s_i=UURL$, then the answer is $10$.

题意概述

给定一棵有$n$个节点的按中序遍历编号的完全二叉树、起始点的编号$u$以及只由$L, R$和$U$组成的操作序列$s$（其中$L$表示走到左儿子，$R$表示走到右儿子，$U$表示走到父亲），求终止点的编号。
数据范围：$1 \le n \le 10^{18}, \; 1 \le u_i \le n, \; 1 \le |s_i| \le 10^5$。

算法分析

设当前走到的数为$p$。将树中的数用二进制表示，可以得到下图：
A Binary Tree with Binary Numbers
如果$p={n+1 \over 2}$，那么$U$操作将无效。如果$p \equiv 1 \pmod 2$，那么$L, R$操作将无效。
观察此图可以发现，进行一次$U$操作相当于将$p$最低位的$1$左移一位（如果前一位已经是$1$则只需将这一位变成$0$）；进行一次$L$操作相当于将最低位的$1$右移一位；进行一次$R$操作相当于将最低位的$1$的后一位变成$1$。
证明如下：

这是一棵中序遍历的完全二叉树。每个节点的编号等于不在它右边的节点个数（如果你把树画的足够标准的话）。
设树的深度为$d$，节点$i$的深度为$d_i$。定义节点$i$的高度$h_i=d-d_i$。显然，节点$i$两棵子树的大小均为$s_i=2^{h_i}-1$。定义$lowbit_i$等于$i$的二进制表示中最低位的$1$所表示的数。可以发现$lowbit_i=2^{h_i}$。那么$s_i=lowbit_i-1$。
设数字$i$进行一次操作后的数字为$j$。
对于$L$操作：
$\because j$的右子树在$j$的右边，且在$i$的左边.
$\therefore (i-1)-j=s_j$.
$j=i-lowbit_j$.
又$\because h_i=h_j+1$.
$\therefore lowbit_i=2lowbit_j$.
$j=i-{lowbit_i \over 2}$.
这等价于将最低位的$1$右移一位。
对于$R$操作：
$\because j$的左子树在$j$的左边，且在$i$的右边.
$\therefore (j-1)-i=s_j$.
$j=i+lowbit_j$.
又$\because h_i=h_j+1$.
$\therefore lowbit_i=2lowbit_j$.
$j=i+{lowbit_i \over 2}$.
这等价于将最低位的$1$的后一位变成$1$。
对于$U$操作：
①$i$在$j$左边.
$\because$等价于$L$操作的逆操作.
$\therefore i=j-lowbit_i$.
$j=i+lowbit_i$.
②$i$在$j$右边.
$\because$等价于$R$操作的逆操作.
$\therefore i=j+lowbit_i$.
$j=i-lowbit_i$.
这等价于将$p$最低位的$1$左移一位。

由此得证。

代码

#include <iostream>
using namespace std;
long long n, t, p, len;
string s;
long long lowbit(long long t) {
    return t & -t;
}
int main()
{
    cin >> n >> t;
    while (t--) {
        cin >> p >> s;
        len = s.length();
        for (int i = 0; i < len; ++i) {
            long long q = lowbit(p);
            switch (s[i]) {
                case 'U': {
                    if (p != n + 1 >> 1) {
                        p -= q;
                        p |= q << 1;
                    }
                    break;
                }
                case 'L': {
                    if (!(p & 1)) {
                        p -= q >> 1;
                    }
                    break;
                }
                case 'R': {
                    if (!(p & 1)) {
                        p += q >> 1;
                    }
                    break;
                }
            }
        }
        cout << p << endl;
    }
    return 0;
}