[Codeforces] Codeforces Round #676 C. Palindromifier
問題
方針
どちらの操作も \( S \) の先頭または末尾の文字を含む部分列を選ぶことができないので、\( S \) の末尾が中心となるような回文を作ることを考えます。
まず初めに、"L 2″ という操作を行うと、
\[ s = s_{2}s_1s_2 \cdots s_{n-1}s_{n}\]
となり、長さ \( n + 1 \) の文字列が得られます。次に、\( s_1 \) を含んだ部分文字列は、\( s_1 \) または \( s_1s_2 \cdots s_{n-1} \) があります。ここで、"R 2″ という操作を行うと、
\[s = s_2s_1s_2 \cdots s_{n-1}s_ns_{n – 1}s_{n-2} \cdots s_2s_1\]
となり、長さ \( 2n\) の文字列が得られます。この文字列の末尾に、\( s_2 \) という文字を追加すると回文となるので、"R 2n-1″ という操作を行います。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { string S; cin >> S; int n = S.length(); cout << "3\n"; cout << "L " << 2 << "\n"; cout << "R " << 2 << "\n"; cout << "R " << 2 * n - 1<< "\n"; return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません