集训队 普罗2015

## 上午简单排序 - [P5143 攀爬者](https://www.luogu.com.cn/problem/P5143) 点击查看代码 ``` #include using namespace std; const int N=5e4+10; struct T{ int x,y,z; }a[N ......

##写在前面： 本文总结自信息学奥赛一本通《算法高效进阶》 ##$kmp$: 1.如果前缀$i$存在一个长为$j$的公共前后缀，那么它有一个长为$i-j$的周期[P4391](https://www.luogu.com.cn/problem/P4391 "P4391") 2.用一个$t$串,令其长度 ......

# 8.18 ### T1 推式题．推式能力不强，消耗了大量时间． 由期望的线性，可以对每个位置分开计算贡献． 每个位置的地位对等． 对于每个位置，考虑进行 $m$ 次操作后仍在该位置的信封仍在原位置的概率．考虑递推 $F_i$ 表示 $i$ 操作后仍在原位置的概率． $$ F_i=(\frac{n ......

## 0821 复赛模拟 ### T1 > [洛谷 P7398](https://www.luogu.com.cn/problem/P7398) 裸的模拟，对得丑陋 ```cpp #include using namespace std; const int N = 1e4 + 50; int an ......

## 上午 - [P1789 【Mc生存】插火把](https://www.luogu.com.cn/problem/P1789) 点击查看代码 ``` #include using namespace std; const int N=110; bool a[N][N]; int n,m,k,x, ......

1. 二分找最小限制。 2. 树上差分找 $R$ 。 3. 最大路线耗时 - $R$ 的 $t[i]$ 值 $\le$ $limit$ ,就满足条件。 ......

## 题目链接 [洛谷](https://www.luogu.com.cn/problem/P2168) [LOJ](https://loj.ac/p/2132) ## 题目分析 哈夫曼编码模板题。 使用 k 进制，即编码时将 k 个点合并为一个。 最后要求的就是哈夫曼编码的长度，以及哈夫曼树最深的 ......

#### VS2015里面没有.NET Framework 4.6.2 VS2015默认安装的目标框架最高是.NET Framework 4.6.1，但是我的项目里面某些NuGet软件包更新需要依赖.NET Framework 4.6.2，项目就需要升级到目标框架.NET Framework 4.6 ......

# [A 陷阱](https://hydro.ac/d/xiaozhu0602/p/17) 我们可以从 $l$ 枚举到 $d$，再计算是否满足要求，满足要求加入到数组中，输出第一个和最后一个 ``` #include using namespace std; const int N = 1e5 + ......

2015年12月英语六级翻译真题及参考答案 沪江英语 2015-12-21 16:29 分享到 12月19日刚刚考完大学英语六级的同学们，答案都对过了吗？今年的三个翻译题目涉及消除贫困，工业升级和父母的教育观，句子结构不算太难，但一些专有名词的表达如果没有记住，可能就会影响整个语段翻译的流程。考试结 ......

## 上午递归，文件 - [B2064 斐波那契数列](https://www.luogu.com.cn/problem/B2064) - [P1255 数楼梯](https://www.luogu.com.cn/problem/P1255) 点击查看代码 ``` #include using na ......

# [A 查找最大元素](http://acm.hdu.edu.cn/showproblem.php?pid=2025) 扫一遍确定最大值，如果是最大值输出字符和"(max)"，不是的话只输出字符 ``` #include #include using namespace std; char max ......

## Day 1 [题单](https://www.luogu.com.cn/training/357814) - 栈 - 单调栈 - 单调队列 - 并查集 - 带权并查集 ## Day 2 [题单](luogu.com.cn/training/358470) - 树状数组 - 单点加、区间查 - ......

# T1 这题一看就很难实现，事实也确实是这样，考场想了半个多小时没有思路，打完暴力就跳了。 这道题的正解技巧和思维性很强，不是很套路，只是融合了一些线段树区间操作的思想。感觉......怎么会评蓝呢？这 T4 一道紫题都明显比 T1 好做啊！关键 T1 的考场通过率竟然最高! 大概思路就是，变化会 ......

写作一 “Knowledge is a treasure, but practice is the key to it” Give one example or two to illustrate your point of view. You should write no more than 2 ......

#强连通分量 一个在**有向图**中的概念 $强连通的定义是：有向图 G 强连通是指，G 中任意两个结点连通。$ $强连通分量（Strongly Connected Components，SCC）的定义是：极大的强连通子图$ ###tarjan算法的一些理解 注意到如果一些点属于一个强连通分量，那么 ......

