【题解】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

知识点:概率论

签到题。每个音符的得分期望是 个音符的总得分期望为每个音符的期望乘以
参考cf难度分:900

level 2 rin和快速迭代

知识点:数论 模拟

只要会 复杂度处理每一次迭代就行。是一道披着假数论的implementation
参考cf难度分:1000

level 3 eli和字符串

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

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

level 4 honoka和格点三角形

知识点:计数

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

level 4 nozomi和字符串

知识点:字符串 贪心

显然操作要么全10,要么全01
分别处理两种操作即可。对于10的情况,可以分别统计每个1的前缀1和后缀1的位置(第一个1的前缀为 ,最后一个1的后缀为 ),那么 次操作,即变换连续 1,最终的字符串长度就是第 1的前缀1到第个后缀1之间的距离。
对于01的情况同理。
参考cf难度分:1600

level 5 maki和tree

知识点:图论
经过一个黑点的路径有两种:两个端点都是白点;其中一个端点是黑点。
因此我们可以先预处理,将每个白点连通块上的白点个数统计出来。这样我们就可以得知每个黑点所连接的白点的权值(即连通块白点数)。
设某黑点连接了 个白点,第 个白点的权值为
这样第一种路径的数量为,第二种路径的数量为。第一种可以用前缀和处理达成 计算
参考cf难度分:1900

level 5 umi和弓道

知识点:计算几何 双指针

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

level 5 nico和niconiconi

知识点:动态规划

代表前 个字符的计数最大值。
那么可得转移方程:



最后输出 即可。
参考cf难度分:1800

level 6 μ's的影响力

知识点:数论 矩阵快速幂

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

标程:

A: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42786029
B:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42786046
C:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42786057
D:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42786062
E:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42786070
F:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42786077
G:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42786086
H:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42786091
I:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42786097
J:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42789798

全部评论
感觉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
请问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
个人感觉 level 5 nico和niconiconi  在CF里大概1600
2 回复 分享
发布于 2020-02-04 18:09
请问j题矩阵快速幂时,为什么要特判判断下面的条件 if(x % mod == 0 || y % mod == 0 || a % mod == 0){ printf("0\n"); return; } 可以给一下这个特判数据吗
1 回复 分享
发布于 2020-02-05 15:58
A题第二种情况的规律是什么
1 回复 分享
发布于 2020-02-04 19:04
F题这个做法是传说中的dsu on tree吗(无知脸)
1 回复 分享
发布于 2020-02-04 19:03
J题b的规律找错了。。。手速还是太慢了吖
1 回复 分享
发布于 2020-02-04 18:27
maki和tree 这个题时间复杂度应该是多少呢。
点赞 回复 分享
发布于 2020-03-03 20:36
G题使用双指针不会超时吗,复杂度为O(N^2)啊
点赞 回复 分享
发布于 2020-02-18 11:34
#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
"01"串是0和1相邻的吗,为什么 16 2 1101110000110111 这组数据应该答案是12,而用标程是7
点赞 回复 分享
发布于 2020-02-06 11:56
请问下c题为什么我初始点设为int就wa。。double就过了啊。。
点赞 回复 分享
发布于 2020-02-05 22:21
我以为F题正解是换根dp呢
点赞 回复 分享
发布于 2020-02-05 20:29
你好 J题的变种矩阵 想请教一下是怎么出来的
点赞 回复 分享
发布于 2020-02-05 19:10
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
level 4 honoka和格点三角形 这个题第一种那个矩形的个数是怎么推出来的呀,为什么是(m-2)*(n-1),是找规律还是?
点赞 回复 分享
发布于 2020-02-05 18:18
为什么要mod-1啊
点赞 回复 分享
发布于 2020-02-05 17:45
楼主,J题看不懂代码啊,函数太多,可以说一下几个关键函数的作用是什么吗?
点赞 回复 分享
发布于 2020-02-05 17:43
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
C题标程取连续k个点是什么意思。。 题目不是说使得射中的数量小于等于k,那不是要遮住连续n-k个点吗?
点赞 回复 分享
发布于 2020-02-05 16:15

相关推荐

02-25 11:29
产品经理
牛客444597598号:兄弟 我只能说如果想找产品经理这种简历 基本就是毕业失业了 你这连实习都找不到的 简历跟产品经理一点都没有关系,你可以去搜搜产品的模版吧
点赞 评论 收藏
分享
03-31 18:02
门头沟学院 Java
白日梦想家_等打包版:不要的哦佛给我
点赞 评论 收藏
分享
评论
44
56
分享

创作者周榜

更多
牛客网
牛客企业服务