牛客小白月赛37题解
写在前面的话
本次比赛总体难度不高,难度区间分布如下:
签到:J
简单:AFD
次简单:H
中等:IG
较难:BE
困难:C
level.0 J 喵
难度:1星(牛客标级)/ 700(cf标级)
知识点:字符串(strings)、模拟(implementation)
题目大意:给定一个字符串,输出其去掉末尾的子串 "nya" 得到的字符串。
思路:签到题,要注意每一行可能带的空格,输入请使用getline(cin,str)来读入。由于保证了数据的合法性,因此只需要输出每个字符串到倒数第四个字符即可。
附:不同语言的读入如下:
c++:
按空格和换行来分割字符串:
cin>>str;
按换行来分割字符串:
getline(cin,str);
java:
按空格和换行来分割字符串:
str=input.next();
按换行来分割字符串:
str=input.nextLine();
python:
由于python默认一次input是读入一行,因此作如下处理:
按空格和换行来分割字符串:
str=input().split() #最后会得到一个list,例如输入ab cd ef,会得到['ab','cd','ef']
按换行来分割字符串:
str=input() #会得到一个字符串
本题参考代码:
#include<bits/stdc++.h> using namespace std; int main(){ string s; getline(cin,s); for(int i=0;i<s.length()-3;i++)cout<<s[i]; }
level.1 A 经此一役小红所向无敌
难度:2星(牛客标级)/ 1000(cf标级)
知识点:数学(math)
题目大意:每回合小红受到 的伤害。对立受到 的伤害,光受到 的伤害。对立总血量为 ,光总血量为 。若对立和光不是同时死亡,则存活的一人对小红造成自身攻击力10倍的伤害。问小红受到的总伤害。
思路:我们可以先求出对立和光的存活回合数:对立的存活回合数为 , 光的存活回合数为 。
之后根据它们的大小进行分类讨论即可。
向上取整的技巧:
一般我们可以通过特判是否整除来求向上取整。不过c++语言可以灵活利用bool类型转int类型的性质(假为0,真为1),通过以下代码实现计算 :
int res=a/b+(a%b!=0); //计算a/b向上取整。
本题参考代码如下:
#include<bits/stdc++.h> using namespace std; #define ll long long int main(){ ll a,h,b,k; cin>>a>>h>>b>>k; ll c1=h/b+(h%b!=0),c2=k/a+(k%a!=0); ll rs=(a+b)*min(c1,c2); if(c1<c2)rs+=b*10; if(c1>c2)rs+=a*10; cout<<rs; }
level.2 F 红色和紫色
难度:2星(牛客标级)/ 1200(cf标级)
知识点:博弈论(games)
题目大意:给定一个 个方格组成的环,两人轮流染色,可以随意选择红色或紫色,但要求任何时刻都不能存在两个相同的颜色相邻。无法操作者输掉游戏。问双方都取最优策略时,先手胜还是后手胜。
思路:可以通过找规律发现 时后手必胜。下面给出证明:
当 的时候答案显然。
当 的时候,分奇偶两种情况讨论:
① 若 为偶数。
参考上图,当小红在某处染成红色或紫色时,紫只需要在她对面的位置染色即可(无论染红色或者紫色都可以获胜)。因为,这样下来构成了一个对称的状态,无论以后小红怎么染色,紫只需要在其对称的位置染同样的颜色即可,这样一定能保证小红是最先无法操作的。
② 若 为奇数。
参考上图,当小红在某处染成红色或者紫色时,紫只需要隔一个格子,染成和小红不同的颜色即可。目前的局面是,红色和紫色之间的格子不能再继续染色,而另一边一共有偶数个格子等待染色。由于相同的颜色不能相邻,因此剩下一定可以染偶数个格子(假设出现了一个紫-空-红的情况,那么一定会再出现一个空白来保证奇偶合拍,因为开头和结尾的颜色都已经固定了)。所以这种情况下依然是由紫来染最后一个颜色,紫获胜。
之所以这道题给了2星,是因为这道题可以通过找规律ac。如果要求推导过程,本题难度约为4星(牛客标级)/1800(cf标级)。
本题参考代码如下(python):
n=int(input()) if n==1:print("akai") else:print("yukari")
level.2 D 比那名居的桃子
难度:2星(牛客标级)/ 1300(cf标级)
知识点:前缀和(prifix sum)/ 队列(queue)
题目大意:给定一个 数组和一个 数组,求一个 使得 尽可能大,如果有多个最大值,要求 尽可能小。
思路:本题需要维护多个长度为 的区间和(显然区间长度 应该被取满,因为每个 都是正整数,取满一定更优)。维护方式有2个:前缀和或者队列。
方法1:前缀和。
我们定义
那么求 区间内的数之和,只需要求 即可。因为
方法2:队列
我们可以发现,当一个区间向右移动的时候,可以用一个队列来维护区间内的元素,每次向右移动一位,只需要让队尾入队一个元素、队首出队即可。因此单次移动的复杂度仅有 。
本题参考代码如下(前缀和解法):
#include<bits/stdc++.h> using namespace std; int a[100010],b[100010]; long long sum1[100010],sum2[100010]; int main(){ int n,i,j,k; long long s1=0,s2=0; cin>>n>>k; for(i=1;i<=n;i++){ cin>>a[i]; sum1[i]=s1+=a[i]; } for(i=1;i<=n;i++){ cin>>b[i]; sum2[i]=s2+=b[i]; } long long ma=0,mi=1e15,m1=k; for(i=k;i<=n;i++){ if(ma<sum1[i]-sum1[i-k]){ ma=sum1[i]-sum1[i-k]; mi=sum2[i]-sum2[i-k]; m1=i; } if(ma==sum1[i]-sum1[i-k]&&mi>sum2[i]-sum2[i-k]){ ma=sum1[i]-sum1[i-k]; mi=sum2[i]-sum2[i-k]; m1=i; } } cout<<m1-k+1; }
level.3 H 漂亮数
难度:3星(牛客标级)/ 1500(cf标级)
知识点:数论(number treory),前缀和(prefix sum)
题目大意:多次询问,求 到 区间内有多少个有且仅有2个素因子(可以相同)的数。
思路:先使用线性筛晒出 到 的所有素数,然后对所有素数进行两两组合即可标记出所有的“漂亮数”,然后做一个cnt的前缀和即可 查询。
复杂度为 ,其中 为 , 为 到 的素数数量。为 到 的素数数量。
本题参考代码如下:
#include<bits/stdc++.h> using namespace std; #define N 50000600 int num[N], prim[N]; int pn = 0; void table(){ memset(num, -1, sizeof(num)); for(int i = 2;i < N;i++){ if(num[i]) prim[pn++] = i; for(int j = 0;j < pn && 1LL*i*prim[j] < N;j++){ num[i*prim[j]] = 0; if(i % prim[j] == 0) break; } } } int dp[100010000]; int main(){ ios::sync_with_stdio(false); cin.tie(0); table(); int l,r,i,j; int n=1e8; for(i=0;prim[i]*prim[i]<=n;i++){ for(j=i;prim[i]*prim[j]<=n;j++){ dp[prim[i]*prim[j]]=1; } } for(i=1;i<=n;i++)dp[i]+=dp[i-1]; int t; cin>>t; while(t--){ cin>>l>>r; cout<<dp[r]-dp[l-1]<< '\n'; } }
level.5 I 加减
难度:4星(牛客标级)/1700(cf标级)
知识点:排序(sortings),前缀和(prefix sum),双指针(two pointers) / 二分(binary search)
题目大意:给一个数组,每次操作可以让一个数加一或者减一。问不超过 次操作后,数组中最多有几个数相等?
思路:显然优先变化尽量接近的数。所以可以先对数组进行排序。
引理:一个数组每次操作可以让一个数加一或者减一,使所有数都相等的操作最小次数的方式是所有数都变成中位数(或两个中间的数的任意一个,若共有偶数个数)。
证明:一个数组有 个数比中位数小, 个数(或 个数,若共有偶数个数)比中位数大,假设把所有数都变成中位数的总操作次数为 。这时如果让所有数变成比中位数更小的数,相当于对于 个数而言 ,操作次数变少了,但对于 个数而言 ,操作次数变多了同样的数值。总体来说操作次数一定是变多的。如果让所有数变成比中位数更大的数同理。证毕。
通过以上引理,我们只需要求出最大的一个区间,令其所有数都变成中位数的次数不超过 即可。区间内部的操作次数可以通过前缀和达成 查询。
如何求这个最大区间呢?有两个方法:二分答案或者双指针。
方法一:二分答案
很明显,一定存在一个数 ,满足至少存在一个长度为 的区间满足其所有数都变成中位数的次数不超过 次,且不存在一个长度为 的区间使得其所有数都变成中位数的次数不超过 次。那么这个 就满足可以用二分答案来求的性质。
复杂度:二分单次判断的复杂度为 ,总复杂度为
方法二:双指针
当固定左端点 时,我们可以找到右边第一个不合法的右端点 ,当 向右移动时, 也向右移动,移动到最新的第一次不合法的位置。维护 的最大值即可。
复杂度为 O(n)
本题参考代码如下(双指针法):
#include<bits/stdc++.h> using namespace std; #define ll long long ll a[100010],k,n; ll sum[100010]; int main(){ ll i,j,temp; cin>>n>>k; ll s=0; for(i=0;i<n;i++)cin>>a[i]; sort(a,a+n); for(i=0;i<n;i++)sum[i+1]=s+=a[i]; i=j=temp=0; ll res=0; for(i=0;i<n;i++)res+=abs(a[i]-a[n/2]); if(res<=k){ cout<<n; return 0; } ll ma=0; for(i=0;i<n;i++){ j--; do { j++; temp=(i+j)/2; res=(temp-i)*a[temp]-(sum[temp]-sum[i]); res+=sum[j+1]-sum[temp+1]-(j-temp)*a[temp]; } while (j<n&&res<=k); ma=max(ma,j-i); } cout<<ma; }
level.5 G 零一奇迹
难度:4星(牛客标级)/1600(cf标级)
知识点:模拟(implementation),双指针(two pointers) / 二分(binary search)
题目大意:给定一个01串(binary string),现在每次询问改变一个其中的字符后,有多少不包含前导零子串对应的十进制在 到 之间。
思路:当固定子串的左端点时,可以通过二分或者双指针来找到右端点的位置合法位置区间。
每次进行修改字符时,由于影响的子串最多只包含左右64位,只需要对这部分进行判断即可(判断改前和改后的合法子串数量)。
总复杂度 ,其中 , 为查询次数。
本题参考代码如下:
#include<bits/stdc++.h> using namespace std; #define ll long long string s; ll n,l,r; ll res=0; int jud(int l2,int r2){ int i,j=l2,k=l2; ll templ=0,tempr=0,tt=0; for(i=l2;i<=r2;i++){ if(s[i]=='1'){ while(templ<l&&j<=r2){ templ*=2; templ+=s[j]-'0'; j++; } while(tempr<=r&&k<=r2){ tempr*=2; tempr+=s[k]-'0'; k++; } if(j==r2+1&&templ<l)tt--; if(k==r2+1&&tempr<=r)tt++; tt+=k-j; templ-=1LL<<(j-i-1); tempr-=1LL<<(k-i-1); } } return tt; } void change(int x){ if(s[x]=='0')s[x]='1'; else s[x]='0'; } void gao(int x){ int l=max(0,x-64),r=min((int)s.length()-1,x+64); int op=jud(l,r); change(x); int ed=jud(l,r); res+=ed-op; } int main(){ ll i,j; cin>>n>>l>>r; cin>>s; ll temp; res=jud(0,n-1); ll q; cin>>q; while(q--){ int x; cin>>x; x--; gao(x); cout<<res<<endl; } }
level.6 B 擅长解密的小红同学
难度:5星(牛客标级)/1800(cf标级)
知识点:概率论(probability),组合数学(combinatorial mathematics)
题目大意:给定0~9每个数字的出现次数,每次猜测后正确答案的数字顺序将会重排。问第一次猜对的猜测次数期望。
思路:由于每次猜测后都会重排,所以每次猜测都是独立实验,设成功的概率为 。
那么次数的期望:
于是有
一式减二式:
因此
对于每次猜测,设数字不同组合的方案数为 ,单次猜测成功的概率是 ,最终的期望次数为 。
怎么求这个组合的方案数呢?我们可以这样想:假设不考虑重复,方案数为 。考虑重复的话,每个数字带来的要被除掉,所以最终答案是
注意这里的除法要用乘以逆元进行处理。
本题参考代码如下:
#include<bits/stdc++.h> using namespace std; #define ll long long ll a[101],dp[10001000]; int mod=1e9+7; ll power(ll a,ll b){ ll res=1; while(b){ if(b&1)res=res*a%mod; b>>=1; a=a*a%mod; } return res; } ll inv(ll x){ return power(x,mod-2); } int main(){ ll a,h,b,k,i,sum=0,x; dp[0]=1; for(i=1;i<=1e7;i++)dp[i]=dp[i-1]*i%mod; ll res=1; for(i=0;i<10;i++)cin>>x,sum+=x,res=res*inv(dp[x])%mod; res=res*dp[sum]%mod; cout<<res; }
level.7 E 小红蹦跳蹦跳
难度:5星(牛客标级)/2000(cf标级)
知识点:动态规划(dp)、前缀和(prefix sum)
题目大意:将 拆成一些数之和,要求不能有连续的两个奇数或连续的两个偶数。问有多少种方案数。对 取模。
思路:我们先考虑一般的递推形式。设 代表最后一步为偶数的方案数, 代表最后一步为奇数的方案数。那么我们可以得到如下的递推式:
①若 为奇数
代表最后一步加了个偶数形成了一个奇数,它的前一步必须是奇数,并且前一步的结尾必须是奇数结尾。
代表最后一步加了个奇数形成了一个奇数,它的前一步必须是偶数,并且前一步的结尾必须是偶数结尾。
②若 为偶数
代表最后一步加了个偶数形成了一个偶数,它的前一步必须是偶数,并且前一步的结尾必须是奇数结尾。
代表最后一步加了个奇数形成了一个偶数,它的前一步必须是奇数,并且前一步的结尾必须是偶数结尾。
这样得到的复杂度为 ,解决本题还是不够的。不过我们可以观察到,所有的偶数和奇数部分可以用前缀和加速达到 来解决。
本题参考代码如下:
#include<bits/stdc++.h> using namespace std; long dp[3030][2]; int mod=1e9+7; int main(){ int n,i,j; cin>>n; if (n == 1 || n == 2) { cout << 1 << endl; return 0; } long long c1,c2,c3,c4; //用四个变量分别储存4个前缀和。 c1=c4=1; c2=c3=0; /* 以下代码为O(n^2)的做法,可以通过n≤3000的样例。 for(i=1;i<=n;i++){ dp[i][i&1]=1; for(j=1;j<i;j++){ dp[i][i+j&1]+=dp[j][i+j+1&1]; dp[i][i+i&1]%=mod; } } cout<<(dp[n][0]+dp[n][1])%mod; */ for(i=3;i<n;i++){ if(i&1)c2+=c1,c2%=mod,c1+=c4+1,c1%=mod; else c4+=c3+1,c4%=mod,c3+=c2,c3%=mod; } if(n&1)cout<<(c1+c4+1)%mod<<endl; else cout<<(c2+c3+1)%mod<<endl; }
level.7 C 简单的三角形构造
难度:5星+(牛客标级)/ ?(cf标级)
知识点:计算几何(geometry)、构造(constructive algorithm)
题目大意:给定一个圆和圆内一个点 ,构造一个三角形满足三角形在圆内、点 在三角形外,并且三角形面积不小于
思路:我们可以先这么想,假设没有“点 在三角形外”的限制,可以构造的三角形面积最大是多少?
显然答案是圆内接正三角形。那么这道题首先就是要判断,能否构造一个圆内接正三角形满足 在三角形外部。
观察下图:
可以发现,只要 到圆心 的距离不小于 即可。
如果 怎么办呢?观察下图:
只需要构造一个等腰三角形,使得三角形的高为 的延长线即可。是否能构造成功取决于该三角形面积与 的大小比较。
因此三角形的构造方式如下:
若 ,那么连接 并延长,交圆于点 ,构造等边三角形即可。
否则,延长 交圆于点 ,以 为高构造等腰三角形。
本题参考代码如下:
#include<bits/stdc++.h> using namespace std; struct point { /* data */ double x,y; point(){} point(double x,double y):x(x),y(y){} }; double dis(point a){ return sqrt((a.x)*(a.x)+(a.y)*(a.y)); } double dis(point a,point b){ return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } point AB(point a,point b){ return point(b.x-a.x,b.y-a.y); } point dwh(point a){ double d=dis(a); return point(a.x/d,a.y/d); } int main(){ double r,s; point p,p0; cin>>r>>p.x>>p.y>>s>>p0.x>>p0.y; double d=dis(p,p0); double maxs=3.0/4*sqrt(3)*r*r; if (p0.x == p.x && p0.y == p.y) { maxs = r * r; if(maxs<s){cout<<-1;return 0;} point p1(p.x - r, p.y); point p2(p.x + r, p.y); point p3(p.x, p.y + r); printf("%.7f %.7f %.7f %.7f %.7f %.7f\n", p1.x, p1.y, p2.x, p2.y, p3.x, p3.y); return 0; } if(d*2<r){ double dd=sqrt(r*r-d*d); maxs=(r+d)*dd; } if(maxs<s){cout<<-1;return 0;} point vt=AB(p0,p); point dvt=dwh(vt); point p1(p.x+dvt.x*r,p.y+dvt.y*r); double dd; point dv1(dvt.y,-dvt.x); point dv2(-dvt.y,dvt.x); if(d*2<r){ dd=sqrt(r*r-d*d); point p2(p0.x+dv1.x*dd,p0.y+dv1.y*dd); point p3(p0.x+dv2.x*dd,p0.y+dv2.y*dd); printf("%.7f %.7f %.7f %.7f %.7f %.7f\n", p1.x, p1.y, p2.x, p2.y, p3.x, p3.y); } else{ dd=sqrt(3)*r/2; point pp(p.x+0.5*(p.x-p1.x), p.y+0.5*(p.y-p1.y)); point p2(pp.x+dv1.x*dd,pp.y+dv1.y*dd); point p3(pp.x+dv2.x*dd,pp.y+dv2.y*dd); printf("%.7f %.7f %.7f %.7f %.7f %.7f\n", p1.x, p1.y, p2.x, p2.y, p3.x, p3.y); } }