## 上午二维数组/函数 - [B2101 计算矩阵边缘元素之和](https://www.luogu.com.cn/problem/B2101) 点击查看代码 ``` #include using namespace std; const int N=110; int n,m,a[N][N]; i ......

在开发时，vita打包报错如下： 原因： ECMAScript 提案 Top-level await 由 Myles Borins 提出，它可以让你在模块的最高层中使用 await 操作符。在这之前，你只能通过在 async 函数或 async generators 中使用 await 操作符。To ......

## 上午/一维数组排序 - 排序：sort，冒泡，选择，插入，计数 复杂度：$O(nlogn),O(n^2),O(n^2),O(n^2),O(n)$ 点击查看代码 ``` #include #include using namespace std; const int N=1e5+10; int ......

说句题外话，这个博客不更是因为我转cnblogs了。 2023正睿金华暑假集训 7月15日，我跟随大队来到了金华 第一次参加暑假出省线下集训，之前在高中部集训过， 但都是校内的集训，没怎么出去过。唯一一次好像还是去六中集训，但最多也就是几个学校之间的小打小闹。 7月份是在C班集训，课没怎么听，主要是 ......

# [COCI2015-2016#7] Prokletnik 有那么一点点启发性。 假设右端点是最大值，思路很简单很经典，考虑扫描线+线段树，那么修改涉及到的点就是当前的后缀最小值，维护一个单调不减的单调栈，那么单调栈里面的点都要改。 难道我们要遍历单调栈吗？哈哈，并不用，我们直接在单调栈上面建一棵 ......

## 上午测试讲题 - [U259234 累加累乘/accmul](https://www.luogu.com.cn/problem/U259234) 分析：直接开两个变量记录答案即可，使用for循环n次，对于s1也可以使用等差数列求和公式。 点击查看代码 ```cpp #include using ......

# T2 考场一直卡在二进制思路里面，最后打了一个 $O(n\max\{a_i\})$ 的方法，居然忘了继续向后跑 $\log$ 位，挂掉 $20pts$（像这种情况全挂也是有可能的）。 我认为其实有的时候**不要随便简化问题**，或者说想多了也要及时回来（虽然这可能很不容易）。自己认为的简化不一定 ......

####快速幂 ```c++ #include using namespace std; unsigned long long a,b,k,ans=1; int main(){ cin>>a>>b>>k; if(b==0){ ans=1%k; cout>=1; }cout using namespa ......

[题解 P3345 【[ZJOI2015]幻想乡战略游戏】 - Baka's Blog - 洛谷博客 (luogu.org)](https://kai586123.blog.luogu.org/solution-p3345) 耗时：半个下午 代码注释： ```cpp #include typedef ......

# 1.整除，最大公因数和最小公倍数 ## 1.1 整除 若整数 $b$ 除以非零整数 $a$ ，商为整数，且余数为零，$b$ 为被除数，$a$ 为除数，即$a|b$，读作“ $a $整除 $b $ ”或“ $b $能被 $a $ 整除”。 其中，整除具有如下三条性质： - 整除的传递性，证明如下： ......

# T2 考场先是想到（根本没想）了一个 $O(n^5)$ 的思路，然后猜了一个比较好打的结论开打。结果小样例和答案差一点，大样例就差的多了。确认不是精度问题后就明显是猜的结论有问题了。这下是彻底没办法了，只有打了那个 $O(n^5)$ 的暴力。 出分我一看——怎么挂了 $20pts$？而且按照暴力 ......

# T1 考场打的是一个伪正解（没正确性的那种），评测的时候发现有 subtask 人都给我吓傻了，还好还有 $50pts$。就是不知道为什么 zxc 和我思路一样但是有 $85$ pts。 这个正解确实有点难想，而且证明正确性也比较困难。 关于题解的正确性： - 若 $a$ 的逆元不是本身。那么如 ......

### [在洛谷中查看](https://www.luogu.com.cn/problem/P1407) ### 题意： 自己读一下，大致就是 $2n$ 个点，每个点编号为 $1 - 2n$，$\lfloor 编号/2 \rfloor$ 相同的点连条边。 然后再给 $m$ 条边。 问：将每个 $\l ......

给定 $01$ 矩阵 $C$，求有多少个 $01$ 矩阵的有序对 $(A,B)$ 满足 $A \times B \equiv C \pmod 2$。 $n \leq 2 \times 10^3$。 先考虑如果知道了 $A$ 怎么做。考虑把 $C$ 和 $A$ 写成若干行向量的组合 $c_1 \sim ......