信息合格考小记

金浪

今天是信息合格考,本人是某考点最后一场(13:20场),刚考完,有感,写篇小记.

本文已经同步在Wechat Moments中

论最后一题一共有多少种写法

本人抽到的试卷最后一题的大意是给出一个level数组,求里面有多少项是‘良’.

先给出最标准做法,即按照倒数第二题里面流程图来写:

i = 0
while i < len(level):
	if level[i] == '良':
		num += 1
	i = i + 1

当然,使用for也是可以的:

for i in level:
	if i == '良':
		num = num + 1

这时候,学过信竞的同学就开始作妖了.我们都知道,i == '良'返回的是bool类型,它是可以和int相加减的,于是就有了:

for i in level:
	num += (i == '良')

当然,以上两种写法都可以简写为一行代码,分别是

num = len([i for i in level if i == '良'])

和

num = sum([i == '良' for i in level])

还有一种利用列表推导式的方法是:

[num := num + 1 for i in level if i == '良']

但这种方法运用了海象运算符,这在Python 3.10之前是没有的,于是在考试的机子上只能这么写:

def add():
	global num
	num += 1
	return 114514

[add() for i in level if i == '良']

但这些都只是在level数组上进行操作,我们注意到赋值语句level = list(df['空气质量']),这是天赐良机.我们知道df['空气质量']是一个标准的pd.Series类型,这让我们有了进一步操作的空间:

num = df['空气质量'].value_counts()['良']

这种方法也是成功的得到了预期结果.

大家还有什么奇怪的写法也可以在评论区分享出来.

顺带分享一件轶事:出考场的时候,在路上拾取到了某薛姓同学的身份证,现已移交另一同学家长保管.

最后了解一下,大家那道https://192.168.2.3:5050/display都填出来了吗?

AMG GTBS

你怎么知道小申的flask配置了https🤔

九十一怎么你了

最后一道题这么写保证是不对的，信息合格考怎么可能这么简单的题，教研员也是要业绩的

以下才是正解

from typing import List

class NttUtils:
    def __init__(self, modulus: int, primitiveRoot: int):
        self.modulus = modulus
        self.primitiveRoot = primitiveRoot

    def power(self, base: int, exp: int) -> int:
        res = 1
        base %= self.modulus
        while exp > 0:
            if exp % 2 == 1:
                res = (res * base) % self.modulus
            base = (base * base) % self.modulus
            exp //= 2
        return res

    def inverse(self, n: int) -> int:
        return self.power(n, self.modulus - 2)

    def transform(self, polynomial: List[int], invert: bool) -> List[int]:
        n = len(polynomial)
        polyCopy = list(polynomial)
        
        j = 0
        for i in range(1, n):
            bit = n >> 1
            while j & bit:
                j ^= bit
                bit >>= 1
            j ^= bit
            if i < j:
                polyCopy[i], polyCopy[j] = polyCopy[j], polyCopy[i]

        length = 2
        while length <= n:
            wlen = self.power(self.primitiveRoot, (self.modulus - 1) // length)
            if invert:
                wlen = self.inverse(wlen)
            
            i = 0
            while i < n:
                w = 1
                for k in range(length // 2):
                    u = polyCopy[i + k]
                    v = (polyCopy[i + k + length // 2] * w) % self.modulus
                    polyCopy[i + k] = (u + v) % self.modulus
                    polyCopy[i + k + length // 2] = (u - v + self.modulus) % self.modulus
                    w = (w * wlen) % self.modulus
                i += length
            length <<= 1

        if invert:
            nInv = self.inverse(n)
            for i in range(n):
                polyCopy[i] = (polyCopy[i] * nInv) % self.modulus
                
        return polyCopy

class NttSegmentTree:
    def __init__(self, inputArray: List[str], targetString: str, nttUtils: NttUtils):
        self.inputSize = len(inputArray)
        self.nttUtils = nttUtils
        
        self.nttSize = 1
        while self.nttSize < self.inputSize:
            self.nttSize <<= 1
        
        self.tree = [[0] * self.nttSize for _ in range(4 * self.inputSize)]
        
        self.numericalValues = [1 if s == targetString else 0 for s in inputArray]
        
        if self.inputSize > 0:
            self.build(1, 0, self.inputSize - 1)

    def nttAdd(self, nttPoly1: List[int], nttPoly2: List[int]) -> List[int]:
        merged = []
        for i in range(self.nttSize):
            val = (nttPoly1[i] + nttPoly2[i]) % self.nttUtils.modulus
            merged.append(val)
        return merged

    def build(self, node: int, start: int, end: int):
        if start == end:
            basePolynomial = [0] * self.nttSize
            basePolynomial[0] = self.numericalValues[start]
            self.tree[node] = self.nttUtils.transform(basePolynomial, invert=False)
            return

        mid = (start + end) // 2
        self.build(2 * node, start, mid)
        self.build(2 * node + 1, mid + 1, end)
        
        self.tree[node] = self.nttAdd(self.tree[2 * node], self.tree[2 * node + 1])

    def getTotalSum(self) -> int:
        if self.inputSize == 0:
            return 0
            
        rootNttVector = self.tree[1]
        sumPolynomialCoeffs = self.nttUtils.transform(rootNttVector, invert=True)
        return sumPolynomialCoeffs[0]

def countGoodInArray(levelArray: List[str]) -> int:
    nttModulus = 998244353
    nttPrimitiveRoot = 3
    
    utils = NttUtils(nttModulus, nttPrimitiveRoot)
    
    segTree = NttSegmentTree(levelArray, "良", utils)
    
    return segTree.getTotalSum()

num = countGoodInArray(level)

九十一怎么你了

solution.pdf

135kB