USACO计算机竞赛每年的月赛落下帷幕！
老师希望大家都斩获高分！
话不多说，来看北大乔老师为大家带来的
USACO竞赛二月赛银牌题目分析
一起来看USACO竞赛的关键信息吧！
USACO竞赛课程
长按扫描左侧二维码
Wechat：xnew1111
带来USACO银牌题目分析
2月赛白银组共有4100多名参与者，其中四分之三是大学预科生。本次晋升黄金组的分数线为750分。
目前我们收集到的家长朋友们多把自己家小朋友的学习目标设定在银牌升金上，因为学习编程语言本就是之后理科学习的必经之路（多数专业会在大一大二期间设计python课程，完成对应的计算/统计/系统实现开发等作业），这些技能也成为目前理工科学生实力的最强说明。而且，编程学习中的创造体验，是让很多学生欲罢不能的，这一点是其他学科学习所不具备的。
好，下面我们开始相对硬核的内容，此次USACO计算机竞赛银牌赛的题目有何难点与亮点，有一定编程基础跃跃欲试的同学们看过来～
让我们首先计算以下数量Q：最少移动次数使全部液体1至管1，且全部液体2至管2。
试管和烧杯中液体的当前状态可以用三个二进制字符串f，s，b 表示。f和s与题目参数意义相同，而b代表的是beaker中从底到顶的状态，
首先，在这些条件下，Q不会改变：
1.压缩所有三个字符串中相同字符的运行。例如，1221 变为 121，2211 变为 21。
2.如果 f 为 1，则删除它的第一个字符，因为该液体永远不需要离开管 1。
3.同样，如果s的第一个字符是2，则删除它。
接下来，观察 Q 必须至少是简化后的字符数，因为在执行任何移动并再次简化后，字符数将保持不变或减少 1。最终状态对应于所有 f、s 和 b 简化为空字符串。
所以化简后的字符数为1，Q=1，因为我们只需要一次倾倒即可分离液体（管1进入管2）。但是，当简化后的字符数大于1时，我们需要利用烧杯，并且当我们第一次将液体倒入烧杯中时，简化后的字符数不会改变。在这种情况下，Q 至少是简化后的字符数加一。
在这里，我们提供了一种解决思路，将所有液体 i 移动到管 i 中，并实现最多移动次数为压缩运行后的字符数加 2。从前面的分析中，我们知道答案必须至少是压缩运行后的字符数减二。因此，我们的解决方案距离最优解最多差了4。
而最后，我们需要对于剩下的4做简单暴力的求解即可。
题目代码
def to_reduced_list(s):
"""Compress runs of equal chars in a string s, and converts to int
>>> to_reduced_list('2211')
[2, 1]
"""
l = []
for c in s:
c = int(c)
if len(l) > 0 and l[-1] == c:
continue
l.append(c)
return l
def solve():
N, P = map(int, input().split())
tubes = [to_reduced_list(input()) for _ in range(2)]
tubes.append([])
if tubes[0][0] == tubes[1][0]: # ensure f and s start with different chars
tubes[0].insert(0, tubes[0][0] ^ 3)
ans = len(tubes[0]) + len(tubes[1]) - 2
if ans > 1:
ans += 1
print(ans)
if P == 1:
return
moves = []
def move(src, dst):
moves.append((src, dst))
if len(tubes[dst]) == 0 or tubes[dst][-1] != tubes[src][-1]:
tubes[dst].append(tubes[src][-1])
tubes[src].pop()
if tubes[0][-1] == tubes[1][-1]: # step 1: if equal last chars
if len(tubes[0]) > len(tubes[1]):
move(0, 1)
else:
move(1, 0)
for i in range(2):
if len(tubes[i]) > 1:
move(i, 2) # step 2: move from any tube with string length > 1 to beaker
idx_to_empty = 0 # step 3: choose a tube to (almost) empty first
if tubes[idx_to_empty][0] == tubes[2][0]:
idx_to_empty ^= 1
while len(tubes[idx_to_empty]) > 1:
if tubes[idx_to_empty][-1] == tubes[2][0]:
move(idx_to_empty, 2)
move(idx_to_empty, idx_to_empty ^ 1)
idx_to_empty ^= 1 # step 4: next, (almost) empty the other tube
move(2, idx_to_empty) # step 5: finish
break
assert len(moves) == ans
for a, b in moves:
print(1 + a, 1 + b)
T = int(input())
for _ in range(T):
solve()
USACO竞赛活动安排
01
USACO竞赛介绍
02
USACO竞赛规则
03
USACO竞赛等级介绍
参赛资格：注册USACO账号即为铜级。
难度分析：铜级考试只要基本编程基本语法知识，至少要会一种编程语言的基本的读入读出（一学就会啦～）。铜级考试的时间对于解决问题来说是很充裕的，充分准备晋级白银是每一位同学都可以做到的～
考点：基本编程知识、基本数据结构、输入输出、排序、二分法、遍历。
学习周期：0基础的同学需要50小时编程语法以及基本数据结构的学习，以及20小时左右的简单算法学习和模拟赛训练，是比较合理的一个备考周期。
学习成果不仅看天赋技能，还需要有素地训练学习，因此不存在一个标准的时间估计。每个人在掌握技能的过程中，都将面临独特的学习曲线和挑战。关键在于通过明确的学习计划、持之以恒的努力，不断优化自己的方法，最大程度地实现学习目标。
USACO竞赛直通班
竞赛课程由金牌导师带队，采用体系化教研的专业教材，结合竞赛真题和考察范围全考点覆盖课程。
课程根据不同组别、不同基础的同学依据自己的情况来选择；丰富的学习资料，赛事真题，全真模考，全方位帮助学生稳步提高，高效学习。
目前，已在上海、北京、广州、深圳、苏州、杭州、南京、青岛、无锡、合肥、武汉、成都、郑州等多个城市开设校区，致力于为准留学生家庭提供全方位升学服务。
关键字：USACO竞赛,USACO培训班,USACO竞赛辅导,USACO计算机竞赛,
