7.2正式开始集训期末周太久没练今天主要是康复训练练习模板题A题DFS基本模板题B题单调栈贪心C题最长重复子串规模小枚举D题小规模组合数计算数字三角形E题01背包F题C基本知识G题是简化版本的区间合并问题H题大模拟主要是判断字符串的合法I题简单递推递归问题J题广搜模板题KL题属于是转换角度接下来从简单到难分析一下K题农夫约翰正尝试通过给奶牛们一组通常用于学龄前儿童的N个拼字板来教它们阅读1≤N≤100。每个板上都有一面是单词另一面是图片。例如一面可能是单词cat和一张猫的图片另一面可能是单词dog和一张狗的图片。当板块放在地上时因此会显示出N个单词。通过翻转一些板块可以展示出一组不同的N个单词。为了帮助奶牛们拼写农夫约翰想要制作一些木块每个木块上刻有一个字母。他希望为每个字母制作足够多的木块这样无论向上的拼写板上显示的是哪一组N个单词奶牛们都能使用这些木块拼写出所有这些单词。例如如果N3单词box、cat和car朝上奶牛们至少需要一块b木块、一块o木块、一块x木块、两块c木块、两块a木块、一块t木块和一块r木块。请帮助农夫约翰确定他需要提供的每个字母积木块的最小数量以便无论每块板的哪一面朝上奶牛都能拼写出所有N个可见单词。显然对于所有单词满足只需要每个双单词的加和即可可以转换为求这两个的每个单词需要的字母然后max(cnt1[i],cnt2[i])合并即可。L题甲乙两人进行围棋比赛谁先获胜n局谁就会取得比赛的胜利。如果最后甲获胜用C编程求出比赛的进程可能有多少种。例如n3时可以是以下10种获胜的可能甲甲甲甲甲乙甲甲乙甲甲甲乙甲乙甲甲乙乙甲甲甲甲乙乙甲乙甲甲甲乙甲甲乙甲乙甲乙甲甲乙乙甲甲甲一开始我当成了对乙选3个位置还考虑了乙乙的重复和对称把问题复杂化了实际上思路来源于甲的最后一次获胜位置是固定的相当于对前面的位置插入n-1个甲的位置可以表示为,组合恒等式也可以用数字三角形解决。H题主要是字符串判断我的思路是四个标点存在先后关系没错无除这四个和数字无关的符号数字长度限制防止溢出数字大小限制无前导0处理单个0正确。接下来汇总一下今天真正学到的知识1.单调栈分析这里Nearest Smaller Values找更小值问题-CSDN博客已经分析过再次看了视频和理解一遍之后感觉非常通透印证了我们教练的反复刷题才能真正掌握尤其对我这种经常遗忘的来说。总的来说就是对栈顶部入栈和出栈操作通过保证栈的数值单调性让每个值在出栈时获得它对应的答案这里再给一个例题https://www.luogu.com.cn/problem/P2866以及洛谷代码#includebits/stdc.h using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cinn; vectorint a(n); for(int i0;in;i)cina[i]; stackpairint,int s; long long cnt0; for(int i0;in;i) { while(!s.empty()s.top().firsta[i]) { cnti-1-s.top().second; s.pop(); } if(in-1) { while(!s.empty()) { cnti-s.top().second; s.pop(); } } else s.push({a[i],i}); } coutcnt\n; }2.区间类似问题临近期末考试自习室的学生来来往往。这可忙坏了管理自习室的大爷他随时准备开关灯。自习室只要有学生来就需要开灯。一开始没有学生来之前灯是关闭的。周日这一天共有n位同学来自习第i个同学将在时间Ti来自习室并在时间Ti 1离开。按照规定任何时间最多一个同学在自习室防止同学之间说话影响学习。大爷可以随时开灯和关灯有学生在自习室的时候不能关灯。由于学生频繁出入大爷已经厌倦了每天反复开关灯所以他决定一天最多开灯k次当然他想尽量减少灯亮的时间节约用电。请计算这一天灯亮时间的最小值。显然这个问题由于每个学生在的时间为1那么对于无缝衔接的学生无需管对于相差时间为t存到一个数组里面最大的前k-1个减去即可。那么这个问题显然有变型对于时间不限的学生计算相邻两个学生的空档是一样的而进一步对于不限于一个学生的如果求最多学生数就是一个区间调度问题对于求灯亮最小值如果时间1e5内可以预处理遍历时间如果时间在1e9内那么每次遍历维护最大右区间对于空档记录同样。对于区间调度问题可以看区间调度问题及其升级-CSDN博客下面给出求灯亮遍历维护的代码这种类似题一是通过遍历对i进行处理二是无关时分为左右区间具体怎么描述目前还没汇总好还需要多做题掌握核心技巧类似校赛的M绝世裁缝#includebits/stdc.h using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n,k; cinnk; vectorint lei; vectorpairint,int a(n); for(int i0;in;i)cina[i].firsta[i].second; int max_righta[0].second; for(int i1;in;i) { if(a[i].firstmax_right) { lei.push_back(a[i].first-max_right); } max_rightmax(max_right,a[i].second); } int ansmax_right-a[0].first; sort(lei.begin(),lei.end(),greaterint()); for(int i0;imin(k,(int)lei.size());i) { ans-lei[i]; } coutans\n; }3.最长重复串问题 CWhere Am I题目描述Farmer John 出门沿着马路散步但是他现在发现可能迷路了沿路有一排共 N 个农场1≤N≤100。不幸的是农场并没有编号这使得 Farmer John 难以分辨他在这条路上所处的位置。然而每个农场都沿路设有一个彩色的邮箱所以 Farmer John 希望能够通过查看最近的几个邮箱的颜色来唯一确定他所在的位置。每个邮箱的颜色用 A..Z 之间的一个字母来指定所以沿着道路的 N 个邮箱的序列可以用一个长为 N 的由字母 A..Z 组成的字符串来表示。某些邮箱可能会有相同的颜色。Farmer John 想要知道最小的 K 的值使得他查看任意连续 K 个邮箱序列他都可以唯一确定这一序列在道路上的位置。例如假设沿路的邮箱序列为 ABCDABC 。Farmer John 不能令 K3因为如果他看到了 ABC沿路有两个这一连续颜色序列可能所在的位置。最小可行的 K 的值为 K4因为如果他查看任意连续 4 个邮箱这一颜色序列可以唯一确定他在道路上的位置。输入输入的第一行包含 N第二行包含一个由 N 个字符组成的字符串每个字符均在 A..Z 之内。输出输出一行包含一个整数为可以解决 Farmer John 的问题的最小 K 值。样例输入7ABCDABC样例输出4小规模枚举大规模需要用到后缀数组的最大重复前缀已力竭明天再补习后缀数组以及相应的排序方法、倍增思想。4.组合数计算方法1.对于n20基础语法通过组合数的公式计算每个数的阶乘。2.先算分子再算分母相除这个过程中每次约去最大公因数可以一定规模提升longlong范围内60-70左右对于__int128可以达到1e63.杨辉三角数字三角形显然是预处理可以用于求小范围内的多个数字4.卢卡斯定理费马小定理逆元取模今天时间不够了明天下午补习先给出快速幂的模板long long qpow(long long a,long long b,long long mod) { if(mod1)return 0; if(mod0)return -1;//mod为0无意义 a%mod;//b不取模 long long res1%mod; while(b) { if(b1)resres*a%mod; aa*a%mod; b1; } return res; }最后作为暑假集训的开端表达一下个人对集训以及自我在学习过程中的感悟我们常常在意别人的状态别人的成就实则对于每个人自己来说最重要的是相信自己我们可能在这个过程中自我松懈但是你一定要给松懈过的自己创造一个能过从头再来的条件真正努力的人必须是享受努力的过程的不然无法坚持下去我今年才18岁认知浅显不可否认二十多岁的工作对后半生十分重要但是人不应该只着眼于未来成就的那一刻更应当在每次努力的过程中做好劳逸结合做好对生活的享受感悟自己的性格。有付出就不会迷茫情绪的波动决定不了你人生享受与充实的常态愿我们一起加油。