hairtail

分类

题解(15)

/ 注册

全部文章（共15篇）

2020暑假牛客多校第九场 K The Flee Plan of Groundhog （树形结构/思维）

The Flee Plan of Groundhog 题目大意：有一个土拨鼠在节点1，一个橘子在节点n，在t时刻之前土拨鼠向着n走，橘子不动，从t时刻开始，橘子开始抓土拨鼠，土拨鼠开始跑，土拨鼠 1m/s 橘子 2m/s，问还有多长时间橘子才能抓到土拨鼠。解题思路：t 时刻之后，土拨鼠必然朝着n...

2020-08-08

4 712

2020牛客暑期多校训练营（第八场）Game SET （暴力出奇迹）

Game SET 题目大意：给你n个扑克牌，他有四种属性，每种属性有三个种类，问你有没有可能n个中有三个扑克牌四种属性都相同或者都不同。解题思路：直接暴力跑一下三重for循环就行，虽然最多有256张牌但是只要跑到21个的时候就能判断出答案来了，因为到第21个扑克牌的时候，每个属性不一样的已经都出现...

2020-08-05

0 858

2020暑期牛客多校第八场（K）Kabaleo Lite（前缀和贪心，大数爆longlong__int128）

Kabaleo Lite 题目大意: 有n道菜，每道菜有a[i]的利润，b[i]的数量，然后有一堆人来吃，要满足以下两个条件必须从第一道菜开始吃吃的菜必须连续求最多有多少人来吃，和基于最多人来吃的最大利润和。解题思路：第一问：最多有多少人来吃，这个问题很简单，即第一道菜的数量a[1]就...

2020-08-04

0 910

2020牛客暑期多校训练营（第八场）I题 Interesting Computer Game（离散化+图论dfs）

Interesting Computer Game 题目大意：给出n对 a[i] , b[i] ，每次可以选择一个之前没有选择过的数，问最多能选几个。解题思路：因为每次只能从a[i] b[i]中选一个，可以把a[i]和b[i]用一条线连接起来，只能选择该线左端点或者右端点，然后把n对a[i] b...

2020-08-04

0 631

2020牛客暑期多校训练营（第七场）H-Dividing （数学/分块整除）

Dividing 题目大意：定义(1,k)为传奇元组如果(n,k)是传奇元组的话，(n*k,k)也是传奇元组如果(n,k)是传奇元组的话，(n+k,k)也是传奇元组解题思路：题意第二条可以转换一下，因为n只能加k或者乘k，而n起始为1，所以n一定为k的倍数或者n%k==1,即(n+...

2020-08-01

3 723

牛客国庆集训派对Day6 A-Birthday （最小费用最大流）

牛客国庆集训派对Day6 A-Birthday （最小费用最大流）题目大意：宇扬在蛋糕上插了 n (1<=n<=50)支蜡烛，并把蛋糕分为 m (2<=m<=50)个区域。因为某种原因，他必须把第i根蜡烛插在第ai个区域或第bi个区域。区域之间是不相交的。宇扬在一个区...

2020-07-31

0 791

[CQOI2007]涂色PAINT （区间dp）

题目大意：给出目标字符串，然后从空串开始涂色，每次可以任意选择一个区间涂，问最少次数。解题思路：区间dp问题，开一个二维dp数组，dp[i][j] 代表区间从 i 到 j 最小染色次数，可分为两种情况。如果区间两端颜色相同 s[i]==s[j] 的话，dp[i][j]=min(dp[i][j...

2020-07-30

0 732

wpy的请求（spfa变形求负权通路）

wpy的请求 spfa变形题目大意：给一个n个点，m条边的有向图，可能有负权边，现在要把负边权都变成非负，并且使得原图中的任意两点u,v最短路经过路径不变并且使得原图中的任意两点u,v最短路经过路径不变解题思路：解法就是建立一个超级原点（也就是0节点），与所有点相连，且边权值为0，然后跑一遍sp...

2020-07-30

0 802

2020牛客暑假多校第三场 C Operation Love （计算几何/叉积确定直线位置）

Operation Love 题目链接：链接题目大意：给出爱丽丝的右手，由二十个点组成，已知她的左手和右手对称，然后给出二十个点，问这些点组成的手是左手还是右手。思路：计算长度为 6 和 9 这两个向量的叉积，如果相乘为正数，则为逆时针，为右手，反之是左手。如图，将长度为6的向量平移之...

2020-07-22

0 610

2020牛客暑假多校第二场 B Boundary (数学/map+三点共圆圆心公式)

题目大意：二维平面坐标系，给出很多无序的点，然后求出一个必过（0，0）点且边界上点最多的一个圆。思路：因为平面中三点确定一个圆，所以可以枚举两个点，用这两个点和原点确定圆心，这两点和原点不能关于原点对称-->否则圆心就是原点了，不在圆边界上，mp[圆心]++，然后最大值即为答案（要+1因...

2020-07-21

0 565