AC情况
整体体验
easy：ABFHL
mid：MJGC
hard：IDKE
心得
感觉出了一堆典题，少数题还有些意思，E题确实神仙
题解
A. 欢迎来到辽宁省赛（签到）
输出27
B. 胜率（枚举）
枚举分母到10000
F. 隔板与水槽（枚举）
枚举一下中间的隔板
H. 取石子（博弈 性质题）
和都是奇数，所以只和初始局面奇偶性有关
L. 区间与绝对值（莫队+树状数组）
莫队+树状数组维护增加/删除时对应贡献改变即可
n=q=1e5，4s，O(nsqrt(n)logn)还可以
M. 让二追三（概率期望）
n<5的情况输出0，n>=5的话，统计每个五连位置00111对答案个数的贡献，
有n-4个这样的五连位置，所以是(n-4)*p，其中p为出现00111的概率
J. 齐次递推公约数（反演 gcd fib性质）
类斐波那契数列性质，有f(gcd(i,j))=gcd(f(i),f(j))
所以只需要枚举gcd=d，统计gcd=d的(i,j)对数有多少对，
假设有x对，则对答案的贡献是f(d)*x
可以反演，这里用的是减掉d的倍数的方式，得到恰好等于d的方案数
G. 树上公约数（树的直径 ）
枚举gcd=d，将边权是d的倍数的边都连起来，得到对应森林
若森林里存在长度为k的路径，即森林的某棵树上存在长度>=k的直径
对于每棵树两遍搜索求直径，找到符合条件的最大的d，不存在输出-1
复杂度
C. 连环爆炸（dp）
题目链接：https://ac.nowcoder.com/acm/contest/68774/C
这个题还挺有意思的，出的挺好的，虽然三个ac的代码都是贪心骗过去的
按怪的先死到后死排序，这样就是无后效性，所以按血量增序排序，
假设我们已经获得了一些预制伤害值就可以顺利触发流程炸死所有怪，
但是不知道这个值具体是多少，所以把这个值存入dp值
按血量增序排序，
dp[i][j]表示前i个怪，手动消灭了j个，令前i个怪全死，还需要在开局预置的伤害数最少是多少
转移就是枚举第i个怪是手动爆的，
还是被前面的崩死的，
还是没崩死，需要开局再补充delta伤害
补题部分
D. 三角形打野（计算几何 叉积 三分）
题意
给定x轴正半轴，以及从原点出发的一条射线（在第一象限内），
以及两个点（保证这两个点在给定射线与x正半轴夹角范围内，而不在x轴或给定的射线上），
做一条直线AB，使得这条直线与x正半轴和给定射线组成的三角形将给定的两个点包含在内或边界上。
求满足条件的三角形的最小面积。
两点坐标可能相等，误差小于0.001即为正确
题解
太久不写计算几何感觉基础题都没什么思路，补的话感觉也只能用高中的思路写
手玩一下发现，所求直线AB和x轴的交点是在一个区间内，并且一定过其中至少一个点
记原来给的两个点为P、Q，作PX1平行射线交x轴于X1，作QX2平行射线交x轴于X2
左端点是X1和X2更靠右的那个，右端点可以设成一个很大的值，比如1e18
既然有当前x轴交点坐标，并且能取得最小值，所以凹函数，三分这个x的位置
将当前x轴交点X与P、Q分别连线，XP在XQ顺时针方向说明外侧是XP，否则是XQ
这个也画一下，就很显而易见
然后就是求外侧向量（不妨是XP）与射线的交点，求出交点后用叉积即可求得面积
代码
I. 元-神（单调栈 单调队列）
题意
题解
写到这个题的时间有点不够，感觉再手玩玩就玩出来了，诈骗题
考虑暴力怎么做，最暴力当然是从左往右迭代轮
稍微不那么暴力一点的暴力，是从右到左维护第i个值按时间序都可能是哪些值，是一条链表
但是链表的复杂度也是最坏的，
考虑最右的值只有一种，右数第二的值有两种，以此类推
如果拿第i个值暴力的和第i+1个值的链表上的值一个一个比，自然是的
称第i值为L，第i+1个值的链表上当前要比的值为R
1. 若c[L][R]=1，说明第i个值不会变成这个R，那么第i个值左侧的值有L的阻挡也不会变成R，可以把R从链表里删了
2. 若c[R][L]=1，说明第i个值是L的时候，会在这一轮被同化成R，那么把L加到R的前面，停止操作即可
由于比每次都是从链头比的，并且第i条链是从第i+1条链删掉若干次头结点后塞入元素L，
所以，实际是一个栈结构，单调栈维护即可，就是一个弹栈的过程，
弹到为空或出现第二种情况后，把L放入栈顶，此时栈底的元素就是经过若干轮后最终变成的元素
因为还要访问栈底，所以写的实际是个双端队列
代码
K. 稻妻扑克（大模拟，2024.10.26）
题目
https://ac.nowcoder.com/acm/contest/94343/Kt
题解
大模拟，按题意模拟即可
把70张牌先映射成0-69，按照题目约束对有加成的组加上系数
对应第二种选择，也就是选一张没出现过的牌的时候，加个剪枝，
因为手里有两张牌，所以剩下一张牌要么是X10，要么是X9，剩下的牌不用考虑
注意到有五张牌ABCDE的时候，先打ABC再打DE和先打DE再打ABC实际是一样的，
这里我们强制先打牌数多的，也就是先打3，再打2，再打1，
这样一个合法序列就只会被搜到一次，不加这个剪枝就会T成sb
当然严格的说，对于ABCD这种序列，先AB后CD和先CD后AB还是会搜两次，
但是已经减少了很多无效搜索了
另一个想法是，用二进制11111表示这5个数，
于是取1个数/2个数/3个数也就是得到当前数的子集，
用子集状态S和当前状态i差的二进制的位数去控制，
做一下子集dp即可，有点大炮轰蚊子了
代码（搜索）
代码2（状压）
E. 神-原（lucas定理 递归 极值点）
题目
思路来源
2023辽宁省赛E-CSDN博客
题解
纯纯神仙题，完全根据思路来源补的代码
虽然lucas的部分是暴力展开的，但是我极值取到的[l,r]就没求出来
虽然理论复杂度在p=2这是1e7左右，但是写的时候是瓶颈，实际提交的过程中一度TLE
最后想起来，p=2的时候，lucas定理的推论，n&m=m时C(n,m)%p=1，
加上之后就AC了，那一刻，真香！
代码
到此这篇nowcoder竞赛（nowcoder acm）的文章就介绍到这了,更多相关内容请继续浏览下面的相关推荐文章，希望大家都能在编程的领域有一番成就！版权声明：
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！
转载请注明出处，原文链接：https://www.xkablog.com/rfx/24682.html