牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共241篇）

模拟70 题解

A. 木板相似三角形，简单推出结论。发现要求的是$\sum \limits_{i=1}^{n-1}[n|i*i]$。那么只要把$n$质因数分解，设为$\prod_{j}^{} p_j^{c_j}$，那么设$k$为最小的合法的$i$，有$k=\prod_{j}^{} p_j^{\l...

数学 dp 构造题搜索

2019-10-13

0 301

模拟69 题解

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

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

2019-10-12

0 304

模拟68 题解

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

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

2019-10-11

0 401

模拟67 题解

A. 神炎皇尝试枚举$a$,$b$的$gcd$，设为$d$。那么有$$ans=\sum \limits_{d=1}^{n} \sum \limits_{i=1}^{n} \sum \limits_{j=1}^{n} [gcd(i,j)==d][i+j<=n][i+j|i=j]$$ ...

dp 数学树状数组

2019-10-10

0 385

模拟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

模拟65 题解

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

贪心直径数学

2019-10-09

0 750

模拟64 题解

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

贪心莫队组合计数并查集

2019-10-08

0 350

zkw线段树学习笔记

ZKW线段树应某迪要求，写一篇数据结构学习笔记。实际上还没有学很多东西，只是一些基础的操作。 zkw线段树的学习资料，网上有很多，这里记录的只是自己的一些理解。建树 1 inline void build(){ 2 for(bit=1,n=read();bi...

线段树

2019-10-07

0 421

模拟63 题解

A. Median 线性筛完质数，就会发现给的时间已经快没了。所以只能$O(n)$求$n-k$个中位数？不会做，所以打权值线段树。在权值线段树上二分找第k大值，可以做到$O(nlogn)$。打$zkw$线段树，比传统线段树快一倍，然而并没有什么用，仍然T70。题中确实给出了一些...

dp 桶贪心

2019-10-07

0 407

模拟62 题解

A. Graph 在树的情况下，答案是显然的。一次dfs，尽量将子树内不同的边合并就可以了。考虑非树的情况，可以生成一棵树。将非树边任意加在一个端点上，视作点权加一。对于树上的每一个点，先考虑它的子节点，子节点的父边尽量在子节点处作连接节点使用。如果子节点的父边还没有被使用，那...

线段树结论题贪心最小生成树拓扑排序

2019-10-06

0 365