horz

分类

题解(38)

/ 注册

全部文章（共38篇）

选择客栈

分析对于每种颜色单独考虑，从左往右扫，记录最后出现的小于 p 的位置，对于贡献，我们枚举右端点，当记录的位置大于前一次出现的的位置时，更新可用左端点的数量。 #include <bits/stdc++.h> using namespace std; #define mem(a,b) m...

2020-09-03

1 908

Abracadabra

分析我们可以利用递归求解。我们枚举每个串中心，对于一个区间，如果它包含了串中心，我们就把它分解成两个串，另一个区间也这样做，然后就是最多种情况。如果一个区间包含了另一个区间，直接返回小的那个区间的长度。 #include <bits/stdc++.h> using namespac...

2020-09-03

0 737

[SCOI2009]生日礼物

写在前面没给出数据范围，差评。补充一下数据范围：「数据规模」对于50%的数据， N≤10000；对于80%的数据， N≤800000；对于100%的数据，1≤N≤1000000，1≤K≤60，0≤彩珠位置<2^31。分析考虑尺取法，说白了就是双指针。先对 x 排个序，然后利用一个数...

2020-08-14

1 988

2020牛客暑期多校训练营（第三场）

A Clam and Fish 贪心，有鱼的时候肯定是直接抓鱼，没鱼的时候，制作诱饵抓鱼。考虑 1 和 0 出现的次数，0 出现的次数的有效值会小于等于 1 出现的次数，最后再把多余的 1 ，分一半去钓鱼。 code B Classical String Problem 只需要维护好第一个字符所...

2020-08-14

0 624

[SCOI2010]游戏

分析二分图匹配，对于第 i 个装备两个属性 x 和 y ，建立两条边，x -> i ，y -> i 。然后利用匈牙利算法，从 1 开始往后匹配，当匹配不成功的时候就结束。正常的匈牙利算法可能会因为要 memset 很多次可能超时，虽然没有超时，可能数据水或者我理解有问题之类的。然...

2020-08-14

0 1046

2020牛客暑期多校训练营（第二场）

All with Pairs 求其中表示的前缀可以匹配的后缀的最长长度。考虑，先对后缀，求出某个值的后缀有多少个，用存。然后对每个字符串求一个前缀，计算匹配的个数，然后乘以长度的平方。但是有一个问题，有一些部分是重复计算的。比如我们算的时候会把的贡献也算进去，所以...

2020-08-13

1 620

地斗主

题意用的骨牌去填充的矩阵，问有几种方法。分析手算一下前五项，可以得到这么一个序列：1,5，11，36，95 设表示拼完前 i 列的方案数。这时考虑 OEIS 。可以得到递推式：然后利用矩阵快速幂就可以解决了。 #include <bits/stdc++.h> usin...

2020-08-13

0 1239

Mr. Kitayuta, the Treasure Hunter

题意有30000个岛屿，某些岛屿上有一些宝石，第一次跳到了d号岛上，每次跳跃的距离与上一次跳跃的距离之差不超过1，问你最多可以收集多少宝石。分析我们可以定义 dp[i][j] 表示为跳到第 i 个岛屿，且上一次跳跃距离为 j ，那么显然有但是这样做，显然时间和空间都不够。我们可以发现，第...

2020-08-12

0 734

矩阵消除游戏

题意一个矩阵，每次可以消除一行或者一列，问最大可以消除的和是多少。分析由于矩阵比较小，所以我们可以先枚举消去了哪些行，之后贪心的消去剩下的列（也就是选择列的和更大的），可以利用 dfs 实现。 #include <bits/stdc++.h> using namespace std...

2020-08-11

0 927

排座椅

分析显然横向通道和纵向通道的放置是相互独立的，所以我们可以只考虑放一种通道应该怎么放，贪心的放，优先放更多对的地方，可以拆分的对数会更多。 #include <bits/stdc++.h> using namespace std; #define mem(a,b) memset(a,...

2020-08-08

0 556