pts:25 + 20 + 0 + 30 = 75
最惨淡的一场。
出现的最大问题是脑子掉线。。。。
今后考试策略：
拿到题先读完所有的题，然后把所有能写的暴力全敲完之后再来想正解。
考试一定要带脑子 ！！！
题目描述
给出三个整数 \({x,y,P(1\le x,y<P)}\), \({P}\) 为素数，可以重复对 \({x}\) 执行如下操作：选择一个整数 \({z\in[1,P-1]}\) ，花费 \({|x-z|}\) 的牛币，使得 \(x=x\times z\bmod P\)。
最小需要花费多少牛币才能使得 \({x=y}\) ?
设 \({ans(i,j)}\) 为当 \({x=i,y=j}\) 时的答案，为了减少输出，你需要输出
\({\sum\limits_{i=1}^{P-1}\sum\limits_{j=1}^{P-1}ans(i,j)*t^{(i-1)*(P-1)+j-1}\bmod 998244353}\)
数据范围
\(2 \leq P \leq 2000\)
考试的时候真没忘建图那方面想，然后就草草打了个暴力走人了。
solution
对于每一个操作，相当于从 \(x\) 向 \(x * z \mod P\) 建一条边权为 \(|x - z|\) 的边，然后到 \(y\) 跑一个最短路就好了。
30pts
当 \(P \leq 500\) 直接 \(Floyed\) 就好了。
但由于数据水或者牛客神机太快了，这玩意赛时能过 \(85\) ，现在加强了数据，但是还能过 \(75\) 分，就挺反人类行为的 = =
code
题目描述
有 \(n + 2\) 个整数 \(a_0, a_1, \dots, a_n, a_{n + 1}\)
你需要做确切地 \(n\) 次操作，每次操作以下形式：
选择一个整数 \(x\) 满足 \(a_x \neq 0\), 使得 \(a_x\)， 令 \(l = \max_{i < x, a_i = 0}(i), r = \min_{i > x, a_i = 0}(i)\)
此次操作的操作为 \(\max\{a_l, a_{l + 1}, \dots, a_{x - 1}\} + \max\{a_{x + 1},\dots, a_{r - 1}, a_r\}\) 牛币
有多少不同的操作方式使得操作花费的牛币最少，两种操作不同当且仅当两种操作的操作序列不同。答案对 \({998244353}\) 取模。
数据范围
\(1 \leq T \leq 10\)， 每个测试点 \(|n|\) 的和 \(\leq 10000000\)
solution
这道题我的 n! 过掉了 \(n = 20\) 的数据就挺反人类的 = =
这道题 \(n^3\) 能过也挺反人类的 = =。
正解是个卡常。。。。
10pts
枚举全排列就好了。
20pts
状态压缩，计算代价，对比代价，得出答案。
70pts(实测 90)
设第一个操作的人的编号为 \(x\)， 在 \(x\) 进行操作 \([1,x−1]\) 和 \({[x+1,n]}\) 的操作就独立了，这两段区间进行操作不会对另一段区间的价值产生影响，因此可以进行区间 \({dp}\)。
设 \(f_{l, r}\) 表示对 \(l, r\) 区间进行操作的最小代价。
显然 \(f_{l, r} = \min\{f_{l, k - 1} + f_{k + 1, r}\}\)
设 \(g_{l, r}\) 为 \([l, r]\) 区间内最小操作的序列数量，枚举断点 \(k\)。
显然只有当 \(f_{l, r} = f_{l, k - 1} + f_{k +1, r}\) 才可以转移。
\(g_{l, r} = g_{l, r} + g_{l, k - 1} \times g_{k +1, r} \times C_{r - l}^{k - l}\)
因为两个序列之间的操作顺序先后都可，所以就有 \(C_{r - l}^{k - l}\) 种方案。
复杂度： \(n^3\)
code
100pts
code
100pts
对于一段区间 \([l,r]\)，如果存在 \({a_i=a_{i+1}=\max\limits_{i=l}^r(a_i)(i\in[l,r))}\)
此时 \(i, i + 1\) 谁先选择没有关系，因此有 \(g_{l, r} = g_{l, i - 1} \times g_{i + 1, r} \times C_{r - l + 1}^{i - l + 1}\)
定义无穷序列 \({f：f_1=1,f_{n}=f_{n-1}*2+1}\)
定义函数 \({G(x)=\min\limits_{f_i\ge x}(f_i})\) \({dp_{c,0}=0,dp_{c,i}=max(dp_{c,i-1},[((i*c)\&G(i))==i]*i)}\)
其中 \({[p]}\) 为真值函数，当 \({p}\) 为真返回 \({1}\)，否则返回 \({0}\)。
求 \({\sum\limits_{i=0}^ndp_{c,i}}\bmod 998244353\)
数据范围
\(1 \leq T \leq 10\) 每个测试点 \(|n|\) 的和 \(\leq 10000000\)
solution
20pts
直接模拟题意就好。
100pts
设 \(G(i) = 2^{t + 1} - 1\) (\(G(x)\)必然是这样的形式，其中 \(t\) 为 \(i\) 二进制的最高位)，则 \(x \& G(i)\) 相当于 \(x\mod 2^{t + 1}\)，则：\((i\times c) \& G(i) = i \rightarrow (i \times c) \mod 2^{t + 1} = i \rightarrow i \times (c - 1) \mod 2^{t + 1} = 0\)
设 \(c - 1 = 2^p \times x\)，则 \(i\) 需要含有因子 \(2^{t + 1 - p}\)。
设 \(m = |n|\)，我们可以枚举 \(t\)， 如果 \(t < m - 1\) 则 \([2^t, 2^{t + 1} - 1]\) 内的所有数最高位都为 \(t\)，设 \(g = t + 1 - p\)， \(i\) 含有因子 \(2^g\) 即 \(i\) 的低于 \(g\) 位的全为 \(0\)，这样的数为 \(2^t, 2^t + 2^g, \dots, 2^t + x\times 2^g(2^t + (x + 1)\times 2^g = 2^{t + 1})\), 这是个 \(x + 1\) 项的等差数列，很容易求和，同时每个数对答案贡献了 \(2^g\) 次。
当 \(t = m - 1\) 时，由于 \(2^{t + 1} > n\), 我们需要满足，\(2^t + x\times 2^g \leq n \rightarrow x = \lfloor \frac{n}{2^g}\rfloor - 2^{t - g}\)，对这个 \(x + 1\) 项的等差数列计算贡献后，由于最后一项被计数了 \(2^g\) 次（计数范围为\([2^t + x\times 2^g, 2^t + (x + 1)\times 2^g - 1]\)），此时多计数了 \(2^t + (x + 1) \times 2^g - 1 - n\) 次，把这个贡献减掉就好了。
code
100pts
题目描述
给出 \({n}\) 行 \({m}\) 列的矩阵，第 \({i}\) 行第 \({j}\) 列的元素为 \({a_{i,j}}\) ，找出满足以下条件的三元组{(i,j,x)}(i,j,x)的数量：
数据范围
\(1 \leq k \leq n\times m, 1 \leq a[i]\leq 100\)
solution
用 \(bitset\) 记录颜色种类。
在边长扩展的过程中，不同数量的数只会增加不会减少，具有单调性。于是可以二分找到不同数量 \({<k}\) 的最大边长 \({x}\) 和不同数量 \({\le k}\) 的最大边长 \({y}\)，\({y-x}\) 即为固定一个左上角符合条件的正方形的数量。
这样需要处理 \({O(n^2logn)}\) 个查询，每个查询查询一个正方形内不同颜色的数量，由于是正方形，故可以采用二维 \({st}\) 表来做。
code
飞桨护航计划集训营已经开启报名?快来参加～
一场关于栈的面试----最小栈的实现
今天给大家分享一个真实的技术故事，讲述了如何通过优化数据库查询，解决生产环境中商品库CPU飙升的问题。接下来，我将带大家一步步分析问题，分享优化方案，让你也能从中获得宝贵的数据库优化经验！
题目描述 小N得到了一个非常神奇的序列A。这个序列长度为N，下标从1开始。A的一个子区间对应一个序列，可以由数对[l,r]表示，代表A[l], A[l + 1], ..., A[r]这段数。对于一个序列B[1], B[2], ..., B[k]，定义B的中位数如下： 1. 先对B排序。得到新的序列C
题目描述 小N对于数字的大小一直都有两种看法。第一种看法是，使用字典序的大小（也就是我们常用的判断数字大小的方法，假如比较的数字长度不同，则在较短一个前面补齐前导0，再比较字典序），比如43<355,10<11。第二种看法是，对于一个数字，定义他的权值为，也就是各个数位的乘积。 现在给定两个区间，[
前一个小时看这三道题感觉要爆零
比赛地址 得分：\(80 + 20 + 0 + 37.5 = 137.5\) 排名：\(51\) 第一题 \(n^3\) 能骗 \(80\) 是我没想到的，第四题暴力最多能到 \(95\) 也是我没想到的。 A 本来以为是什么牛逼数论做法 发现 \(P \le 2000\)，考虑把所有 \(i \t ...
前言 我只想说，我都氪金考试了，能不能不掉分。 每天一遍： YCC 是 SB。 还有，孙土蛋同学的代码是真的上头。 T1 40pts 对于每个$\leq p - 1$ 的数，在乘以每个 $z(\leq q)$的情况下，得到的数当做节点，以花费的代价作为边权，建边跑弗洛伊德算法。 /* Date:20 ...
前三题略 T4： 题目描述 小A有n个长度都是L的字符串。这些字符串只包含前8个小写字符，'a'~'h'。但这些字符串非常的混乱，它们几乎长得互不相同。小A想通过一些规则，让它们长得尽可能相同。小A现在有K次机会，他可以每次机会，可以选择一对字符x,y，让x,y变成等价的字符（注意这里x,y和字符'
A. 牛牛的方程式 数学题。 考虑 \(ax + by = c\) 有解的充要条件是 \(c|\mathrm{gcd}(a, b)\)，于是 \(ax + by\) 可以表示的所有整数即为 \(\mathrm{gcd}(a,b)t\) 代入原式：\(\mathrm{gcd}(a,b)t + cz = ...
T1 串串串 题目描述 题面 你有两个长度为 \(n, m\) 的 \(01\) 串 \(S, T\)。 有 \(Q\) 次询问，每次询问给出 \(l_1, r_1, l_2, r_2\)，其中 \(r_1 - l_1 + 1 = r_2 - l_2 + 1\) 令 \(a = S[l_1 \dot ...
比赛链接 2021牛客OI赛前集训营-普及组（第七场） B.采集灵石 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld 题目描述 牛牛打开了一个有趣的游戏。在游戏中，灵石是一种非常重要的资源。每位玩家每 ...
比赛传送 得分：\(100 + 0 + 100 + 40 = 240pts\) D 挂了 60 /ll 我感觉 B 挺好的，场上根本没想到怎么做/kk A 观察一下他给的条件。 对于任意一个序列 \(a\)，如果所有的 \(a_i \to a_i + k\)，那么新的序列和原序列一样。 所以任意一个 ...
Description 给你 \(n\) 个点，将其按 \(y_i\) 从大到小排序，从中任意选出一些点，组成序列 \(a\)，要使其满足 $a_{i-2} < a_i < a_{i-1} $ 或 \(a_{i-1} < a_i < a_{i-2}\)，求合法方案数。 Solution 只谈正解。 ...
T1 牛牛刚学习了输入输出，他遇到了一道这样的题目。 输入2个整数a和b 保证输入的a和b在long long范围之内，即满足 -9223372036854775808 <= a, b <= 9223372036854775807 计算a+b的值，即这两个数字的和。 如果a+b在long long范
来源 A - Alice and Bob （sg函数打表） 暴力打表，时间复杂度为O(n^3logN)。可以发现后手胜的状态数非常少：如果某堆石头数量是i，另一堆石头最多只有一种数量满足后手胜。 反证法：假设 (i, p) 和 (i, q) 都是后手必胜，且 q > p。那么在状态 (i, q) 时 ...
Java并发 文章目录Java并发堆的概念并发的难点原子性：可见性：有序性：JMM并发编程的关键目标并发编程的内存模型内存模型JMM源代码和指令间的重排如何解决重排序带来的问题happens-before程序顺序规则Volatitevolatile变量自身具有的特性volatile的内存语义volatile的实现机制锁锁的内存语义锁内存语义的实现锁内存语义的实现 堆的概念堆是被所有线程所共享的资源
Java 官方对反射（Reflection）的描述是：简单来说，反射让 Java 从 “静态语言” 具备了部分 “动态语言” 的能力。通过反射，我们可以获得类的等，还可以进行等一系列操作。
既然“先戳谁”会扰乱未来，那我们何不反过来想：在区间(i, j)（开区间，不含i和j）内，我们最后一个戳破的气球是哪个？dp[i][j]表示：戳破所有在开区间(i, j)内的气球，所能获得的最大金币数。为了计算dp[i][j]，我们枚举在这个区间内，最后一个被戳破的气球ki < k < j当k是最后一个被戳破的英雄时，它左右两边的气球(i, k)和(k, j)必然已经被全部戳光了。那么，在戳k的那一瞬间，它的左右邻居是谁？必然是i和j！因为i和j是区间的边界，我们假定它们一直“存活”到最后。
---恢复内容开始---以前对于各种引擎也稍微有点理解，可是却并没有深入研究过，最近打算看看Innodb引擎，InnoDB 存储引擎前言：数据库：物理操作系统文件或其他形式文件类型的集合，数据库实例：有数据库后台进程/线程以及一个共享内存区组成mysql被设计成了一个单进程多线程架构的数据库开始：1、默认的InnoDB存储引擎的后台线程有7个，4个IO threa
解决AI推理性能瓶颈，提供实用PythonAI性能优化建议。针对GPU利用率低问题，剖析模型推理、内存管理与并行计算等关键环节，适用于深度学习部署场景。涵盖异步处理、批量化推理与框架调优技巧，显著提升系统吞吐量与响应速度，值得收藏。