https://hihocoder.com/contest/mstest2015octpractice/problem/1
思路：肯定是吧聯(lián)系的天數(shù)補(bǔ)簽了啊盒延，這樣結(jié)果才能最長
cases=int(raw_input())
for _ in range(cases):
n,m=map(int,raw_input().strip().split(' '))
a=map(int,raw_input().strip().split(' '))
if m>=n:
print 100
continue
ma=a[m]-1
for i in range(m,n-1):
ma=max(ma,a[i+1]-1-a[i-m])
ma=max(ma,100-a[n-m])
print ma
https://hihocoder.com/contest/mstest2015octpractice/problem/3
思路：直接DFS肯定不行演闭，有博客是說用bitset表示當(dāng)前位置可以到達(dá)的地方宦棺，這樣DFS遍歷的時(shí)候就可以prune很多
https://blog.csdn.net/ldw201510803006/article/details/71272679
https://blog.csdn.net/lisong_jerry/article/details/76474781
目前寫出來的代碼有bug，不知道哪里錯(cuò)了肠仪，有點(diǎn)泄氣啊，明明秋招都開始了，自己還是半吊子水平喝滞，真的很難受
from collections import defaultdict
T=int(raw_input())
def getChild(p,c,bitset,adj):
bitset[c]|=1<<c
for t in adj[c]:
if t==p: continue
getChild(c, t, bitset,adj)
bitset[c]|=bitset[t]
def dfs(p,c,bitset,m,idx,vis,adj):
# print(idx)
if c==m[idx]: idx+=1
if idx==len(m): return True
for t in adj[c]:
if bitset[t]&(1<<m[idx]) and not vis[t]:
# if current is in latter m: break
vis[t]=True
if dfs(c,t,bitset,m,idx,vis,adj): return True
# vis[t]=False
return False
for _ in range(T):
n=int(raw_input())
adj=defaultdict(set)
for t in range(n-1):
i,j=map(int,raw_input().strip().split(' '))
adj[i].add(j)
adj[j].add(i)
mt=int(raw_input())
m=map(int,raw_input().strip().split(' '))
bitset=[0]*(n+1)
getChild(-1,1,bitset,adj)
vis=[False]*(1+n)
vis[1]=True
print 'YES' if dfs(-1,1,bitset,m,0,vis,adj) else 'No'
https://hihocoder.com/contest/mstest2017april/problems
題目1 : Queen Attack
思路：統(tǒng)計(jì)x，y膏秫，x+y（把點(diǎn)沿著對角線平移到x軸）右遭，x-y（沿著例外一個(gè)對角線平移）
from collections import Counter
n=int(raw_input())
a=[(0,0)]*n
for i in range(n):
t=map(int,raw_input().strip().split(' '))
a[i]=(t[0],t[1])
res=0
dx=Counter([t[0] for t in a])
for k in dx.values():
res+=k*(k-1)/2
dy=Counter([t[1] for t in a])
for k in dy.values():
res+=k*(k-1)/2
dxy=Counter([t[1]-t[0] for t in a])
for k in dxy.values():
res+=k*(k-1)/2
dyx=Counter([t[0]+t[1] for t in a])
for k in dyx.values():
res+=k*(k-1)/2
print res
題目2 : Diligent Robots
http://www.cnblogs.com/ECJTUACM-873284962/p/7136061.html
https://www.cnblogs.com/zufezzt/p/6683153.html
每個(gè)輪回要么所有robot復(fù)制，要么都用來生產(chǎn)
n,q=map(int,raw_input().strip().split(' '))
c,r=1,0
res=n
while 1:
t=n//c+r
if n%c: t+=1
res=min(res,t)
c=2*c
r+=q
if c>n: break
print res
題目3 : A Box of Coins
思路：貪心：
從最左邊考慮缤削，如果上下之間有一個(gè)有盈余窘哈，必定是相互補(bǔ)充最優(yōu)。
其次 如果上下兩個(gè)都有富余亭敢，則都往右邊輸送
再者 如果上下之間都缺乏滚婉，則都向左借
模擬即可 ，感覺自己成智障了帅刀，woc让腹，這樣的題也不會(huì)了
n=int(raw_input())
a,b=[0]*n,[0]*n
for i in range(n):
a[i],b[i]=map(int,raw_input().strip().split(' '))
su=sum(a)+sum(b)
ta=su//2//n
res=0
for i in range(n-1):
ai,bi=a[i],b[i]
if (ai>=ta and bi>=ta):
res+=ai-ta+bi-ta
a[i+1]+=ai-ta
b[i+1]+=bi-ta
elif ai<=ta and bi<=ta:
res+=abs(ai-ta+bi-ta)
a[i+1]+=ai-ta
b[i+1]+=bi-ta
elif ai<ta:
if ai+bi>=2*ta:
res+=bi-ta
b[i+1]+=bi-ta-(ta-ai)
else:
res+=ta-ai
a[i+1]-=ta-ai-(bi-ta)
else:
if ai+bi>=2*ta:
res+=ai-ta
a[i+1]+=ai-ta-(ta-bi)
else:
res+=ta-bi
b[i+1]-=ta-bi-(ai-ta)
print res+abs(a[-1]-ta)
題目4 : EL SUENO
思路：樹狀DP，就是邊DFS扣溺，邊DP骇窍，每次DP就是個(gè)01背包問題
https://blog.csdn.net/viphong/article/details/70163053
from collections import defaultdict
inf=float('inf')
n=int(raw_input())
xs=defaultdict(list)
boss=-1
inf0,inf1,c=[0]*(n+1),[0]*(n+1),[0]*(n+1)
for i in range(1,n+1):
f,inf0[i],inf1[i],c[i]=map(int,raw_input().strip().split(' '))
if f==0: boss=i
else: xs[f].append(i)
def dfs(b):
dp=[inf]*(1+inf0[b])
dp[0]=0
for x in xs[b]:
t=dfs(x)
for j in range(len(dp)-1,0,-1):
dp[j]=min(dp[j], dp[max(j-inf1[x],0)]+t+c[x])
return dp[-1]
res=dfs(boss)+c[boss]
print res if res!=inf else -1
https://hihocoder.com/contest/mstest2016oct/problem/2
題目2 : Composition
思路：DP，最開始想直接用dp[i]表示到i位置需要的最小delete數(shù)锥余，但是這樣你根本無法狀態(tài)轉(zhuǎn)移案鼓伞！Ｇ獭嘲恍！因?yàn)閐p[i]根本就沒有表示出狀態(tài)信息！着绷！
因?yàn)橹皇遣荒芟噜徎赘疲杂胐p[i][j]表示到i位置未知，以j結(jié)尾的最小delete數(shù)
感覺老是刷LC荠医，都快overfitting了
from collections import defaultdict
n=int(raw_input())
s=raw_input()
m=int(raw_input())
d=defaultdict(set)
for _ in range(m):
t=raw_input()
t0=ord(t[0])-ord('a')
t1=ord(t[1])-ord('a')
d[t0].add(t1)
d[t1].add(t0)
#
dp=[[float('inf') for _ in range(26)] for _ in range(n)]
dp[0]=[1]*26
dp[0][ord(s[0])-ord('a')]=0
for i in range(1,n):
for j in range(26):
dp[i][j]=dp[i-1][j]+1
j=ord(s[i])-ord('a')
for k in range(26):
if k in d[j]: continue
dp[i][j]=min(dp[i][j], dp[i-1][k])
print min(dp[-1])
