AC：1/3，score=1.4

https://ac.nowcoder.com/acm/contest/6915
第一题10分钟秒了，第二题知道怎么做写不出代码，第三题感觉代码写对了思路也对了，只能过40%，原来是递归受限，可惜了，但是好歹也小幅提升。

第一题：

题目：

答案：

class Solution:
    def numbers(self , a , b , c , d , p ):
        # write code here
        x1=0
        y1=0
        def getp(a,b,p):
            k=a%p
            if k==0:temp=a
            else:temp = a+p-k
            if temp>b:return 0
            return (b-temp)//p+1
        x1=getp(a,b,p)
        y1=getp(c,d,p)
        x2=b-a+1-x1
        y2=d-c+1-y1
        return x1*y2+x1*y1+y1*x2

思路：

答案是xp数ynp数+xp数yp数+yp数*xnp数
主要数两个区间的p数有多少就可以了b``// p - (a-1) // p。写的稍微复杂一点也无伤大雅。

第二题：

题目：

答案：

# class Point:
#     def __init__(self, a=0, b=0):
#         self.x = a
#         self.y = b
#
# 牛牛经过的房间数。
# @param n int整型 
# @param x int整型 
# @param Edge Point类一维数组 
# @return int整型
#
from collections import defaultdict
class Solution:
    def solve(self , n , x , Edge ):
        if x==1:return 0
        graph=defaultdict(list)
        for node in Edge:
            graph[node.x].append(node.y)
            graph[node.y].append(node.x)
        dx=[0]*(n+1)
        stack=[(-1,x,1)]# pre,cur,d
        while stack:
            pre,cur,d= stack.pop()
            dx[cur]=d
            for node in graph[cur]:
                if node!=pre:
                    stack.append((cur,node,d+1))
        ans=0
        stack=[(-1,1,1)]
        while stack:
            pre,cur,d=stack.pop()
            if d>dx[cur] and d>ans:
                ans=d
            for node in graph[cur]:
                if node!=pre:
                    stack.append((cur,node,d+1))
        return ans

思路：

x==1特判，考试时提醒过的。
评论区说dfs 可能会爆，你看我上面和下面都是dfs，事实上不会爆，是因为递归会爆，要import sys设置一下，下面的代码是dfs递归的。
第一个搜索，找出距离x的距离
第二个搜索，找出距离1的距离
答案更新：距离1的大于距离x的，就可以更新了，注意第一个房间也算，所以起点为1.

import sys
sys.setrecursionlimit(10000000)
class Solution:
    def solve(self , n , x , Edge ):
        # write code here
        from collections import defaultdict
        if x == 1:
            return 0
        graph = defaultdict(list)
        for i in Edge:
            graph[i.x].append(i.y)
            graph[i.y].append(i.x)
        dx = [0]*(n+1)
        def dfx(pre, cur, d):
            dx[cur] = d
            for q in graph[cur]:
                if q != pre:
                    dfx(cur, q, d+1)
        dfx(-1, x, 1)
        result = [0]
        def dfs(pre, cur, d):
            if d > dx[cur]:
                if d > result[0]:
                    result[0] = d
            for q in graph[cur]:
                if q != pre:
                    dfs(cur, q, d+1)
        dfs(-1, 1, 1)
        return result[0]

第三题：

题目：

答案：

import sys
sys.setrecursionlimit(10000000)
class Solution:
    def arrange(self , firstRow , secondRow ):
        n=len(firstRow)
        def dfs(i,count):
            if i==n:
                self.ans=min(self.ans,count)
                return
            if i==0:
                dfs(i+1,count)
                firstRow[i],secondRow[i]=secondRow[i],firstRow[i]
                dfs(i+1,count+1)
                firstRow[i],secondRow[i]=secondRow[i],firstRow[i]
            else:
                if firstRow[i]<firstRow[i-1] and secondRow[i]>secondRow[i-1]:
                    dfs(i+1,count)
                if firstRow[i]>secondRow[i-1] and secondRow[i]<firstRow[i-1]:
                    firstRow[i],secondRow[i]=secondRow[i],firstRow[i]
                    dfs(i+1,count+1)
                    firstRow[i],secondRow[i]=secondRow[i],firstRow[i]
            return
        self.ans=float("inf")
        dfs(0,0)
        if self.ans==float("inf"):return -1
        return self.ans

思路：

我的思路是对的，只不过在牛客网递归有限制，要import sys 设置一下，我的本质还是dp。