回归梦想

题解

dfs(2) leetcode(3) PTA(5) python(1) 一起开心(1) 后缀数组(2) 图论(4) 多校(4) 天梯赛(8) 字符串(8) 数据结构(1) 未归档(539) 模板(4) 每日一题(56) 点分治(2) 牛客题霸(117) 知识(4) 算法(76) 经验分享(2) 网络流24(11) 莫比乌斯反演(2) 队列(2)

/ 注册

全部文章 / 题解（共25篇）

1414. 牛异或来自专栏

题意：区间长度为n的数组a，取连续一段子序列，问哪段子序列的异或和最大，如果存在多个这样的序列，那么选择序列末端整数对应的编号更小的那个序列。如果仍然存在多个可选的序列，那么选择长度最短的那个序列。题解： 01字典树模板题简单说一下，我们每次是将异或值的前缀和sum存在树中对于每次插入第j个su...

** 01字典树

2021-01-30

0 591

Codeforces Round #694 Div. 2 来自专栏

Codeforces Round #694 Div. 2CodeForces 1471A Strange PartitionCodeForces 1471B Strange ListCodeForces 1471C Strange Birthday Party签到有难度Code...

** 比赛

2021-01-29

0 571

Strange Housing CodeForces - 1471F 来自专栏

题意：有 n 个点和 m 条边，对点进行染色。要求一条边的两个点不能都染色，并且删除两端都没有染色的边之后，图连通。请给出一种染色方案。题解：第一反应就是01染色，但是题目是有可能存在奇环的，那怎么办？01染色是保证1和1,0和0都不能相邻，如果把1当做染色，根据本题，0是可以相邻的，那我们...

** 图论

2021-01-29

0 616

Strange Shuffle CodeForces - 1471E（交互题）来自专栏

交互题这类型不同于普通的题。可以理解为有个问题需要你解决，你通过输入某些东西表示你要问系统的问题，这时系统会回答你的问题。在代码中的回答方式就是会输入某个东西就是系统给你的答案，通过这些信息你可以得到问题的解你是不可以自己测试的，只能提交给系统测试。有个东西需要用到C++中的fflush(stdo...

** 交互题思维

2021-01-29

0 583

加分二叉树来自专栏

题目描述设一个n个节点的二叉树tree的中序遍历为（1,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第i个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下： subt...

** dp

2021-01-29

0 787

Xor Transformation 来自专栏

题目：给定一个X和Y，对于X每次可以选择一个A（0<=A<X），使得X = X xor A，现在要求在5步内将X变为Y，请输出操作数目，以及每步的A 题解：我一开始被题目给的样例个迷惑了，以为将Y分解开，然后再加一步X就可以了，但发现想复杂了对于W = (X ^ Y)，也就是W，X，...

** 思维

2021-01-24

0 709

Stone Game 来自专栏

题意：有n堆石头，每堆石头最多只有三个石头（最少1个），每两堆石头（这两堆各含石头x个和y个）合一起的费用为(x mod 3) * (y mod 3)，现在把所有堆合成一堆，问最小费用题目第一行给出三个数，第i个数表示有i个石头的堆有多少个题解：费用是(x mod 3) * (y mod 3)...

** 思维题 icpc2020济南

2021-01-24

0 993

[USACO09FEB]Revamping Trails G

题意：约翰一共有 N 个牧场.由 MM 条布满尘埃的小径连接。小径可以双向通行。每天早上约翰从牧场 1 出发到牧场 N 去给奶牛检查身体。通过每条小径都需要消耗一定的时间。约翰打算升级其中 K 条小径，使之成为高速公路。在高速公路上的通行几乎是瞬间完成的，所以高速公路的通行时间为 0。请帮助约...

** 分层图

2021-01-18

0 780

NC51307 Redundant Paths

NC51307 Redundant Paths 题目： • 给定无向连通图，求至少需要添加几条边使它变成一个边双连通图。（添多少边可以消灭所有的桥）题解：先用边双连通缩点• 缩点之后是一棵树• 无根树的叶子（度数为1的点）都需要再添一条边，叶子节点两两连接• 答案是是（叶子数+1）/2 代码：...

** tarjan 缩点

2021-01-14

0 535

NC106972 Cow Ski Area

NC106972 Cow Ski Area 题目： • N*M的滑雪场，每个点都有他的高度，滑雪的时候只能向四周相邻的不高于当前点的高度的点滑，现在滑雪场准备修建若干个缆车线路，使得奶牛可以从任意一个点运动到滑雪场的每个点，问最少需要建多少条缆车线路。题解：本质还是有向图，通过加边使其强连通• ...

** tarjan 缩点

2021-01-14

0 586