关注我：二仙桥耐笔王 ， 强力1v1辅导暑期实习&春招笔试

第1题-小红的字符串

题目内容

小红了一个串。她将进行恰好一次以下操 作:

选择下标，交换和。

小红想知道，不同的操作方案，最终能生成多少不同的字符串?

输入描述

一个仅由和构成的字符串。字符串长度不小于,不大于。

输出描述

一个整数，代表最终的方案数。

样例1

输入

1100			

输出

5 

思维。统计字符串中x个'0'和y个'1'答案为x*y加上当cnt0>1或cnt1>1时额外的1

s = input().strip()
s0 = s.count('0')
s1 = s.count('1')
res = s0*s1
if s0>=2 or s1>=2:
    res += 1
print(res)

第2题-小红的验证码

题目内容

小红是一个程序员，他正在开发一个验证码功能。为了正确识别机器人和真实用户，小红需要对验证码进行特殊处理。

他想出来了如下加密法:

图像+数字识别法，在一张图片中放入一个数字，例如：

这张图片机器人会识别数字 ，但是正确的识别码为 。 给出所有的数字摆放形态:

系统将会在?处随机填入的数字，然后给出个图片，为，你需要按照1~m的顺序输出这个数字以正确识别小红的系统。

输入描述

第一行一个整数，表示图片个数。

接下来共行，每行列，表示给定的图片。输入保证仅含和 #。

输出描述

一个整数，表示图片所所表示的正确验证码。

样例1

输入

1
#222#
#2###
#232#
###2#
#272#

输出

5 

样例2

输入

2
#222#
#2###
#232#
###2#
#272#
##1##
##1##
##1##
##1##
##1##

输出

51

模拟。直接按照9种不同的数字模块模拟即可

import sys
digitPatterns = [
        [
            "#...#",
            "#.#.#",
            "#.#.#",
            "#.#.#",
            "#...#"
        ],
        [
            "##.##",
            "##.##",
            "##.##",
            "##.##",
            "##.##"
        ],
        [
            "#...#",
            "###.#",
            "#...#",
            "#.###",
            "#...#"
        ],
        [
            "#...#",
            "###.#",
            "#...#",
            "###.#",
            "#...#"
        ],
        [
            "#.#.#",
            "#.#.#",
            "#...#",
            "###.#",
            "###.#"
        ],
        [
            "#...#",
            "#.###",
            "#...#",
            "###.#",
            "#...#"
        ],
        [
            "#...#",
            "#.###",
            "#...#",
            "#.#.#",
            "#...#"
        ],
        [
            "#...#",
            "###.#",
            "###.#",
            "###.#",
            "###.#"
        ],
        [
            "#...#",
            "#.#.#",
            "#...#",
            "#.#.#",
            "#...#"
        ],
        [
            "#...#",
            "#.#.#",
            "#...#",
            "###.#",
            "#...#"
        ]
    ]

m = sys.stdin.readline().strip('/n')
m = int(m)
inp = []
for _ in range(int(m)):
    inp.append([sys.stdin.readline().strip('/n') for _ in range(5)])

for i in range(m):
    for j in range(5):
        st = ""
        for k in range(5):
            if inp[i][j][k] != "#":
                st += "."
            else:
                st += "#"
        inp[i][j] = st

ans = []

for i in range(m):
    for j in range(10):
        jud = True
        for k in range(5):
            if inp[i][k] != digitPatterns[j][k]:
                jud = False
                break
        if jud:
            ans.append(str(j))
            break

print("".join(ans))

第3题-小红玩游戏

题目内容

小红最近想到了一个好玩的游戏，这个游戏一共会进行轮，每一轮，小红会从下方三种操作中选择一种进行:

在黑板上写一个整数; 擦去黑板上的一个整数(此操作之前保证黑板上有这个整数); 询问黑板上哪个数字与整数的异或值最大(若黑板上此时没有数字，则输出 )。 对于每一次询问操作，你需要告诉他答案。

输入描述

第一行输入一个正整数代表操作的轮数。

此后几行，每行先输入一个整数代表操作类型，编号同题干;随后在同一行输入一个整数 代表操作的参数。

除此之外，保证存在至少一次询问操作。

输出描述

对于每一次询问操作，输出一个整数，代表答案。

样例1

输入

10
1 5
1 7
1 4
3 8
2 4
1 2
1 6
3 9
2 6
3 9

输出

15
15
14

题解

题面描述

题目给定一个游戏，共进行 轮操作。每一轮操作中可以选择以下三种之一：

1. 插入操作：在黑板上写入一个整数 ；
2. 删除操作：擦去黑板上一个整数 （题目保证该整数在黑板中一定存在）；
3. 询问操作：查询黑板上哪个数字与给定整数 的异或值最大。如果黑板为空，则输出 。

题目保证至少存在一次询问操作。

字典树。字典树模版题，三种不同的操作对应字典树的插入，删除，查找最大异或值

# 定义字典树节点类
class TrieNode:
    def __init__(self):
        self.child = [None, None]  # 两个分支，分别代表 0 和 1
        self.cnt = 0               # 经过该节点的数字个数

# 插入数字 x 到字典树中
def insert(root, x):
    node = root
    node.cnt += 1
    # 固定使用 32 位（或 31 位，根据题目数字范围；这里用 32 位保证万无一失）
    for i in range(31, -1, -1):
        bit = (x >> i) & 1
        if node.child[bit] is None:
            node.child[bit] = TrieNode()
        node = node.child[bit]
        node.cnt += 1

# 删除数字 x 从字典树中（保证 x 存在）
def remove(root, x):
    node = root
    node.cnt -= 1
    for i in range(31, -1, -1):
        bit = (x >> i) & 1
        node = node.child[bit]
        node.cnt -= 1

# 查询给定 x 与字典树中数字异或值的最大值
def query(root, x):
    # 如果黑板（字典树）为空，则返回 -1
    if root.cnt == 0:
        return -1
    node = root
    res = 0
    for i in range(31, -1, -1):
        bit = (x >> i) & 1
        opp = 1 - bit  # 优先选择相反的位
        if node.child[opp] is not None and node.child[opp].cnt > 0:
            res |= (1 << i)
            node = node.child[opp]
        else:
            node = node.child[bit]
    return res

if __name__ == '__main__':
    # import sys
    # input = sys.stdin.readline
    n = int(input().strip())
    root = TrieNode()
    for _ in range(n):
        parts = input().split()
        op = int(parts[0])
        x = int(parts[1])
        if op == 1:
            insert(root, x)
        elif op == 2:
            remove(root, x)
        elif op == 3:
            print(query(root, x))