2020-02-06 20:21 已编辑偶像大师灰姑娘女孩后端

关注

【题解】2020牛客寒假算法基础集训营第一场

注：每道题的参考cf难度分指codeforces.com对题目的难度评分（出题人自己估计）

写在题解前面的话

首先这次的题目难度并不大，大概是codeforces的div3水平（因为出题人rating只有1900太菜了QAQ）。比赛进行相对比较顺利，值得庆幸的是数据并没有出什么问题。
另外A题的样例描述有个小错误(坐标(3,2)写成了(3,3))，G题的题面容易引起歧义(“k个相同字母”)。
J题的测试样例仍然不够强，放过了部分错误代码。
这些都是我要检讨的，这里向大家说一声抱歉QAQ

J的样例已经加强，之前ac的童鞋们可以重新提交试试（不会影响排名）

J原来的标程也有错，不能通过加强后的样例，已更新标程。

level 1 hanayo和米饭

知识点： 数组循环

签到题。有多种方法可以做，最省事的方法是把每个数标记一下，然后遍历输出没标记的那个数就可以了。
参考cf难度分：700

level 1 kotori和bangdream

知识点：概率论

签到题。每个音符的得分期望是 $x\%*a+(100-x)\%*b$ ， $n$ 个音符的总得分期望为每个音符的期望乘以 $n$ 。
参考cf难度分：900

level 2 rin和快速迭代

知识点：数论模拟

只要会 $O($ $\sqrt{n}\$ $)$ 复杂度处理每一次迭代就行。是一道披着假数论的implementation
参考cf难度分：1000

level 3 eli和字符串

知识点：字符串前缀和双指针

可以单独处理每种字母找 $k$ 个的长度（双指针），然后求最小值。
或者也可以开26个前缀和，然后双指针找区间维护最小值。
参考cf难度分：1300

level 4 honoka和格点三角形

知识点：计数

可以把面积为 $1$ 的“好三角形”分为两类分开统计：两条边和两个坐标轴平行；只有一条边和某个坐标轴平行。
对于第一种情况，一定是 $1*2$ 或者 $2*1$ 的形式，一个 $1*2$ 的矩形中含有4个不同的三角形。总数是 $4*((n-2)*(m-1)+(m-2)*(n-1))$
对于第二种情况，可以分别统计底边为 $2$ 、高为 $1$ 和底边为 $1$ 、高为 $2$ 的情况。要注意底边靠近边界时的特殊讨论。
①对于底边为2，高为1的情况：
若底边和x轴平行，那么底边横向移动（指x轴水平移动，下同）有 $n-2$ 种可能，“对点”（指底边相对的点）的某一面选择有 $n-2$ 种可能（某一面选择，指的是底边固定的情况，对点在一条直线上移动所做出的选择），而底边纵向移动有 $m$ 种情况，其中有 $(m-2)$ 种情况对点可以选择两个面，2种情况对点只能选择一个面（当底边移动到格点阵边界的时候）。因此纵向移动折合为 $2*(m-2)+2$ ，即 $2*(m-1)$
以上可计算为 $2*(m-1)*(n-2)*(n-2)$
若底边和y轴平行，同理可推出 $2*(n-1)*(m-2)*(m-2)$
②对于底边为1，高为2的情况，推理方法和上面类似，请选手们自行推理。
参考cf难度分：1500

level 4 nozomi和字符串

知识点：字符串贪心

显然操作要么全1变0，要么全0变1。
分别处理两种操作即可。对于1变0的情况，可以分别统计每个1的前缀1和后缀1的位置（第一个1的前缀为 $0$ ，最后一个1的后缀为 $n+1$ ），那么 $k$ 次操作，即变换连续 $k$ 个1，最终的字符串长度就是第 $i$ 个1的前缀1到第 $i+k$ 个后缀1之间的距离。
对于0变1的情况同理。
参考cf难度分：1600

level 5 maki和tree

