慢慢记录自己经历的笔试

题一

求函数 $y_2=2Ax$ 和 $y=Bx+C$ 两个曲线所围出的面积。如果没有所围面积，则输出0。

第一思路是蒙特卡洛去做，但是试了很多次都是超时。看网上的做法是直接手动求原函数然后计算积分。

题二

计算$m*(m^{n-1}−(m−1)^{n−1})\%100003$，$m$和$n$都非常大。

第一种简化，对m取100003的余数，再带回去计算，这样能化简一部分计算量。

第二种就是快速幂运算，每次将指数减半（奇数先减一再减半）。代码如下：

def fastExpMod(b, e, m):
    result = 1
    while e != 0:
        if (e&1) == 1: #当前次数为奇数
            result = (result * b) % m
        e >>= 1 #当前次数减半
        b = (b*b) % m #当前结果平方
    return result

题三

找相反数对的个数

刚开始想到统计每个数的次数，然后遍历字典看相反数是否在字典当中。最后相乘求和结果除以2。但是有一些情况比较特殊，比如0，这时候就会出现自身的数量没有计算到。

其实这个比较好的方法就是每次加入数组之前就计算相反数的个数，总共加起来就是最后的结果。这样能够保证不重不漏。

题四

有$10^7$个用户，编号从1开始，这些用户中有m个关系，每一对关系用两个数x,y表示，意味着用户x和用户y在同一圈子，关系具有传递性，A和B是同一个圈子，B和C是同一个圈子，则A，B，C就在同一个圈子。问最大的圈子有多少个用户。

这道题论坛给的方法是并查集，可惜我还没写过。但是还有一种直接使用集合运算的方法：

T = int(input())

def setIndex(target, uf):
    for idx, comp in enumerate(uf):
        if target in comp:
            return idx
    return -1

for t in range(T):
    n = int(input())
    uf = []
    for N in range(n):
        line = input().split(" ")
        x = int(line[0])
        y = int(line[1])
        xi = setIndex(x, uf)
        yi = setIndex(y, uf)
        if (xi == -1) and (yi == -1): #不在集合
            uf.append(set([x, y]))
        elif xi == -1: #y在集合
            uf[yi].add(x)
        elif yi == -1: #x在集合
            uf[xi].add(y)
        else: #都在集合
            uf[xi] = uf[xi].union(uf[yi])
            del uf[yi]

    print(len(max(uf, key=lambda x: len(x))))

题五

N个人排成一列，现在要让他们按身高从低到高排列，每次只能交换相邻两个人的位置，问最少需要多少次。

输入：第一行是人数，第二行开始每行为身高。

这道题调用bisect会比较好做一点，即仿照插入排序的方法进行排序，每次将新数字插入前面排好的位置。

from bisect import bisect_left

n = int(input())
l = []
for i in range(n):
    l.append(int(input()))
List,cnt = [l[0]],0
for i in range(1,n):
    pos = bisect_left(List,l[i])
    cnt+=abs(i-pos)
    List.insert(pos,l[i])
print(cnt)