牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共26篇）

模拟65 题解

A. Simple 首先求出n,m的gcd，那么显然只有gcd的倍数可能被拼出，其他数一定是不好的数。所以问题转化为用$\frac{n}{gcd}$,$\frac{m}{gcd}$，拼不出的$\frac{q}{gcd}$范围内的数。因为除gcd后的n，m互质，用某凯的疑惑中的结论可知最...

贪心直径数学

2019-10-09

0 750

模拟68 题解

考试过程大概是：上来看T1，看懂了题但是丝毫没有思路，甚至没有想到第一步贪心，心态稍崩。接着看T2，发现似乎可以直接上主席树上树，然后想了想复杂度，直接找前趋后继，复杂度似乎很正确。 T3只会暴力。然后就回去把T2切了，一遍过大样例自信不对拍。结果忘了在线这回事，一个小时之后才发现...

trie树主席树贪心位运算二分答案

2019-10-11

0 401

模拟74 题解

A. 梦境已经做过很多类似的套路题。都是排序后贪心就完了。将所有的区间以右端点排序，因为每个区间对答案贡献相同为1，区间右端点不断增加，那么显然可以直接取尽量靠左的点。用$multiset$维护一下点，支持后继操作就可以了。因为题中有相同的点，用$set$必死。 ...

dp 贪心组合计数 set 图论树状数组

2019-10-15

0 374

模拟85 题解

A. 表达式密码观察样例，发现答案就是将减法拆为一个减法和多个加法，于是就完了。 B. 电压机制发现问题是认为一条边相邻的两个点颜色相同并不考虑这条边，问图能否二分图染色。暴力做法是$O(nm)$的。仔细想想就可以发现：对于奇环，不能二分图染色，所以必须选择奇...

二分图 tarjan 贪心

2019-10-25

0 697

模拟95 题解

A. 简单计算发现向下整除会损失一些贡献，然后就无法直接用等差数列考虑。如果不计损失，那么答案是一个等差数列求和。可以考虑损失的是什么，即$\sum \limits_{i=1}^{p}i*q\ mod\ p$。这个式子就很好，不妨设$gcd(p,q)=1$，因为$gcd$不为1的情况...

贪心桶

2019-10-31

0 338

模拟99 题解

A. 陶陶摘苹果一眼线段树维护单调栈，所以写就完了。当然本题中修改不继承，所以有更好的一个$log$的做法。 B. 开心的金明贪心地选择当前最优的策略。用一个$set$维护备选的集合。当跨月的时候，如果集合中元素个数大于限制数，可以不断去除最劣的选择。 ...

set 贪心线段树单调栈构造题

2019-11-04

0 359

模拟103 题解

A. Game $yxs$大神教你转化题意：将B哥的牌视作左括号，小A的牌视作右括号。那么问题转化为最多匹配多少个括号，并求出最大字典序的一组解。如果不需要最大字典序，问题是简单的贪心，每次取出最小的右括号尝试匹配。考虑一个暴力做法：对于B哥的每一张牌，做$nlogn$的...

启发式合并分治线段树贪心差分树状数组

2019-11-07

0 394

模拟109 题解

A. Adore 似乎是显然的状压。 $dp_{i,S}$表示第$i$层，其中每个点到达终点路径条数的奇偶性为$S$的方案数。直接用位运算转移，复杂度是$O(m*k*2^k)$，然后卡卡常（把$k$循环展开）就过了。似乎考虑单次的变化量，可以继续消掉一个$k$，然后就好了。 ...

贪心 bitset 状压 dp

2019-11-11

0 437

CSP-S 2019 题解

D1T1-格雷码题中给出了构造格雷码的方法。 $solve(n,k)$表示求出$2^n$意义下排名为$k$的格雷码，只要比较一下考虑最高位的0/1取值就好了。部分分提示了要开$unsigned\ long\ long$，注意一下就可以了。 D1T2-括号树子序列...

倍增单调队列 dp 并查集贪心

2019-12-02

0 477

省选模拟5 题解

A. 青蛙因为每个青蛙都可以一步跳到终点。所以二分几个青蛙可以无消耗跳到终点，只要让最贵的几个青蛙跳过去。之后特判一下一个青蛙都跳不过去的情况就好了。 B. 一起自习的日子伯努利数练习题。不断的把自然数幂和用伯努利数展开，顺便二项式展开一下就好了。另外分析可知原式可以...

贪心主席树 lct 二分答案伯努利数后缀自动机

2020-01-12

0 418