企业官网建设流程全解析

7.2正式开始集训，期末周太久没练，今天主要是康复训练，练习模板题

A题DFS基本模板题，B题单调栈（贪心），C题最长重复子串规模小枚举，D题小规模组合数计算数字三角形，E题01背包，F题C++基本知识，G题是简化版本的区间合并问题，H题大模拟（主要是判断字符串的合法），I题简单递推递归问题，J题广搜模板题，K，L题属于是转换角度

接下来从简单到难分析一下：

K题

农夫约翰正尝试通过给奶牛们一组通常用于学龄前儿童的N个拼字板来教它们阅读（1≤N≤100）。每个板上都有一面是单词，另一面是图片。例如，一面可能是单词'cat'和一张猫的图片，另一面可能是单词'dog'和一张狗的图片。当板块放在地上时，因此会显示出N个单词。通过翻转一些板块，可以展示出一组不同的N个单词。
为了帮助奶牛们拼写，农夫约翰想要制作一些木块，每个木块上刻有一个字母。他希望为每个字母制作足够多的木块，这样无论向上的拼写板上显示的是哪一组N个单词，奶牛们都能使用这些木块拼写出所有这些单词。例如，如果N=3，单词'box'、'cat'和'car'朝上，奶牛们至少需要一块'b'木块、一块'o'木块、一块'x'木块、两块'c'木块、两块'a'木块、一块't'木块和一块'r'木块。
请帮助农夫约翰确定他需要提供的每个字母积木块的最小数量，以便无论每块板的哪一面朝上，奶牛都能拼写出所有N个可见单词。

显然，对于所有单词满足，只需要每个双单词的加和即可，可以转换为求这两个的每个单词需要的字母然后max(cnt1[i],cnt2[i])合并即可。

L题

甲乙两人进行围棋比赛，谁先获胜n局谁就会取得比赛的胜利。如果最后甲获胜，用C++编程求出比赛的进程可能有多少种。
例如n=3时，可以是以下10种获胜的可能
甲，甲，甲
甲，甲，乙，甲
甲，乙，甲，甲
甲，乙，甲，乙，甲
甲，乙，乙，甲，甲
甲，甲，乙，乙，甲
乙，甲，甲，甲
乙，甲，甲，乙，甲
乙，甲，乙，甲，甲
乙，乙，甲，甲，甲

一开始我当成了对乙选3个位置，还考虑了乙乙的重复和对称，把问题复杂化了，实际上（思路来源于甲的最后一次获胜位置是固定的），相当于对前面的位置插入n-1个甲的位置，可以表示为

,组合恒等式，也可以用数字三角形解决。

H题主要是字符串判断，我的思路是，四个标点存在，先后关系没错，无除这四个和数字无关的符号，数字长度限制（防止溢出），数字大小限制，无前导0（处理单个0正确）。

接下来汇总一下今天真正学到的知识：

1.单调栈分析，这里Nearest Smaller Values（找更小值问题）-CSDN博客已经分析过，再次看了视频和理解一遍之后感觉非常通透（印证了我们教练的反复刷题才能真正掌握，尤其对我这种经常遗忘的来说）。

总的来说就是，对栈顶部入栈和出栈操作，通过保证栈的数值单调性让每个值在出栈时获得它对应的答案，这里再给一个例题https://www.luogu.com.cn/problem/P2866

以及洛谷代码

#include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin>>n; vector<int> a(n); for(int i=0;i<n;i++)cin>>a[i]; stack<pair<int,int>> s; long long cnt=0; for(int i=0;i<n;i++) { while(!s.empty()&&s.top().first<=a[i]) { cnt+=i-1-s.top().second; s.pop(); } if(i==n-1) { while(!s.empty()) { cnt+=i-s.top().second; s.pop(); } } else s.push({a[i],i}); } cout<<cnt<<"\n"; }

2.区间类似问题