知识点：图论
经过一个黑点的路径有两种：两个端点都是白点；其中一个端点是黑点。
因此我们可以先预处理，将每个白点连通块上的白点个数统计出来。这样我们就可以得知每个黑点所连接的白点的权值（即连通块白点数）。
设某黑点连接了 $k$ 个白点，第 $i$ 个白点的权值为 $f(i)$ 。
这样第一种路径的数量为 $\mathop{ \sum }\limits_{{i=1}}^{{k}}{{\mathop{ \sum }\limits_{{j=i+1}}^{{k}}{f \left( i \left) *f \left( j \right) \right. \right. }}}$ ，第二种路径的数量为 ${\mathop{ \sum }\limits_{{i=1}}^{{k}}{f \left( i \right) }}$ 。第一种可以用前缀和处理达成 $O(k)$ 计算
参考cf难度分：1900

level 5 umi和弓道

知识点：计算几何双指针

首先确定umi所在位置的象限。很明显同一象限的点是不可能用挡板挡掉的，对于剩下的点找出线段和 $x$ 轴或 $y$ 轴的交点，统计坐标位置（如果存在交点的话）。
之后双指针维护 $x$ 轴上或者 $y$ 轴挡住 $n-k$ 个点的挡板长度最小值。注意 $x$ 轴和 $y$ 轴要分开计算。
参考cf难度分：2000

level 5 nico和niconiconi

知识点：动态规划

计 $dp[i]$ 代表前 $i$ 个字符的计数最大值。
那么可得转移方程：

$if(substring(i-3,i)==nico)then$ $dp[i]=max(dp[i],dp[i-4]+a)$
$if(substring(i-5,i)==niconi)then$ $dp[i]=max(dp[i],dp[i-6]+b)$
$if(substring(i-9,i)==niconiconi)then$ $dp[i]=max(dp[i],dp[i-10]+c)$

最后输出 $dp[n]$ 即可。
参考cf难度分：1800

level 6 μ's的影响力

知识点：数论矩阵快速幂

显然 $f(n)$ 可以用 $x$ , $y$ 和 $a$ 这三个因子表达出来。
每一项a的幂次分别是 $0、0、b、2b、4b、7b、12b……$ 从第三项开始每一项为前两项之和加1。
而x和y的幂次构成斐波那契数列：x的幂次第一项是1，第二项是0；y的幂次第一项是0，第二项是1。之后每一项均为前两项之和。
根据费马小定理，由于1e9+7是素数，有 ${a\mathop{{}}\nolimits^{{1e9+6{\text{ }}}} \equiv 1 \left( mod\text{ }1e9+7 \right) }$ 。因此幂的指数对1e9+6取模即可。要注意a是1000000007的倍数的特殊情况。
可以用矩阵快速幂O(logn)求出x、y、a幂次的第n项。
矩阵快速幂求斐波那契数列的第n项方法如下:
假设 $f(i)$ 代表斐波那契数列的第 $i$ 项，显然有：
$图片说明$
因此
$图片说明$
而 $图片说明$ 的值可以用快速幂算出来，这样就可以O(logn)实现计算斐波那契数列的第n项了。
有关快速幂的知识：
要求 $a^b$ mod p，我们可以得出
①若b为偶数， $a^b=({a^{b/2}})^2$
②若b为奇数， $a^b=({a^{(b-1)/2}})^2*a$
可以看到幂是指数级别下降的，因此最终复杂度是 $O(logn)$ 而不是朴素算法的 $O(n)$
参考cf难度分：2200

标程：

全部评论

推荐最新楼层

肖战公关团队

没上过大学 C++

