前言 赛中一位同学过了L没过K，这位同学的代码wa在了K的小数据，但由于牛客塞不下那么多组数据，那组数据没加在L和M中，出题人为此谢罪（悲）。过会儿会在L和M中放那组小数据。 然后请大家锐评一下本场比赛与题目，问卷链接：https://www.wjx.cn/vm/OowqS3N.aspx# 难度情况 出题时预估的难度： 通过率 (过题人数/有提交人数:4526) 预测情况： 主要偏差大的是：BIJK B：主要是题意有一些不清，以及可能萌新对循环没那么上手(?) IJ：似乎很多同学都被无向图和完全图的概念卡了，题目本身难度不大 K：前排大佬想直接冲LM，后排在跟榜，导致中后期才被大家发觉K不难...

【题解】牛客小白月赛68 A. Tokitsukaze and New Operation 直接模拟即可。 代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=61169745 B. Tokitsukaze and Order Food Delivery 直接模拟即可。 代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=61169766 C. Tokitsukaze and Average of Substring 枚举区间的...

题解写的比较匆忙，有误请指出。 2023.01.19 UPD：更新E题证明与三分反例，感谢这几位群友，以及提出疑问的群友：恶魔妹妹。 2023.01.25 UPD：更新一个牛客能跑4e10的证据。 这个提交在polygon不管用哪个版本的cpp都是TLE的，后台有n,q都大于1e5的数据。提交中的a数组把bool改成int会TLE，猜测是牛客神机把bool当成bitset，复杂度是nq/64，大概6e8，由于for里只有一个赋值语句，常数极小，所以跑的飞快。 https://ac.nowcoder.com/acm/contest/view-submission?submissionId=605...

A. tokitsukaze and Connection tag：模拟 为字母第一次出现的下标，为字母最后一次出现的下标，为字母总共出现的次数。那么对于所有出现过的字母，判断他们是否都满足即可。时间复杂度为。 B. tokitsukaze and Hash Table tag：模拟，并查集，STL 解法一：用并查集维护空位。在位置插入一个数后，合并和即可。要注意，合并的时候，必须当爹，才能达到维护的效果。 解法二：用set维护所有空位，每次lower_bound找到第一个可用空位即可。(可能会卡常) C. tokitsukaze and Soldier tag：贪心 按从大到小排序。用一个小...

http://tokitsukaze.live/2018/08/16/2018niuke9.A/ 题解： 观察样例感觉是个卷积，然后发现是个xor的FWT。 题意转换成，给个a数组和c数组，求一个b数组，使得a数组和b数组做FWT后的结果为c数组。 然后观察FWT的过程：对a，b数组做FWT，c[i]=a[i]*b[i]，然后对c数组做UFWT。 我们把这个过程倒过来：先对c数组做UFWT，然后对a数组做FWT，然后b[i]=c[i]/a[i]，最后对b数组做FWT，就把b数组还原了。 代码： #include...

http://tokitsukaze.live/2018/08/04/2018niuke6.I/ 题意： 给n个列车和m个爆破点。每个列车有一个运行区间[L,R]。 刚开始，所有列车都在运行。 每次爆破一个点后输出有多少运行中的列车因为这次爆破而停止运行。然后那些列车就停止运行了。 最后输出每个列车是因为第几次爆破而停止运行的。 爆破点是加密的，所以强制在线。 题解： 先把L从小到大离散化一下，然后开2e5个set存每个R和列车的id，注意R是要求从大到小存。 然后每次爆破，暴力遍历每个set，遇到满足的就记...

http://tokitsukaze.live/2018/07/27/2018niuke3.I/ 题意： 给一个三角形，让你在三角形内随机选n个点，问这n个点在凸包上的期望是多少。 题解： 显然三角形长什么样，对答案没有影响。 注意到n<=10，所以做法就是：在三角形内随机n个点，求凸包，然后求多少个点在凸包上。随机次数越多，答案是准确率越高。最后打个表交上去就行了。 代码： #include <bits/stdc++.h> using namespace std; #pragma comment(linker, &quo...

http://tokitsukaze.live/2018/07/26/2018niuke3.E/ 题意： 给一个字符串，复制前n-1个字符后，问有多少种长度n的子串，分类后按字典序输出下标。 题解： 复制一遍字符串，然后预处理hash表。之后for每个起始位置，可以在O(1)的时间获取子串的hash值，然后扔进map分类即可。对于这种写法字典序不需要特殊处理。 这个题卡常…有两个点要注意一下。 1.mod取1e9+7会冲突(过了62.5%的数据)，而且每次%常数很大，会tle，这里选用了ull(自动%2^64)。 2.要用unordered_map，不然...

http://tokitsukaze.live/2018/07/21/2018niuke2.J/ 题解： now[i][j]表示在T次操作后，第(i，j)个格子放的数的和。 cnt[i][j]表示在T次操作后，第(i，j)个格子被更新的次数。 v[i][j]表示第(i，j)个格子的初始值。 now和cnt用二维前缀和更新。 那么答案就是now[i][j]!=cnt[i][j]*v[i][j]的个数。 很明显这是假算法，出题人会构造数据卡你。 所以对初始值随机打乱一下，被卡的概率就很低。 复杂度O(n*m)。 ...

http://tokitsukaze.live/2018/07/19/2018niuke1.F/ 题解：   至于杜教的拉格朗日插值板子，是从这里扒的：http://codeforces.com/contest/995/submission/39615335 代码： #include <bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:1024000000,1024000000") #...