2023蓝桥杯大学A组C++决赛游记+个人题解

Day0

发烧了一晚上没睡着，感觉鼻子被打火机烧烤一样难受，心情烦躁

早上6点起来吃了个早饭，思考能力完全丧失了，开始看此花亭奇谭

看了六集，准备复习数据结构考试，然后秒睡

一睁眼就是下午2点了

挂了个毛概课串讲，点了个外卖，吃完又睡着了

醒来就晚上8点了

然后又点了个外卖，复习了三章数据结构

就凌晨2点了，睡觉

Day1

7：40醒，被催着上了车，精神恍惚

然后开始考试

第一题

第一题就被难到了

分割圆形，以为是卡特兰数，但又觉得不一样

不给样例，题意也不是很清楚啊。。。

随便推了推

首先，连接相邻两个点的边（外圈）肯定得单独拿出来考虑，也就是2^n种外圈情况

然后设f[n]表示n边形内部划线不相交的方案数

简单推推得到f[n]=2*f[n-1]+Σf[i+1]*f[n-i+1]

f[3]=1;f[4]=3;.........

也不知道对不对，反正这么写了

最后好像是1392（可能是错的）

第二题

求2^(3^(4^(……^2023)))%2023

扩展欧拉定理

没什么好说的，背不到公式了

（翻了翻以前的博客）

 emm……犯了一个扩展欧拉定理的典型错误

没加phi(p)

所以答案好像是869？

后面补的代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int gcd(int x,int y){return !y?x:gcd(y,x%y);}
int phi(int n)
{int sum=0;for(int i=1;i<n;i++)if(gcd(i,n)==1)sum++;return sum;
}
int ksm(int x,int y,int m)
{int ret=1;while(y){if(y&1)ret=1ll*ret*x%m;x=1ll*x*x%m;y>>=1;}return ret;
}
int minksm(int x,int y,int m)
{int ret=1;while(y){if(y&1)ret=min(1ll*ret*x,1ll*m);x=min(1ll*x*x,1ll*m);y>>=1;}return ret;
}
const int mod=2023;
pair<int,bool> f(int n,int m)
{if(m==1)return pair(1,1);pair<int,int> p=f(n+1,phi(m));int b=p.first;if(p.second) b+=phi(m);printf("%d^%d\n",n,b);if(minksm(n,b,m)==m)return pair(ksm(n,b,m),1);return pair(ksm(n,b,m),0);
}
int main()
{printf("%d",f(2,2023).first);
}

（所以搞了40分钟填空题是一分没得是吧）

第三题

把长方形分割成小正方形，让小正方形的数量最多

寻找大于2的最小公因数（没错是最小）

然后直接除一除就结束了

第四题

给出L,R

求x+y=z算式的数目(L<=x,y,z<=R)

数学题，稍微推一推就好

这题极度阴间，小心爆你的longlong（针对某些特定的写法）

第五题

第K小的和

给两个数组A，B。

从A、B中各选一个数加起来，组成C数组，求C数组中第K小的数。

二分答案+two-pointers，注意边界条件的验证

第六题

相连的边

给出一棵带权树，选择相连的三条边，让他们的边权和最大。

首先这三条边只可能是一条链，或者是菊花图

菊花图直接对每个点的相连的边排序

把树定根后，链的情况分两种，一种是直链，一种是有LCA的链

直链的情况直接枚举每个点，向上走三步统计边权

有LCA的情况，其实是两种直链的情况加起来，一边直链长度是2，另一边是1

枚举长度为2的直链，即枚举每个点向上走两步，然后在爷爷节点选择除去走上来的边的最大邻接边即可

注意细节处理。

第七题

01游戏

题目保证有解

直接爆搜

剪枝很多，横竖相连三个不能相同，每行的01个数不超过一半，算完每行每列用二进制val值去重

从11点10写到11点40

最后时间10*10的全下划线不到0.5s

第八题

求一个字符串中长度为i的本质不同的子串的个数（i=1~n）

应该是SAM板题，可惜我背不到了，老了啊┭┮﹏┭┮

写了个双哈希n^2logn，能过4000都顶天了

第九题

求一棵树中距离为i的简单路径条数(i=L~R)

点分治板题，可惜我背不到了，老了老了

暴力n^2走人，居然还有40%

md，lqb出题这么这个样子？？？尽是出板题是吧？？？欺负我退役多年的老同志

第十题

本来只剩20分钟了，想着暴力也不是很好写，于是想了想正解，发现正解不难

状压DP，SPFA型转移

f[u][S][hp]表示当前在点u，存在怪兽的点的状态为S，当前血量为hp

很显然

(u,v)存在时：

if(S&(1<<v))

        f[v][S-(1<<v)][hp-cal(S,v)]=min(f[u][S][hp]+w(u,v))

else

        f[v][S][hp]=min(f[u][S][hp]+w(u,v))

然后就利用SPFA转移

最后答案应该是max(f[n-1][……][1~HP])

最后没写完，哪怕前面填空题不做也好啊，最后留个10~20分钟就搞定了，太菜了

总结

总之就是非常菜，简单题背不到公式，板题背不到板子，题目都写不完，太菜了。