感觉F题的数据有点水，如果这样生成的数据能让 https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42775397 tle。上面的做法是抠掉所有的黑色节点，然后对每一个黑色节点都进行dfs，下面这组数据所有的白色节点在每一次dfs的时候都会被找一遍，从而卡掉上面的做法。 #include<bits/stdc++.h> using namespace std; int main() { // freopen("test.txt", "w", stdout); int n = 32222 << 1; cout << n << "\n"; for(int i = 1; i <= n / 2; i++) cout << "W"; for(int i = 1; i <= n / 2; i++) cout << "B"; cout << "\n"; for(int i = 1; i < n / 2; i++) cout << i << " " << i + 1 << "\n"; for(int i = n / 2 + 1; i <= n; i++) cout << 1 << " " << i << "\n"; } 加上这样的数据会更好一点。

3 回复分享

发布于 2020-02-04 20:14

三金老师

荔枝FM_交易技术部_Java 工程师

请问A题中在题解中所提到的特殊情况比如说统计边平行与x轴时 s=(s+2*(n-1)*(m-2)%mod*(m-2)%mod+2*(m-1)*(n-2)%mod*(n-2)%mod)%mod; 为何是（m-2）以及（n-2)

2 回复分享

发布于 2020-02-04 20:11

QieQiemin

东南大学 C++

个人感觉 level 5 nico和niconiconi 在CF里大概1600

2 回复分享

发布于 2020-02-04 18:09

Emcikem

浙江工商大学 Java

请问j题矩阵快速幂时，为什么要特判判断下面的条件 if(x % mod == 0 || y % mod == 0 || a % mod == 0){ printf("0\n"); return; } 可以给一下这个特判数据吗

1 回复分享

发布于 2020-02-05 15:58

win_the_medal

银山小学

A题第二种情况的规律是什么

1 回复分享

发布于 2020-02-04 19:04

FriedChicken

北京理工大学算法工程师

F题这个做法是传说中的dsu on tree吗（无知脸）

1 回复分享

发布于 2020-02-04 19:03

塔子哥学算法

Fleet AntiSubmarine Warfare Training Center (San Diego) C++

J题b的规律找错了。。。手速还是太慢了吖

1 回复分享

发布于 2020-02-04 18:27

NotDeep

中国戏曲学院算法工程师

maki和tree 这个题时间复杂度应该是多少呢。

点赞回复分享

发布于 2020-03-03 20:36

Boops

西南大学 C++

G题使用双指针不会超时吗，复杂度为O(N^2)啊

点赞回复分享

发布于 2020-02-18 11:34

1914010219，宁文语

哈尔滨理工大学 Java

#define ll long long ll f(ll x){ //求x的因子个数 ll i,res=0; for(i=1;i*i<x;i++){ if(x%i==0)res+=2; } returnres+(i*i==x); } ，，楼主.，请问这个ll是干嘛的还有if(x%i==0)res+=2这步

点赞回复分享

发布于 2020-02-06 19:31

ngwz

门头沟学院算法工程师

"01"串是0和1相邻的吗，为什么 16 2 1101110000110111 这组数据应该答案是12，而用标程是7

点赞回复分享

发布于 2020-02-06 11:56

wdnmdwdnmd

门头沟学院 C++

请问下c题为什么我初始点设为int就wa。。double就过了啊。。

点赞回复分享

发布于 2020-02-05 22:21

OerUUU

门头沟学院前端工程师

我以为F题正解是换根dp呢

点赞回复分享

发布于 2020-02-05 20:29

三金老师

荔枝FM_交易技术部_Java 工程师

你好 J题的变种矩阵想请教一下是怎么出来的

点赞回复分享

发布于 2020-02-05 19:10

Bazoka13

东北育才学校后端

