4. 递增三元组
问题分析：遍历数组b，当访问到b[i]，统计a中<b[i]的个数p，统计c中>b[i]的个数q
cnt：作为答案输出;统计完后,cnt+=p*q
那么该如何统计？
最简单的方法:先将a,c排序 遍历a(c)，统计个数即可 但这样只能过75分
n=int(input()) a=list(map(int,input().split())) b=list(map(int,input().split())) c=list(map(int,input().split())) a.sort() c.sort(reverse=True) cnt=0 for i in range(n): j,k=0,0 t=b[i] while j<=n-1 and a[j]<t:j+=1 while k<=n-1 and c[k]>t:k+=1 cnt+=j*k print(j,k) print(cnt)#超时 75分
如何优化：利用前缀和，用空间换时间，每次统计的时候直接从列表查询
对于数组a而言，创建一个列表ans,ans[i]代表i在数组a中出现的次数
对于数组c而言，创建一个列表cns,cns[i]代表i在数组c中出现的次数
创建一个数组x,作为ans的前缀和,x[i]代表数组a中<=i的数字出现的次数
创建一个数组y,作为cns的前缀和,y[i]代表数组c中<=i的数字出现的次数
对于一个一个确定的b[i] 我们统计a中<b[i]的个数，即查询p=x[b[i]-1]
对于一个一个确定的b[i] 我们统计c中>b[i]的个数，即查询q=y[-1]-y[b[i]]
细节的地方：对于x[b[i]-1]，b[i]-1有可能越界，即b[i]-1>len(x)-1
那么q=x[-1],这是由于a中最大的元素可能比b[i]-1还要小，所以此时前缀和x的最大下标小于b[i]-1，那么a中小于b[i]的个数一定也就是x[-1]个
同时，b[i]-1有可能变为负数，，即b[i]<1，即b[i]=0，但那对应的x[b[i]-1]并不是我们想要的。实际上，这种特殊情况,p=0，因为a中不会有比0更小的数字了。
对于y[-1]-y[b[i]],y[b[i]]有可能越界，如果len(y)-1<=b[i]，那么意味着c中最大的元素小于b[i]，那么q=0，因为c中不会有比b[i]更大的数字了。
n=int(input()) a=list(map(int,input().split())) b=list(map(int,input().split())) c=list(map(int,input().split())) ans=[0 for i in range(max(a)+1)] for i in a: ans[i]+=1 x=[0 for i in range(max(a)+1)] x[0]=a.count(0) for j in range(1,max(a)+1): x[j]=x[j-1]+ans[j] cns=[0 for i in range(max(c)+1)] for i in c: cns[i]+=1 y=[0 for i in range(max(c)+1)] y[0]=c.count(0) for j in range(1,max(c)+1): y[j]=y[j-1]+cns[j] cnt=0 for k in range(n): if b[k]-1>len(x)-1: p=x[-1] elif b[k]-1<0: p=0 else: p=x[b[k]-1] if len(y)-1<=b[k]: q=0 else: q=y[-1]-y[b[k]] cnt+=p*q print(cnt)
5. 发现环
问题分析：利用拓扑排序来检测环 可以看我之前这篇文章
!!如果对拓扑排序没有理解的，下面讲的会很难理解，需要基于对拓扑排序的理解基础！
与有向图应用的拓扑排序不同：我们需要做几点改变
第一个就是入度的概念：之前的入度指的是其他点指向u点的边数
这里由于是无向图 只要其他点连着u点，不论方向，边数都应该累加进来
第二个就是：原有删除结点是基于该结点的入度为0，这里需要稍作改变，改作入度为1
其他的保持不变，最后输出[1,2....,N]和拓扑序列seq的差集再排序一下就好了
#构图 n=int(input()) G=dict((i,[]) for i in range(1,n+1)) for i in range(n): x,y=map(int,input().split()) G[x].append(y) G[y].append(x) indegrees=dict((i,0) for i in G.keys()) for i in G.keys(): for j in G[i]: indegrees[j]+=1 stack=[i for i in indegrees.keys() if indegrees[i]==1] seq=[]#拓扑序列 while stack: tmp=stack.pop() seq.append(tmp) for i in G[tmp]: indegrees[i]-=1 if indegrees[i]==1: stack.append(i) ans=list(set([i for i in range(1,n+1)])-set(seq)) ans.sort() for i in range(len(ans)-1): print(ans[i],end=' ') print(ans[-1])
有任何疑惑欢迎提问！程序题还是要自己多尝试多实践！
