阶段性测试题解

助教机器人

a=input()
if (a=='Why was I right on my machine, but WA on OJ?'):
    print('OJ must be broken!')
elif (a=='Why did my code work out the wrong result?'):
    print('Output intermediate variables during running, and find error!')
elif (a=='I do not know what data my code would go wrong on!'):
    print('Here may be the data you need!')
else:
    print('Let me have a look.')

注意中间是elif连接的,很多人WA在这上面.

自闭程度

n,m=map(int,input().split())
a=[]
for i in range(m):
    x,y=map(int,input().split())
    a.append(y)
if (a.count(1)==n):
    print('-998244353')
elif (a.count(0)==m):
    print('998244353')
else:
    print(50*(n-a.count(1))-100*a.count(1))

思路很简单,统计一下提交序列中有多少个1就可以了.

这里解释一下90分WA的原因.正常的题目中,数字和数学公式是要进行数学公式渲染的,题面中的那个-998244353也进行渲染了.但是OJ后台的这个Markdown编辑器比较地奇葩,把那个负号被渲染成了一个ASCII码为8722的奇怪符号(我做了这么多题还是头一次听说这情况).导致有同学直接复制题目描述的输出的时候出现了问题,符号的输出其实是错误的,最终WA在了第一个点上(也就是样例1).所以在这里澄清一下,出题的时候是绝对没有想着在这里挖坑的,验题的环节也没人发现OJ上的那个负号其实是假的...

最后推荐大家以后直接复制样例中的输出,不要复制题面中的QAQ

汉诺塔栈

T=int(input())
for i in range(T):
    a=list(map(int,input().split()))
    ans=0
    for j in range(len(a)):
        for k in range(j):
            if (a[k]<a[j]):
                ans+=1
    print(ans)

其实这道题和栈根本就没有关系...

根据题意,如果这个盘子大于栈首的盘子,那么就要先把栈首的盘子拿出来.也就是说,对于原序列,第i个盘子前有多少个盘子比它小,那么在放入第i个盘子的时候就要进行多少次出栈操作,也就是逆序对的数量.

题面中有个纰漏,本来是"不大于"的,结果OJ和PDF上错写成"大于",后来第一次修改的时候比较着急,改成了"小于",忽视了等于的情况,导致很多人在这道题上卡了不少时间.这个问题确实是出题组的锅,所以在这里向大家表示歉意.后期给分的时候,也会针对这个问题给出一定的补偿(加分)策略.

异或序列

本题有三档部分分,先看60分的这一档:

n=int(input())
a=list(map(int,input().split()))
ans=0
for i in range(len(a)):
    for j in range(i,len(a)):
        x=0
        for k in range(i,j+1):
            x^=a[k]
        if (x==0):
            ans+=1
print(ans)

枚举区间左端点,再枚举区间右端点,计算区间异或值,统计答案.很纯粹的一个暴力.因为是一个三重循环,时间复杂度为O(n^3),只能拿到前60分.

接下来是第一次优化,有两种优化策略.第一种是,假如说我们枚举的左端点是l,右端点将会依次枚举l+1,l+2,...,n,从上面的代码中可以看出,每一次枚举一个新的右端点,都重新算了一遍异或值,但是右端点其实只比上次多向后移了一位,导致进行了大量的重复计算,所以,为了充分利用之前的计算结果,优化代码如下:

n=int(input())
a=list(map(int,input().split()))
ans=0
for i in range(len(a)):
    x=0
    for j in range(i,len(a)):
        x^=a[j]
        if (x==0):
            ans+=1
print(ans)

每一次在上次的异或结果上再异或一个数就行了,复杂度降为了O(n^2),可以拿到80分.

但是这个优化策略并没有利用性质2和性质3.有的同学可能有印象,我曾经在第三周周报提过这么一句话:

(其实很久以前就在为期中考试的部分分埋下伏笔了,没想到吧)

忘记前缀和优化是什么的请移步第三周周报

简单来说,原来的前缀和优化是s_{r}-s_{l-1},现在针对异或操作,前缀和改成前缀异或,然后某段区间的异或值就可以表示成s_{r} \ xor \ s_{l-1}.原理很简单,一个数异或自身是0.那么异或上s_{l-1},相当于把前面这l-1个数的异或值给消去了,就可以得到[l,r]这个区间的异或值了.根据这个思路,有了如下代码:

n=int(input())
a=[0]+list(map(int,input().split()))
s=[0 for i in range(n+10)]
ans=0
for i in range(1,len(a)):
    s[i]=s[i-1]^a[i]
for i in range(1,len(a)):
    for j in range(i,len(a)):
        if (s[i-1]^s[j]==0):
            ans+=1
print(ans)

下标之所以从1开始是为了方便,不然i-1可能取到-1,会出问题.

