当前没有测试数据。

USACO 2024 US Open Contest, Gold Problem 1: Cowreography

一、题目描述

1. 舞蹈团队情况
   • 奶牛们组成了一个舞蹈团队，共有N头奶牛（$2\leq N\leq10^{6}$）站成一排。
   • 队伍中有两种奶牛：Guernseys（用0表示）和Holsteins（用1表示）。农夫John将舞蹈记录为长度为N的二进制字符串序列，其中0代表Guernsey，1代表Holstein，整个字符串表示奶牛在队伍中的排列方式。
2. 舞蹈动作规则
   • 每次舞蹈动作涉及两头奶牛，它们之间最多相隔K个位置（$1\leq K<N$），然后优雅地交换位置。
3. 问题情境
   • 竞争对手农夫Nhoj破坏了舞蹈记录，只留下了第一个和最后一个二进制字符串。
   • 给定这两个二进制字符串，需要帮助农夫John找到舞蹈中最少的动作次数。

二、输入格式

1. 第一行包含N和K。
2. 第二行包含第一个二进制字符串。
3. 第三行包含最后一个二进制字符串。
   • 保证两个二进制字符串中1的数量相同。

三、输出格式

输出舞蹈中最少的动作次数。

四、样例输入输出

1. 样例1
   • 输入
     • 4 1
     • 0111
     • 1110
   • 输出
     • 3
   • 解释
     • 一种可能的舞蹈动作序列：0111 -> 1011 -> 1101 -> 1110
2. 样例2
   • 输入
     • 5 2
     • 11000
     • 00011
   • 输出
     • 3
   • 解释
     • 一种可能的舞蹈动作序列：11000 -> 01100 -> 00110 -> 00011
3. 样例3
   • 输入
     • 5 4
     • 11000
     • 00011
   • 输出
     • 2
   • 解释
     • 一种可能的舞蹈动作序列：11000 -> 10010 -> 00011

五、评分规则

1. 输入4 - 5：K = 1。
2. 输入6 - 7：两个字符串中最多有8个1。
3. 输入8 - 15：N≤5000。
4. 输入16 - 23：无其他额外限制。

六、题目来源

题目作者：Benjamin Qi。