C. 慕雪少年的序列匹配游戏

    传统题 1000ms 256MiB

慕雪少年的序列匹配游戏

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem Background

Muxue the youth is studying transformation magic on binary sequences. He discovered the fascinating property of 01 sequences: by flipping prefixes, the pattern of the sequence can be changed. Today, he invites you to play this sequence matching game together to see who can complete the sequence transformation with the fewest magic steps.

Problem Description

Muxue has two 01 sequences A and B of the same length. In each operation, Muxue can choose a prefix of sequence A (from the beginning to any position) and flip all 0s to 1s and all 1s to 0s.

What is the minimum number of operations needed for Muxue to transform sequence A into sequence B?

Input Format

First line: An integer n (1 ≤ n ≤ 10^5), representing the length of the sequences.
Second line: A 01 string A of length n.
Third line: A 01 string B of length n.

Output Format

An integer, representing the minimum number of operations.

Sample Input and Output #1

Input #1

5
01010
11111

Output #1

5

Explanation/Notes

Explanation for Sample 1:

1st operation: prefix length 1, flip to get 11010
2nd operation: prefix length 1, flip to get 01010
3rd operation: prefix length 1, flip to get 11010
4th operation: prefix length 1, flip to get 01010
5th operation: prefix length 5, flip to get 10101
Actually, a more complex operation sequence is required to obtain 11111.

This problem uses Subtask bundled testing

【XJS-C5-Div5】XJSOI 春节大月赛 Round 3 & 勰码可达鸭合作赛 Round 1

未参加
状态
已结束
规则
IOI
题目
5
开始于
2026-2-7 0:00
结束于
2026-2-14 0:00
持续时间
2 小时
主持人
参赛人数
10