- 博客(20)
- 收藏
- 关注
RSS订阅原创 同余最短路
共有n种糖豆，有k种颜色，第i种糖豆颜色是ki，重量是mi，价格ci。现在要去购买糖豆，购买的糖豆需要包含所有k种颜色，且每种颜色购买的数量相同。问对于在区间0m−1的每个整数r，满足购买的糖豆总重量对m取模为r的购买方案中最小花费是多少？如果不存在满足条件的购买方案，则输出−1。
2024-11-29 09:31:02
1041
原创 [✗✓OI R1] 左方之地
给你一个自然数n和一个自然数参数k，你需要构造一个长度为2n的序列a，满足02n间的所有整数恰好出现一次，并且∀i∈22npopcountai⊕ai−1k。其中popcountx表示x在二进制下1的个数，⊕表示按位异或运算。若有解则输出1并输出这个序列，否则输出0。
2024-11-28 14:33:43
772
原创 Colors and Intervals
n×k个格子，编号从1到n×k，染成n种颜色，每种颜色恰好k个。构造n个区间，第i个区间aibi满足1≤aibi≤n×kaibii⌈k−1n⌉。
2024-11-26 15:28:25
1213
原创 树上可修改式背包
给出一棵n个点以1为根的有根树，第i个点的父亲为fi，每个点上有点权ai。你需要维护m次操作，操作分为两种：格式为1xy，表示令ax⟵y。格式为2xy，查询在点x的邻居中选出一个集合S，满足i∈S∑aiy的方案数对998244353取余的结果。对于100%的数据，1≤nqaiy≤4×1031≤x≤n。
2024-11-25 15:18:43
675
原创 关于在矩阵中枚举点的 dp
第一个方程表示将矩阵拓展一行一列，由于新的一行一列是空列，有四个方向，我们只考虑向下拓展行，而可以在任意位置拓展列，在行列交点处放一个点，由于行列上没有其他点，故有四个方向；第二个方程表示拓展两行一列，每行放置一个，让两个格子的方向相对，使那个列填满，其中一行必然在最底下，而另一行则可以选择位置插入；第二个方程表示，选择一个空列，令点的方向向下，形成一个半列；放了一个，可以朝四个方向。在矩阵中放一个点，每个点所在的行与列至多有一个别的点，且若有点，两个点的方向要相对，而若无点，则可任意指向四个方向。
2024-11-23 14:57:36
1370
原创 Colors and Intervals
n×k个格子，编号从1到n×k，染成n种颜色，每种颜色恰好k个。构造n个区间，第i个区间aibi满足1≤aibi≤n×kaibii⌈k−1n⌉。
2024-11-22 08:41:35
1232
原创 三种排列 dp 的比较
有一个长为N的正整数排列。给定一个由和组成长为N−1的的字符串。对于任意满足1≤i≤N−1的字符si，如果si是则PiPi1、如果si是则PiPi1。求满足这样的性质的排列P的方案数。令dpij表示到第i个位置，前面一个数是排列数中第j大的方案数。
2024-11-21 14:31:22
885
原创 [JOISC2022] 洒水器
JOI 君有多年在自家菜园种植蔬菜的经验，现在他计划管理 IOI 农场。IOI 农场由N块土地组成。土地间有N−1条双向道路相连，编号从1到N−1，第i条道路连接土地Ai和Bi，任意两块土地间都可以通过道路互达。农场的每块土地上都有一个洒水器，使用洒水器可以向附近的土地洒水。JOI 君计划在 IOI 农场种植 JOI 谷。JOI 谷是一种奇特的作物，它在被浇水时高度会立刻发生变化。但是同时，JOI 谷是一种脆弱的植物，若它的高度大于等于L，JOI 谷顶部长为L。
2024-11-19 14:47:49
970
原创 矩阵快速幂加速最短路
对于【无环】一栏为“是”的测试点，保证给出的图是一张有向无环图，否则不对图的形态做任何保证。次魔法，使得通过下一条道路时，需要的费用变为原来的相反数，即费用从。注意：使用魔法只是改变一次的花费，而不改变一条道路自身的。最终的费用可以为负，并且一个城市可以经过多次（包括。输入的第一行有三个整数，分别代表城市数。首先有70分的做法，即使用动态规划。表示从i到j使用k次魔法时的最短路。条有向道路组成，城市与道路都从。表示边的两端，g[i].w表示边权。的单向道路，经过它需要花费。刚好为k，表示魔法的使用次数。
2024-11-18 17:52:40
896
原创 状态压缩、预处理
给定正整数N，和两个长为N的01序列a和b。b0110b1ab1bb1b2⋯bnbnb1b2⋯bn−1有T次询问，对每一次询问，你需要回答出至少需要几次操作，才能使a序列中每一个位置的值都变为0。
2024-11-16 15:55:01
823
原创 线段树优化dp
你说得对，但是小∭在打 CF 时将 Earn or Unlock 错看成了下面的鬼畜样子，痛失 2h 遗憾离场，希望大家引以为戒。
2024-11-15 14:33:43
1315
原创 倍增求解最短路
农民约翰有N2≤N≤2⋅105台拖拉机, 其中第i台拖拉机只能在序列liri内使用。拖拉机有左端点l1l2⋯lN和右端点r1r2⋯rN. 有一些拖拉机是特别的。如果liri和ljrj相交，则两台拖拉机i和j是相邻的。约翰可以从一辆拖拉机转移到任何相邻的拖拉机上。两台拖拉机a和b之间的路径由一个传输序列组成，这样序列中的第一个拖拉机是a，序列中的最后一个拖拉机是b。
2024-11-14 09:44:42
666
原创 倒序处理、并查集
Farmer John 经营着总共N个农场（1≤N≤105），编号为1N。最初，这些农场之间没有道路连接，并且每个农场都在活跃地生产牛奶。由于经济的动态性，Farmer John 需要根据Q次更新操作（0≤Q≤2⋅105）对他的农场进行改造。(D x)停用一个活跃的农场x，使其不再生产牛奶。(A x y)在两个活跃的农场x和y之间添加一条道路。(R e)删除之前添加的第e条道路（e1是添加的第一条道路）。一个农场x。
2024-11-13 12:11:55
683
原创 寻找两条最短路的公共路径
最近，Elaxia 和 w** 的关系特别好，他们很想整天在一起，但是大学的学习太紧张了，他们必须合理地安排两个人在一起的时间。Elaxia 和 w** 每天都要奔波于宿舍和实验室之间，他们 希望在节约时间的前提下，一起走的时间尽可能的长。现在已知的是 Elaxia 和 w** 所在的宿舍和实验室的编号以及学校的地图：地图上有n个路口，m条路，经过每条路都需要一定的时间。具体地说，就是要求无向图中，两对点间最短路的最长公共路径。
2024-11-11 14:55:09
464
原创 CF1968F
对于每个查询，如果子数组是有趣的，输出 “YES”；否则输出 “NO”。时间求区间异或值，我们可以设一个前缀异或数组。通过这一道题，可以更家深刻地理解异或的性质。的范围过大，无法直接存下，可以建一个。个部分，使得每个部分的异或和都相等。）——数组中的元素数量和查询的数量。每个测试用例的第一行包含两个整数。有意思，当且仅当它可以被分成。中，再用二分寻找满足条件的。由上述的可得，仅需要判断在。时是否可行，就能得到答案。行，每行包含两个整数。的奇偶性进行分类讨论。时是好求的，来看一下。）——测试用例的数量。
2024-11-08 13:35:54
846
原创 NOIP常用模板整理
模板数学数论快速幂时间复杂度 Θ(logb)\Theta(\log b)Θ(logb)long long ksm(long long a,long long b){ long long res=1; while(b){ if(b&1) res=res*a%mod; b>>=1; a=a*a%mod; } return res;}素数埃式筛时间复杂度 Θ(nloglogn)\Theta(n\log\log n)Θ(nloglogn)const
2024-11-07 10:33:39
1053
原创 可撤销并查集
由于现在已经来到了魔幻的龙年，帆帆的深蓝之树已经被染上了颜色，结点i的颜色为ai。帆帆是一个喜新厌旧的人，在接下来的q天中，他每天都会改变他喜欢的颜色，第i天他喜欢的两种颜色是xiyixiyi但是为了照顾自己的树，他需要经常在树上移动，并且只会经过自己喜欢的颜色。具体来说，第i天，帆帆会选择一个有序结点对uv，然后沿着u→v的唯一简单路径移动，并且中间经过的结点（包含uv）颜色必须∈xiyiu可以等于v。
2024-11-07 10:30:45
1231
原创 分层图求最短路
在这个繁忙的社会中，我们往往不再去选择最短的道路，而是选择最快的路线。开车时每条道路的限速成为最关键的问题。不幸的是，有一些限速的标志丢失了，因此你无法得知应该开多快。一种可以辩解的解决方案是，按照原来的速度行驶。你的任务是计算两地间的最快路线。每条道路是有向的，只连接了两条道路，并且最多只有一块限速标志，位于路的起点。当然，你的车速不能超过当前的速度限制。输出的顺序必须按照你经过这些城市的顺序，以。是你到达该路口前的速度。的最短路的上一个点。），表示道路的数目，用。，表示这条路的限速未知。
2024-11-04 20:10:15
556
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人