比赛注意事项

1. 在所有的实验中,严格禁止代码抄袭的行为,之后一经发现当次实验成绩直接归零.请不要小看代码查重程序,不要报任何侥幸心理,我可以保证你目前能想到的降低相似度的方法都没有用.之后期中期末考试的排名也会和你之前的排名进行比对,异常波动的会对之前实验中的提交进行二次查重.
2. 很多人问为什么本地测试通过了但是OJ上WA/TLE/PE.这个问题强调过了,本地能通过样例说明不了任何问题.你的代码里仍可能存在没有被发现的bug;或者是时间复杂度不对,小范围的数据测不出TLE.发现代码没有AC后请根据反馈结果在本地继续Debug.
3. 有人反映OJ可以正常登陆,但是打不开比赛页面.首先换浏览器,这里明确说明不要用360浏览器,搜狗浏览器,IE浏览器.换成火狐或者是Chrome,最好两个都装,哪个访问快用哪个.然后网页VPN可能有时候不好用,最好提前再安装上VPN客户端(安装完客户端后直接在浏览器中输入网址就行了).如果是在比赛期间突然发生这种情况,请及时联系助教.如果对做题产生了较大影响,请在实验报告中注明这一点.比赛期间学校VPN的访问压力很大,请大家理解.

上机题目题解

Fizzbuzz

n=int(input())
for i in range(n):
    s=int(input())
    if (s%5==0 and s%3==0):
        print('fizzbuzz')
    elif (s%5==0):
        print('buzz')
    elif (s%3==0):
        print('fizz')
    else:
        print(s)

有很多同学问n+1行该怎么读入.首先要审题,n+1行分为两部分,第一行是正整数n,后面跟着n行数据.你可以先把第一行读进来再通过一个循环读入后面的数据.

对话过滤

c=input()
flag=-1
for i in c:
    x=ord(i)
    if (97<=x<=122):
        x-=32
    if (65<=x<=90):#是字母
        if (x != flag):#和上次不同
            print(i,end='')
            flag=x#更新
    else:#不是字母直接输出
        print(i,end='')
        flag=x#更新

这次实验的第二题非常惨烈,很多同学卡在了"连续相同的字母只保留一个"这个条件上.很多人写的字符串切片或者是用了各种函数来判断.其实思路并不是很复杂.首先一位位地输出,假如我们输出了一个字母,那么在这个字母后面,如果再出现相同的字母,忽略;否则输出这个新的字符,然后重新记录上次输出的字符是什么就行了.

我这里没有用指导书给出的函数,而是按照个人习惯用ASCII码进行判断.flag变量记录的是上次输出的字符是什么.首先得到即将被输出的字符的ASCII码.如果发现是小写字母就转成大写,方便之后判断.然后如果即将被输出的字符是字母,那么进行进一步判断,看和上次输出的是否一样.如果不一样,输出,更新flag.如果不是字母,直接输出,更新flag.

Cantor表

n=int(input())
for i in range(1,n+1):
    for j in range(1,n-i+1):
        print(i,'/',j,sep='',end=' ')
    print(i,'/',(n-i+1),sep='')

注意循环次数的设置.

在答疑的时候见到了非常多的下面这种写法:

print('\n')

这样的话是输出两个换行符,因为print在输出时自带一个换行符.当你只需要换一行时,写

print('')

就行了.很多的PE也是因为多输出了好多换行符.

题目中说行末不要有多余的空格可能给大家造成了一些影响,其实行末有空格OJ也会判定为AC......我们并没有把评测系统的等级调的那么高.所以以后在做题的时候,每一行后面多余的空格,最后一行后面多余的回车都不需要处理.如果需要处理会在题面中进行说明(这次是忘了删了QAQ).

新数根的计算

ans=n=int(input())
while n>=10:
    ans=1
    while n:
        x=n%10
        if (x):
            ans*=x
        n//=10
    n=ans
print(ans)

当面对不定次数的循环时,需要用while.

