作物杂交
单元汇最短路，SPFA，Dijkstra
痛苦冲刺蓝桥杯中……记不住算法板子啊啊啊啊啊
中文题目就不概括了（）
第一眼感觉像个图论，但是还是不知道怎么做……求最短时间可以看成求最短路，由于到达每个点需要考虑两个点，这就是这题与平常的题目不一样的地方。
听y总讲得很有道理但是只知道要用最短路算法，但又感觉得总结一下就去翻了翻题解，参考了AcWing 3305. 作物杂交(建图解释) - AcWing的解释，关于怎么建图的细节讲得非常不错，建议去看看
摘录一下自己觉得很有用的部分：
- 在构建图的过程中，边不仅可以存储边权，还可以存储其他额外信息
- 超级源点：对于一个可以有多个起点的图（但不是全部点都是起点），我们可以假设一个节点0，从这个节点指向了所有起点，我们就把原来的问题转化为了从0点开始的单元汇最短路（这里思考一下和多源汇最短路的区别）
我们先来解释下怎么建图：
由于我们是两个点a、b一起可达才可以到达c，所以我们在建图的时候要同时建立a->c和b->c两条边，同时还要记录a--b间的联系，对于更新c的距离，就是\(max(dis[a],dis[b])+max(t[a],t[b])\)。
a--b间的联系正如上方摘录的第一点，是在我们存边的时候存储的，很自然的，我们可以想到struct，既然如此，可以顺便用链表来存图。（虽然数据范围没有很大）
再结合上面的第二点来看，这题就很清晰明了了，可用spfa/dijkstra，下面把两种方法都的代码都给出了（背背板子）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
const int N=2010;
int n,m,k,t,h[N],dis[N],ti[N],idx;
bool state[N];
queue<int> q;
struct type{
int to,nxt,cp;
//多加一个cp用于记录联系
}tr[N*N];
int read(){
int i=0,j=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') j=-1;
ch=getchar();
}
while(isdigit(ch)){
i=i*10+ch-'0';
ch=getchar();
}
return i*j;
}
void add(int a,int b,int c){
idx++;
tr[idx].cp=b;
tr[idx].to=c;
tr[idx].nxt=h[a];
h[a]=idx;
}
//一个普通的板子罢辽
void spfa(){
while(!q.empty()){
int a=q.front();
q.pop();
state[a]=false;
for(int i=h[a];i;i=tr[i].nxt){
int b=tr[i].cp,c=tr[i].to;
if(dis[c]>max(dis[a],dis[b])+max(ti[a],ti[b])){
dis[c]=max(dis[a],dis[b])+max(ti[a],ti[b]);
if(!state[c]){
state[c]=true;
q.push(c);
}
}
}
}
}
int main(){
n=read(),m=read(),k=read(),t=read();
memset(dis,0x3f,sizeof(dis));
for(int i=1;i<=n;i++) ti[i]=read();
for(int i=1;i<=m;i++){//超级源点乌拉！！！
int x=read();
state[x]=true;
dis[x]=0;
q.push(x);
}
for(int i=1;i<=k;i++){
int a=read(),b=read(),c=read();
add(a,b,c);
add(b,a,c);
}
spfa();
cout<<dis[t];
return 0;
}
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
const int N=2010;
int n,m,k,t,h[N],dis[N],ti[N],idx;
bool state[N];
priority_queue<pii,vector<pii>,greater<pii>> q;
struct type{
int to,nxt,cp;
}tr[N*N];
int read(){
int i=0,j=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') j=-1;
ch=getchar();
}
while(isdigit(ch)){
i=i*10+ch-'0';
ch=getchar();
}
return i*j;
}
void add(int a,int b,int c){
idx++;
tr[idx].cp=b;
tr[idx].to=c;
tr[idx].nxt=h[a];
h[a]=idx;
}
void dijkstra(){
while(!q.empty()){
int a,d,b,c;
tie(d,a)=q.top();
q.pop();
if(state[a]) continue;
state[a]=true;
for(int i=h[a];i;i=tr[i].nxt){
b=tr[i].cp,c=tr[i].to;
if(dis[c]>max(dis[a],dis[b])+max(ti[a],ti[b])){
dis[c]=max(dis[a],dis[b])+max(ti[a],ti[b]);
//这里加不加判断区别不大
//q.push({dis[c],c});
if(!state[c]){
q.push({dis[c],c});
}
}
}
}
}
int main(){
n=read(),m=read(),k=read(),t=read();
memset(dis,0x3f,sizeof(dis));
for(int i=1;i<=n;i++) ti[i]=read();
for(int i=1;i<=m;i++){
int x=read();
//注意这里和spfa不一样，不需要把state置为true
dis[x]=0;
q.push({0,x});
}
for(int i=1;i<=k;i++){
int a=read(),b=read(),c=read();
add(a,b,c);
add(b,a,c);
}
dijkstra();
cout<<dis[t];
return 0;
}
和多源汇的区别：多源汇我们一次遍历后可任意查询图中任意两点间的距离，而超级源点的本质其实还是单源路径，我们只能得到源点到任意一点的距离（由于我们定义源点到起始点的距离为0，所以看起来好像有多个起点）
举一个例子，多源汇可以从任意一点开始，但如果我们超级源点把所有点都认为起点的话，我们最后得到的所有距离都将为0 。
周期
KMP
原理不太难但是方法很巧妙的一题
简单理解题意，求出s的每个前缀是否存在循环节，如果存在就输出最短的那个循环节的长度。
可以简单看一下，如果一个串存在循环节，那么它必然存在相同的前缀和后缀，当这个相同的前缀和后缀最长的时候，我们就得到了最短的循环节。这种相同的前后缀我们就要想到KMP中的PMT表。
也就是说，我们把字符串求出它的PMT，对于每一位，它的循环节就是\(i-nxt[i]\)，题目要求至少有两个且要求是完整的循环节，只需要判断上面求出的循环节长度能否整除\(i\)且和\(i\)不相等就可以了。
代码就是板子就不给出了。
装饰珠
背包dp，分组背包
如果把所有装备上的孔统一到一起看（因为在这里不同装备上配备的珠子并不影响它本身的作用效果），这题就可以转化为：我们一共有4个等级的背包，每个背包内可以装小于等于它等级的珠子。
我们再细想想，对于每种珠子，它装在背包里的总数量一定是相互排斥的，那么如果把每种珠子的数量看成一个分组，那么这题就可以看成一道分组背包问题。
但这里还有一个问题需要注意，低等级的珠子可以放在高等级的背包里，反之则不可以。如果我们枚举背包的时候从低等级的开始枚举，那么会出现当达到高等级背包的时候，它可以放进更低等级的珠子，但由于我们枚举问题而没有办法实现，为了解决这个问题，这题我们要从高等级的背包开始枚举。
此外还有一些需要注意的细节放在代码里面了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
const int N=1e4+10;
int m,cnt[10],val[N][10],f[310],num[N];
vector<int> lv[5];
//方便遍历每个等级的珠子
//注意这里加入一个等级的背包时只需要考虑和它相同等级的珠子就可以
int read(){
int i=0,j=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') j=-1;
ch=getchar();
}
while(isdigit(ch)){
i=i*10+ch-'0';
ch=getchar();
}
return i*j;
}
int dp(){
int tot=0,sum=0;
for(int i=4;i>0;i--){
sum+=cnt[i];
//枚举当前等级的珠子
for(auto it:lv[i]){
//先枚举体积再枚举种类就可以只用一维数组记录
//详情看分组背包
for(int j=sum;j>0;j--){
for(int k=1;k<=num[it];k++){
if(j>=k){
f[j]=max(f[j],f[j-k]+val[it][k]);
}
}
}
}
}
int ans=0;
for(int i=1;i<=sum;i++){
ans=max(ans,f[i]);
}
return ans;
}
int main(){
for(int i=1;i<=6;i++){
int t=read();
while(t--){
int x=read();
//记录不同等级背包的容量
cnt[x]++;
}
}
m=read();
for(int i=1;i<=m;i++){
int a=read(),b=read();
num[i]=b;
lv[a].push_back(i);
for(int j=1;j<=num[i];j++){
val[i][j]=read();
}
}
cout<<dp();
return 0;
}
C. Restore the Array
构造
想了好久
看完题解感觉还是没有很懂（崩溃）
参考了以下两篇题解
C. Restore the Array_向夕阳Salute的博客-CSDN博客
Codeforces Round 863 (Div. 3)__yxc___的博客-CSDN博客
先记录下等我再细品品（……）
D. Umka and a Long Flight
递归
初见的时候还以为是推公式之类的……完全没往递归上去想呃啊啊啊啊啊
翻译下题意，已知斐波那契数\(f\)其中\(f(0)=f(1)=1\)，我们有长\(f(n+1)\)宽\(f(n)\)的矩形，将其中位置为\((x,y)\)的方格固定，问该方格和剩下的方格能否形成\(n+1\)个边长为斐波那契数列的正方形，且要求边长相同的矩形不能超过2个。
稍微手推一下，很容易可以发现，每次我们从边长为\(f(n)\)的正方形开始构造，如果能构造出来，就继续下一个构造\(f(n-1)\)，不可以就结束，由此推出这题的递归。
但这题的判断条件相当有技巧（赛后发现是递归后自己写改了好久，最后无奈去参考了题解代码）
首先，结束条件是最好判断的，就是x=1且y=1。
接下来是其中的一些细节：
1. 每次减长度的时候一定是从长边减，并且**减完后得到的是小一级的斐波那契矩阵**，**原来的短边变成长边，原来的长边变成短边**。
1. 如果当前减去的长度是在固定格的右边或者下面，对固定格的坐标是不会造成影响的，但需要保证**固定格的坐标小于等于$f(c-1)$**，否则我们无法在固定格的右边得到我们想要的图形。
1. 如果是在固定格的上面或左边，固定格的坐标会变化。
由上面对应过来，可得：
1. 每次递归到下一层的时候要交换xy坐标，以保证长边永远位于矩形的长上，短边永远位于矩形的宽上，方便我们接下来的递归（不然上下左右什么的判别条件就太复杂啦）
1. 判断不能达到的条件就是当前长边大于$f(c-1)$但小于等于$f(c)$
至此这题就结束啦！
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
const int N=1e5+10;
const int M=1000000007;
ll n,x,y,f[50];
int read(){
int i=0,j=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') j=-1;
ch=getchar();
}
while(isdigit(ch)){
i=i*10+ch-'0';
ch=getchar();
}
return i*j;
}
bool check(int a,int b,int c){
if(a==1&&b==1) return true;//结束条件
if(b>f[c-1]&&b<=f[c]) return false;
//看看是否要减，但无论如何都记得翻转一下
if(b>f[c]) return check(b-f[c],a,c-1);
return check(b,a,c-1);
}
int main(){
int _=read();
f[0]=f[1]=1;
for(int i=2;i<=50;i++){
f[i]=f[i-1]+f[i-2];
}
while(_--){
n=read(),x=read(),y=read();
if(check(x,y,n)) printf("YES\n");
else printf("NO\n");
}
return 0;
}
E. Living Sequence
构造
非常巧妙的一题
简单翻译下题意，我们需要把数字中含有4的全部去掉后，重新排序，现在给出我们排序后的数字编号，输出它所对应的数字。
这题有个非常巧妙的方法，参考这位大佬的题解
Codeforces Round 863 (Div. 3) D~E - 知乎 (zhihu.com)
我们可以把题目看成一个有关进制的问题，我们知道，十进制中没有10，有十个数字，同理，九进制中没有9，有九个数字。我们需要构造的就是，我们如果把九进制中的各个数字的对应关系再换一下，就可以得到一个没有4的数字。
所以，我们可以先把题目给的数字转换成九进制表示，再对数字一个一个扫描，如果当前位数字大于4就+1。
代码非常简短。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
const int N=1e5+10;
const int M=1000000007;
ll n;
ll read(){
ll i=0,j=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') j=-1;
ch=getchar();
}
while(isdigit(ch)){
i=i*10+ch-'0';
ch=getchar();
}
return i*j;
}
string solve(){
string res;
while(n){
res+=n%9+'0';
n/=9;
}
reverse(res.begin(),res.end());
for(int i=0;i<res.length();i++){
if(res[i]>='4') res[i]++;
}
return res;
}
int main(){
int _=read();
while(_--){
n=read();
cout<<solve()<<endl;
}
return 0;
}
最后一点碎碎念：蓝桥杯的题目下周再整理吧，比完感觉省一悬了（崩溃)，积累经验明年再战吧……