这份代码也是O(n^{2})的,能拿到80分,距离满分其实已经非常的接近了.然后注意到这个代码里的最核心的式子:

s[i-1]^s[j]==0

回想一下性质2:当且仅当两个数相等时,异或值为0.也就是说,当且仅当s[i-1]和s[j]相等的时候,答案才会+1.

所以,只需要统计一下,s这个列表中有多少个1,多少个2,多少个3,......然后,假设某个数有x个,那么就会为答案产生C_{x}^{2}=\frac{x(x-1)}{2}的贡献.有一个地方需要注意,s[i-1]的下标是从0开始的,也就是s[0]会参与运算,所以在统计的时候不要忘了统计最前头这个0,

最后的优化结果:

n=int(input())
a=[0]+list(map(int,input().split()))
s=[0 for i in range(n+10)]
c=[0 for i in range(n+1000)]
ans=0
for i in range(1,len(a)):
    s[i]=s[i-1]^a[i]
    c[s[i]]+=1
c[0]+=1
for i in range(len(c)):
    ans+=c[i]*(c[i]-1)//2
print(ans)

时间复杂度降为了O(n),可以拿到100分.

VSCode配置指北

写在最前面的话

首先要声明,这部分内容并不是推荐所有人都去安装配置VSCode,而是给已经安装了或是正打算安装VSCode的同学提供一个简单的指南.如果你的代码实现能力还不强,做必做题感觉有些吃力的话,我推荐还是把精力更多地放在刷题上,而不是花大量的时间去配置一款编辑器.VSCode的配置过程可以说是个吃时间的无底洞,希望同学们能掌握好这个度,把VSCode配置到能满足自己的需求就可以了,不要过于追求一些花哨的东西.

安装及基本插件的选择

直接在官网下载安装包即可:官网.下载完毕后,一路next正常安装.

安装完成后打开.以我的VSCode为例,讲一下基本的布局:

最左边有五个按钮(最后一个是我后来装的拓展,不用在意).从上到下,依次是当前文件夹文件目录,搜索框,Debug栏,拓展页面以及Git代码托管.(顺序可能和大家的有所不同,因为我可能后来自己修改过,认一下图标就可以了).图中是选中了当前文件夹目录,可以在左侧看到当前文件夹下的所有文件.中间的部分是代码编辑区,最下面是终端,右上角是代码的略缩图,可以通过它快速跳转到某个位置.

上面是安装了中文拓展包的结果,而且装了一个背景图的拓展,不用在意这些区别.细心的同学可能发现了这就是最后一题造输出数据的代码

安装完毕后,打开VSCode,点击拓展按钮,会出一个搜索框.然后依次搜索Chinese(简体中文),Python(这个不需要解释),C++(大部分人在大二会学C,所以提前准备好),vscode-icons(一个简单的图标美化拓展).搜索完成后,均选择第一个搜索出的结果,然后点Install.全部安装完成后,退出VSCode,再重进一下,这样刚刚的拓展才会被启用.

VSCode是基于文件夹工作的,所以在运行代码前要选择好文件夹.点击左上角的文件->打开文件夹,然后选中你平时放代码的文件夹,点击确定就可以了.然后点击右边的当前文件目录,就会看到之前写的所有代码.注意,文件夹目录及文件夹名不要带有任何中文!不然可能会产生一些奇怪的错误,我这里不会讲怎么强制使用中文目录.

随便点击进入一个之前的代码,在代码编辑区右键,找到在终端中运行Python文件,点击后就可以正常运行了.下方的终端可以进行交互,和Spyder右下角的交互区是类似的.(VSCode 的终端支持一次粘贴多行数据).也可以自己修改下快捷键,使用快捷键运行也可以.

剩下的内容就靠自己摸索了~

VSCode基本功能介绍

1. 代码补全

比如你起了一个变量名叫helloworld,那么在下面使用的时候,打出hel就会弹出提示,直接回车,VSCode就把这个变量名自动补全了.在变量名比较长的时候这个功能及其实用.

2. 错误提示

每写完一段代码,Ctrl+S保存,下面终端的问题区会给出代码中的语法错误的提示.(根据我的测试,好像只对C,C++语言有用...)

3. Debug

可以打断点,监视变量,相比Spyder好上手很多.

4. 代码片段

可以通过设置代码片段,然后在写代码的时候打出特定的某几个字符,回车,VSCode会根据设置好的内容自动补上一段代码(长度,格式,甚至补全后光标出现的位置均可自定义).请自行上网查找配置教程.

5. 丰富的主题方案

网上有很多美化教程,这里也不展开介绍.

深度拓展

参考之前的一篇文章:VSCode配置笔记.不过大部分内容是C++相关的,有需求的同学可以参考一下.里面的配色方案和插件推荐也可以看一下.