注意终止条件是n<10.while循环的条件是有等号的,很多人忽略了题目中说的数根是个位数的条件.

对于一个正整数,如果我们想得到他的各位上的值,我们通常使用上面这种方法,一位位整除取模获取.一般不会把这个数转化为字符串,再遍历字符串.因为这种写法很麻烦,而且转化的过程会带来大量的时间消耗.这道题如果是类似第一题那样的多组数据可能会TLE.

第k对角线

n=int(input())
k=int(input())
flag=int(input())
if (flag==1):
    flag=-1
    w=n-1
else:
    flag=1
    w=0#初始化部分
for i in range(n):
    for j in range(n):
        if (j==w+k or j==w-k):#距离为k
            print('x',end='')
        else:
            print('*',end='')
    print('')#换行符
    w=w+flag#下一行的对角线向左或者向右移动

w记录的是原本的对角线应该出现在这一行的第几个.flag用于控制后一行的对角线的位置相对于前一行是向左还是向右移动.根据题意,当距离原本位置的对角线k个距离的时候输出x即可.

中国剩余定理

首先说明,这道题目中对逆元的描述是极其不严谨的,和数论中的概念不符,请大家注意.只是为了解题方便简化了逆元的概念.

下面是正确代码:

p=[0 for i in range(1000)]#模数
r=[0 for i in range(1000)]#余数
#个人习惯,提前开好list(C++系写法).用append当然也行
n=int(input())
P=1#用于计算模数之积
t=inv=ans=0

for i in range(n):
    p[i],r[i]=map(int,input().split())
    P=P*p[i]#计算模数之积

for i in range(n):
    t=P//p[i]
    inv=1#数论定义中真正的逆元
    while t*inv%p[i]!=1:
        inv+=1#采用暴力枚举的方法按照题目要求计算.如果inv不是逆元,直接加1.
    ans=(ans+r[i]*inv*t)%P#按照公式计算答案.对P取模的原因是最后的答案一定是不超过P的.

if (ans==0):
    print(P)#很多人WA在了这一点,题目要求输出的是正整数,如果ans=0,是需要输出P的.
else:
    print(ans)

TLE的原因是,在计算P//p[i]的时候写成了int(P/p[i]),浮点数除法加上int类型转换使得程序的常数大大增加,最后导致TLE.

WA的原因一般是忘记考虑输出正整数了.

在比赛期间我看见好几位大佬写了快速幂,想通过费马小定理直接求逆.但是最后都WA了.因为题目中并没有说模数一定是质数,只是说互质.所以要是想快速幂求逆的话还需要再求一下欧拉函数.或者干脆直接上拓展欧几里得定理求逆也行.

基于扩展欧几里得定理的方程组合并写法.

