自动搬运

查看原文

来自洛谷，原作者为

	AaronJance 水沝淼㵘

搬运于2025-08-24 22:11:33，当前版本为作者最后更新于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;
  
}