-
Noip2016Day2T3 愤怒的小鸟
题目链接problem平面内有n个点,每次可以确定一条过原点且开口向上的抛物线,将这条抛物线上所有的点都删去。问最少需要删几次可以删掉全部的点。solutionn比较小,直接状压一下。因为已经确定了要过原点。所以每两个点都可以确定一条抛物线。预处理出所有抛物线以及每条抛物线可以删掉的点。然后记忆化搜索,枚举每次选择的抛物线。转移即可。注意精度!确定抛物线的方法就用解二元一次方程组的方法即可。具体如下:设抛物线的二次项系数为$a$,一次项系数为$b$ ,两个点的坐标分别为$(x_i,y_i)...…
-
Noip2016Day1T2 天天爱跑步
题目链接problemsolution这是一道一个顶六个的好题!!!说一下各档部分分怎么写吧。先看一下$S_i=1$和$T_i=1$的部分分怎么写。如果$S_i=1$当且仅当第$i$个点的深度$dep_i=w_i$时,该点可以观察到人。且观察到的人数为终点位于其子树内的人数。如果$T_i=1$这时第$i$个点能观察到的人数就是子树内起点深度=$dep_i+w[i]$的人数。用个桶记录下来这个值。如果得到该子树内$dep[s_i]=dep_i+w[i]$的数量呢?其实很简单。当第一次$bfs...…
-
Noip2017Day2T2 宝藏
题目链接problem有$n$个点,$m$条无向边,选择一个点开始开辟道路。开辟一条长度为$L$的链接$u,v$的道路会花费$L \times K$,K表示从选择的最初点到$u$所经过的点的数量。solution因为n比较小,所以可以状态压缩。第$i$位为1表示当前已经开辟了第$i$个点。枚举一个最初的状态,然后每次枚举下一个开辟的边得到下一个状态,转移即可。转移的过程中要维护出每个状态到初始点的距离。code#include<cstdio>#include<iostr...…
-
Noip2017Day1T3 逛公园
题目链接problem一个有向无重边自环图,设$D$为从$1$号点走到$n$号点的最短距离。问有多少条从$1$到$n$的路径长度不超过$D+K$。$K$为给定的值,且$K\le 50$如果有无数条,输出-1solution下面有$dis[i]$表示$i$号点到$n$号点的最短路径长度。设$f[i][j]$表示从$i$号点走到$n$号点,走了$j$的多余路径的方案数。就有如下转移:\[f[i][j]=\sum\limits_{i,v之间有边}f[v][j-(dis[v]+w-dis[i])]...…
-
Noip2018Day1T3 赛道修建
题目链接problem给出一棵有边权的树。一条链的权值定义为该链所经过的边的边权值和。需要选出$m$条链,求$m$条链中权值最小的链的权值最大是多少。solution首先显然二分。然后考虑如何判断二分出来的一个答案$x$是否是可行的。也就是能否选出$m$条链,每条链权值都大于等于$x$。这个其实是贪心。定义直链为从一个某个点的祖先到该点的路径。可以发现每条链要么就是一条直链,要么由两条直链在某个点处合并起来得到。贪心的地方在于,对于每个点肯定都是优先将能合成的直链合成。然后再保证向上传递的...…
-
cometOJ10C 鱼跃龙门
题目链接problem实际上就是对于给定的$n$求一个最小的$x$满足$\frac{x(x+1)}{2}=kn(k\in N^*)$。solution对上面的式子稍微变形可得$x(x+1)=2kn$。因为$x$与$(x+1)$互质,所以将$n$质因数分解后,同种质因子肯定都位于$x$或$(x+1)$中。$10^{12}$以内的整数质因数分解后种类不超过$13$种,所以可以暴力枚举每种质因子属于$x$还是$x+1$。然后分别得到$a$和$b$。下面要使得$bx=ay+1$。扩展欧几里得求解即...…
-
AtCoder Beginner Contest 139F Engines
链接problem给出$n$个二元组$(x,y)$。最初位于原点$(0,0)$,每次可以从这$n$个二元组中挑出一个,然后将当前的坐标$(X,Y)$变为$(X+x,Y+y)$,每个二元组只能被选一次。选出一些二元组,使得按照这些二元组移动后与原点的欧几里得距离最大。求这个距离。solution将这$n$个二元组看做$n$个向量。移动方式遵循平行四边形定则。所以两个向量夹角越小,相加形成的和向量模长就越大。所以将这些向量按照极角排序。选择的向量肯定是一个区间。枚举左右端点,求最大值即可。co...…
-
正睿暑期培训day1考试
链接A理解一下题意,然后玩几组样例就能发现,实际上就是$k$个$i$等价于$1$个$i-1$。所以就类似于$k$进制进行进位,如果最后$0$位上不是$0$,那么就存在划分方案。否则就不存在划分方案。输出第一次划分方案就记录一下每个数字是不是后面的数字凑出来的。如果是的话就像后面数字连边。这样就形成了一棵$k$叉树。最后$dfs$一遍输出即可。考场上$vector$下标从1开始记录了。就$wa$惨了。。。/** @Author: wxyww* @Date: 2019-08-04 11:41:...…
-
正睿暑期培训day4考试
链接A求出来到每座山的距离后,就可以计算出每只猫等待的时间与出发时间的关系。如果出发时间为$x$,求出来只猫的等待时间。这里用$b_i$表示第i只猫的等待时间。然后我们将这些时间排序。问题就转化为了,从m个有序的数中,选出p个,每个数字覆盖以其为开头的一段区间。这段区间的贡献为$x\times num-sum$,其中x为当前选定的数字。$num$为覆盖区间的长度。$sum$为覆盖区间的数字和。这样就可以得到一个$m^2p$的朴素dp。$f[i][j]$表示选出i个点,覆盖前j个元素,最小贡...…
-
正睿暑期培训day3考试
链接A可以发现一个小棍的贡献是使得左右两列上的球位置互换。所以只要找出哪两个球会经过当前位置,然后swap一下就行了。。考场上调了2.5h,依然没过样例。赛后发现忘了排序!!!!。。。/** @Author: wxyww* @Date: 2019-08-06 08:19:23* @Last Modified time: 2019-08-06 18:45:46*/#include<cstdio>#include<iostream>#include<cstdlib...…