def extended_euclid(a, b) :
    if b==0 :
        return(a,1,0)
    else :
        res,x,y=extended_euclid(b,a%b)
        t=x
        x=y
        y=t-(a//b)*y
        return (res,x,y)

def Gcd(a,b):
    if (b==0):
        return a
    else:
        return Gcd(b,a%b)

n=int(input())
p=[0 for i in range(1000)]
r=[0 for i in range(1000)] 
GCD=1

for i in range(1,n+1):
    p[i],r[i]=map(int,input().split())
    GCD=GCD*p[i]

for i in range(1,n):
    a=p[i]
    b=p[i+1]
    c=r[i+1]-r[i]
    gcd=Gcd(a,b)
    a//=gcd
    b//=gcd
    c//=gcd
    gcd,k1,k2=extended_euclid(a,b)
    k1=((k1*c)%b+b)%b
    p[i+1]=p[i]//gcd*p[i+1]
    r[i+1]=(k1*p[i]%p[i+1]+r[i])%p[i+1]
if (r[n]==0):
    print(GCD+r[n])
else:
    print(r[n])

这份代码可以求任意模数的同余方程组,也就是可以忽略掉题目中模数互质这一条件.算法原理属于超纲内容,这里不做解释.感兴趣的同学可以移步这篇文章的后半部分.

知识补充

前缀和优化

引入例题:

给出一个长度为n的数字序列,第i位记为a_{i},下标从1开始.有m个询问操作,每一个询问给出一个区间[l,r].对于每一个询问,输出\sum_{i=l}^{r}a_{i} . 1 \leq n,m \leq 10^{5}

首先,我们有一个最朴素的做法,那就是对每一个询问操作,都通过一个for循环来计算这段数列的和.经过计算,时间复杂度为O(n^{2}),会超时.所以我们需要对询问部分进行优化.

观察一下上面的式子,\sum_{i=l}^{r}=\sum_{i=1}^{r}-\sum_{i=1}^{l-1},一段区间的和被拆成了从1开始的两端区间和的差.后两项和数列中的S_{n}类似.于是,在得到题目给出的序列后,我们可以先通过一个循环预处理出S_{n},然后对于每一个询问,我们就可以直接用S_{r}-S_{l-1}来回答.时间复杂度降为了O(n),可以满足要求.

示例代码:

n,m=map(int,input().split())
a=[0 for i in range(100010)]
s=[0 for i in range(100010)]
for i in range(1,n+1):
    a[i]=int(input())
for i in range(1,n+1):
    s[i]=s[i-1]+a[i] # 预处理出前缀和
for i in range(m):
    l,r=map(int,input().split())
    print(s[r]-s[l-1])

前缀和优化是一种很常见的优化手法,一般用于数列求一段连续区间和这样的操作.此外,根据异或操作的特性,一段序列的区间异或值也可以用类似前缀和的方法来优化.这部分不再展开叙述,感兴趣的同学可以自己想一下原理.

差分标记

引入例题:

给出一个长度为n的数字序列,第i位记为a_{i},下标从1开始,初始时每一位都是0.有m个操作,每一个操作给出一个区间[l,r]和一个数k.对于每一个操作,a_{i}的值要加上k,l \leq i \leq r.求所有操作完毕后,这个区间每个位置的值是多少. 1 \leq n,m \leq 10^{5}

朴素做法是,对于每一个操作,通过一个for给对应位置的值加上k.显然,这种写法的时间复杂度也是O(n^{2}),还需要进一步优化.这时引入差分标记.

题目中的修改操作是针对一段连续区间的.这意味着数值的增加从第l位开始,停止于第r+1位.我们希望把这个信息保留下来,等到所有的操作都处理完毕后一次性算出最终序列的值.

新建另外一个列表,记为s.对于一个操作l,r,k,对s进行以下修改:s_{l}+=k,s_{r+1}-=k.在所有操作处理完毕后求s的前缀和.对应位置的前缀和就是a的值.

我们通过下面的例子来理解这一过程.

假设序列长度为5,有3个操作.初始时s每一位都是0.

第一个操作是1,3,2,修改后:

第一个操作是2,4,3,修改后:

第三个操作是1,5,1,修改后:

求出的前缀和如下:

不难验证这就是最后的答案.

差分标记的原理是,在计算前缀和的时候,第l位的值增加了k,就会导致l之后每个位置的前缀和都增加了k.r+1位减去k,就是消除对第r位后面的影响,使得只有[l,r]这一段区间的每个位置的前缀和增加了k.于是就可以通过计算前缀和得到最后的序列.时间复杂度优化为了O(n).

示例代码如下:

n,m=map(int,input().split())
s=[0 for i in range(100010)]
for i in range(m):
    l,r,k=map(int,input().split())
    s[l]+=k
    s[r+1]-=k
for i in range(1,n+1):
    s[i]+=s[i-1]
    print(s[i])

上面两个补充的知识提供了两种优化算法的思路,一种是通过适当的预处理,减小之后每个操作所需的时间;另一种是把所有的操作先全部"攒"起来,等到最后一次性处理以节省时间.这是两种很重要的优化算法的思想,在之后的题目中也会有体现,希望大家仔细体会.