NOI2017

提供一个来自 CF 大佬 adament 的有趣思路。 首先我们知道的是一个只增加的 \(b\) 进制整数计数器，如果 \(b\) 是常数那么复杂度是均摊 \(O(1)\) 的。证明只需要考虑将 \(b\) 进制中为 \(b-1\) 的所有位的位数当...

提供一个来自 CF 大佬 adament 的有趣思路。 首先我们知道的是一个只增加的 \(b\) 进制整数计数器，如果 \(b\) 是常数那么复杂度是均摊 \(O(1)\) 的。证明只需要考虑将 \(b\) 进制中为 \(b-1\) 的所有位的位数当...

分析： 30+暴力应该还是蛮水的，可以随便写写... 60+的就没那么容易了，但是应该挺裸的，往上架一颗线段树，查询连续1或0的长度，或者找到前缀中，第一个1或0，之后区间覆盖，单点查询，开bool，完全可做，手动模...

NOI2017 整数 题意： ​ 让你实现两个操作： 1 \(a\) \(b\)：将\(x\)加上整数\(a \cdot 2 ^ b\)，其中 \(a\)为一个整数，\(b\)为一个非负整数 2 \(k\)：询问 \(x\)在用二进制表示时，位权为\(2 ^ k\)的位的值（即...

[NOI2017]整数 题目大意： \(n(n\le10^6)\)次操作维护一个长度为\(30n\)的二进制整数\(x\)，支持以下两种操作： 将这个整数加上\(a\cdot2^b(|a|\le10^9,b\le30)\)。 询问这个整数第\(k\)位的值。 题目保证任何时...

原题链接 发现 k<=50 ，在插入和删除时最多会影响不超过 k2 个串，用链表实现插入和删除,然后只需用哈希表维护每个长度不超过k的串的出现次数，哈希的话可以先用比较大的范围的值处理冲突，再映射到1e8的桶里...

题目链接 \(S=k\)可以拆成\(S\le k\)减去\(S\le k-1\)。用\((i,j)\)表示第i行第j列。 设\(g(i,j)\)表示前i行前j列都安全其他未知满足条件的概率，\(h(i,j)\)表示前i行前j列是安全的但是\((i+1,j)\)是危险的，其他...

人生第一道Ynoi，开心 Description https://www.luogu.com.cn/problem/P5607 Solution 拿到这个题，看了一下，发现询问要求最大异或和，怎么办？ 没办法，我只学过线性基，就顺着这个思路硬上吧。 我们开一颗线段...