26spring做题记录 - May
2026.5做题记录及5月数算月考
May the force be with you
2026.5.3
估计直径
先采取O(n)方法得到一个直径的2-近似T，然后格点化。作的网格，并round到中心，因此每个点移动的距离小于.对网格代表点暴力求直径即可。
#include<bits/stdc++.h>
using namespace std;
struct Point{
double x,y;
};
double get_dist(Point a, Point b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int main(){
int n;
scanf("%d",&n);
if(n==1){
double x,y;
scanf("%lf %lf",&x,&y);
printf("%0.6lf",0.0);
return 0;
}
Point points[n];
for(int i=0;i<n;i++){
scanf("%lf %lf",&points[i].x,&points[i].y);
}
Point p1=points[0];
double maxd=-1.0;
for(int i=0;i<n;i++){
double dist=get_dist(p1,points[i]);
if(dist>maxd){
maxd=dist;
}
}
double T=maxd;
if(T==0.0){
printf("%0.6lf",0.0);
return 0;
}
double epsilon=0.1;
double l=epsilon*T/sqrt(2.0);
map<pair<long long,long long>,Point> grid;
for(int i=0;i<n;i++){
long long gx=floor(points[i].x/l);
long long gy=floor(points[i].y/l);
grid[make_pair(gx,gy)]=points[i];
}
vector<Point> candidates;
for(auto &[key,pt]:grid){
candidates.push_back(pt);
}
double ans=T;
int m=candidates.size();
for(int i=0;i<m;i++){
for(int j=i+1;j<m;j++){
double dist=get_dist(candidates[i],candidates[j]);
if(dist>ans){
ans=dist;
}
}
}
printf("%0.6lf",ans);
return 0;
}最近点查询
使用四分树。 1.递归建树：对要插入的每个点，判断在四个位置中的哪个，如果原先节点是叶子结点就将其分裂并插入旧点，然后把新点插入对应位置，用0-3表示，用位运算得出点的位置。 2.查询：如果为叶子结点则直接更新答案。否则计算四个节点到目标点的距离，并从小到大排序。优先搜距离近的点，剪枝：如果子节点的最小距离已经是当前答案的1.15倍，则不用搜索。
#include<bits/stdc++.h>
using namespace std;
struct Point{
double x,y;
int id;
};
struct QuadNode{
double cx,cy,size;
int pointIdx;
QuadNode *children[4];
QuadNode(double _cx,double _cy,double _size):cx(_cx),cy(_cy),size(_size),pointIdx(-1){
for(int i=0;i<4;i++){
children[i]=nullptr;
}
}
};
Point points[100005];
double bestdist;
int bestid;
void insert(QuadNode *node,int pidx){
if(node->pointIdx==-1){
node->pointIdx=pidx;
return;
}
double s2=node->size/2.0;
double s4=node->size/4.0;
auto getIdx=[&](int idx){
int res=0;
if(points[idx].x>node->cx) res|=1;
if(points[idx].y>node->cy) res|=2;
return res;
};
int subold=node->pointIdx;
if(subold>=0){
int oldIdx=getIdx(subold);
node->pointIdx=-2;
if(node->children[oldIdx]==nullptr){
double ncx=node->cx+(oldIdx&1?s4:-s4);
double ncy=node->cy+(oldIdx&2?s4:-s4);
node->children[oldIdx]=new QuadNode(ncx,ncy,s2);
}
insert(node->children[oldIdx],subold);
}
int newIdx=getIdx(pidx);
if(node->children[newIdx]==nullptr){
double ncx=node->cx+(newIdx&1?s4:-s4);
double ncy=node->cy+(newIdx&2?s4:-s4);
node->children[newIdx]=new QuadNode(ncx,ncy,s2);
}
insert(node->children[newIdx],pidx);
}
double get_dist(QuadNode *node,double x,double y){
if(node==nullptr) return 1e20;
double dx=max(0.0,abs(node->cx-x)-node->size/2.0);
double dy=max(0.0,abs(node->cy-y)-node->size/2.0);
return sqrt(dx*dx+dy*dy);
}
void query(QuadNode *node,double x,double y){
if(node==nullptr) return;
if(node->pointIdx>=0){
double dist=sqrt((points[node->pointIdx].x-x)*(points[node->pointIdx].x-x)+(points[node->pointIdx].y-y)*(points[node->pointIdx].y-y));
if(dist<bestdist){
bestdist=dist;
bestid=points[node->pointIdx].id;
}
}
vector<pair<double,int>> candidates;
for(int i=0;i<4;i++){
if(node->children[i]!=nullptr){
double dist=get_dist(node->children[i],x,y);
candidates.push_back({dist,i});
}
}
sort(candidates.begin(),candidates.end());
for(auto &p:candidates){
if(p.first*1.15>=bestdist) break;
query(node->children[p.second],x,y);
}
}
int main(){
int n,q;
scanf("%d %d",&n,&q);
double minx=1e7,maxx=-1e7,miny=1e7,maxy=-1e7;
for(int i=0;i<n;i++){
scanf("%lf %lf",&points[i].x,&points[i].y);
points[i].id=i+1;
minx=min(minx,points[i].x);
maxx=max(maxx,points[i].x);
miny=min(miny,points[i].y);
maxy=max(maxy,points[i].y);
}
double size=max(maxx-minx,maxy-miny)+1;
QuadNode *root=new QuadNode((minx+maxx)/2.0,(miny+maxy)/2.0,size);
for(int i=0;i<n;i++){
insert(root,i);
}
for(int i=0;i<q;i++){
double x,y;
scanf("%lf %lf",&x,&y);
bestdist=1e20;
bestid=-1;
query(root,x,y);
printf("%d\n",bestid);
}
return 0;
}最近点对（26）
使用三维四分树找WSPD. 如果两个方块距离大于最优距离则停止。否则计算最近距离。对内部节点进行拆分，注意拆分尺寸较大的内部节点，并递归求距离。
#include<bits/stdc++.h>
using namespace std;
struct Point{
double x,y,z;
int id;
};
struct OctNode{
double cx,cy,cz,size;
int idx;
OctNode *children[8];
OctNode(double _cx,double _cy,double _cz,double _size):cx(_cx),cy(_cy),cz(_cz),size(_size){
for(int i=0;i<8;i++){
children[i]=nullptr;
}
idx=-1;
}
};
Point points[100005];
double bestdist=4e18;
void insert(OctNode *node,int pidx){
if(node->idx==-1){
node->idx=pidx;
return;
}
double s2=node->size/2.0;
double s4=node->size/4.0;
auto getIdx=[&](int idx){
int res=0;
if(points[idx].x>node->cx) res|=1;
if(points[idx].y>node->cy) res|=2;
if(points[idx].z>node->cz) res|=4;
return res;
};
if(node->idx>=0){
int subold=node->idx;
int oldidx=getIdx(subold);
if(points[subold].x==points[pidx].x&&points[subold].y==points[pidx].y&&points[subold].z==points[pidx].z){
bestdist=0.0;
return;
}
node->idx=-2;
if(node->children[oldidx]==nullptr){
double ncx=node->cx+(oldidx&1?s4:-s4);
double ncy=node->cy+(oldidx&2?s4:-s4);
double ncz=node->cz+(oldidx&4?s4:-s4);
node->children[oldidx]=new OctNode(ncx,ncy,ncz,s2);
}
insert(node->children[oldidx],subold);
}
int newidx=getIdx(pidx);
if(node->children[newidx]==nullptr){
double ncx=node->cx+(newidx&1?s4:-s4);
double ncy=node->cy+(newidx&2?s4:-s4);
double ncz=node->cz+(newidx&4?s4:-s4);
node->children[newidx]=new OctNode(ncx,ncy,ncz,s2);
}
insert(node->children[newidx],pidx);
}
double get_dist(Point a,Point b){
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z);
}
double box_dist(OctNode *u,OctNode *v){
double dx=max(0.0,abs(u->cx-v->cx)-u->size/2.0-v->size/2.0);
double dy=max(0.0,abs(u->cy-v->cy)-u->size/2.0-v->size/2.0);
double dz=max(0.0,abs(u->cz-v->cz)-u->size/2.0-v->size/2.0);
return dx*dx+dy*dy+dz*dz;
}
void find_pairs(OctNode *u,OctNode *v){
if(!u||!v||bestdist==0.0) return;
if(box_dist(u,v)>=bestdist) return;
if(u->idx>=0&&v->idx>=0){
if(u->idx!=v->idx){
double dist=get_dist(points[u->idx],points[v->idx]);
if(dist<bestdist){
bestdist=dist;
}
return;
}
}
if(u->idx>=0||(v->idx<0&&v->size>=u->size)){
swap(u,v);
}
for(int i=0;i<8;i++){
if(u->children[i]) find_pairs(u->children[i],v);
}
}
void solve_internal(OctNode *u){
if(!u||u->idx>=0) return;
for(int i=0;i<8;i++){
solve_internal(u->children[i]);
}
for(int i=0;i<8;i++){
for(int j=i+1;j<8;j++){
find_pairs(u->children[i],u->children[j]);
}
}
}
int main(){
int n;
double minx=2e9,miny=2e9,minz=2e9,maxx=-2e9,maxy=-2e9,maxz=-2e9;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%lf %lf %lf",&points[i].x,&points[i].y,&points[i].z);
points[i].id=i;
minx=min(minx,points[i].x);
maxx=max(maxx,points[i].x);
miny=min(miny,points[i].y);
maxy=max(maxy,points[i].y);
minz=min(minz,points[i].z);
maxz=max(maxz,points[i].z);
}
double size=max({maxx-minx,maxy-miny,maxz-minz})+1.0;
OctNode *root=new OctNode((minx+maxx)/2.0,(miny+maxy)/2.0,(minz+maxz)/2.0,size);
for(int i=0;i<n;i++){
insert(root,i);
}
solve_internal(root);
printf("%0.2lf",sqrt(bestdist));
}向下调整构建大顶堆
对二叉树的每个非叶节点，使其下沉到正确的位置，并递归调整受影响的子树。
def heapify(heap,n,i):
largest=i
l=2*i+1
r=2*i+2
if(l<n and heap[l]>heap[largest]):
largest=l
if(r<n and heap[r]>heap[largest]):
largest=r
if(largest!=i):
heap[i],heap[largest]=heap[largest],heap[i]
heapify(heap,n,largest)
n=int(input())
heap=list(map(int,input().split()))
for i in range(n//2-1,-1,-1):
heapify(heap,n,i)
print(*heap)执行交换操作后的最小汉明距离
并查集。同一个联通分量里面元素可以互相交换，因此比较每个分量的source和target即可。使用Counter统计个数，并贪心匹配。 Counter:记录数组中每个数出现次数，并用字典存储。
from typing import List
from collections import defaultdict,Counter
class Solution:
def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:
n=len(source)
m=len(allowedSwaps)
fa=[i for i in range(n)]
size=[1]*n
def find(x):
if(fa[x]!=x):
fa[x]=find(fa[x])
return fa[x]
def merge(x,y):
fx=find(x)
fy=find(y)
if(fx==fy):
return
if(size[fx]<size[fy]):
fx,fy=fy,fx
fa[fy]=fx
size[fx]+=size[fy]
for i in range(m):
merge(allowedSwaps[i][0],allowedSwaps[i][1])
d=defaultdict(list)
for i in range(n):
d[find(i)].append(i)
ans=0
for lst in d.values():
cnt=Counter(source[i] for i in lst)
for i in lst:
if(cnt[target[i]]>0):
cnt[target[i]]-=1
else:
ans+=1
return ans
print(Solution().minimumHammingDistance([1,2,3,4], [2,1,4,5], [[0,1],[2,3]]))哈夫曼编码树
自定义比较顺序。建树使用小根堆，每次取出最小两个作为左右节点，再把它们的父节点放回去。编码直接dfs即可。解码字符串根据搜索得出的表来，解码01串则直接在树上往下搜，搜到底记录答案并返回根部即可。
import heapq
class Node:
def __init__(self,weight,chars,left=None,right=None):
self.weight=weight
self.chars=sorted(list(chars))
self.min_char=self.chars[0]
self.left=left
self.right=right
def __lt__(self,other):
if(self.weight!=other.weight):
return self.weight<other.weight
return self.min_char<other.min_char
def build(nodes):
heapq.heapify(nodes)
while(len(nodes)>1):
left=heapq.heappop(nodes)
right=heapq.heappop(nodes)
new_weight=left.weight+right.weight
new_chars=left.chars+right.chars
parent=Node(new_weight,new_chars,left,right)
heapq.heappush(nodes,parent)
return nodes[0]
def decode(node,res,codes):
if(not node.left and not node.right):
codes[node.chars[0]]=res
return
if(node.left):
decode(node.left,res+'0',codes)
if(node.right):
decode(node.right,res+'1',codes)
n=int(input())
nodes=[]
for i in range(n):
char,freq=input().split()
freq=int(freq)
nodes.append(Node(freq,[char]))
root=build(nodes)
char_to_code={}
decode(root,'',char_to_code)
code_to_char={}
while(True):
try:
q=input()
if(q[0] in "01"):
res=""
cur=root
for c in q:
if(c=='0'):
cur=cur.left
else:
cur=cur.right
if(not cur.left and not cur.right):
res+=cur.chars[0]
cur=root
else:
res=""
for c in q:
res+=char_to_code[c]
print(res)
except EOFError:
break实现 Trie (前缀树)
26叉树。每个节点指向当前字母对应的子节点。
class TreeNode:
def __init__(self):
self.children=[None]*26
self.isEnd=False
class Trie:
def __init__(self):
self.root=TreeNode()
def searchprefix(self,word):
node=self.root
for c in word:
idx=ord(c)-ord('a')
if(node.children[idx]==None):
return None
node=node.children[idx]
return node
def insert(self, word: str) -> None:
node=self.root
for c in word:
idx=ord(c)-ord('a')
if(node.children[idx]==None):
node.children[idx]=TreeNode()
node=node.children[idx]
node.isEnd=True
def search(self, word: str) -> bool:
node=self.searchprefix(word)
return node!=None and node.isEnd
def startsWith(self, prefix: str) -> bool:
return self.searchprefix(prefix) != None
# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)区域和检索 - 数组可修改
单点修改+区间查询，使用树状数组/线段树。 树状数组：1-i的前缀和每次按lowbit(i)的长度拆分。 线段树：每个节点不断平分区间和
class NumArray:
def __init__(self, nums: list[int]):
self.n=len(nums)
self.nums=nums
self.tree=[0]*(self.n*4)
self.build(1,0,self.n-1)
def build(self,node,l,r):
if(l==r):
self.tree[node]=self.nums[l]
return
mid=(l+r)>>1
self.build(node*2,l,mid)
self.build(node*2+1,mid+1,r)
self.tree[node]=self.tree[node*2]+self.tree[node*2+1]
def update_tree(self,node,l,r,idx,val):
if(l==r):
self.tree[node]=val
self.nums[idx]=val
return
mid=(l+r)>>1
if(idx<=mid):
self.update_tree(node*2,l,mid,idx,val)
else:
self.update_tree(node*2+1,mid+1,r,idx,val)
self.tree[node]=self.tree[node*2]+self.tree[node*2+1]
def update(self, index: int, val: int) -> None:
self.update_tree(1,0,self.n-1,index,val)
def sums(self,node,start,end,l,r):#l-r目标区间，start-end当前区间
if(l<=start and end<=r):
return self.tree[node]
if(end<l or start>r):
return 0
mid=(start+end)>>1
return self.sums(node*2,start,mid,l,r)+self.sums(node*2+1,mid+1,end,l,r)
def sumRange(self, left: int, right: int) -> int:
return self.sums(1,0,self.n-1,left,right)附：带lazy tag的线段树实现（区间修改+区间查询） lazy tag即先存下要修改的地方，等访问到了再修改，且能够实现区间完全覆盖时就统一更新。
class NumArray:
def __init__(self, nums: list[int]):
self.n=len(nums)
self.nums=nums
self.tree=[0]*(self.n*4)
self.lazy=[0]*(self.n*4)
self.build(1,0,self.n-1)
def pushup(self,node):
self.tree[node]=self.tree[node*2]+self.tree[node*2+1]
def pushdown(self,node,l,r):
if(self.lazy[node]!=0):
mid=(l+r)>>1
self.tree[node*2]+=(mid-l+1)*self.lazy[node]
self.tree[node*2+1]+=(r-mid)*self.lazy[node]
self.lazy[node*2]+=self.lazy[node]
self.lazy[node*2+1]+=self.lazy[node]
self.lazy[node]=0
def build(self,node,l,r):
if(l==r):
self.tree[node]=self.nums[l]
return
mid=(l+r)>>1
self.build(node*2,l,mid)
self.build(node*2+1,mid+1,r)
self.pushup(node)
def update_range(self,node,start,end,l,r,val):
if(l<=start and end<=r):
self.tree[node]+=(end-start+1)*val
self.lazy[node]+=val
return
if(end<l or start>r):
return
self.pushdown(node,start,end)
mid=(start+end)>>1
self.update_range(node*2,start,mid,l,r,val)
self.update_range(node*2+1,mid+1,end,l,r,val)
self.pushup(node)
def sums(self,node,start,end,l,r):#l-r目标区间，start-end当前区间
if(l<=start and end<=r):
return self.tree[node]
if(end<l or start>r):
return 0
self.pushdown(node,start,end)
mid=(start+end)>>1
return self.sums(node*2,start,mid,l,r)+self.sums(node*2+1,mid+1,end,l,r)
def sumRange(self, left: int, right: int) -> int:
return self.sums(1,0,self.n-1,left,right)n
平衡二叉树的建立
class AVLNode:
def __init__(self,val):
self.val=val
self.left=None
self.right=None
self.height=1
class AVLTree:
def get_height(self,node):
if(node==None):
return 0
return node.height
def get_balance(self,node):
if(node==None):
return 0
return self.get_height(node.left)-self.get_height(node.right)
def right_rotate(self,y):
x=y.left
T2=x.right
x.right=y
y.left=T2
y.height=max(self.get_height(y.left),self.get_height(y.right))+1
x.height=max(self.get_height(x.left),self.get_height(x.right))+1
return x
def left_rotate(self,x):
y=x.right
T2=y.left
y.left=x
x.right=T2
x.height=max(self.get_height(x.left),self.get_height(x.right))+1
y.height=max(self.get_height(y.left),self.get_height(y.right))+1
return y
def insert(self,node,val):
if(node==None):
return AVLNode(val)
if(val<node.val):
node.left=self.insert(node.left,val)
else:
node.right=self.insert(node.right,val)
node.height=1+max(self.get_height(node.left),self.get_height(node.right))
balance=self.get_balance(node)
if(balance>1 and val<node.left.val):
return self.right_rotate(node)
if(balance<-1 and val>node.right.val):
return self.left_rotate(node)
if(balance>1 and val>node.left.val):
node.left=self.left_rotate(node.left)
return self.right_rotate(node)
if(balance<-1 and val<node.right.val):
node.right=self.right_rotate(node.right)
return self.left_rotate(node)
return node
def dfs(node,res):
if(node==None):
return
res.append(node.val)
dfs(node.left,res)
dfs(node.right,res)
avl=AVLTree()
root=None
n=int(input())
tree=list(map(int,input().split()))
for val in tree:
root=avl.insert(root,val)
res=[]
dfs(root,res)
print(' '.join(map(str,res)))2026.5.5
词梯
使用通配符模式匹配为节点连边。bfs时直接在通配符桶中寻找邻居。剪枝：搜过一个桶之后，可以直接把这个桶删除，因为已经中转过了，不需要再用到。
from collections import deque,defaultdict
n=int(input())
words=[]
for i in range(n):
words.append(input())
patterns=defaultdict(list)
for i in range(n):
for j in range(4):
p=words[i][:j]+"*"+words[i][j+1:]
patterns[p].append(i)
start,end=input().split()
si=words.index(start)
ei=words.index(end)
q=deque()
q.append(si)
flag=0
pre=[-1]*n
vis=[0]*n
vis[si]=1
while(q):
node=q.popleft()
if(node==ei):
flag=1
break
for i in range(4):
w=words[node][:i]+"*"+words[node][i+1:]
if(w in patterns):
for j in patterns[w]:
if(vis[j]==0):
vis[j]=1
pre[j]=node
q.append(j)
patterns.pop(w)
if(flag==0):
print("NO")
else:
res=[]
cur=ei
while(cur!=-1):
res.append(words[cur])
cur=pre[cur]
print(*res[::-1])有向图判环
有向图判环，需使用三状态标记，判断下一个节点是否在当前路径上。（有可能出现访问了已经访问但不在当前路径上的节点的情况。）（三色dfs）
无向图判环，排除是否为父节点即可。
Kahn:一个无环的有向图，必然存在至少一个入度为0的节点（没有依赖），拿掉它和它的边之后，剩下的图依然是无环的。（拓扑排序）
n,m=map(int,input().split())
a=[[] for _ in range(n)]
for i in range(m):
u,v=map(int,input().split())
a[u].append(v)
vis=[0]*n
flag=0
def dfs(node):
global flag
for c in a[node]:
if(vis[c]==0):
vis[c]=2
dfs(c)
elif(vis[c]==2):
flag=1
return
vis[c]=1
for i in range(n):
if(vis[i]==0):
vis[i]=2
dfs(i)
vis[i]=1
if(flag==1):
break
if(flag==1):
print("Yes")
else:
print("No")
骑士周游
采用Warnsdorff’s Rule进行启发式搜索。即在后续格子中选择出路最少、离边界最近的，可以减少后续走了很长的路然后进入死胡同的可能性。
n=int(input())
x0,y0=map(int,input().split())
vis=[[0 for _ in range(n)]for _ in range(n)]
vis[x0][y0]=1
dx=[-2,-1,1,2,2,1,-1,-2]
dy=[-1,-2,-2,-1,1,2,2,1]
flag=0
def get_degree(x,y):
degree=0
for i in range(8):
xx=x+dx[i]
yy=y+dy[i]
if(xx>=0 and xx<n and yy>=0 and yy<n and vis[xx][yy]==0):
degree+=1
return degree
def get_dist(x,y):
return (x-n/2.0)**2+(y-n/2.0)**2
def dfs(x,y,step):
global flag
if(step==n*n):
flag=1
return
candidates=[]
for i in range(8):
xx=x+dx[i]
yy=y+dy[i]
if(xx>=0 and xx<n and yy>=0 and yy<n and vis[xx][yy]==0):
candidates.append((get_degree(xx,yy),-get_dist(xx,yy),xx,yy))
candidates.sort()
for _,__,xx,yy in candidates:
vis[xx][yy]=1
dfs(xx,yy,step+1)
if(flag==1):
return
vis[xx][yy]=0
dfs(x0,y0,1)
if(flag==1):
print("success")
else:
print("fail")通过质数传送到达终点的最少跳跃次数
bfs. 1.使用类埃氏筛方法得到质数跳转数组。 2.bfs访问过跳转数组之后将其清空 3.bfs不要忘记vis数组
from collections import deque,defaultdict
from typing import List
from math import sqrt
MX=1000001
factors=[[] for _ in range(MX)]
for i in range(2,MX):
if(not factors[i]):
for j in range(i,MX,i):
factors[j].append(i)
class Solution:
def minJumps(self, nums: List[int]) -> int:
n=len(nums)
m=max(nums)
groups=defaultdict(list)
for i in range(n):
for p in factors[nums[i]]:
groups[p].append(i)
q=deque()
q.append((0,0))
vis=[0]*n
vis[0]=1
while(q):
idx,steps=q.popleft()
if(idx==n-1):
return steps
cur=groups[nums[idx]]
cur.append(idx+1)
if(idx-1>=0):
cur.append(idx-1)
for i in cur:
if(i!=idx and not vis[i]):
vis[i]=1
q.append((i,steps+1))
cur.clear()
print(Solution().minJumps([1,2,4,6]))[USACO3.1] 最短网络 Agri-Net
Kruskal：将所有边从小到大排序，依次选择，如果边的两端已经在树上（使用并查集，联通），则跳过。 Prim：选一个点，从连出去的边中选择最短的，把新点加入树中。之后每次选择树上的点和不在树上的点之间的最短边。
import sys
n=int(input())
lst=sys.stdin.read().strip().split()
edges=[]
for i in range(n):
for j in range(i+1,n):
idx=i*n+j
edges.append((int(lst[idx]),i,j))
edges.sort()
m=len(edges)
fa=[i for i in range(n)]
size=[1]*n
def find(x):
if(fa[x]!=x):
fa[x]=find(fa[x])
return fa[x]
def merge(x,y):
fx=find(x)
fy=find(y)
if(fx!=fy):
if(size[fx]>size[fy]):
fx,fy=fy,fx
fa[fx]=fy
size[fy]+=size[fx]
ans=0
i=0
cnt=0
for i in range(m):
w,x,y=edges[i]
if(find(x)!=find(y)):
merge(x,y)
ans+=w
cnt+=1
if(cnt==n-1):
break
print(ans)3维欧氏空间最小生成树（26）
WSPD找所有良好分离的点对，选取代表值连边，对所有边跑一遍Kruskal。
#include<bits/stdc++.h>
using namespace std;
struct Point{
double x,y,z;
int id;
};
struct Edge{
int u,v;
double w;
bool operator<(const Edge &e) const {
return w < e.w;
}
};
struct OctNode{
double cx,cy,cz,size;
int idx;
int rep_id;
OctNode *children[8];
OctNode(double _cx,double _cy,double _cz,double _size):cx(_cx),cy(_cy),cz(_cz),size(_size),rep_id(-1){
for(int i=0;i<8;i++){
children[i]=nullptr;
}
idx=-1;
}
};
Point points[100005];
void insert(OctNode *node,int pidx){
if(node->rep_id==-1) node->rep_id=pidx;
if(node->idx==-1){
node->idx=pidx;
return;
}
double s2=node->size/2.0;
double s4=node->size/4.0;
auto getIdx=[&](int idx){
int res=0;
if(points[idx].x>node->cx) res|=1;
if(points[idx].y>node->cy) res|=2;
if(points[idx].z>node->cz) res|=4;
return res;
};
if(node->idx>=0){
int subold=node->idx;
int oldidx=getIdx(subold);
node->idx=-2;
if(node->children[oldidx]==nullptr){
double ncx=node->cx+(oldidx&1?s4:-s4);
double ncy=node->cy+(oldidx&2?s4:-s4);
double ncz=node->cz+(oldidx&4?s4:-s4);
node->children[oldidx]=new OctNode(ncx,ncy,ncz,s2);
}
insert(node->children[oldidx],subold);
}
int newidx=getIdx(pidx);
if(node->children[newidx]==nullptr){
double ncx=node->cx+(newidx&1?s4:-s4);
double ncy=node->cy+(newidx&2?s4:-s4);
double ncz=node->cz+(newidx&4?s4:-s4);
node->children[newidx]=new OctNode(ncx,ncy,ncz,s2);
}
insert(node->children[newidx],pidx);
}
double get_dist(Point a,Point b){
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z);
}
double box_dist(OctNode *u,OctNode *v){
double dx=max(0.0,abs(u->cx-v->cx)-u->size/2.0-v->size/2.0);
double dy=max(0.0,abs(u->cy-v->cy)-u->size/2.0-v->size/2.0);
double dz=max(0.0,abs(u->cz-v->cz)-u->size/2.0-v->size/2.0);
return dx*dx+dy*dy+dz*dz;
}
vector<Edge> edges;
const double s=2.0;
void find_pairs(OctNode *u,OctNode *v){
if(!u||!v) return;
if(box_dist(u,v)>=(s*max(u->size,v->size))*(s*max(u->size,v->size))){
edges.push_back({u->rep_id,v->rep_id,get_dist(points[u->rep_id],points[v->rep_id])});
return;
}
if(u->idx>=0&&v->idx>=0){
if(u->idx!=v->idx){
double dist=get_dist(points[u->idx],points[v->idx]);
edges.push_back({u->idx, v->idx, dist});
}
return;
}
if(u->idx>=0||(v->idx<0&&v->size>=u->size)){
swap(u,v);
}
for(int i=0;i<8;i++){
if(u->children[i]) find_pairs(u->children[i],v);
}
}
void solve_internal(OctNode *u){
if(!u||u->idx>=0) return;
for(int i=0;i<8;i++){
solve_internal(u->children[i]);
}
for(int i=0;i<8;i++){
for(int j=i+1;j<8;j++){
find_pairs(u->children[i],u->children[j]);
}
}
}
int fa[50005],siz[50005];
int find(int x){
if(fa[x]==x) return x;
fa[x]=find(fa[x]);
return fa[x];
}
void merge(int x,int y){
int fx=find(x),fy=find(y);
if(fx!=fy){
if(siz[fx]<siz[fy]) swap(fx,fy);
fa[fy]=fx;
siz[fx]+=siz[fy];
}
}
int main(){
int n;
double minx=2e9,miny=2e9,minz=2e9,maxx=-2e9,maxy=-2e9,maxz=-2e9;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%lf %lf %lf",&points[i].x,&points[i].y,&points[i].z);
points[i].id=i;
minx=min(minx,points[i].x);
maxx=max(maxx,points[i].x);
miny=min(miny,points[i].y);
maxy=max(maxy,points[i].y);
minz=min(minz,points[i].z);
maxz=max(maxz,points[i].z);
}
double size=max({maxx-minx,maxy-miny,maxz-minz})+1.0;
OctNode *root=new OctNode((minx+maxx)/2.0,(miny+maxy)/2.0,(minz+maxz)/2.0,size);
for(int i=0;i<n;i++){
insert(root,i);
}
solve_internal(root);
int m=edges.size();
for(int i=0;i<n;i++){
fa[i]=i;
siz[i]=1;
}
sort(edges.begin(),edges.end());
int res[n-1][2];
int cnt=0;
for(int i=0;i<m;i++){
if(find(edges[i].u)!=find(edges[i].v)){
merge(edges[i].u,edges[i].v);
res[cnt][0]=edges[i].u;
res[cnt][1]=edges[i].v;
cnt++;
if(cnt==n-1) break;
}
}
for(int i=0;i<n-1;i++){
printf("%d %d\n",res[i][0]+1,res[i][1]+1);
}
}2026.5.6 月考
最小新整数
单调栈
t=int(input())
for _ in range(t):
n,k=input().split()
k=int(k)
m=len(n)
s=[]
cnt=0
for c in n:
while(s and c<s[-1] and cnt<k):
s.pop()
cnt+=1
s.append(c)
while(cnt<k):
s.pop()
cnt+=1
print("".join(s))和为给定数
使用字典可能会爆内存。考虑排序后双指针。
from collections import Counter
n=int(input())
a=list(map(int,input().split()))
m=int(input())
s=Counter(a)
res=[]
for c in s:
if((c<m/2 and c!=m-c and s[c]>0 and s[m-c]>0) or (c==m/2 and s[c]>1)):
res.append([c,m-c])
if(len(res)==0):
print("No")
else:
res.sort()
print(res[0][0],res[0][1])n=int(input())
a=list(map(int,input().split()))
m=int(input())
a.sort()
i=0
j=n-1
flag=0
while(i<j):
if(a[i]+a[j]==m):
flag=1
print(a[i],a[j])
break
elif(a[i]+a[j]>m):
j-=1
else:
i+=1
if(flag==0):
print("No")求二叉树的高度和叶子数目
先用节点和叶子节点的差集找根，然后dfs即可。
n=int(input())
tree=[]
child=set()
leaves=0
for i in range(n):
x,y=map(int,input().split())
tree.append([x,y])
child.add(x)
child.add(y)
if(x==-1 and y==-1):
leaves+=1
for i in range(n):
if(i not in child):
root=i
break
dep=0
def dfs(node,parent,cur):
global dep
if(tree[node][0]==-1 and tree[node][1]==-1):
dep=max(dep,cur)
return
for i in tree[node]:
if(i!=parent and i!=-1):
dfs(i,node,cur+1)
dfs(root,-1,0)
print(dep,leaves)地铁换乘
倍增lca以得到两节点之间的距离，然后计算出相遇点即可。
from math import log2
n,t=map(int,input().split())
tree=[[] for _ in range(n+1)]
for i in range(n-1):
x,y=map(int,input().split())
tree[x].append(y)
tree[y].append(x)
p,q,v1,v2=map(int,input().split())
max_log=20
par=[0]*(n+1)
dep=[0]*(n+1)
def dfs(node,parent,depth):
par[node]=parent
dep[node]=depth
for i in tree[node]:
if(i!=parent):
dfs(i,node,depth+1)
return
dfs(t,0,0)
up=[[0 for _ in range(max_log)]for _ in range(n+1)]
for i in range(1,n+1):
up[i][0]=par[i]
for j in range(1,max_log):
for i in range(1,n+1):
up[i][j]=up[up[i][j-1]][j-1]
def lca(x,y):
if(dep[x]<dep[y]):
x,y=y,x
diff=dep[x]-dep[y]
for i in range(max_log):
if((diff>>i)&1):
x=up[x][i]
if(x==y):
return x
for i in range(max_log-1,-1,-1):
if(up[x][i]!=up[y][i]):
x=up[x][i]
y=up[y][i]
return par[x]
def get(x,k):
for i in range(max_log):
if((k>>i)&1):
x=up[x][i]
return x
lca_node=lca(p,q)
d1=dep[p]-dep[lca_node]
d2=dep[q]-dep[lca_node]
tot=(d1+d2)//(v1+v2)
s1=tot*v1
ans=0
if(s1<=d1):
ans=get(p,s1)
else:
ans=get(q,d1+d2-s1)
print(tot,dep[ans])排队又来了
[USACO22JAN] Minimizing Haybales P 如果i<j，且>k，则与的位置不能互换。因此将->连边，所得即为DAG.根据规则，输出最小拓扑排序即可。 考虑优化复杂度，求每个点入度时，排序并离散化，在从左往右扫描的过程中使用树状数组维护已经扫描过的高度情况。拓扑排序使用线段树优化区间修改入度，即采用线段树记录最小值，每次取根节点并二分查找需要更新入度的区间。
import heapq
from bisect import bisect_right
n,k=map(int,input().split())
a=list(map(int,input().split()))
sorted_a=sorted(a)
idxa=[]
for i in range(n):
idxa.append((a[i],i))
sorted_idxa=sorted(idxa)
rank_to_h=[0]*(n+1)#rank->高度
pos_to_rank=[0]*(n+1)#原始下标->rank
for i in range(n):
x,idx=sorted_idxa[i]
pos_to_rank[idx]=i+1
rank_to_h[i+1]=x
def lowbit(x):
return x&(-x)
bit=[0]*(n+1)
def bit_add(idx,v):
while(idx<=n):
bit[idx]+=v
idx+=lowbit(idx)
def bit_query(idx):
res=0
while(idx>0):
res+=bit[idx]
idx-=lowbit(idx)
return res
deg=[0]*(n+1)
for i in range(n):
cur_rank=pos_to_rank[i]
cur_h=rank_to_h[cur_rank]
x=bisect_right(sorted_a,cur_h-k-1)
y=bisect_right(sorted_a,cur_h+k)
deg[cur_rank]=bit_query(x)+(i-bit_query(y))
bit_add(cur_rank,1)
tree=[(0,0)]*(4*n)
tag=[0]*(4*n)
def build(node,l,r):
if(l==r):
tree[node]=(deg[l],l)
return
mid=(l+r)//2
build(node*2,l,mid)
build(node*2+1,mid+1,r)
tree[node]=min(tree[node*2],tree[node*2+1])
def push_up(node,val):
tag[node]+=val
tree[node]=(tree[node][0]+val,tree[node][1])
def push_down(node):
if(tag[node]!=0):
push_up(node*2,tag[node])
push_up(node*2+1,tag[node])
tag[node]=0
def update(node,start,end,l,r,val):
if(start>r or end<l):
return
if(start>=l and end<=r):
push_up(node,val)
return
push_down(node)
mid=(start+end)//2
update(node*2,start,mid,l,r,val)
update(node*2+1,mid+1,end,l,r,val)
tree[node]=min(tree[node*2],tree[node*2+1])
build(1,1,n)
res=[]
maxm=10**9
for i in range(n):
min_deg,idx=tree[1]
res.append(rank_to_h[idx])
update(1,1,n,idx,idx,maxm)
h=rank_to_h[idx]
x=bisect_right(sorted_a,h-k-1)
y=bisect_right(sorted_a,h+k)
if(x>=1):
update(1,1,n,1,x,-1)
if(y<n):
update(1,1,n,y+1,n,-1)
print(" ".join(map(str,res)))2026.5.9
败方树的构建与维护
对每个节点，存储败者与胜者信息，以便继续比较。从叶子往上bfs构建败方树，修改同理。
from collections import deque
n,m=map(int,input().split())
a=list(map(int,input().split()))
class Node:
def __init__(self,val=0):
self.val=val
self.win=val
self.left=None
self.right=None
self.parent=None
leaves=[Node(x) for x in a]
q=deque(leaves)
while(len(q)>1):
a=q.popleft()
b=q.popleft()
cur=Node()
cur.val=max(a.win,b.win)
cur.win=min(a.win,b.win)
cur.left=a
cur.right=b
a.parent=b.parent=cur
q.append(cur)
cur=q.popleft()
root=Node(cur.win)
root.left=cur
cur.parent=root
def bfs():
res=[]
qaq=deque()
qaq.append(root)
while(qaq and len(res)<n):
cur=qaq.popleft()
res.append(cur.val)
if(cur.left):
qaq.append(cur.left)
if(cur.right):
qaq.append(cur.right)
return res
res=bfs()
print(*res)
for i in range(m):
idx,val=map(int,input().split())
cur=leaves[idx]
cur.val=cur.win=val
p=cur.parent
while(p):
if(p.right):
p.val=max(p.left.win,p.right.win)
p.win=min(p.left.win,p.right.win)
else:
p.val=p.win=p.left.win
p=p.parent
res=bfs()
print(*res)2026.5.8
[CERC 1995] 小木棍
上学期暑假写的，py过不了，用C++重新写了一遍。 剪枝： 1.还剩一根时直接返回 2.前一根不行后一根相同长度的也不行 3.当前长度大于剩余长度直接跳（二分） 4.当前长度刚好填满、刚好等于一根的长度但之前的操作失败了则直接返回失败 5.vis数组回溯改标记，不用每次memset
#include<bits/stdc++.h>
using namespace std;
bool cmp(int a,int b){
return a>b;
}
int a[70],vis[70],n;
bool dfs(int cnt,int rest,int last,int len){
if(cnt==1) return true;
if(rest==0) return dfs(cnt-1,len,0,len);
int i=last,pre=-1;
while(i<n){
if(a[i]>rest){
i=lower_bound(a,a+n,rest,cmp)-a;
continue;
}
if(vis[i]){
i++;
continue;
}
if(a[i]==pre){
i++;
continue;
}
vis[i]=1;
if(dfs(cnt,rest-a[i],i+1,len)) return true;
vis[i]=0;
pre=a[i];
if(rest==len||rest==a[i]) return false;
i++;
}
return false;
}
int main(){
int sum=0;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
sum+=a[i];
}
sort(a,a+n,cmp);
memset(vis,0,sizeof(vis));
for(int i=a[0];i<=sum;i++){
if(sum%i!=0) continue;
if(dfs(sum/i,i,0,i)){
printf("%d\n",i);
break;
}
}
}2026.5.10
细菌的战争
n=int(input())
for _ in range(n):
bad,good=map(int,input().split())
res=0
while(bad>0):
res+=1
bad-=good
if(bad<=0):
break
bad<<=1
if(bad>1000000):
bad=1000000
good=int(1.05*good)
print(res)拼点游戏
田忌赛马。cs前后各一个指针，如果遇到相等的情况就从后比较。注意c获得的最大点数不等于s获得的最大点数，因此要跑两遍。
while(True):
n=int(input())
if(n==0):
break
c=list(map(int,input().split()))
s=list(map(int,input().split()))
c.sort(reverse=True)
s.sort(reverse=True)
i0=0
j0=0
i1=n-1
j1=n-1
maxs=0
maxc=0
while(i0<=i1 and j0<=j1):
if(s[i0]>c[j0]):
maxs+=3
i0+=1
j0+=1
elif(s[i0]<c[j0]):
maxs+=1
i1-=1
j0+=1
else:
if(s[i1]>c[j1]):
maxs+=3
i1-=1
j1-=1
else:
if(s[i1]<c[j0]):
maxs+=1
i1-=1
j0+=1
else:
maxs+=2
i0+=1
j0+=1
i0=0
j0=0
i1=n-1
j1=n-1
while(i0<=i1 and j0<=j1):
if(c[i0]>s[j0]):
maxc+=3
i0+=1
j0+=1
elif(c[i0]<s[j0]):
maxc+=1
i1-=1
j0+=1
else:
if(c[i1]>s[j1]):
maxc+=3
i1-=1
j1-=1
else:
if(c[i1]<s[j0]):
maxc+=1
i1-=1
j0+=1
else:
maxc+=2
i0+=1
j0+=1
print(maxs,4*n-maxc)胡
from collections import Counter
def check(x,y,z):
if(x+1==y and y+1==z):
return True
if(x==y and y==z):
return True
def HU(s):
n=len(s)
i=0
while(i<n-2):
if(not check(s[i],s[i+1],s[i+2])):
return False
i+=3
return True
while(True):
s=input()
if(s=='0'):
break
s=list(map(int,s.split()))
n=len(s)
if(n%3!=2):
print("XIANGGONG")
continue
s.sort()
a=Counter(s)
flag=0
for i in range(1,10):
if(a[i]>=2):
t=s.copy()
t.remove(i)
t.remove(i)
if(HU(t)):
print("HU")
flag=1
break
if(flag==0):
print("BUHU")n-gram串频统计
from collections import defaultdict
n=int(input())
s=input()
t=defaultdict(int)
ans=0
for i in range(len(s)-n+1):
t[s[i:i+n]]+=1
ans=max(ans,t[s[i:i+n]])
if(ans<=1):
print("NO")
else:
res=[]
for key,val in t.items():
if(val==ans):
res.append(key)
print(ans)
print("\n".join(res))TOYS
while(True):
s=input()
if(s=='0'):
break
n,m,x1,y1,x2,y2=map(int,s.split())
d={}
res={}
# test if y1==y2
#(0,x1)
for i in range(0,n):
u,l=map(int,input().split())
k=(u-l)/(y1-y2)
b=(l*y1-u*y2)/(y1-y2)
d[i]=(u,l,k,b)#x=ky+b
d[n]=(x2,x2,0,x2)
for i in range(n+1):
res[i]=0
for i in range(m):
x,y=map(int,input().split())
for j in range(n+1):
u,l,k,b=d[j]
if(x<=max(u,l) and k*y+b>=x):
res[j]+=1
break
for i in range(n+1):
print(f"{i}: {res[i]}")
print()二分查找+叉乘。
while(True):
s=input()
if(s=='0'):
break
n,m,x1,y1,x2,y2=map(int,s.split())
d={}
res={}
# test if y1==y2
#(0,x1)
for i in range(0,n):
u,l=map(int,input().split())
d[i]=(u,l,)#x=ky+b
d[n]=(x2,x2)
for i in range(n+1):
res[i]=0
for i in range(m):
x,y=map(int,input().split())
#边界x线段（从上往下），为负则在左侧，为正则在右侧
left=0
right=n
ans=-1
while(left<=right):
mid=(left+right)>>1
u,l=d[mid]#(u-l,y1-y2)x(u-x,y1-y)
cross=(u-l)*(y1-y)-(y1-y2)*(u-x)
if(cross<=0):
ans=mid
right=mid-1
else:
left=mid+1
res[ans]+=1
for i in range(n+1):
print(f"{i}: {res[i]}")
print()带通配符的字符串匹配
dp数组记录a的前i位与b的前j位能否匹配。如果a当前位为*,那么从a的前一位匹配到的位置开始到目标串的结束，a的这一位都能匹配上。用tag数组记录a的前一位最早匹配到的位置。
a=" "+input()
b=" "+input()
n=len(a)
m=len(b)
dp=[[0 for _ in range(m)]for _ in range(n)]#a的前i位与b的前j位能否匹配
dp[0][0]=1
tag=[m]*n
for i in range(1,n):
if(a[i]=="*" and dp[i-1][0]==1):
dp[i][0]=1
tag[i]=0
for i in range(1,n):
for j in range(1,m):
if(a[i]=="*" and tag[i-1]!=m):
for k in range(tag[i-1],m):
dp[i][k]=1
continue
elif(dp[i-1][j-1] and (a[i]==b[j] or a[i]=='*' or a[i]=='?')):
dp[i][j]=1
if(dp[i][j]):
tag[i]=min(tag[i],j)
if(dp[n-1][m-1]):
print("matched")
else:
print("not matched")带通配符的字符串匹配
根据dp表的值从后往前回溯。如果遇到则检查前一层的dp并移动指针，否则同时移动两个指针。注意区间长度去掉0，以及和?不能合并到一起。
from math import gcd
a=" "+input().strip()
b=" "+input().strip()
n=len(a)
m=len(b)
dp=[[0 for _ in range(m+1)]for _ in range(n+1)]#a的前i位与b的前j位能否匹配
dp[0][0]=1
for i in range(1,n):
if(a[i]=="*"):
dp[i][0]=dp[i-1][0]
else:
break
for i in range(1,n):
if(a[i]=="*"):
first=-1
if(dp[i][0]):
first=0
else:
for j in range(1,m):
if(dp[i-1][j]):
first=j
break
if(first!=-1):
for j in range(first,m):
dp[i][j]=1
elif(a[i]=='?'):
for j in range(1,m):
dp[i][j]=dp[i-1][j-1]
else:
for j in range(1,m):
dp[i][j]=dp[i-1][j-1] and a[i]==b[j]
def get_gcd(arr):
res=arr[0]
for i in range(1,len(arr)):
res=gcd(res,arr[i])
return res
if(dp[n-1][m-1]):
print("matched")
res=[0]*n
i=n-1
j=m-1
while(i>0):
if(a[i]=="*"):
if(dp[i-1][j]):
i-=1
else:
res[i]+=1
j-=1
else:
res[i]+=1
i-=1
j-=1
s=[]
cur=0
for i in range(1,n):
if(a[i]=="*" or a[i]=='?'):
if(i>1 and a[i]!=a[i-1] and cur>0):
s.append(cur)
cur=0
cur+=res[i]
else:
if(cur>0):
s.append(cur)
cur=0
if(cur>0):
s.append(cur)
if(len(s)==0):
print(0)
else:
print(sum(s)//get_gcd(s))
else:
print("not matched")[NOIP 2012 提高组] 同余方程
exgcd:求ax+by=gcd(a,b)的解 ->ax=1(mod b) (ax+by=m有解->gcd(a,b)整除m) https://www.luogu.com.cn/problem/solution/P1082
x=0
y=0
def exgcd(a,b):#ax+by=gcd(a,b)
global x,y
if(b==0):
x=1
y=0
return
exgcd(b,a%b)
x,y=y,x-(a//b)*y
a,b=map(int,input().split())
exgcd(a,b)
print((x%b+b)%b)【模板】有理数取余
即求b mod 19260817的乘法逆元。 exgcd求解或者求.(Fermat小定理模mod余1) 快读的时候同时取模。
import sys
a=sys.stdin.readline().strip()
b=sys.stdin.readline().strip()
new_a=0
new_b=0
mod=19260817
for i in range(len(a)):
new_a=(new_a*10+int(a[i]))%mod
for i in range(len(b)):
new_b=(new_b*10+int(b[i]))%mod
x=0
y=0
if(new_b==0):
print("Angry!")
sys.exit(0)
def exgcd(b,m):
global x,y
if(m==0):
x=1
y=0
return
exgcd(m,b%m)
x,y=y,x-(b//m)*y
exgcd(new_b,mod)
print((new_a*x)%mod)import sys
a=sys.stdin.readline().strip()
b=sys.stdin.readline().strip()
new_a=0
new_b=0
mod=19260817
for i in range(len(a)):
new_a=(new_a*10+int(a[i]))%mod
for i in range(len(b)):
new_b=(new_b*10+int(b[i]))%mod
x=1
if(new_b==0):
print("Angry!")
sys.exit(0)
i=mod-2
t=new_b
while(i):
if(i&1):
x=x*t%mod
t=t*t%mod
i>>=1
print((x*new_a)%mod)C Looooops
扩展欧几里得Exgcd.
from math import gcd
def exgcd(a,b):
if(b==0):
return 1,0
x,y=exgcd(b,a%b)
return y,x-(a//b)*y
while(True):
a,b,c,k=map(int,input().split())
if(a*a+b*b+c*c+k*k==0):
break
'''
a+cx=b(mod 2^k)
cx=b-a(mod 2^k)
cx+(2^k)y=b-a
t=(b-a)/gcd(c,2^k)
x=x0t,y=y0t
cx0+(2^k)y0=gcd(c,2^k)
(c/gcd)x+(2^k/gcd)y=(b-a)/gcd
res=x+k*(2^k/gcd)
'''
p=1<<k
g=gcd(c,p)
diff=(b-a)%p
if(diff%g!=0):
print("FOREVER")
continue
#b<a:b=b+kp>a,k>(a-b)/p
x,y=exgcd(c,p)
p_prime=p//g
ans=(x*diff//g)%p_prime
print(ans)2026.5.12
帮助 Jimmy
dp.注意特判如果下面没有任何平台能够接住时直接落地的情况。
t=int(input())
for _ in range(t):
n,x0,y0,maxs=map(int,input().split())
p=[]
h0=0
for i in range(n):
x,y,h=map(int,input().split())
p.append([h,x,y])
p.append([y0,x0,x0])
p.sort(reverse=True)
MAXM=float('inf')
dp=[[MAXM for _ in range(2)]for _ in range(n+1)]#dp[i][0]:第i个平台左端点的最短时间，dp[i][1]:右端点
if(p[-1][0])<=maxs:
dp[n][0]=dp[n][1]=p[-1][0]
for i in range(n-1,-1,-1):
h0=p[i][0]
curx,cury=p[i][1],p[i][2]
flag1=0
flag2=0
for j in range(i+1,n+1):
x,y,h=p[j][1],p[j][2],p[j][0]
if(x<=curx<=y and flag1==0):
if(h>=h0-maxs):
dp[i][0]=min(dp[j][0]+(curx-x),dp[j][1]+(y-curx))+(h0-h)
flag1=1
if(x<=cury<=y and flag2==0):
if(h>=h0-maxs):
dp[i][1]=min(dp[j][0]+(cury-x),dp[j][1]+(y-cury))+(h0-h)
flag2=1
if(flag1&flag2):
break
if(flag1==0):
if(h0<=maxs):
dp[i][0]=h0
if(flag2==0):
if(h0<=maxs):
dp[i][1]=h0
print(min(dp[0][0],dp[0][1]))积水量
m=int(input())
for _ in range(m):
n=int(input())
a=list(map(int,input().split()))
s=[]
ans=0
for i in range(n):
while(s and a[i]>a[s[-1]]):
h=s.pop()#水槽底部
if(s):
ans+=(min(a[i],a[s[-1]])-a[h])*(i-s[-1]-1)
s.append(i)
print(ans)倒排索引查询
多测清空
n=int(input())
doc=[]
res_glob=set()
for i in range(n):
a=list(map(int,input().split()))
s=a[0]
t=set(a[1:])
doc.append(t)
res_glob|=t
m=int(input())
for i in range(m):
w=list(map(int,input().split()))
res=res_glob.copy()
for j in range(n):
if(w[j]==1):
res&=doc[j]
for j in range(n):
if(w[j]==-1):
res-=doc[j]
ans=sorted(list(res))
if(len(ans)==0):
print("NOT FOUND")
else:
print(*ans)2026.5.13
Sequence
两两合并n次。两两求前n个的方式是n路归并，即a[0]+b[i],a[1]+b[i],……,a[m-1]+b[i]这m路取最小。m个队头加入优先队列，每次取了哪个就把下一个放入。 注意heapq取出头部用heapq.heappop()，直接用pop是取最后一个。
import heapq
t=int(input())
for _ in range(t):
m,n=map(int,input().split())
a=[]
for i in range(m):
t=list(map(int,input().split()))
a.append(sorted(t))
ans=a[0].copy()
for k in range(1,m):
minq=[]
cur=[]
for i in range(n):
heapq.heappush(minq,(ans[i]+a[k][0],i,0))
for i in range(n):
sum,idx1,idx2=heapq.heappop(minq)
cur.append(sum)
if(idx2+1<n):
heapq.heappush(minq,(ans[idx1]+a[k][idx2+1],idx1,idx2+1))
ans=cur.copy()
print(*ans)
最大最小整数
本质冒泡排序。注意cmp_to_key的写法。
from functools import cmp_to_key
def cmp_max(x,y):
if(x+y>y+x):
return -1
elif(x+y==y+x):
return 0
else:
return 1
def cmp_min(x,y):
if(x+y>y+x):
return 1
elif(x+y==y+x):
return 0
else:
return -1
n=int(input())
a=list(input().split())
maxa=sorted(a,key=cmp_to_key(cmp_max))
mina=sorted(a,key=cmp_to_key(cmp_min))
print("".join(maxa),"".join(mina))变换的迷宫
使用三维vis数组，而不是累加，因为每次抵达这个点的状态不一样。
from collections import deque
dx=[0,1,0,-1]
dy=[1,0,-1,0]
t=int(input())
for _ in range(t):
r,c,k=map(int,input().split())
a=[]
for i in range(r):
a.append(input())
x0,y0,x1,y1=0,0,0,0
for i in range(r):
for j in range(c):
if(a[i][j]=='S'):
x0=i
y0=j
if(a[i][j]=='E'):
x1=i
y1=j
q=deque()
q.append((x0,y0,0))
flag=0
vis=[[[0 for _ in range(k)]for _ in range(c)]for _ in range(r)]
vis[x0][y0][0]=1
while(q):
x,y,time=q.popleft()
if(x==x1 and y==y1):
print(time)
flag=1
break
for i in range(4):
xx=x+dx[i]
yy=y+dy[i]
if(0<=xx<r and 0<=yy<c):
if(vis[xx][yy][(time+1)%k]==0):
if((time+1)%k==0 or a[xx][yy]!='#'):
q.append((xx,yy,time+1))
vis[xx][yy][(time+1)%k]=1
if(flag==0):
print("Oop!")最大整数
排序后dp.
from functools import cmp_to_key
def cmp(x,y):
if(x+y<y+x):
return 1
elif(x+y==y+x):
return 0
else:
return -1
def f(x):
if(x==""):
return 0
else:
return int(x)
m=int(input())
n=int(input())
a=sorted(list(input().split()),key=cmp_to_key(cmp))
dp=[["" for _ in range(m+1)]for _ in range(n)]#考虑前i个数，组成不超过j位的最大值
for j in range(len(a[0]),m+1):
dp[0][j]=a[0]
for j in range(1,m+1):
for i in range(1,n):
if(len(a[i])>j):
dp[i][j]=dp[i-1][j]
else:
dp[i][j]=str(max(f(dp[i-1][j]),f(dp[i-1][j-len(a[i])]+a[i])))
print(dp[n-1][m])使数组互补的最少操作次数
差分数组处理整个区间的加减。用数组存储目标和为某个值的情况下需要的总操作数，注意到这只与目标和在哪一段区间有关系，因此可以对目标和数组的一整段进行操作，从而转化为差分做法。
from typing import List
from math import inf
class Solution:
def minMoves(self, nums: List[int], limit: int) -> int:
n=len(nums)
diff=[0]*(limit*2+2)#diff[i]:全部变成i的操作数的差分
for i in range(n//2):
x=nums[i]
y=nums[n-1-i]
l=min(x,y)+1
r=max(x,y)+limit
#[2.l-1]+=2
diff[2]+=2
diff[l]-=2
#[l,r]+=1
diff[l]+=1
diff[r+1]-=1
#去除x+y
diff[x+y]-=1
diff[x+y+1]+=1
#[r+1,limit*2]+2
diff[r+1]+=2
ans=inf
sum=0
for i in range(2,limit*2+1):
sum+=diff[i]
ans=min(ans,sum)
return ans2026.5.14
炸鸡排
n,k=map(int,input().split())
t=list(map(int,input().split()))
t.sort(reverse=True)
s=sum(t)
idx=0
while(idx<n and t[idx]>s/k):
s-=t[idx]
k-=1
idx+=1
print(f"{s/k:.3f}")2022决战双十一
n,m=map(int,input().split())
goods=[[-1 for _ in range(m)]for _ in range(n)]
shops=[[]for _ in range(m)]
for i in range(n):
s=list(input().split())
for c in s:
x,y=map(int,c.split(':'))
goods[i][x-1]=y
for i in range(m):
s=list(input().split())
for c in s:
x,y=map(int,c.split("-"))
shops[i].append((x,y))
for i in range(m):
shops[i]=sorted(shops[i],key=lambda x:-x[1])
shop_sum=[0]*m
vis=[[0 for _ in range(m)]for _ in range(n)]
ans=float("inf")
def op(sum):
for i in range(m):
for x,y in shops[i]:
if(shop_sum[i]>=x):
sum-=y
break
return sum
def dfs(sum,cur):
global ans,shop_sum
if(cur==n):
sum-=(sum//300)*50
ans=min(ans,op(sum))
return
for i in range(m):
if(goods[cur][i]!=-1 and vis[cur][i]==0):
sum+=goods[cur][i]
shop_sum[i]+=goods[cur][i]
vis[cur][i]=1
dfs(sum,cur+1)
shop_sum[i]-=goods[cur][i]
vis[cur][i]=0
sum-=goods[cur][i]
dfs(0,0)
print(ans)An Easy Problem
while(True):
a=int(input())
if(a==0):
break
low=a&(-a)
new=a+low
a=a^new
a=a//low
a=a//4
print(new|a)2026.5.19
生日相同
from collections import defaultdict
n=int(input())
a=defaultdict(list)
for i in range(n):
idx,m,d=input().split()
birth=int(m)*100+int(d)
a[birth].append(idx)
a=dict(list(sorted(a.items(),key=lambda x:x[0])))
for i in a.keys():
if(len(a[i])>1):
mon=i//100
day=i-mon*100
print(mon,day,*a[i])满足合法工时的最少人数
from math import ceil
a=list(map(int,input().split(",")))
t=int(input())
l=1
r=max(a)
ans=r
while(l<=r):
mid=(l+r)>>1
s=0
for i in a:
s+=ceil(i/mid)
if(s<=t):
ans=mid
r=mid-1
else:
l=mid+1
print(ans)虫子的生活
种类并查集/dfs染色
t=int(input())
for qaq in range(1,t+1):
n,m=map(int,input().split())
fa=[i for i in range(2*n+2)]
siz=[1]*(2*n+2)
def find(x):
if(fa[x]==x):
return x
fa[x]=find(fa[x])
return fa[x]
def merge(x,y):
fx=find(x)
fy=find(y)
if(fx==fy):
return
if(siz[fx]>siz[fy]):
fx,fy=fy,fx
fa[fx]=fy
siz[fy]+=siz[fx]
flag=0
for i in range(m):
x,y=map(int,input().split())
if(flag==1):
continue
if(find(x)==find(y)):
flag=1
continue
merge(x,y+n)
merge(x+n,y)
print(f"Scenario #{qaq}:")
if(flag==0):
print("No suspicious bugs found!")
else:
print("Suspicious bugs found!")
print()[USACO03FALL / HAOI2006] 受欢迎的牛 G
使用Tarjan SCC缩点，一个SCC中的所有奶牛都相互爱慕。然后记录每个SCC的出度，可知如果有一个SCC的出度为0那么其中的所有点为最受欢迎，如果有多个SCC出度为0那么没有最受欢迎的奶牛。
import sys
sys.setrecursionlimit(1000000)
n,m=map(int,input().split())
c=[[]for _ in range(n+1)]
for i in range(m):
x,y=map(int,input().split())
c[x].append(y)
low=[0]*(n+1)
dfn=[0]*(n+1)
time=0
s=[]
scc=[]
idx=[0]*(n+1)
def tarjan(k):
global time
time+=1
low[k]=dfn[k]=time
s.append(k)
for i in c[k]:
if(dfn[i]==0):
tarjan(i)
low[k]=min(low[k],low[i])
elif i in s:
low[k]=min(low[k],dfn[i])
if(low[k]==dfn[k]):
tmp=[]
while(True):
x=s.pop()
tmp.append(x)
idx[x]=len(scc)
if(x==k):
break
scc.append(tmp)
for i in range(1,n+1):
if(dfn[i]==0):
tarjan(i)
cnt=len(scc)
out=[0]*cnt
for i in range(1,n+1):
for j in c[i]:
if(idx[i]!=idx[j]):
out[idx[i]]+=1
ans=0
flag=0
for i in range(cnt):
if(out[i]==0 and ans!=0):
flag=1
print(0)
break
elif(out[i]==0):
ans+=len(scc[i])
if(flag==0):
print(ans)[IOI 1996 / USACO5.3] 校园网 Network of Schools
使用Tarjan缩点。第一问即求入度为0的点个数，因为这些点没有学校传给它们。第二问特判整个图是否强连通，如果强连通则输出0，否则答案为入度和出度为0的点的个数中的较大值。（第二问要求使整个图强连通最少要增加的边，考虑将入度0和出度0的点两两连接。）
import sys
sys.setrecursionlimit(1000000)
n=int(input())
a=[[]]
for i in range(1,n+1):
a.append(list(map(int,input().split()))[:-1])
dfn=[0]*(n+1)
low=[0]*(n+1)
time=0
s=[]
scc=[]
idx=[0]*(n+1)
def tarjan(k):
global time
time+=1
low[k]=dfn[k]=time
s.append(k)
for i in a[k]:
if(dfn[i]==0):
tarjan(i)
low[k]=min(low[k],low[i])
elif(i in s):
low[k]=min(low[k],dfn[i])
if(low[k]==dfn[k]):
tmp=[]
while(True):
x=s.pop()
tmp.append(x)
idx[x]=len(scc)
if(x==k):
break
scc.append(tmp)
for i in range(1,n+1):
if(dfn[i]==0):
tarjan(i)
lens=len(scc)
in_deg=[0]*lens
out_deg=[0]*lens
for i in range(1,n+1):
for j in a[i]:
if(idx[i]!=idx[j]):
out_deg[idx[i]]+=1
in_deg[idx[j]]+=1
ans1=0
ans2=0
for i in range(lens):
if(in_deg[i]==0):
ans1+=1
if(out_deg[i]==0):
ans2+=1
print(ans1)
if(lens==1):
print(0)
else:
print(max(ans1,ans2))【模板】缩点
Tarjan缩点，将图变为DAG.然后进行拓扑排序，dp最大权值和，注意dp需要在拓扑序上进行以保证正确更新。
from collections import deque
import sys
sys.setrecursionlimit(1000000)
n,m=map(int,input().split())
p=[0]+list(map(int,input().split()))
a=[[]for _ in range(n+1)]
for i in range(m):
x,y=map(int,input().split())
a[x].append(y)
dfn=[0]*(n+1)
low=[0]*(n+1)
time=0
s=[]
scc=[]
idx=[0]*(n+1)
val=[]
def tarjan(k):
global time
time+=1
low[k]=dfn[k]=time
s.append(k)
for i in a[k]:
if(dfn[i]==0):
tarjan(i)
low[k]=min(low[k],low[i])
elif(i in s):
low[k]=min(low[k],dfn[i])
if(low[k]==dfn[k]):
tmp=[]
sum=0
while(True):
x=s.pop()
tmp.append(x)
sum+=p[x]
idx[x]=len(scc)
if(x==k):
break
scc.append(tmp)
val.append(sum)
for i in range(1,n+1):
if(dfn[i]==0):
tarjan(i)
lens=len(scc)
in_deg=[0]*lens
dag=[[]for _ in range(lens)]
for i in range(1,n+1):
for j in a[i]:
if(idx[i]!=idx[j]):
in_deg[idx[j]]+=1
dag[idx[i]].append(idx[j])
q=deque()
dp=[0]*lens
for i in range(lens):
if(in_deg[i]==0):
q.append(i)
dp[i]=val[i]
while(q):
x=q.popleft()
for i in dag[x]:
dp[i]=max(dp[i],dp[x]+val[i])
in_deg[i]-=1
if(in_deg[i]==0):
q.append(i)
print(max(dp))【模板】最小斯坦纳树
先跑一遍Floyd计算任意两点间的最短路，然后状压dp枚举每个状态（s的子集）的子集，最短长度可以由两个子集的dp值更新。每个状态dp完之后使用dijkstra进行松弛操作，以得到对于状态mask的单源最短路。最后答案取以1-n为根的dp值中的最小值。
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
const int INF=0x3f3f3f3f;
int a[101][101];
int dp[1<<10][101];//j为根，将i中的关键点全部联通的最短距离
int n,m,k;
void dijkstra(int x){
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
for(int i=1;i<=n;i++){
if(dp[x][i]<INF){
q.push({dp[x][i],i});
}
}
while(!q.empty()){
auto [dist,u]=q.top();
q.pop();
if(dist>dp[x][u]){
continue;
}
for(int v=1;v<=n;v++){
int w=a[u][v];
if(dp[x][v]>dp[x][u]+w){
dp[x][v]=dp[x][u]+w;
q.push({dp[x][v],v});
}
}
}
}
int main(){
scanf("%d %d %d",&n,&m,&k);
memset(a,INF,sizeof(a));
for(int i=0;i<m;i++){
int u,v,w;
scanf("%d %d %d",&u,&v,&w);
if(a[u][v]>w){
a[u][v]=w;
a[v][u]=w;
}
}
int s[k];
for(int i=0;i<k;i++){
scanf("%d",&s[i]);
}
for(int p=1;p<=n;p++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
a[i][j]=min(a[i][j],a[i][p]+a[p][j]);
}
}
}
memset(dp,INF,sizeof(dp));
for(int i=1;i<(1<<k);i++){
if(!(i&(i-1))){//i只有1个1
for(int j=0;j<k;j++){
if(i&(1<<j)){
dp[i][s[j]]=0;
break;
}
}
}
for(int j=i;j>0;j=(j-1)&i){//枚举i的子集
for(int p=1;p<=n;p++){
dp[i][p]=min(dp[i][p],dp[j][p]+dp[i^j][p]);
}
}
dijkstra(i);
}
int ans=INF;
for(int i=1;i<=n;i++){
ans=min(ans,dp[(1<<k)-1][i]);
}
printf("%d\n",ans);
}简单题
KD Tree:把 K 维空间不断用垂直于坐标轴的超平面进行二分切割，每个节点代表一个切分点。
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
const int MAXN=200005;
const double alpha=0.75;//替罪羊树平衡因子
struct Node{
int x,y;
int v,sum;
int x1,y1,x2,y2;
int l,r;
int size;
} t[MAXN];
int root,tot;
int cur_nodes[MAXN],node_cnt;
bool cmpx(int a,int b){
return t[a].x<t[b].x;
}
bool cmpy(int a,int b){
return t[a].y<t[b].y;
}
void push_up(int u){
int l=t[u].l,r=t[u].r;
t[u].size=t[l].size+t[r].size+1;
t[u].sum=t[l].sum+t[r].sum+t[u].v;
t[u].x1=min({t[u].x,t[l].x1,t[r].x1});
t[u].y1=min({t[u].y,t[l].y1,t[r].y1});
t[u].x2=max({t[u].x,t[l].x2,t[r].x2});
t[u].y2=max({t[u].y,t[l].y2,t[r].y2});
}
void flatten(int u){//替罪羊树思想：不平衡时拍平子树重构
if(!u) return;
cur_nodes[node_cnt++]=u;
flatten(t[u].l);
flatten(t[u].r);
}
int build(int l,int r,int dim){
if(l>r) return 0;
int mid=(l+r)>>1;
if(dim==0){
nth_element(cur_nodes+l,cur_nodes+mid,cur_nodes+r+1,cmpx);
}
else{
nth_element(cur_nodes+l,cur_nodes+mid,cur_nodes+r+1,cmpy);
}
int u=cur_nodes[mid];
t[u].l=build(l,mid-1,dim^1);
t[u].r=build(mid+1,r,dim^1);
push_up(u);
return u;
}
void insert(int &u,int p,int dim){
if(!u){
u=p;
push_up(u);
return;
}
if(dim==0){
if(t[p].x<t[u].x){
insert(t[u].l,p,dim^1);
}
else{
insert(t[u].r,p,dim^1);
}
}
else{
if(t[p].y<t[u].y){
insert(t[u].l,p,dim^1);
}
else{
insert(t[u].r,p,dim^1);
}
}
push_up(u);
if(t[u].size*alpha<max(t[t[u].l].size,t[t[u].r].size)){
node_cnt=0;
flatten(u);
u=build(0,node_cnt-1,dim);
}
}
int query(int u,int x1,int y1,int x2,int y2){
if(!u) return 0;
if(t[u].x1>=x1 && t[u].y1>=y1 && t[u].x2<=x2 && t[u].y2<=y2){
return t[u].sum;
}
if(t[u].x2<x1 || t[u].y2<y1 || t[u].x1>x2 || t[u].y1>y2){
return 0;
}
int res=0;
if(t[u].x>=x1 && t[u].x<=x2 && t[u].y>=y1 && t[u].y<=y2){
res+=t[u].v;
}
res+=query(t[u].l,x1,y1,x2,y2);
res+=query(t[u].r,x1,y1,x2,y2);
return res;
}
int main(){
t[0].x1=t[0].y1=2e9;
t[0].x2=t[0].y2=-2e9;
t[0].sum=t[0].size=0;
int n;
scanf("%d",&n);
int op;
int last_ans=0;
while(scanf("%d",&op) && op!=3){
if(op==1){
int x,y,A;
scanf("%d %d %d",&x,&y,&A);
x^=last_ans;
y^=last_ans;
A^=last_ans;
tot++;
t[tot].x=x;
t[tot].y=y;
t[tot].v=t[tot].sum=A;
insert(root,tot,0);
}
else if(op==2){
int x1,y1,x2,y2;
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
x1^=last_ans;
y1^=last_ans;
x2^=last_ans;
y2^=last_ans;
last_ans=query(root,x1,y1,x2,y2);
printf("%d\n",last_ans);
}
}
}2026.5.20 月考
（from 群友fxc)
Huffman编码树
贪心地可知，Huffman编码的方式可使题目所求式子最小。
import heapq
n=int(input())
a=list(map(int,input().split()))
q=[]
for i in a:
heapq.heappush(q,i)
ans=0
while(len(q)>1):
x=heapq.heappop(q)
y=heapq.heappop(q)
ans+=x+y
heapq.heappush(q,x+y)
print(ans)兔子与樱花
使用Floyd求出全图最短路。记录路径的方法是对每一组起点和终点，记录起点下一步的点，并在松弛操作时更新。
from collections import defaultdict
from math import inf
p=int(input())
d=defaultdict(int)
name=[]
for i in range(p):
s=input()
d[s]=i
name.append(s)
a=[[inf for _ in range(p)]for _ in range(p)]
q=int(input())
next=[[0 for _ in range(p)]for _ in range(p)]
for i in range(q):
x,y,z=input().split()
idxx=d[x]
idxy=d[y]
a[idxx][idxy]=min(a[idxx][idxy], int(z))
a[idxy][idxx]=min(a[idxy][idxx], int(z))
for i in range(p):
for j in range(p):
if(i!=j and a[i][j]!=inf):
next[i][j]=j
else:
next[i][j]=-1
for k in range(p):
for i in range(p):
for j in range(p):
if(a[i][k]+a[k][j]<a[i][j]):
a[i][j]=a[i][k]+a[k][j]
next[i][j]=next[i][k]
r=int(input())
for i in range(r):
x,y=input().split()
idxx=d[x]
idxy=d[y]
cur=idxx
nxt=next[idxx][idxy]
while(cur!=idxy):
print(f"{name[cur]}->({a[cur][nxt]})->",end="")
cur=nxt
nxt=next[cur][idxy]
print(name[idxy])两座孤岛最短距离
dfs求连通块找到一个孤岛，并从这个岛上每个点对另一个岛bfs找最短路。
from collections import deque
n=int(input())
a=[]
vis=[[0 for _ in range(n)]for _ in range(n)]
dx=[-1,0,1,0]
dy=[0,1,0,-1]
q=deque()
def dfs(x,y):
for i in range(4):
xx=x+dx[i]
yy=y+dy[i]
if(xx>=0 and xx<n and yy>=0 and yy<n):
if(vis[xx][yy]==0 and a[xx][yy]=="1"):
vis[xx][yy]=1
q.append((xx,yy,0))
dfs(xx,yy)
for i in range(n):
a.append(list(input()))
flag=0
for i in range(n):
if(flag==1):
break
for j in range(n):
if(a[i][j]=="1"):
vis[i][j]=1
q.append((i,j,0))
dfs(i,j)
flag=1
break
for i in range(n):
for j in range(n):
if(vis[i][j]==1):
a[i][j]='0'
while(q):
x,y,dis=q.popleft()
if(a[x][y]=="1"):
print(dis-1)
break
for i in range(4):
xx=x+dx[i]
yy=y+dy[i]
if(xx>=0 and xx<n and yy>=0 and yy<n):
if(vis[xx][yy]==0):
vis[xx][yy]=1
q.append((xx,yy,dis+1))宝藏二叉树
树形dp.两个dp数组分别记录以i为根，选/不选i时整棵子树的最大值。从下往上更新。
n=int(input())
a=[0]+list(map(int,input().split()))
dp1=[0 for _ in range(n+1)]#以i为根，选i
dp2=[0 for _ in range(n+1)]#以i为根，不选i
for i in range(n,0,-1):
left=i<<1
right=(i<<1)|1
dp1[i]=a[i]
if(left<=n):
dp1[i]+=dp2[left]
dp2[i]+=max(dp1[left],dp2[left])
if(right<=n):
dp1[i]+=dp2[right]
dp2[i]+=max(dp1[right],dp2[right])
print(max(dp1[1],dp2[1]))Catenyms
对每个单词建立从第一个字母指向最后一个字母的有向边，题目转化为求欧拉路径。通过入度与出度判断是否存在合法的路径以及起点，然后使用Hierholzer算法，dfs搜索，每次经过一条边即删除，并在当前点无出边时将该点倒序加入答案路径。
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
t=int(input())
for _ in range(t):
n=int(input())
words=[]
for i in range(n):
tmp=input()
words.append(tmp)
words.sort()
a=defaultdict(list)
in_deg=defaultdict(int)
out_deg=defaultdict(int)
for i in range(n):
start=words[i][0]
end=words[i][-1]
a[start].append((end,words[i],i))
out_deg[start]+=1
in_deg[end]+=1
flag=0
m=len(in_deg)
start=""
end=""
for i in a.keys():
if(out_deg[i]-in_deg[i]==1):
if(start==""):
start=i
else:
flag=1
break
elif(in_deg[i]-out_deg[i]==1):
if(end==""):
end=i
else:
flag=1
break
elif(in_deg[i]!=out_deg[i]):
flag=1
break
if(flag==1):
print("***")
continue
if(start==""):
start=min(a.keys())
ans=[]
vis=[0]*n
def dfs(x):
for i in range(len(a[x])):
end,word,idx=a[x][i]
if(vis[idx]==0):
vis[idx]=1
dfs(end)
ans.append(word)
dfs(start)
if(len(ans)!=n):
print("***")
else:
ans.reverse()
print(".".join(ans))力场叠加模拟
使用lazy tag的线段树。
class SegmentTree:
def __init__(self,n,nums):
self.n=n
self.nums=nums
self.tree=[0]*(n*4)
self.lazy=[0]*(n*4)
self.build(1,1,n)
def pushup(self,node):
self.tree[node]=max(self.tree[node*2],self.tree[node*2+1])
def pushdown(self,node,l,r):
if(self.lazy[node]!=0):
mid=(l+r)>>1
self.tree[node*2]+=self.lazy[node]
self.tree[node*2+1]+=self.lazy[node]
self.lazy[node*2]+=self.lazy[node]
self.lazy[node*2+1]+=self.lazy[node]
self.lazy[node]=0
def build(self,node,l,r):
if(l==r):
self.tree[node]=self.nums[l]
return
mid=(l+r)>>1
self.build(node*2,l,mid)
self.build(node*2+1,mid+1,r)
self.pushup(node)
def update_range(self,node,start,end,l,r,val):
if(l<=start and end<=r):
self.tree[node]+=val
self.lazy[node]+=val
return
if(end<l or start>r):
return
self.pushdown(node,start,end)
mid=(start+end)>>1
self.update_range(node*2,start,mid,l,r,val)
self.update_range(node*2+1,mid+1,end,l,r,val)
self.pushup(node)
def query(self,node,start,end,l,r):
if(l<=start and end<=r):
return self.tree[node]
if(end<l or start>r):
return 0
self.pushdown(node,start,end)
mid=(start+end)>>1
return max(self.query(node*2,start,mid,l,r),self.query(node*2+1,mid+1,end,l,r))
n,q=map(int,input().split())
tree=SegmentTree(n,[0]*(n+1))
for _ in range(q):
s=input().split()
op=s[0]
if(op=='Add'):
l,r,v=map(int,s[1:])
tree.update_range(1,1,n,l,r,v)
elif(op=="Query"):
l,r=map(int,s[1:])
print(tree.query(1,1,n,l,r))2026.5.21
高维欧氏空间最小完美匹配（26）
Tree embedding->把数据放入2-HST中，树上距离近似替代两点距离。 使用随机平移四分树以保证相近的点被分到两个格子的概率很小。子树内的点优先和同一子树匹配。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
#include<random>
#include<map>
using namespace std;
int n,d;
double points[3005][105];
double shift[105];
double match[3005];
int solve(const vector<int> &points_idx,const vector<double> &mins,double len){
if(points_idx.empty()) return -1;
if(points_idx.size()==1) return points_idx[0];
if(len<1e-3){
int tmp=-1;
for(int i:points_idx){//内部两两匹配
if(tmp==-1){
tmp=i;
}
else{
match[tmp]=i;
match[i]=tmp;
tmp=-1;
}
}
return tmp;
}
double mid=len/2.0;
map<vector<int>,vector<int>> sub_blocks;//子块
for(int i:points_idx){
vector<int> cell(d);
for(int j=0;j<d;j++){
if(points[i][j]>=mins[j]+mid){
cell[j]=1;
}
else cell[j]=0;
}
sub_blocks[cell].push_back(i);
}
vector<int> unmatched;
for(auto &block:sub_blocks){
const vector<int>& cell_id=block.first;
const vector<int>& sub_points=block.second;
vector<double> sub_mins(d);
for(int i=0;i<d;i++){
sub_mins[i]=mins[i]+cell_id[i]*mid;
}
int res=solve(sub_points,sub_mins,mid);
if(res!=-1){
unmatched.push_back(res);
}
}
int tmp=-1;
for(int i:unmatched){
if(tmp==-1){
tmp=i;
}
else{
match[tmp]=i;
match[i]=tmp;
tmp=-1;
}
}
return tmp;
}
int main(){
scanf("%d %d",&n,&d);
vector<int> idx(n);
for(int i=0;i<n;i++){
idx[i]=i;
for(int j=0;j<d;j++){
scanf("%lf",&points[i][j]);
}
}
double minm=-1e8-100.0;
double maxm=1e8+100.0;
mt19937_64 rng(250903);
double delta=1LL<<29;
uniform_real_distribution<double> dist_shift(0.0,delta*0.1);
vector<double> base_mins(d);
for(int i=0;i<d;i++){
shift[i]=dist_shift(rng);
base_mins[i]=minm-shift[i];
}
solve(idx,base_mins,delta*2.0);
for(int i=0;i<n;i++){
printf("%d ",(int)match[i]+1);
}
}高维欧氏空间最小生成树（加强）（26）
独立采样m棵随机平移四分树，对每棵树的每个节点，建立星形图并加入候选边集中，最后对边集跑一遍MST.
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
#include<random>
#include<map>
using namespace std;
int n,d;
double points[20005][105];
struct Edge{
int u,v;
double w;
bool operator<(const Edge& other) const{
return w<other.w;
}
};
vector<Edge> cand_edges;
double get_dist(int i,int j){
double dist=0;
for(int k=0;k<d;k++){
double diff=points[i][k]-points[j][k];
dist+=diff*diff;
}
return sqrt(dist);
}
void build_spanner_edges(const vector<int>& points_idx,const vector<double>& mins,double len){
if(points_idx.size()<=1) return;
int center=points_idx[0];
for(int i=1;i<points_idx.size();i++){
int to=points_idx[i];
cand_edges.push_back({center,to,get_dist(center,to)});
}
if(len<1.0) return;
double mid=len/2.0;
map<vector<int>,vector<int>> sub_blocks;
for(int i:points_idx){
vector<int> cell(d);
for(int j=0;j<d;j++){
if(points[i][j]>=mins[j]+mid){
cell[j]=1;
}
else cell[j]=0;
}
sub_blocks[cell].push_back(i);
}
for(auto &block:sub_blocks){
const vector<int>& cell_id=block.first;
const vector<int>& sub_points=block.second;
vector<double> sub_mins(d);
for(int i=0;i<d;i++){
sub_mins[i]=mins[i]+cell_id[i]*mid;
}
build_spanner_edges(sub_points,sub_mins,mid);
}
}
int fa[200005];
int find(int x){
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
bool merge(int x,int y){
int fx=find(x),fy=find(y);
if(fx==fy) return false;
fa[fx]=fy;
return true;
}
int main(){
scanf("%d %d",&n,&d);
vector<int> idx(n);
for(int i=0;i<n;i++){
idx[i]=i;
for(int j=0;j<d;j++){
scanf("%lf",&points[i][j]);
}
}
double global_min=-1000.0;
double delta=1LL<<30;
mt19937_64 rng(111);
uniform_real_distribution<double> dist_shift(0.0,delta*0.2);
int m=15;
for(int t=0;t<m;t++){
vector<double> mins(d);
for(int i=0;i<d;i++){
double shift_v=dist_shift(rng);
mins[i]=global_min-shift_v;
}
build_spanner_edges(idx,mins,delta);
}
sort(cand_edges.begin(),cand_edges.end());
for(int i=0;i<n;i++) fa[i]=i;
int cnt=0;
for(const Edge edge:cand_edges){
if(merge(edge.u,edge.v)){
printf("%d %d\n",edge.u+1,edge.v+1);
cnt++;
if(cnt==n-1) break;
}
}
return 0;
}2026.5.25
高维欧氏空间范围点数查询
对网格进行随机平移，dfs搜索合法的网格，将点数相加。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<random>
#include<string>
#include<cmath>
#include<vector>
#include<map>
using namespace std;
int d,n,m,r;
double points[100005][20];
double shift[20];
map<vector<int>,int> grid_counts;
double len_l;
vector<int> cur_grid;
vector<double> q_coords;
int ans;
void dfs(int dim,double cur_dist){
if(cur_dist>r*r) return;
if(dim==d){
auto it=grid_counts.find(cur_grid);
if(it!=grid_counts.end()){
ans+=it->second;
}
return;
}
int center_id=(int)floor((q_coords[dim]+shift[dim])/len_l);
for(int i=-1;i<=1;i++){
int next_id=center_id+i;
cur_grid[dim]=next_id;
double min_coord=next_id*len_l-shift[dim];
double max_coord=(next_id+1)*len_l-shift[dim];
double next_dist=0.0;
if(q_coords[dim]<min_coord){
next_dist=min_coord-q_coords[dim];
}
else if(q_coords[dim]>max_coord){
next_dist=q_coords[dim]-max_coord;
}
dfs(dim+1,cur_dist+next_dist*next_dist);
}
}
int main(){
scanf("%d %d %d %d",&d,&n,&m,&r);
len_l=3.0*r;
if(len_l<1.0) len_l=1.0;
mt19937_64 rng(0);
uniform_real_distribution<double> dist_shift(0.0,len_l);
for(int i=0;i<d;i++){
shift[i]=dist_shift(rng);
}
for(int i=0;i<n;i++){
vector<int> tmp(d);
for(int j=0;j<d;j++){
scanf("%lf",&points[i][j]);
tmp[j]=(int)floor((points[i][j]+shift[j])/len_l);
}
grid_counts[tmp]++;
}
cur_grid.resize(d);
q_coords.resize(d);
for(int i=0;i<m;i++){
for(int j=0;j<d;j++){
scanf("%lf",&q_coords[j]);
}
ans=0;
dfs(0,0.0);
printf("%d\n",ans);
}
}2026.5.26
排序链表
找到中点然后归并排序。
# Definition for singly-linked list.
from typing import Optional
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def middle(self,head):
slow=fast=head
while(fast and fast.next):
pre=slow
slow=slow.next
fast=fast.next.next
pre.next=None
return slow
def merge(self,l1,l2):
cur=dummy=ListNode()
while(l1 and l2):
if(l1.val<l2.val):
cur.next=l1
l1=l1.next
else:
cur.next=l2
l2=l2.next
cur=cur.next
if(l1):
cur.next=l1
if(l2):
cur.next=l2
return dummy.next
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if(head is None or head.next is None):
return head
head2=self.middle(head)
head=self.sortList(head)
head2=self.sortList(head2)
return self.merge(head,head2)合并 K 个升序链表
小根堆存储每个表头，然后每次取最小的并将其后一个加入堆。注意如果加入自定义类型需要定义__lt__lt，以及Leetcode的自定义节点会覆盖掉自己写的，所以前面加入值和下标以确保不会比较到节点上。
# Definition for singly-linked list.
from typing import List, Optional
import heapq
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def __lt__(self,other):
return self.val<other.val
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
h=[]
n=len(lists)
for i in range(n):
if(lists[i]):
heapq.heappush(h,(lists[i].val,i,lists[i]))
dummy=cur=ListNode()
while(h):
val,index,node=heapq.heappop(h)
cur.next=node
cur=cur.next
if(node.next):
heapq.heappush(h,(node.next.val,index,node.next))
return dummy.next对称二叉树
递归即可.
# Definition for a binary tree node.
from typing import Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def check(p,q):
if(p is None and q is None):
return True
if(p is None or q is None):
return False
if(p.val!=q.val):
return False
return Solution.check(p.left,q.right) and Solution.check(p.right,q.left)
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
if(root is None):
return True
return Solution.check(root.left,root.right)二叉树的直径
递归将左子树和右子树的深度相加.
# Definition for a binary tree node.
from typing import Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
ans=0
def dfs(root,dep):
nonlocal ans
if(root is None):
return dep
left_depth=dfs(root.left,dep+1)
right_depth=dfs(root.right,dep+1)
ans=max(ans,left_depth+right_depth-2*dep-2)
return max(left_depth,right_depth)
dfs(root,0)
return ans验证二叉搜索树
bfs看前一个数是否小于自己即可。或者递归，每次检查对应的区间范围并更新。
# Definition for a binary tree node.
from typing import Optional
from math import inf
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
pre=-inf
def search(node):
nonlocal pre
if(node is None):
return True
if(not search(node.left)):
return False
if(node.val<=pre):
return False
pre=node.val
return search(node.right)
return search(root)二叉树的右视图
层次遍历找每层最右边的。一直搜右边不一定是解。
# Definition for a binary tree node.
from typing import Optional, List
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
node=root
ans=[]
q=deque()
q.append(node)
if(node==None):
return ans
while(q):
n=len(q)
for i in range(n):
node=q.popleft()
if(i==n-1):
ans.append(node.val)
if(node.left):
q.append(node.left)
if(node.right):
q.append(node.right)
return ans二叉树展开为链表
空间O(1)的方法是类似Morris遍历，把左子树叶子接回来。
# Definition for a binary tree node.
from typing import Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def flatten(self, root: Optional[TreeNode]) -> None:
"""
Do not return anything, modify root in-place instead.
"""
res=[]
def dfs(node):
if(node is None):
return
res.append(node)
dfs(node.left)
dfs(node.right)
dfs(root)
for i in range(len(res)-1):
res[i].left=None
res[i].right=res[i+1]2026.5.27
01最小生成树
要求最小生成树即需要包含尽可能多的零边。考虑零边连接成的连通块，最终的MST即为将这些连通块连在一起，因此MST的大小即为连通块个数减1.使用bfs+差集操作避免超时。
import sys
from collections import deque
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
g=set()
for i in range(m):
x,y=map(int,input().split())
g.add((x,y))
g.add((y,x))
ans=0
vis=set()
for i in range(1,n+1):
vis.add(i)
q=deque()
for i in range(1,n+1):
if(i in vis):
vis.remove(i)
q.append(i)
while(q):
node=q.popleft()
tmp=set()
for j in vis:
if((node,j) not in g):
tmp.add(j)
q.append(j)
vis-=tmp
ans+=1
print(ans-1)邮递员送快递
构建正向与反向图，并分别跑一遍Dijkstra。注意如果使用邻接矩阵存图要判重，以及此处要使用邻接表以避免超时。
import heapq
n,m=map(int,input().split())
a=[[]for _ in range(n+1)]
b=[[]for _ in range(n+1)]
for i in range(m):
x,y,z=map(int,input().split())
a[x].append((y,z))
b[y].append((x,z))
dist=[float("inf") for _ in range(n+1)]
dist[1]=0
dist2=[float("inf") for _ in range(n+1)]
dist2[1]=0
h=[]
heapq.heappush(h,(0,1))
while(h):
d,node=heapq.heappop(h)
if(d>dist[node]):
continue
for nxt,cost in a[node]:
if(dist[node]+cost<dist[nxt]):
dist[nxt]=dist[node]+cost
heapq.heappush(h,(dist[nxt],nxt))
h=[]
heapq.heappush(h,(0,1))
while(h):
d,node=heapq.heappop(h)
if(d>dist2[node]):
continue
for nxt,cost in b[node]:
if(dist2[node]+cost<dist2[nxt]):
dist2[nxt]=dist2[node]+cost
heapq.heappush(h,(dist2[nxt],nxt))
ans=0
for i in range(1,n+1):
ans+=dist[i]+dist2[i]
print(ans)
累加树
插入构建BST，然后从大到小，即右根左遍历，全局变量累加和并更新到节点中。最后bfs层序遍历输出。
from collections import deque
class TreeNode:
def __init__(self,val=0,left=None,right=None,sum=0):
self.val=val
self.left=left
self.right=right
self.sum=sum
def insert(root,val):
if(root is None):
return TreeNode(val)
if(val<root.val):
root.left=insert(root.left,val)
else:
root.right=insert(root.right,val)
return root
n=int(input())
a=list(map(int,input().split()))
root=TreeNode(a[0])
for i in range(1,n):
insert(root,a[i])
tot=0
def dfs(root):
global tot
if(root is None):
return 0
dfs(root.right)
tot+=root.val
root.sum=tot
dfs(root.left)
dfs(root)
q=deque()
q.append(root)
ans=[]
while(q):
node=q.popleft()
ans.append(node.sum)
if(node.left):
q.append(node.left)
if(node.right):
q.append(node.right)
print(*ans)火星大工程
from collections import deque
n,m=map(int,input().split())
g=[[]for _ in range(n+1)]
r=[[]for _ in range(n+1)]
in_deg=[0]*(n+1)
out_deg=[0]*(n+1)
for i in range(m):
x,y,z=map(int,input().split())
g[x].append((y,z))
r[y].append((x,z))
in_deg[y]+=1
out_deg[x]+=1
q=deque()
ve=[0]*(n+1)
for i in range(1,n+1):
if(in_deg[i]==0):
q.append(i)
while(q):
node=q.popleft()
for i,val in g[node]:
ve[i]=max(ve[i],ve[node]+val)
in_deg[i]-=1
if(in_deg[i]==0):
q.append(i)
ans=max(ve)
print(ans)
vl=[ans]*(n+1)
q=deque()
for i in range(1,n+1):
if(out_deg[i]==0):
q.append(i)
while(q):
node=q.popleft()
for i,val in r[node]:
vl[i]=min(vl[i],vl[node]-val)
out_deg[i]-=1
if(out_deg[i]==0):
q.append(i)
res=[]
for i in range(1,n+1):
for j,k in g[i]:
if(ve[i]+k==vl[j]):
res.append((i,j))
res.sort()
for i,j in res:
print(i,j)
upstairs
同余最短路。选择a,b,c中最小的数（不妨a）作为最后叠加的层数，问题转化为在模a意义下，h=by+cz，而当此时的h最小，它是否小于目标的h。因此对每个余数u构建(u+b) mod a和(u+c) mod a的路径，从0开始跑一遍Dijkstra，得到的即为最小的h.
import heapq
a,b,c=map(int,input().split())
query=int(input())
step=[]
if(a>0):
step.append(a)
if(b>0):
step.append(b)
if(c>0):
step.append(c)
step.sort()
if(len(step)>=2):
m=step[0]
edges=step[1:]
dist=[float("inf")]*m
dist[0]=0
q=[]
heapq.heappush(q,(0,0))
while(q):
d,node=heapq.heappop(q)
if(d>dist[node]):
continue
for i in edges:
nxt=(node+i)%m
if(dist[nxt]>d+i):
dist[nxt]=d+i
heapq.heappush(q,(dist[nxt],nxt))
def solve(h):
if(len(step)==0):
if(h==0):
return True
else:
return False
elif(len(step)==1):
if(h%step[0]==0):
return True
else:
return False
rem=h%m
if(dist[rem]<=h):
return True
else:
return False
for i in range(query):
h=int(input())
if(solve(h)):
print("Yes")
else:
print("No")猫猫搭积木
按秩合并并查集，同时维护代表节点的集合中的所有元素。注意计算集合个数的操作需要特判自己与自己合并的情况，因此在merge函数中进行。
n,q,s=map(int,input().split())
fa=[i for i in range(n+1)]
siz=[1]*(n+1)
group=[set([i]) for i in range(n+1)]
ans=n
def find(x):
if(fa[x]==x):
return x
fa[x]=find(fa[x])
return fa[x]
def merge(x,y):
global ans
fx=find(x)
fy=find(y)
if(fx==fy):
return
if(siz[fx]<siz[fy]):
fx,fy=fy,fx
fa[fy]=fx
siz[fx]+=siz[fy]
group[fx]|=group[fy]
ans-=1
for i in range(q):
x,y=map(int,input().split())
merge(x,y)
fx=find(x)
if(siz[fx]>=s):
ans+=siz[fx]-1
for j in group[fx]:
if(j==fx):
continue
fa[j]=j
siz[j]=1
group[j]=set([j])
fa[fx]=fx
siz[fx]=1
group[fx]=set([fx])
print(ans)
# for j in range(1,n+1):
# print(find(j),end=" ")从前序与中序遍历序列构造二叉树
# Definition for a binary tree node.
from typing import List, Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
if not preorder or not inorder:
return None
root_val=preorder[0]
root=TreeNode(root_val)
root_index=inorder.index(root_val)
root.left=self.buildTree(preorder[1:1+root_index],inorder[:root_index])
root.right=self.buildTree(preorder[1+root_index:],inorder[root_index+1:])
return root路径总和 III
dfs->前缀和。 使用哈希表存储前缀和出现的次数，遍历到每一个都判断是否可以对答案造成贡献。
# Definition for a binary tree node.
from typing import Optional
from collections import defaultdict
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
cnt=defaultdict(int)
cnt[0]=1
ans=0
def dfs(node,cur_sum):
nonlocal ans
if(not node):
return
cur_sum+=node.val
ans+=cnt[cur_sum-targetSum]
cnt[cur_sum]+=1
dfs(node.left,cur_sum)
dfs(node.right,cur_sum)
cnt[cur_sum]-=1
dfs(root,0)
return ans二叉树中的最大路径和
递归求解每个点的贡献（自己的值+左子树贡献+右子树贡献）。然后经过每个点的路径最大值即为自己加上左右子树的最大贡献。
# Definition for a binary tree node.
from typing import Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def maxPathSum(self, root: Optional[TreeNode]) -> int:
maxm=-float('inf')
def maxgain(node):#以node为根,相当于node的贡献
nonlocal maxm
if(node is None):
return 0
left_gain=max(maxgain(node.left),0)
right_gain=max(maxgain(node.right),0)
maxm=max(maxm,node.val+left_gain+right_gain)
return node.val+max(left_gain,right_gain)
maxgain(root)
return maxm终于把力扣100写完了！
2026.5.30
最小二乘法
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<vector>
#include<random>
using namespace std;
#pragma GCC optimize("O2")
int n,d;
int m=8000;
int main(){
scanf("%d %d",&n,&d);
mt19937 rng(0);
uniform_int_distribution<int> dist_row(0,m-1);
uniform_int_distribution<int> dist_sign(0,1);
vector<vector<double>> hatx(m,vector<double>(d,0.0));
vector<double> haty(m,0.0);
for(int i=0;i<n;i++){
int l;
scanf("%d",&l);
int h=dist_row(rng);
int s=dist_sign(rng)*2-1;
vector<pair<int,double>> v(l);
for(int j=0;j<l;j++){
scanf("%d %lf",&v[j].first,&v[j].second);
v[j].first--;
}
double y;
scanf("%lf",&y);
for(int j=0;j<l;j++){
hatx[h][v[j].first]+=s*v[j].second;
}
haty[h]+=s*y;
}
//A=hatx^T *hatx B=hatx^T *haty
vector<vector<double>> A(d,vector<double>(d,0.0));
vector<double> B(d,0.0);
for(int i=0;i<m;i++){
for(int j=0;j<d;j++){
double val=hatx[i][j];
for(int k=j;k<d;k++){
A[j][k]+=val*hatx[i][k];
}
B[j]+=val*haty[i];
}
}
// for(int j=0;j<d;j++){
// A[j][j]+=1e-9;
// }
for(int i=0;i<d;i++){
for(int j=0;j<i;j++){
A[i][j]=A[j][i];
}
}
for(int i=0;i<d;i++){
int pivot=i;
for(int j=i+1;j<d;j++){
if(abs(A[j][i])>abs(A[pivot][i])){
pivot=j;
}
}
if(pivot!=i){
swap(A[i],A[pivot]);
swap(B[i],B[pivot]);
}
if(abs(A[i][i])<1e-12){
continue;
}
for(int j=i+1;j<d;j++){
double factor=A[j][i]/A[i][i];
for(int k=i;k<d;k++){
A[j][k]-=factor*A[i][k];
}
B[j]-=factor*B[i];
}
}
vector<double> w(d,0.0);
for(int i=d-1;i>=0;i--){
double sum=B[i];
for(int j=i+1;j<d;j++){
sum-=A[i][j]*w[j];
}
if(abs(A[i][i])<1e-12){
w[i]=0.0;
}else{
w[i]=sum/A[i][i];
}
}
for(int i=0;i<d;i++){
printf("%lf ",w[i]);
}
}最大主成分
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<random>
#include<cstdlib>
using namespace std;
#pragma GCC optimize("O2")
struct Element{
int i,j;
long double val;
};
int n,m,d;
int main(){
scanf("%d %d %d",&n,&d,&m);
vector<Element> a(m);
for(int i=0;i<m;i++){
scanf("%d %d %Lf",&a[i].i,&a[i].j,&a[i].val);
a[i].i--;
a[i].j--;
}
vector<long double> x(d,1.0);
long double sum=0;
for(int j=0;j<d;j++){
sum+=x[j]*x[j];
}
sum=sqrt(sum);
for(int j=0;j<d;j++){
x[j]/=sum;
}
int iter=100;
vector<long double> y(n,0.0);
for(int i=0;i<iter;i++){
vector<long double> y(n,0.0);
for(int j=0;j<m;j++){
y[a[j].i]+=a[j].val*x[a[j].j];
}
vector<long double> z(d,0.0);
for(int i=0;i<m;i++){
z[a[i].j]+=a[i].val*y[a[i].i];
}
long double norm=0;
for(int j=0;j<d;j++){
norm+=z[j]*z[j];
}
norm=sqrt(norm);
for(int j=0;j<d;j++){
x[j]=z[j]/norm;
}
}
for(int i=0;i<d;i++){
printf("%Lf\n",x[i]);
}
return 0;
}
DISCUSSION
Comments
Sign in with GitHub to join the conversation.