2021-04-24 23:25 已编辑长沙学院 C++

关注

题解 | #小圆前辈去上学#

小圆前辈去上学

https://ac.nowcoder.com/acm/contest/15332/A

小圆前辈去上学

https://paste.ubuntu.com/p/cXP69W222X/

题解：签到题，字符串存取，判断一下小数点后第一位数即可，为5即以上进位，或者直接用long double。

小圆前辈的素数

https://paste.ubuntu.com/p/ZbQvcKv8hC/

题解：容易看出一种会超时的 $O(n*m)$ 的解法，所以需要考虑优化，我们可以把相同的数用一个cnt数组统计在一起，然后开始组合，举个例子，假如统计出第一个数组中1的个数为5，第二个数组中2的个数为3，那么第一个数组中1和第二个数组中2组合成为素数3的个数就为 $5*3=15$ 个。有了这个基础后观察发现对于复杂度的优化并没有什么实质性的优化，但是这样的运算规则可以映射到多项式中去，两个数之间组合例如1+2可以看作是多项式相乘中，指数的相加，5*3就可以看作是多项式乘法中系数相乘，这样的话对于每一项的组合我们都可以映射到多项式的运算中去，前面的例子就是第一个多项式中 $5x^1$ 这一项与另一个多项式中 $3x^2$ 这一项相乘得到 $15x^3$ 。可以把两个数组中每一项都这样搞，然后两个多项式相乘后得到的结果中指数为素数的项的系数之和就是答案。然后你就会发现，这样的做法仍然是 $O(n^2)$ 的，但是问题可以映射到多项式上其实就会衍生出很多接发，因为前人提出了许多多项式之间计算的性质，这道题应用的就是FFT(快速傅立叶变换)。我们知道，多项式乘法的时间复杂度是 $O(n * m)$ 的，因为我们平时使用的多项式是属于一种系数表达式，如果用另一种表达方式来作乘法的话时间复杂度就可以达到 $O(n)$ ，这种表达方式就是点值表达式，我们现在需要做的就是把系数表达式转换为点值表达式，这个过程就称为傅立叶变换，具体可以百度，就不在这里赘述。快速傅立叶变换的时间复杂度是 $O(log_2^n)$ 的，所以整道题的时间复杂度就是 $O(n*log_2^n)$ 。

小圆前辈去爬山

https://paste.ubuntu.com/p/rMXTPQ6NXZ/

题解：首先floyd预处理两点间最短距离，之后可以利用单调性处理最短距离后对每次二分求答案，也可以将询问离线，对于每个查询的id按费用排序乱搞。

小圆前辈的魔法

https://paste.ubuntu.com/p/dVfkDqB3yP/

题解：线段切割三角形有以下两种情况：

PNG图像-37F2BFF5B02C-1

第一种就是经过三角形的一个顶点，切出来的两个图形就都是三角形，另一种情况线段只经过三角形的两条边，会切出一个三角形和一个四边形。

我们分两种情况来讨论：第一种情况就把两个三角形的面积求出来取min输出，第二种就是找出与切割点形成三角形的点，计算出面积与总面积减去这个三角形的面积取min输出即可。其中涉及了判断线段相交、求线段交点、求凸包面积等知识点，可以自行学习补充。或者直接套用线段切割凸包的模版也可直接AC

小圆前辈的排列组合

https://paste.ubuntu.com/p/HC5zp8s6rP/

题解：素数筛后，取出素数位的字符，有2个C，1个S，1个U输出YES。

小圆前辈的暴力枚举

https://paste.ubuntu.com/p/3pzJTsbkG3/

题解：排列组合问题，n,m为两条边，令x=min(n,m)，答案为

C(n,0) * A(m,0)+C(n,1) * A(m,1)+...+C(n,x) * A(m,x)

相当在棋盘上放0个，1个，2个...x个棋子方案数之和，对于放k个棋子，我们可以理解为从n行中取出k行，从m列中取k行来放棋子，对于第一行的棋子有m种放法，第二行有m-1种放法，即再乘上全排列即可。

小圆前辈的数组Ⅱ

https://paste.ubuntu.com/p/824TV3f2tY/

题解：要求通过打表或常识得知，对于1e5以下的所有数的因子不超过100，同时我们在dp转移时只需要知道最大值即可，所以我们在转移前可先用线段树将当前数因子覆盖，然后区间最大值+1就是当前转移的最大值，再将覆盖的操作还原。

小圆前辈的数组

https://paste.ubuntu.com/p/2VY3vPFcwx/

处理前缀和 $pre_i$ ，由于是要找所有数和为 $k$ 的倍数的数，我们对于每个 $pre_i \%k$ ,当 $pre_i=pre_j$ ， $i<j$ 时，则 $(\sum_{i}^j a[i]) \%k=0$ 。及区间[l,r]的和为k的倍数。这就能找到满足第一个条件的区间。

要满足第二个条件，我们要将pre相等的放进vector里面二分，即枚举 $pre_i$ ,二分查找，有多少个数小于等于 $pre_i-z$ ，即满足和大于等于为k。

小圆前辈的博弈

https://paste.ubuntu.com/p/TFPcnmvyHY/

题解：字典树板题，将T串的所有后缀插入字典树，用S串的所有后缀去查匹配失败的总次数就是答案。

小圆前辈的异或树

https://paste.ubuntu.com/p/ZQ7r9ByCTs/

题解：可用树上启发式合并（或点分治）+字典树解决。在dfs过程中，用当前链的权值去跑字典树查最大值更新答案，子树枚举完后再将贡献插入字典树。

小圆前辈的888

https://paste.ubuntu.com/p/5ZHDWmFrwg/

题解：数位dp，利用两个记忆化搜索解决，一个处理当前位取x时最后一位是8的方案数，一个计算处理当前为取x时产生的价值贡献，很明显每一位的贡献就是其x*取x时最后一位为8的方案数。

全部评论

推荐最新楼层

❤由比滨结衣❤

网易互娱_引擎开发

为啥我I题这样写错了，还有这个组合数：fac[n]*inv(fac[m])%mod*inv(fac[n-m])%mod;，这个是啥意思emmm 我的组合数是这么写的： ll C(ll x){ return fac[n] / fac[x] / fac[n - x]; } //以下为源码 #include <iostream> using namespace std; const int N = 1005; typedef long long ll; const int mod = 998244353; ll n, m; ll fac[N]; ll C(ll x){ return fac[n] / fac[x] / fac[n - x]; } ll A(ll x){ return fac[m] / fac[n - x]; } void init(){ fac[0] = 1; for(int i = 1; i < N; i++){ fac[i] = fac[i - 1] * i % mod; } } int main(){ init(); cin >> n >> m; ll ans = 0; ll t = min(n ,m); for(ll i = 0; i <= t; i++){ ans += C(i) * A(i) % mod; ans %= mod; } cout << ans; return 0; }</iostream>

点赞回复分享

发布于 2021-04-24 23:59

欠我半块小饼干

长沙学院 C++

一人血书代码来点注释┭┮﹏┭┮

点赞回复分享

发布于 2021-04-25 00:11