https://hihocoder.com/contest/mstest2015octpractice/problem/1
思路：肯定是吧联系的天数补签了啊，这样结果才能最长
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表示当前位置可以到达的地方，这样DFS遍历的时候就可以prune很多
https://blog.csdn.net/ldw201510803006/article/details/71272679
https://blog.csdn.net/lisong_jerry/article/details/76474781
目前写出来的代码有bug，不知道哪里错了，有点泄气啊，明明秋招都开始了，自己还是半吊子水平，真的很难受
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
思路：统计x，y，x+y（把点沿着对角线平移到x轴），x-y（沿着例外一个对角线平移）
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
每个轮回要么所有robot复制，要么都用来生产
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
思路：贪心：
从最左边考虑，如果上下之间有一个有盈余，必定是相互补充最优。
其次 如果上下两个都有富余，则都往右边输送
再者 如果上下之间都缺乏，则都向左借
模拟即可 ，感觉自己成智障了，woc，这样的题也不会了
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就是个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数，但是这样你根本无法状态转移啊！！！因为dp[i]根本就没有表示出状态信息！！
因为只是不能相邻，所以用dp[i][j]表示到i位置未知，以j结尾的最小delete数
感觉老是刷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])