临近期末考试，自习室的学生来来往往。
这可忙坏了管理自习室的大爷，他随时准备开关灯。
自习室只要有学生来，就需要开灯。一开始没有学生来之前灯是关闭的。
周日这一天共有n位同学来自习，第i个同学将在时间Ti来自习室，并在时间Ti + 1离开。
按照规定任何时间最多一个同学在自习室（防止同学之间说话影响学习）。
大爷可以随时开灯和关灯（有学生在自习室的时候不能关灯）。
由于学生频繁出入，大爷已经厌倦了每天反复开关灯，所以他决定一天最多开灯k次，当然他想尽量减少灯亮的时间（节约用电）。
请计算这一天灯亮时间的最小值。

显然这个问题由于每个学生在的时间为1，那么对于无缝衔接的学生无需管，对于相差时间为t存到一个数组里面，最大的前k-1个减去即可。

那么这个问题显然有变型，对于时间不限的学生，计算相邻两个学生的空档是一样的

而进一步对于不限于一个学生的，如果求最多学生数，就是一个区间调度问题，对于求灯亮最小值，如果时间1e5内可以预处理遍历时间，如果时间在1e9内那么每次遍历维护最大右区间（对于空档记录同样）。

对于区间调度问题可以看区间调度问题及其升级-CSDN博客

下面给出求灯亮遍历维护的代码（这种类似题，一是通过遍历对i进行处理，二是无关时分为左右区间，具体怎么描述目前还没汇总好，还需要多做题掌握核心技巧，类似校赛的M绝世裁缝）

#include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n,k; cin>>n>>k; vector<int> lei; vector<pair<int,int>> a(n); for(int i=0;i<n;i++)cin>>a[i].first>>a[i].second; int max_right=a[0].second; for(int i=1;i<n;i++) { if(a[i].first>max_right) { lei.push_back(a[i].first-max_right); } max_right=max(max_right,a[i].second); } int ans=max_right-a[0].first; sort(lei.begin(),lei.end(),greater<int>()); for(int i=0;i<min(k,(int)lei.size());i++) { ans-=lei[i]; } cout<<ans<<"\n"; }

3.最长重复串

问题 C：Where 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 不能令 K=3，因为如果他看到了 'ABC'，沿路有两个这一连续颜色序列可能所在的位置。最小可行的 K 的值为 K=4，因为如果他查看任意连续 4 个邮箱，这一颜色序列可以唯一确定他在道路上的位置。
输入
输入的第一行包含 N，第二行包含一个由 N 个字符组成的字符串，每个字符均在 A..Z 之内。

输出
输出一行，包含一个整数，为可以解决 Farmer John 的问题的最小 K 值。
样例输入
7
ABCDABC
样例输出
4

小规模枚举，大规模需要用到后缀数组的最大重复前缀（已力竭，明天再补习后缀数组以及相应的排序方法、倍增思想）。

4.组合数计算方法

1.对于n<=20（基础语法），通过组合数的公式计算每个数的阶乘。

2.先算分子，再算分母相除（这个过程中每次约去最大公因数可以一定规模提升），longlong范围内60-70左右，对于__int128可以达到1e6

3.杨辉三角（数字三角形），显然是预处理，可以用于求小范围内的多个数字

4.卢卡斯定理+费马小定理（逆元取模），今天时间不够了，明天下午补习，先给出快速幂的模板

long long qpow(long long a,long long b,long long mod) { if(mod==1)return 0; if(mod==0)return -1;//mod为0无意义 a%=mod;//b不取模 long long res=1%mod; while(b) { if(b&1)res=res*a%mod; a=a*a%mod; b>>=1; } return res; }

最后，作为暑假集训的开端，表达一下个人对集训以及自我在学习过程中的感悟：我们常常在意别人的状态，别人的成就，实则对于每个人自己来说，最重要的是相信自己，我们可能在这个过程中自我松懈，但是你一定要给松懈过的自己创造一个能过从头再来的条件，真正努力的人必须是享受努力的过程的，不然无法坚持下去，我今年才18岁，认知浅显，不可否认二十多岁的工作对后半生十分重要，但是人不应该只着眼于未来成就的那一刻，更应当在每次努力的过程中做好劳逸结合，做好对生活的享受，感悟自己的性格。有付出，就不会迷茫，情绪的波动决定不了你人生享受与充实的常态，愿我们一起加油。