题解 P5513 【[CEOI2013]Board】

AaronJance · 2020-07-25 16:02:13 · 题解

水个题解。

巨佬们轻喷。

二进制高精度肯定是要用的(见题目提供者的分析)线段树大可不必本蒟蒻也写不来。

解决进位的最简方式就是不理它暂时不必进位,最后复原格式,不影响最终数据。

用官方题解代码

// CEOI 2013 - Task: Board - Solution

// Author: Gustav Matula

#include <cstdio>

#include <cstring>

#include <cassert>

#include <algorithm>

using namespace std;

#define MAX 100005

char pa[MAX]; int _a[MAX], loga, *a;

char pb[MAX]; int _b[MAX], logb, *b;

void carry(int *idx, int i) {

  idx[i - 1] += idx[i] / 2 - (idx[i] % 2 == -1);

  idx[i] = abs(idx[i]) % 2;//从后往前复原格式 

}

void trace(char *path, int *idx, int &log) {

  int n = strlen(path);

  idx[0] = log = 1;

  for (int i = 0; i < n; ++i) {

    if (path[i] == '1') idx[log++] = 0;

    if (path[i] == '2') idx[log++] = 1;

    if (path[i] == 'L') --idx[log - 1];

    if (path[i] == 'R') ++idx[log - 1];//总和与是否进退位无关 (最后结果正确只需一次进退位) 

    if (path[i] == 'U') carry(idx, --log);//复原末尾格式便于消除(利用局部格式性质) 

  }

  for (int i = log - 1; i >= 1; --i) carry(idx, i);

  int r = 0; while (idx[r] == 0) ++r;

  for (int i = r; i < log; ++i) idx[i - r] = idx[i];//从后往前依次复原格式 

  log -= r;

}

int main(void)
{
  scanf("%s", pa); trace(pa, a = _a, loga);

  scanf("%s", pb); trace(pb, b = _b, logb);

  int log = min(loga, logb);

  int sol = 1 << 20;

  int delta = 0;

  for (int i = 0; i < log && delta < (1 << 20); ++i) {

    delta = delta * 2 + a[i] - b[i];

    sol = min(sol, abs(delta) + 2 * (log - i - 1));

  }

  printf("%d\n", sol + abs(loga - logb));

  return 0;

}