本文共 8934 字,大约阅读时间需要 29 分钟。
2020牛客寒假算法基础训练营1
A.honoka和格点三角形(计数)
题意:给定n*m个格点构造出的矩阵,问最多可以构造出多少个面积为1的三角形
题解:直接计数,讨论所有情况即可,注意乘法取模
代码:
#include #include #include #include #include #include #include #include #include
B.kotori和bangdream(期望)
题意:每次有x%的概率获得a分,剩下的概率获得b分,一共进行n次,求得分期望
题解:结果是ans = (x%a+(1-(x%))b)*n
代码:
#include #include #include #include #include #include #include #include #include
C.umi和弓道(双指针)
题意:给定一个起始坐标和一群坐标,这些坐标一定不在坐标轴上,现在需要在x轴或y轴设立一个挡板,这个挡板会遮蔽其他坐标和起始坐标的连线,要求遮蔽后最多只有k个点可以连通起始坐标,求这个挡板最短的长度
题解:分两种情况讨论,挡板在x轴上或在y轴上,将其他坐标与起始坐标的连线在x轴和y轴的交点分别记录下来,维护一个挡板长度的最小值,用双指针扫描
代码:
#include #include #include #include #include #include #include #include #include
D.hanayo和米饭(暴力)
题意:1,2,3...n这n个数会给你n-1个,让你把那个没给你的数输出
题解:直接暴力
代码:
#include #include #include #include #include #include #include #include #include
E.rin和快速迭代(数论)
题意:给定一个数x,函数f(x)的值为x的因子个数,若当前的f(x)不为2,则继续进行f(f(x)),直到f(x)为2,求此时的计算次数
题解:本质上就是利用O(\(\sqrt{n}\))的积性函数\(\tau\)(n)暴力枚举出结果判断即可
\(\tau\)(n)函数表示的是正整数n的所有正因子个数,设n的质因子分解为n=\(p_1^{a_1}\)*\(p_2^{a_2}\)......\(p_s^{a_s}\),那么可以得出
\[\tau(n) = (a_1+1)*(a_2+1)*...*(a_s+1) = \prod_{j=1}^s(a_j+1)\]
代码:
#include #include #include #include #include #include #include #include #include
F.maki和tree(并查集)
题意:给定一个n个点n-1条边的树,每个点为“W”白色或“B”黑色,问可以构成多少条两点之间只有一个黑色点的简单路径。、
题解:经过一个黑点的简单路径有两种,一种是路径两端都是白点,一种是有一端是黑点,我们统计每个白色连通块的权值,然后通过统计每个黑点相邻白点的权值和求出第二种的路径,对于第一种的路径,假设1个黑点有k个相邻白点,第一种路径就是从第1个白点开始,剩余的白点权值总和与当前白点的乘积,即
\(\sum_{i=1}^{k}\sum_{j=i+1}^kf(i)*f(j)\)
代码:
#include #include #include #include #include #include #include #include #include
G.eli和字符串(字符串,双指针)
题意:给定一个字符串,要求截取一个最短的子串,这个子串至少包含k个相同的字符
题解:利用map存放每一个字符在字符串中的下标,当前字符数量满足k时调出区间长度维护最小值即可
代码:
#include #include #include #include #include #include #include #include #include
H.nozomi和字符串 (字符串,尺取法)
题意:给定一个01串,最多可以修改k次,仅限将0改为1,1改为0,问这个01串中最长连续子串是多长
题解:尺取维护k次修改区间
代码:
#include #include #include #include #include #include #include #include #include
I.nico和niconiconi(线性DP)
题意:给定长度为n的字符串,子串nico权值为a,子串niconi权值为b,子串niconiconi权值为c,求这个字符串的最大权值,子串不可重复使用
题解:dp即可,计dp[i]表示前i个字符的最大权值,那么有转移方程
if(substring(i-3,i))==nico,dp[i] = max(dp[i-4]+a.dp[i])
if(substring(i-5,i))==nico,dp[i] = max(dp[i-6]+b.dp[i])
if(substring(i-9,i))==nico,dp[i] = max(dp[i-10]+c.dp[i])
最后输出dp[n]即可
代码:
#include #include #include #include #include #include #include #include #include
J.u's的影响力(矩阵快速幂,费马小定理)
题意:给定n,x,y,a,b,设f(1) = x,f(2) = y,之后为f(i) = f(i-1) * f(i-2) *\(a^b\),让你求f(n)的值,结果%1e9+7。
题解:通过观察你会发现表达式由x,y,a三个因子组成,且x和y的幂数都构成斐波那契数列,而a的幂数则是斐波纳契数列的变种,这时候很容易就想到利用矩阵快速幂去解决这个问题。利用费马小定理进行降幂处理,因为%的1e9+7是一个质数,所以对于不等于1e9+7的数字a来说,\(a^{1e9+6} \equiv (1 mod 1e9+7)\),这样可以对x,y,a的系数进行降幂,而它们的系数则有矩阵快速幂递推公式求出。复杂度为O(logn)
代码:
#include #include #include #include #include #include #include #include #include
转载地址:https://www.cnblogs.com/cloudplankroader/p/12266996.html 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!