前言大风天踢了会球,立竿见影就觉得感冒了,无敌了,一会去医务室整点抗病毒颓了一会好点了()思路首先转化题意给你一张\(n\)点\(m\)边的图\(\mathbb{G}\)和一棵同样由这\(n\)个点组成的树\(\mathbb{T}\),求对树上的点有多少中标号方式\(p\),使得\(\forall{(

ZJOI2016旅行者题解题目大意：给定一个\(n\timesm\)的网格图，相邻的四连通的点之间有给定边权的双向边，有\(Q\)个离线询问，问两个点之间的最短路。\(n\timesm\le2\times10^4,Q\le10^5\)。发现了吗？和上次省选组的三角剖分那道题很像，这种平面图上的最短路很有可能是分治

咕了2天才写的题解还是比较经典的题目，分治处理网格图最短路离线下来，利用分治的思想，用一条线把网格图平均劈成两半，每次只考虑询问在两块的一对点，所有的线必须经过直线上的一个点，于是我把线上所有点都在规定范围内跑一次dijkstra，最后直接算答案，显然我想让最短路跑的次数最小，每次选

P3349[ZJOI2016]小星星树形dp+子集反演有一张图和一棵树，点数都为\(n\)，给树上的每个点一个映射\(a_i\)，每个\(a_i\)不同，\(a_i\in[1,n]\)。要求对于树上所有\((u,v)\)，都有\((a_u,a_v)\)在图上。求映射方案数。看到\(n\)的范围，可以想到树形状压dp。设\(F_{i,j,S}\)

P3350[ZJOI2016]旅行者分治+最短路网格图可以想到分治。每次将长边分为两半，处理越过中线的询问。那么就可以枚举中线上的每个点更新答案，经过\(x\)的路径更新\((u,v)\)就是\(dis_{u,x}+dis_{x,v}\)。每次预处理中线上每个点的单源最短路即可。设\(S=nm\)，复杂度\(O(S\sq

标签:子集反演,动态规划[ZJOI2016]小星星题目描述小Y是一个心灵手巧的女孩子，她喜欢手工制作一些小饰品。她有\(n\)颗小星星，用\(m\)条彩色的细线串了起来，每条细线连着两颗小星星。有一天她发现，她的饰品被破坏了，很多细线都被拆掉了。这个饰品只剩下了\(n-1\)条细线，但通

[ZJOI2016]小星星题目描述小Y是一个心灵手巧的女孩子，她喜欢手工制作一些小饰品。她有\(n\)颗小星星，用\(m\)条彩色的细线串了起来，每条细线连着两颗小星星。有一天

绝世容斥好题，刚好NOIp前要复习容斥，就拉过来当100紫了。祝自己明天的NOIprp++这题好久前看过题解，感觉好可惜，浪费了好题。以后自己不会的题也不能看题解了。题意：