题目详情题解（0）讨论（0）提交记录（0）

AT_abc454_f.[ABC454F] Make it Palindrome 2

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

正整数 $ N,M $ と長さ $ N $ の整数列 $ A=(A_1,A_2,\ldots,A_N) $ が与えられます。 $ A $ の各要素は $ 0 $ 以上 $ M $ 未満であることが保証されます。

この整数列 $ A $ に対して以下の操作を $ 0 $ 回以上何回でも行うことができます：

  • $ 1\le l\le r\le N $ を満たす整数の組 $ (l,r) $ を選び、 $ i=l,l+1,\ldots,r $ に対して $ A_i $ を $ (A_i+1) \bmod M $ で置き換える。

$ A $ を回文にするために必要な操作回数の最小値を求めてください。

ただし、 $ A $ が回文であるとは $ i=1,2,\ldots,N $ に対し $ A_i=A_{N+1-i} $ が成り立つことを指します。

$ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $

各テストケースは以下の形式で与えられる。

$ N $ $ M $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

输出格式

各テストケースに対する答えを順に改行区切りで出力せよ。

输入输出样例

  • 输入#1

    3
4 5
0 3 1 2
1 20260418
454
7 12
3 1 4 1 5 9 2

    输出#1

    3
0
5

说明/提示

Sample Explanation 1

$ 1 $ 番目のテストケースについて考えます。

以下のように $ 3 $ 回操作することで $ A $ を回文にすることができます：

  • $ (l,r)=(2,4) $ を選ぶ。 $ A=(0,4,2,3) $ となる。
  • $ (l,r)=(3,4) $ を選ぶ。 $ A=(0,4,3,4) $ となる。
  • $ (l,r)=(3,4) $ を選ぶ。 $ A=(0,4,4,0) $ となる。

$ 3 $ 回未満の操作で $ A $ を回文にすることはできないので、 $ 3 $ を出力してください。

Constraints

  • $ 1\le T $
  • $ 1\le N\le 2\times 10^5 $
  • $ 1\le M\le 10^9 $
  • $ 0\le A_i < M $
  • 全てのテストケースにおける $ N $ の総和は $ 2\times 10^5 $ 以下
  • 入力される値は全て整数

输入解题思路，AI测评打分。不知道怎么写?

首页