Rewinner

未归档

ACM(1) dfsdd(1) DP(6) hash(1) STL(1) 图论(24) 小技巧(4) 思维(6) 搜索(2) 数学(5) 数据结构(16)

/ 注册

全部文章 / 未归档（共69篇）

[SCOI2016] 美味【可持久化线段树+位运算】

传送门题目描述：一家餐厅有 n 道菜，编号 1...n ，大家对第 i 道菜的评价值为 ai(1<=i<=n)。有 m 位顾客，第 i 位顾客的期望值为 bi，而他的偏好值为 xi 。因此，第 i 位顾客认为第 j 道菜的美味度为 bi XOR (aj+xi)，XOR 表示异...

2019-04-30

0 492

[CQOI2015]任务查询系统【可持久化线段树+差分】

传送门最开始思路都想到差分了，但是没有继续想下去。解题思路：利用差分来解决区间的问题，因为最多有 1e5 个任务，所以最多有 2e5 次修改，利用时间戳来建树，首先让新建的这棵树等于上一颗树，如果这次没有修改操作，就跳过，否则就在这一棵树上进行修改。坑点：在进行询问时，如果碰到递归终点，不能返回...

2019-04-29

0 482

美味佳肴【思维+可持久化线段树】

传送门题目描述：众所周知，天才程序员菜哭武是一个伟大的厨师。这天，张老师和石头来到菜哭武家做客，想尝一尝菜哭武的手艺。菜哭武手上有n种食材，每种食材个数无限多，编号为i的食材有一个美味度ai。一道菜中，每种编号的食材至多有一个，而这道菜的美味度是这道菜包含的食材的美味度之和。每次张...

2019-04-23

0 437

Minieye杯 Mex【思维】

传送门题目描述：给你一个大小为 n 的数组，问你这个数组里面不能组成的数中，最小的一个是什么？解释说明：输入: 3 1 2 5 输出： 4 样例说明： S'=(), ∑S'=0 S'=(1), ∑S'=1 S'=(2), ∑S'=2 S'=(1,2), ∑S'=3 ...

2019-04-23

0 533

牛客Wannafly挑战赛4 树的距离【DFS序+可持久化线段树】

传送门题目描述： wyf非常喜欢树。一棵有根数树上有N个节点，1号点是他的根，每条边都有一个距离，而wyf是个爱问奇怪问题的熊孩子，他想知道对于某个点x,以x为根的子树上，所有与x距离大于等于k的点与x的距离之和。输入描述: 第一行一个正整数N 接下来N-1描述这棵树，每行两个数第i行...

2019-04-22

0 491

Chino with Rewrite 【树链剖分+并查集+状压线段树】

传送门中文题面就不在阐述解题思路：题目上的操作2 对一棵树的一条链进行操作，很容易想到树链剖分。由操作1给的叙述，我们能够想到并查集离线建树。要求一个链上知识点种类的数量，而且 wi 不超过60，利用状压来解决。 ///#include<bits/stdc++.h> /...

2019-04-21

0 584

Power OJ 2853 小Z的糖果店【树的中心+DP+优先队列】

传送门思路：要求找一个最小Gg值，当 K = 1 时，我们知道这个点一定在直径上面，要使 Gg 最小，则该点到直径的两个端点距离的最大值最小。 DFS求直径：随意找一个点为起点，距离这个点最远的点就是直径的一个端点S，然后在以S为起点DFS，距离S距离最远的点就是直径的另一个端点E。我们要记录...

2019-04-20

0 487

牛客练习赛44 小y的线段【思维】

传送门题目描述：给出n条线段，第i条线段的长度为 ai ，每次可以从第 i 条线段的j位置跳到第 i + 1 条线段的 j+1 位置。如果第 i+1 条线段长度不到j+1，那么就会回到第 i 条线段的 0 位置，然后继续跳。问从第 i 条线段的 0 位置跳到第 n 条线段需要跳多少次。解题...

2019-04-20

0 442

1154F Shovels Shop【DP】

传送门题意：商店里面有 n 把铲子，商店里有m中优惠方式（可以重复利用优惠方式），要你刚好买 k 把铲子的最小花费。优惠政策：给你一对（x，y），如果你购买了 x 把铲子，那么将 x 把中 y 把最便宜的斧头送给你，即免费。思路：题目上给的 k 的范围 k<=min ( n , 2000...

2019-04-18

0 498

1154G Minimum Possible LCM 【埃氏筛法枚举公约数】

传送门题意：求个数中最小公倍数数值最小的两个数的下标。参考博客：https://blog.csdn.net/qq_41157137/article/details/89353527思路：对于包含...

2019-04-18

0 405