https://hihocoder.com/contest/offers74/problem/2
題目2 : 取球游戲
思路：union-find祭犯，同一個x對應(yīng)的點連在一起纺阔，同一個y對應(yīng)的點連在一起，并且一個聯(lián)通區(qū)域最后一定可以只剩下一個點
n=int(raw_input())
a=[]
for i in range(n):
t=map(int,raw_input().strip().split(' '))
a.append((t[0],t[1],i))
fa=list(xrange(n))
def find(p):
while fa[p]!=p: p=fa[p]
return p
def union(p,q):
fa[find(p)]=find(q)
a.sort()
for i in range(1,n):
if a[i][0]==a[i-1][0]: union(a[i][2],a[i-1][2])
a.sort(key=lambda t:t[1])
for i in range(1,n):
if a[i][1]==a[i-1][1]: union(a[i][2],a[i-1][2])
res=n
for i,v in enumerate(fa):
if i==v: res-=1
print res
https://hihocoder.com/contest/offers70/problem/3
題目3 : 拼三角形
思路：排序，然后從小到大遍歷，能組成就標(biāo)記為用過，可AC
n=int(raw_input())
a=map(int,raw_input().strip().split(' '))
res=0
a.sort()
vis=[False]*n
for i in range(n):
if vis[i]: continue
ok=False
for j in range(i+1,n):
if vis[j]: continue
for k in range(j+1, n):
if vis[k]: continue
if a[i]+a[j]>a[k]:
vis[i]=vis[j]=vis[k]=True
res+=1
ok=True
if ok: break
if ok: break
print res
更嚴謹?shù)姆椒ㄊ菭顗篋P
先講一下狀壓dp好了厚柳。它通常使用在n十分小的情況下（比如n<=20），雖然是指數(shù)級別的復(fù)雜度沐兵，但速度比搜索快别垮，其思想非常之優(yōu)秀。所以看到n非常小時扎谎，就要想到99%是狀壓dp碳想。
狀壓dp的適用情況就是當(dāng)狀態(tài)可以由0或者1來表示時，我們所需狀態(tài)數(shù)組無法滿足毁靶。將狀態(tài)表示成二進制數(shù)轉(zhuǎn)化成十進制通過位運算的處理來進行狀態(tài)的轉(zhuǎn)移胧奔。所以位運算在狀壓dp中有著重要的作用。
n=int(raw_input())
a=map(int,raw_input().strip().split(' '))
a.sort()
b=[]
for i in range(n):
for j in range(i+1,n):
for k in range(j+1,n):
if a[i]+a[j]>a[k]:
b.append((1<<i)|(1<<j)|(1<<k))
dp=[0]*(1<<(n+1))
for i,t in enumerate(b):
for j in range(len(dp)-1,-1,-1):
if t&j==0:
dp[j]=max(dp[j],dp[j|t]+1)
print max(dp)
這里要先構(gòu)造所有的3元數(shù)組合预吆，用來狀態(tài)轉(zhuǎn)移
https://hihocoder.com/contest/offers69/problem/2
題目2 : 特工配對
用優(yōu)先隊列是OK的龙填，或者數(shù)學(xué)上理解一下的話，可以發(fā)現(xiàn)如果最大值小于sum的一半的話，一定是可以全部match的
import heapq
n=int(raw_input())
a=map(int,raw_input().strip().split(' '))
pq=[-t for t in a]
heapq.heapify(pq)
res=0
while len(pq)>1:
if len(pq)==2:
res+=-min(pq)
break
m1,m2=-heapq.heappop(pq),-heapq.heappop(pq)
if m1==m2:
res+=m1
continue
m3=-pq[0]
t=m2-m3+1
res+=t
if m1-t>0: heapq.heappush(pq, -(m1-t))
if m2-t>0: heapq.heappush(pq, -(m2-t))
print res
n=int(raw_input())
a=map(int,raw_input().strip().split(' '))
ma=max(a)
su=sum(a)
if ma*2<=su:
print su//2
else:
print su-ma
https://hihocoder.com/contest/offers69/problem/3
題目3 : 階乘問題
思路：直接求有多少個k的因子是錯誤的岩遗，比如20胶背！有多少個10，其中2和5可以組合起來弄成一個10喘先，所以應(yīng)該先因式分解，然后求每個因子有多少個
n,k=map(int,raw_input().strip().split(' '))
d={}
for i in range(2,k+1):
if i*i>n: break
while k%i==0:
d[i]=d.get(i,0)+1
k//=i
if k!=1: d[k]=d.get(k,0)+1
def cal(t,s):
cnt=0
while t:
cnt+=t//s
t//=s
return cnt
res=float('inf')
for k in d:
t=cal(n,k)
res=min(res, t//d[k])
print(res)
