BOJ 2011パスワード

14033 ワード
2021.01.15 テキストリンク
https://www.acmicpc.net/problem/2011
2秒、128 MBメモリ
input :
  • パスワード(1<=パスワード<=5000)
    • output :
  • で発生する可能性のある分析の個数(1000000を出力)
    • .
  • が解釈できない場合、0が出力される.
    • 条件:
  • Aを1、Bを2、Zを26
    • と呼ぶ
    ASCII
    'A' = 65
    アルゴリズムを豪快に作ったけど...
    0例外を処理しない...
    2つの位置を接続する場合、10~26の間でなければならない異常処理は行わない.
    1つの場所で0より大きい例外処理をしない...
    iが1位になったときだけdpはどこで計算しますか;;
    ㅄㅄㅄㅄㅄ
    精神が崩れる.
    お金持ちですね.
    最初に思いついたアルゴリズムで,長さが1個の場合と2個の場合を分ける.
    長さが1の場合、変換が利用可能であればDPは1、使用不可能であれば0
    長さが2の場合、変換が利用可能であればDPは1、使用不可能であれば0
    動作0を計算すると、
            if dp[0][i]:
            dp[0][i] = dp[0][i - 2] + dp[1][i - 2]
    動作1を計算するとき、
            if dp[1][i]:
            dp[1][i] = dp[0][i - 1] + dp[1][i - 1]
    dp[1][0] = 0
    for i in range(1, len(data)):
        if not (10 <= int(data[i - 1] + data[i]) <= 26):
            dp[0][i] = 0
        if not (1 <= int(data[i]) <= 10):
            dp[1][i] = 0
    異常処理が最も重要です...
    最後に残りを探さなかったので間違っていました...
    困難な問題
    import sys

data = list(sys.stdin.readline().strip())
dp = [[1] * len(data) for i in range(2)]

if data[0] == '0':
    print(0)
else:
    dp[1][0] = 0
    for i in range(1, len(data)):
        if not (10 <= int(data[i - 1] + data[i]) <= 26):
            dp[0][i] = 0
        if not (1 <= int(data[i]) <= 10):
            dp[1][i] = 0

    for i in range(2, len(data)):
        if dp[0][i]:
            dp[0][i] = dp[0][i - 2] + dp[1][i - 2]
        if dp[1][i]:
            dp[1][i] = dp[0][i - 1] + dp[1][i - 1]

    print((dp[0][len(data) - 1] + dp[1][len(data) - 1]) % 1000000)
    簡単なcpコマンドを実現
    boost: tcp client sample