牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共33篇）

模拟39 题解

A. 工业题手玩样例。然后发现就是到达所求点上面点的方案数乘一下a，b的次方。一个简单的组合数问题。 B. 卡常题一眼费用流，然而只有40分。考后才发现费用流是错的，不会建图。部分分中提示可能形成一个大环。 2n个点，2n条边，如果不是大环会形成什么...

dp 基环树组合计数

2019-09-07

0 364

模拟41 题解

A. 夜莺与玫瑰与题解中的定义类似：枚举每个斜率，设为向量$(a,b)$ 如果$gcd(a,b)!=1$，那么直接跳过。考虑每个点(x,y)，它的前趋为(x-a,y-b)，后继为(x+a,y+b)。一个点是合法的当且仅当不存在前趋，存在后继。于是$ans=\sum \limit...

点分治组合计数线段树

2019-09-10

0 346

模拟43 题解

A. A 发现不断加a，乘b。枚举将s乘k次b，则有 $t=s*b^k+\sum \limits_{i=0}^{k-1}used[i]*a*b^i$ 答案即是使得$\sum \limits_{i=0}^{k-1}used[i]$最小的方案。将s，t表示为b进制会比较好算。当a=1时...

dp 组合计数欧拉函数贪心三分

2019-09-15

0 284

模拟64 题解

A. trade 暴力dp，复杂度$O(n^2)$。然后70分等死。考试快结束的时候，突发奇想。快速改了滚动数组，将第二维的上界设为1000。即只考虑同时存1000个货物，然后突然过了大样例。其实只是想多偷一点分，然后就A了，就非常偷税。所以正解其实是基于堆操作的反悔贪心。...

贪心莫队组合计数并查集

2019-10-08

0 350

模拟66 题解

A. 棋盘打表发现$ans_i=ans_{i-1}*i+[i$&$1]?-1:1$ 然后写高精度就完了。所以这个式子的原型其实是： $ans_i=ans_{i-1}*(i-1)+ans_{i-2}*(i-1)$，其含义可以直接画图理解。对于前一个ans的每一种方案，可...

组合计数 bitset 拓扑排序数位dp

2019-10-09

0 376

模拟69 题解

A. chess 想一下合法方案是怎样的。因为要保证每一个正方形合法，所以新加的一列中棋子个数等于刚刚删去一列的棋子个数。当$m$很大的情况下，$mod\ n$相同的列转移系数都是相同的。接着考虑，其实$m\ mod\ n$列转移了$m/n+1$次，而$n-m\ mod \ n$列转移...

dp 组合计数单调栈莫队离线并查集

2019-10-12

0 304

模拟72 题解

A. 简单的序列将‘（’视作1，‘）’视作-1。那么问题转化为给定中间一段序列，要求前缀和恒不小于0，且权值和等于0的方案数。暴力dp求出i位产生j个左括号剩余的方案数，显然右侧是对称的。然后直接暴力枚举左侧有多少个左括号就完了。需要注意中间一段应当对前缀和不断取min，得出左侧...

dp 结论题组合计数

2019-10-14

0 382

模拟74 题解

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

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

2019-10-15

0 374

模拟76 题解

A. 序列观察部分分，可以得到一些奇怪的构造方法。比如当$N=A*B$，直接将数按$A$的大小或$B$的大小分块就可以了接着打表，发现似乎全部的情况都可以通过类似的方法构造出来。只要对后面的部分分块，前面不足的部分不用分块。 B. 购物奇妙的数的范围很宽泛，达...

构造题 dp 组合计数

2019-10-17

0 297

模拟83 题解

A. 最大异或和异或是不进位加法。具有一个很好的性质：$a\ xor\ b=c$ $\rightarrow$ $c\ xor\ b=a$ 若所有点的异或和为$0$,那么显然平手。若异或和不为$0$,先手只要将最高位的$1$选到必胜。 B. 简单的括号序...

dp 结论题组合计数位运算分块最短路

2019-10-23

0 400