J卡在72.73%了，求助😭 #include<bits/stdc++.h> using namespace std; typedef long long ll; #define mod 1000000007 #define maxn 120 #define bite_the_dust continue #define king_crimson break struct matrix{ ll m[maxn][maxn]; }; matrix matrix_mul(matrix a,matrix b,int n){ matrix c; for (int i = 0; i <n ; ++i) { for (int j = 0; j <n ; ++j) { c.m[i][j]=0; } } for (int i = 0; i <n ; ++i) { for (int j = 0; j <n ; ++j) { for (int k = 0; k <n ; ++k) { c.m[i][j]=c.m[i][j]+(a.m[i][k]%mod*(b.m[k][j]%mod))%mod; } c.m[i][j]%=mod; } } return c; } matrix slow_pow(int n,matrix a,ll pow){ matrix b; for (int i = 0; i <n ; ++i) { for (int j = 0; j <n ; ++j) { if(i==j)b.m[i][j]=1; else b.m[i][j]=0; } } while(pow){ if(pow&1)b=matrix_mul(b,a,n); a=matrix_mul(a,a,n); pow>>=1; } return b; } ll guisu_pow(ll a,ll pow){ ll ans=1; while(pow){ if(pow&1)ans=(ans%mod*(a%mod))%mod; a=((a%mod)*(a%mod))%mod; pow>>=1; } return ans%mod; } int main() { ll n,x,y,a,b; cin>>n>>x>>y>>a>>b; if(x%mod==0||a%mod==0||y%mod==0){ cout<<0; return 0; } matrix dd,gg; dd.m[0][0]=0;dd.m[0][1]=1; dd.m[1][0]=1;dd.m[1][1]=1; gg.m[0][0]=0;gg.m[0][1]=1;gg.m[0][2]=0; gg.m[1][0]=1;gg.m[1][1]=1;gg.m[1][2]=1; gg.m[2][0]=0;gg.m[2][1]=0;gg.m[2][2]=1; dd=slow_pow(2,dd,n-1); gg=slow_pow(3,gg,n-1); ll px=dd.m[0][0]%1000000006,py=dd.m[0][1]%1000000006,pa=(gg.m[0][2]%1000000006*(b%1000000006))%1000000006; cout<<(guisu_pow(x%mod,px)%mod*(guisu_pow(y%mod,py)%mod)*(guisu_pow(a%mod,pa)%mod))%mod; return 0; }

点赞回复分享

发布于 2020-02-05 18:49

就离谱怎么还不AC

四川师范大学 C++

level 4 honoka和格点三角形这个题第一种那个矩形的个数是怎么推出来的呀，为什么是（m-2）*(n-1)，是找规律还是？

点赞回复分享

发布于 2020-02-05 18:18

IULeeJiEun

上海第二工业大学游戏后端

为什么要mod-1啊

点赞回复分享

发布于 2020-02-05 17:45

Peterliang

南昌大学 golang

楼主，J题看不懂代码啊，函数太多，可以说一下几个关键

函数的作用是什么吗？

点赞回复分享

发布于 2020-02-05 17:43

sywVivian

湖北经济学院 Java

H题为何只能通过40%的测试数据😂 #include <bits/stdc++.h> using namespace std; vector<int> v0, v1; int main() { int n, k; string s; int ans = 0; cin >> n >> k; cin >> s; for (int i = 0; i < n; i++) { if (s[i] == '0') { v0.push_back(i); } else { v1.push_back(i); } } if (k >= v0.size()) { ans = n; } else { for (int i = 0, j = 1; i < v0.size(); i++) { j = i + 1; while (v0[j] - v0[i] - 1 < k) { j++; } if (v0[j] - v0[i] - 1 == k) { ans = max(ans, v0[j] - v0[i] + 1); } else { ans = max(ans, v0[j - 1] - v0[i] + 1); } } } if (k >= v1.size()) { ans = n; } else { for (int i = 0, j = 1; i < v1.size(); i++) { j = i + 1; while (v1[j] - v1[i] - 1 < k) { j++; } if (v1[j] - v1[i] - 1 == k) { ans = max(ans, v1[j] - v1[i] + 1); } else { ans = max(ans, v1[j - 1] - v1[i] + 1); } } } cout << ans << endl; return 0; }

点赞回复分享

发布于 2020-02-05 17:02

998244353

门头沟学院后端

C题标程取连续k个点是什么意思。。题目不是说使得射中的数量小于等于k，那不是要遮住连续n-k个点吗？

点赞回复分享

发布于 2020-02-05 16:15