国家集训队专题
bzoj 2038: [2009国家集训队]小Z的袜子(莫队算法)
2038: [2009国家集训队]小Z的袜子(hose) Time Limit: 20 Sec Memory Limit: 259 MB Submit: 15386 Solved: 6996 [Submit][Status][Discuss] Description 作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜
![洛谷P1829 - [国家集训队]Crash的数字表格](/front/images/it_default.jpg)
洛谷P1829 - [国家集训队]Crash的数字表格
Portal Description 给出\(n,m(n,m\leq10^7)\)，计算\[ \sum_{i=1}^n \sum_{j=1}^m lcm(i,j) \bmod 20101009\] fdsa Solution 推推推...\[\begin{align} ans &= \sum_{i=1}^n \sum_{j=1}^m lcm(i,j) \\ &= \sum_{i=1}^n \su
[国家集训队]Tree
Tree 题解 一道LCT板题。 看样子就像是一道LCT的板题，只需要将乘与加的懒标记分别传下去即可。 ‘-’就是简单的树上加边与删边 ‘/'就是查询和，update时更新即可。 不过需要注意一下在乘与加时懒标记与总数的变化。 mul是乘的懒标记，add是加的懒标记，sum是当前和，siz是子树大小。 公式其实很好推的，关键是别直接乘与加，笔者就因为这个WA了 源码
P4555 [国家集训队] 最长双回文串 题解
P4555 [国家集训队] 最长双回文串 题解 补一个题解区没有的解法。 解法 通过哈希实现的线性做法，受讨论区启发。 考虑枚举双回文串的分割点，即分割点左右各是一个回文串，对于每个分割点，我们最大化两个回文串的长度，而且两个回文串是互不影响的。 问题转化为求原串的所有前缀的最长回文后缀和所有后缀的最长回文前缀。因为两个问题求法是类似的，所以这里只说如何求所有前缀的最长回文后缀。 我们
四川叙永13岁少女入选跨界跨项跳台滑雪国家集训队
周忆雯在练习武术动作。 钟欣 摄 周忆雯在练习武术动作。 钟欣 摄 中新网泸州1月21日电 (邹立杨 苏忠国)记者21日从四川泸州市叙永县文体广局获悉，经过前期严格的省级测试，叙永县13岁少女周忆雯入选跨界跨项跳台滑雪国家集训队，将赶赴芬兰卡皮奥训练基地进行为期3个月的集中训练。 据介绍，2005年出生的周忆雯是四川叙永人，自小酷爱武术，2011年进入叙永县武术培训中心接受武术培训，后于
![P1297 [国家集训队] 单选错位 对期望的理解](https://img-blog.csdnimg.cn/direct/3d0501a3e6de4de1819e8a8ecdcbb520.png)
P1297 [国家集训队] 单选错位 对期望的理解
[国家集训队] 单选错位 - 洛谷 思路： 其实每个位置的得分只和前一个位置有关。 而他们俩的所有情况的期望就是答案的这部分。 ——这是难想的，我期望学的不好。 （题目给的是每种情况的所有位置的和，全加起来是答案；我们算的是这个位置的所有情况的值） 然后每个位置和前一个位置的情况可以分三种：（其实就是上面大佬的题解分析） ai == ai+1 对ai+1来说每次得分 1/
![Bzoj 2038: [2009国家集训队]小Z的袜子(莫队)](/front/images/it_default.gif)
Bzoj 2038: [2009国家集训队]小Z的袜子(莫队)
2038: [2009国家集训队]小Z的袜子(hose) Time Limit: 20 Sec Memory Limit: 259 MB Description 作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜子过程，于是他决定听天由命…… 具体来说，小Z把这N只袜子从1到N编号，然后从编号L到R(L 尽管小Z并不
![P1903 [国家集训队] 数颜色 / 维护队列](https://img-blog.csdnimg.cn/5a4908784fda4e3eb1c9acfd9faa84c4.png)
P1903 [国家集训队] 数颜色 / 维护队列
带修改的莫队 带修改的莫队就是在基础莫队的基础上增加了一维属性，之前只需要维护l，r现在还需要维护一下时间t，排序还是先按照左端点块儿号排序，然后右端点块儿号排序，最后按时间排序。其它的都是差不多的。 #include<bits/stdc++.h>#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define
![P1494 [国家集训队] 小 Z 的袜子](https://img-blog.csdnimg.cn/ffca3ec7b46e4fc9ba95099a6c31dce5.png)
P1494 [国家集训队] 小 Z 的袜子
这一题是一个关于多次查询区间状态的一个问题，暴力肯定会超限，但是可以用莫队来优化暴力。 莫队的思想就是，用上一个区间的状态来更新当前区间的状态。 问题就是状态怎么更新以及求出当前区间的状态、也就是有多少对相同的袜子以及总共有多少袜子，通过这两个值可以求出来概率。 如何求出来有多少对相同的袜子，只需要遍历一遍当前区间记录每个颜色出现了多少次，当到了某个位置的时候，只需要知道之前的袜子有多少能跟
解题：国家集训队 Crash 的文明世界
题面 这种套着高次幂的统计问题一般都要用到第二类斯特林数和自然数幂的关系：$a^k=\sum\limits_{i=0}^{k}S_k^iC_a^i*i!$ 那么对于每个点$x$有： $ans_x=\sum\limits_{i=0}^k S_{k}^i C_{\sum dis(x,j)}^i i!$ 问题变成求$C_{\sum dis(x,j)}^i$，神仙告诉我们，这个东西要DP求 为什么要DP
洛谷 1407 [国家集训队]稳定婚姻 题解（强连通分量，建图，思维）
原题链接： luogu bzoj 题意简述 给定 2 n 2n 2n个人，一些情侣关系，和 n n n对夫妻关系。定义一对"不安全的"夫妻为：即使离婚，但是算上旧情复燃（就是那些情侣）的关系，依然珂以让每个人都有伴侣（也就是还能找到 n n n对伴侣）。输出 n n n行，按照给定夫妻的顺序，输出每对夫妻关系是否安全。安全输出Safe,不安全输出Unsafe。 数据 输入 n//夫妻对数