牛学奥林匹克

〇〇

s=[1,2,3,4,3,2,5]

ml=[0 for i in range(len(s))]
mr=[len(s)-1 for i in range(len(s))]
#ml,mr分别保存每个位置的最长左右子串的终点位置
def pre(s):
x=len(s)
for i in range(x):
   for j in range(i+1,x):
     if s[j]==s[i]:
       mr[i]=j-1
       break
   for j in range(i-1,0,-1):
     if s[j]==s[i]:
       ml[i]=j+1
       break

pre(s)
>>> ml
[0, 0, 0, 0, 3, 2, 0]
>>> mr
[6, 4, 3, 6, 6, 6, 6]
>>> s
[1, 2, 3, 4, 3, 2, 5]      
  
def j3(b,e):
     x=[]
     l,r=s[b],s[e]
     if l!=r and mr[b] >=e and ml[e] <=b:
       if e-b==2:
        x.append(1)
       else:
        for i in range(1,e-b):
         if mr[b+i] >=e and ml[b+i] <=b:
           x.append(i)
     return len(x),x

def lp3(s):
     cnt=0
     for b in range(0,len(s)-2):
      for e in range(b+2,len(s)):
        s1=s[b:e+1]
        #print("test ",s1)
        c,x=j3(b,e)
        if c>0:
          #print(s1)
          #for y in x:
            #print("lead",(b+1,b+y+1,e+1))
          cnt+=c
     print("cnt=",cnt)

>>> lp3(s)
cnt= 19600
>>> s=list(range(200))
>>> ml=[0 for i in range(len(s))]
>>> mr=[len(s)-1 for i in range(len(s))]
>>> pre(s)
>>> t=time.time();lp(s);print(time.time()-t)
cnt= 1313400
11.5908203125
>>> t=time.time();lp3(s);print(time.time()-t)
cnt= 1313400
1.029601812362671
#比原始快了10倍
>>> s=list(range(300))
>>> ml=[0 for i in range(len(s))]
>>> mr=[len(s)-1 for i in range(len(s))]
>>> pre(s)
>>> t=time.time();lp3(s);print(time.time()-t)
cnt= 4455100
3.2916059494018555

#不保存领队，只计数
def j4(b,e):
     x=[]
     l,r=s[b],s[e]
     c=0
     if l!=r and mr[b] >=e and ml[e] <=b:
       if e-b==2:
        c=1
       else:
        for i in range(1,e-b):
         if mr[b+i] >=e and ml[b+i] <=b:
           c+=1
     return c

def lp4(s):
     cnt=0
     for b in range(0,len(s)-2):
      for e in range(b+2,len(s)):
        c=j4(b,e)
        if c>0:
          cnt+=c
     print("cnt=",cnt)

>>> t=time.time();lp4(s);print(time.time()-t)
cnt= 4455100
3.057605504989624
#没有提高

〇〇

我的是O(NNN)的，标准答案
http://usaco.org/current/data/sol_prob1_platinum_open21.html
有个很强大很短的O(NN),没看懂，改写如下

def nn(B):
        ans = 0
        N=len(B)
        for r in range(0,N) :
                occ =[0 for i in range(N+1)]
                unique = 0
                for l in range(r-1, -1,-1) :
                        if (B[l] == B[r]): break
                        occ[B[l]]+=1
                        if (occ[B[l]]== 1) :
                                ans += unique
                                unique+=1
                        elif (occ[B[l]] == 2) :
                                unique-=1
        print(ans)
       


t=time.time();nn(s);print(time.time()-t)
cnt= 4455100
1.54115891456604
4455100
0.023647546768188477

[Program finished]

〇〇

O(NN)对20万还是太慢，所以答案里有O(NlogN)的程序

〇〇

前面是白金级的题，还有黄金级，2个领队。
http://usaco.org/index.php?page=viewproblem2&cpid=1137&lang=zh

jihuyao

Take 12234556 as input.  For m in 1..8, for n in m+1..8, do something, end.  Now if n=1, start=1, end={4,6}, and mid={...} for each end.  For n=2 start=2 exit from loop m because 2nd 2 found before length=3.  For n=3, start=2 end={4,6} ... for n=4, start=3 end={6} ... for n=5,6 no valid. For n>6 no enough member (so should be m in 1..6 loop).  I can understand without exit in the nested loop it is about N*N in total loop processing.  But what is N*logN?

〇〇

http://usaco.org/index.php?page=dec21results 12月