sunrise__sunrise

题解

未归档(12) 读书笔记(1)

/ 注册

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

2021牛客暑期多校训练营8 D、OR 来自专栏

题目大意你原本有个长度为的序列，现在我只告诉你两个长度为的序列，问合理的序列有多少种？我们定义。 Solution 由于给出的数组都是位运算得来的，我们就可以按位拆分，枚举的每一位，再去枚举不同的数。我们首先看最低位，注意下面的代表着当前枚举的这一位二进制是还是，同理，映射到题目就是：如果在...

位运算

2021-08-27

1 627

2021牛客暑期多校训练营7 来自专栏

B、xay loves monotonicity 题目大意初始你有两个长度为的序列。序列满足下面的要求：。接下来你有三种操作：把赋值成。把这一段区间全部按位取反，即互换。求在这个区间中必选构成的最长不下降子序列，假设为，那么我们取出构成一个串，这个串中有多少个交接处就是这个区间的答案，你...

2021暑假多校训练营

2021-08-26

0 691

2021牛客暑期多校训练营7 xay loves Floyd 来自专栏

题目大意有人把写成下面这样，请问这张有向图还有多少个是正确的？点数，边数，边权 for i from 1 to n for j from 1 to n for k from 1 to n dis[i][j] <- min(dis[i][j], dis[i][k] +...

Floyd

2021-08-26

0 619

2021牛客暑期多校训练营7 F、xay loves trees 来自专栏

题目大意给出棵以为根的树，你要在第一棵树上选择若干个点，并且在第二棵树上选择相同编号的点。现在要求你在第一棵树上选择的点，把他们连接的边全部找出来必须构成一条链；并且你在第二棵树上选择的点，不能存在任何两个点他们之间有祖先关系，换句话说就是某个点选了，它全部的子树节点都不能选了。现在要你输出...

线段树时间戳

2021-08-25

0 712

2021牛客暑期多校训练营7 B、xay loves monotonicity 来自专栏

题目大意初始你有两个长度为的序列。序列满足下面的要求：。接下来你有三种操作：把赋值成。把这一段区间全部按位取反，即互换。求在这个区间中必选构成的最长不下降子序列，假设为，那么我们取出构成一个串，这个串中有多少个交接处就是这个区间的答案，你需要回答这样的操作答案是多少？操作最多有个。 ...

线段树区间合并

2021-08-25

1 620

2021牛客暑期多校训练营6 来自专栏

C、Delete Edges 题目大意你有一张个点的无向完全图，你需要删掉一些边，让这张图里面边数小于点数，输出你删除边的方案。 Solution 结论构造题官方给的证明非常长…直接说结论了，输出全部以及的不同点对。值得注意的是在点对中我们必须保证在三元组中任选两个元素构成的二元组出现了两次。 ...

2021暑假多校训练营

2021-08-25

1 774

2021牛客暑期多校训练营6 J、Defend Your Country 来自专栏

题目大意你有一张个点条边的无向联通图，现在对于图中的连通分量产生的价值做出如下定义。如果一个联通分量里面点的个数是偶数那么它的价值就是里面每个点权的和。如果一个连通分量里面点的个数是奇数那么他的价值就是里面每个点权的和的相反数。保证每个点的点权。你现在可以选择一个点把它删去，并且它连的边也...

tarjan

2021-08-25

0 817

2021牛客暑期多校训练营6 H、Hopping Rabbit 来自专栏

题目大意小兔子在一个二维的格点图中跳跃，每次它都会沿着正负方向共个方向移动个单位长度。现在地图中有个陷阱，陷阱是以矩阵的方式存在的，问你有没有一种方法让小兔子在某个起点随意乱跳的情况下都不会掉入任何一个陷阱，你要输出这个起点，或者。 Solution 考点：线段树维护扫描线首先由于地图本质上是...

线段树扫描线

2021-08-24

0 606

2021牛客暑期多校训练营6 F、Hamburger Steak 来自专栏

题目大意你有个汉堡代煎，每个汉堡要被煎制分钟，你现在只有口锅，每个汉堡可以分两次煎制也可以一次煎完。问完成块汉堡全部的煎制最小的完成时间是多少？ Solution 考点：思维题因为你只有口锅，并且所有汉堡需要煎制的时间也给你了，那么你就可以知道对于工作时间最长的一口锅而言，它需要工作的最长时间。...

模拟

2021-08-24

0 546

2021牛客暑期多校训练营5 来自专栏

B、Boxes 题目大意你有个盒子，每个盒子内存在可能有黑球和白球中的一种，打开每个盒子都有一个代价，你还有一次询问裁判的机会，当然询问裁判代价为，你需要告诉裁判这个盒子每个盒子里面的球颜色，你需要花费的最小代价是多少？ Solution 考点：思维首先我们不询问裁判的话，我们就要把个盒子全部打...

2021暑假多校训练营

2021-08-23

0 632