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转移
最后答案应该是min(f[n-1][……][1~HP])
最后没写完,哪怕前面填空题不做也好啊,最后留个10~20分钟就搞定了,太菜了文章来源:https://www.toymoban.com/news/detail-478878.html
总结
总之就是非常菜,简单题背不到公式,板题背不到板子,题目都写不完,太菜了。文章来源地址https://www.toymoban.com/news/detail-478878.html
到了这里,关于2023蓝桥杯大学A组C++决赛游记+个人题解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!