神崎兰子

2021-11-16 12:32 已编辑偶像大师灰姑娘女孩后端

关注

【题解】牛客小白月赛37

写在前面的话

本次比赛总体难度不高，难度区间分布如下：
签到：J
简单：AFD
次简单：BH
中等：I
较难：EG
困难：C

另外，由于我们的失误，H题空间出了一些问题，导致C/C++以外的语言无法通过，在这里表示道歉~（内存虽然开了2G，但由于oj平台后台设置问题，导致仍然会报错）

请大家务必注意比赛的诚信问题，我们会对代码进行查重，一但发现代码抄袭，我们会实施以下惩罚：

首次作弊：取消本次比赛rating上升并倒扣200分。即本次比赛前rating为 $x$ ，比赛后rating为 $y$ ，那么我们会将 rating 扣为 $min(x,y)-200$

再次作弊：直接封停账号

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)

题目大意：每回合小红受到 $a+b$ 的伤害。对立受到 $b$ 的伤害，光受到 $a$ 的伤害。对立总血量为 $h$ ，光总血量为 $k$ 。若对立和光不是同时死亡，则存活的一人对小红造成自身攻击力10倍的伤害。问小红受到的总伤害。

思路：我们可以先求出对立和光的存活回合数：对立的存活回合数为 $\lceil \frac{h}{b} \rceil$ ，光的存活回合数为 $\lceil \frac{h}{b} \rceil$ 。

之后根据它们的大小进行分类讨论即可。

向上取整的技巧：

一般我们可以通过特判是否整除来求向上取整。不过c++语言可以灵活利用bool类型转int类型的性质（假为0，真为1），通过以下代码实现计算 $\lceil \frac{a}{b} \rceil$ ：

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)

题目大意：给定一个 $n*m$ 个方格的矩阵，两人轮流染色，可以随意选择红色或紫色，但要求任何时刻都不能存在两个相同的颜色相邻。无法操作者输掉游戏。问双方都取最优策略时，先手胜还是后手胜。

思路：可以证明：当且仅当 $n$ 和 $m$ 都是奇数时，小红可以获胜。否则一定是紫获胜。

证明如下：

如果 $n$ 和 $m$ 都是奇数，那么 $n*m$ 是奇数，存在一个中心的方格。小红只需要第一步给中间染色，之后紫在任意地方染色，小红只需要在紫染色的方格中心对称的位置染上和紫上次操作相同的颜色即可。这样一定是紫最先无法行动。

如果 $n$ 和 $m$ 不全是奇数，说明不存在中心的方格。紫只需要在每次小红染色后，在中心对称的位置上染上和小红上次操作不同的颜色（显然，这样一定是合法的）。如此最后不能操作的一定是小红。

本题参考代码如下（python）：

n,m=map(int,input().split())
if n*m%2==1:print("akai")
else:print("yukari")

level.2 D 比那名居的桃子

难度：2星（牛客标级）/ 1300（cf标级）

知识点：前缀和(prifix sum)/ 队列(queue)

题目大意：给定一个 $a$ 数组和一个 $b$ 数组，求一个 $x$ 使得 $\sum_{i=x}^{x+k-1}a_i$ 尽可能大，如果有多个最大值，要求 $\sum_{i=x}^{x+k-1}b_i$ 尽可能小。

思路：本题需要维护多个长度为 $k$ 的区间和（显然区间长度 $k$ 应该被取满，因为每个 $a_i$ 都是正整数，取满一定更优）。维护方式有2个：前缀和或者队列。

方法1：前缀和。

我们定义 $dp[i]=\sum_{i=1}^na_i$

那么求 $[l,r]$ 区间内的数之和，只需要求 $dp[r]-dp[l-1]$ 即可。因为

$dp[r]-dp[l-1]$

$=\sum_{i=1}^ra_i-\sum_{i=1}^{l-1}a_i$

$=\sum_{i=l}^{r}s_i$

方法2：队列

我们可以发现，当一个区间向右移动的时候，可以用一个队列来维护区间内的元素，每次向右移动一位，只需要让队尾入队一个元素、队首出队即可。因此单次移动的复杂度仅有 $O(1)$ 。

本题参考代码如下（前缀和解法）：

#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 B 擅长解密的小红同学

难度：3星（牛客标级）/1400（cf标级）

知识点：概率论(probability)，组合数学(combinatorial mathematics)

题目大意：给定0~9每个数字的出现次数，每次猜测后正确答案的数字顺序将会重排。问第一次猜对的猜测次数期望。

思路：由于每次猜测后都会重排，所以每次猜测都是独立实验，设成功的概率为 $p$ 。

那么次数的期望：

$E(x)=\sum_{i=1}^∞i*p*(1-p)^{i-1}$

于是有

$(1-p)E(x)=\sum_{i=1}^∞i*p*(1-p)^{i}=\sum_{i=2}^∞(i-1)*p*(1-p)^{i-1}$

一式减二式：

$p*E(x)=\sum_{i=1}^∞p*(1-p)^{i-1}=\lim_{i→+∞}p*\frac{1-(1-p)^i}{p}=1$

因此 $E(x)=\frac{1}{p}$

对于每次猜测，设数字不同组合的方案数为 $cnt$ ，单次猜测成功的概率是 $p=\frac{1}{cnt}$ ，最终的期望次数为 $cnt$ 。

怎么求这个组合的方案数呢？我们可以这样想：假设不考虑重复，方案数为 $cnt_{all}!$ 。考虑重复的话，每个数字带来的要被除掉，所以最终答案是 $\frac{cnt_{all}!}{\prod_{i=0}^{9}cnt_i}$

注意这里的除法要用乘以逆元进行处理。

本题参考代码如下：

#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.3 H 漂亮数

难度：3星（牛客标级）/ 1500（cf标级）

知识点：数论(number theory)，前缀和(prefix sum)

题目大意：多次询问，求 $l$ 到 $r$ 区间内有多少个有且仅有2个素因子（可以相同）的数。

思路：先使用线性筛晒出 $1$ 到 $5\times 10^7$ 的所有素数，然后对所有素数进行两两组合即可标记出所有的“漂亮数”，然后做一个cnt的前缀和即可 $O(1)$ 查询。

复杂度为 $O(N+CNT \times CNT_2)$ ，其中 $N$ 为 $10^8$ ， $CNT$ 为 $1$ 到 $\sqrt N$ 的素数数量。 $CNT_2$ 为 $1$ 到 $N$ 的素数数量。

本题参考代码如下：

#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)

题目大意：给一个数组，每次操作可以让一个数加一或者减一。问不超过 $k$ 次操作后，数组中最多有几个数相等？

思路：显然优先变化尽量接近的数。所以可以先对数组进行排序。

引理：一个数组每次操作可以让一个数加一或者减一，使所有数都相等的操作最小次数的方式是所有数都变成中位数（或两个中间的数的任意一个，若共有偶数个数）。

证明：一个数组有 $k$ 个数比中位数小， $k$ 个数（或 $k+1$ 个数，若共有偶数个数）比中位数大，假设把所有数都变成中位数的总操作次数为 $cnt$ 。这时如果让所有数变成比中位数更小的数，相当于对于 $x$ 个数而言 $(x<k)$ ，操作次数变少了，但对于 $y$ 个数而言 $(y>k)$ ，操作次数变多了同样的数值。总体来说操作次数一定是变多的。如果让所有数变成比中位数更大的数同理。证毕。

通过以上引理，我们只需要求出最大的一个区间，令其所有数都变成中位数的次数不超过 $k$ 即可。区间内部的操作次数可以通过前缀和达成 $O(1)$ 查询。

如何求这个最大区间呢？有两个方法：二分答案或者双指针。

方法一：二分答案

很明显，一定存在一个数 $x$ ，满足至少存在一个长度为 $x$ 的区间满足其所有数都变成中位数的次数不超过 $k$ 次，且不存在一个长度为 $x+1$ 的区间使得其所有数都变成中位数的次数不超过 $k$ 次。那么这个 $x$ 就满足可以用二分答案来求的性质。
复杂度：二分单次判断的复杂度为 $O(n)$ ，总复杂度为 $O(nlogn)$

方法二：双指针

当固定左端点 $l$ 时，我们可以找到右边第一个不合法的右端点 $r$ ，当 $l$ 向右移动时， $r$ 也向右移动，移动到最新的第一次不合法的位置。维护 $r-l$ 的最大值即可。
双指针复杂度为 $O(n)$ ，但还有排序的 $O(nlogn)$ ，总复杂度为 $O(nlogn)$

本题参考代码如下（双指针法）：

#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.6 G 零一奇迹

难度：4星（牛客标级）/1800（cf标级）

知识点：模拟(implementation)，双指针(two pointers) / 二分(binary search)

题目大意：给定一个01串(binary string)，现在每次询问改变一个其中的字符后，有多少不包含前导零子串对应的十进制在 $l$ 到 $r$ 之间。

思路：当固定子串的左端点时，可以通过二分或者双指针来找到右端点的位置合法位置区间。

每次进行修改字符时，由于影响的子串最多只包含左右64位，只需要对这部分进行判断即可（判断改前和改后的合法子串数量）。

总复杂度 $O(n+tq)$ ，其中 $t=128$ ， $q$ 为查询次数。

由于本题数据较弱，所以用暴力似乎也可以卡过去（

本题参考代码如下：

#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.7 E 紫妹永不服输

难度：5星（牛客标级）/2000（cf标级）

知识点：构造(constructive algorithm)、数论(number theory)

题目大意：构造一个长度不大于100000的字符串，其中包含 $n$ 个 'RP' 子序列， $m$ 个 'PR' 子序列。

思路：

引理：由 $x$ 个 R 、 $y$ 个 P 组成的字符串，其中 'RP' 子序列的数量和 'PR' 子序列的数量之和为 $x*y$ 。

证明：

一个字符串共有 $x$ 个 R 、 $y$ 个 P ，那么在这些 R 和 P 中各选一个，方案数共有 $x*y$ 种，要么构成 'PR' ，要么构成 'RP'。其必为原串的一个子序列。因此 'RP' 子序列的数量和 'PR' 子序列的数量之和为 $x*y$ 。证毕。

因此我们需要构造一个由 $x$ 个 R 、 $y$ 个 P 组成的字符串，其中 $x$ 和 $y$ 满足 $x*y=m+n$ 。也就是说，我们需要找到 $Q=m+n$ 的两个因子，它们的乘积等于 $Q$ 且和不大于100000。

所以我们可以采取贪心的策略，取尽可能接近 $\sqrt q$ 的两个因子即可。

关于具体的构造方法：

如果构造成 RR..RRPP...PP （ $x$ 个R， $y$ 个P），此时共有 $x*y$ 个 'RP' 。

这时我们如果把最后一个 R 向右移动一为，则可以转化一个 'RP' 为 'PR' 。如果把最后一个 R 放到所有 P 的后面，那么转化了 $y$ 个 PR。以此类推，我们可以找到最终字符串的形态。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long n,m;
    cin>>n>>m;
    long long sum=n+m;
    int x=1,i;
    for(i=2;i*i<=sum;i++){
        if(sum%i==0)x=i;
    }
    if(x+sum/x>=100000){
        cout<<-1;
        return 0;
    }
    int y=sum/x;
    int left=n/y,right=m/y;
    if(n%y==0){
        while(left--)cout<<'R';
        while(y--)cout<<"P";
        while(right--)cout<<'R';
    }
    else{
        int yu=n%y;
        while(left--)cout<<'R';
        while(y--){

            cout<<"P";
            if(y==yu)cout<<'R';

        }
        while(right--)cout<<'R';
    }
}

level.8 C 简单的三角形构造

难度：5星+（牛客标级）/ ?（cf标级）

知识点：计算几何(geometry)、构造(constructive algorithm)

题目大意：给定一个圆和圆内一个点 $P$ ，构造一个三角形满足三角形在圆内、点 $P$ 在三角形外，并且三角形面积不小于 $S$

思路：我们可以先这么想，假设没有“点 $P$ 在三角形外”的限制，可以构造的三角形面积最大是多少？

显然答案是圆内接正三角形。那么这道题首先就是要判断，能否构造一个圆内接正三角形满足 $P$ 在三角形外部。

观察下图：

图片说明

可以发现，只要 $P$ 到圆心 $O$ 的距离不小于 $\frac{1}{2}r$ 即可。

如果 $|OP|<\frac{1}{2}r$ 怎么办呢？观察下图：

图片说明

只需要构造一个等腰三角形，使得三角形的高为 $PO$ 的延长线即可。是否能构造成功取决于该三角形面积与 $S$ 的大小比较。

因此三角形的构造方式如下：

若 $|OP| \geq \frac{1}{2}r$ ，那么连接 $PO$ 并延长，交圆于点 $A$ ，构造等边三角形即可。

否则，延长 $PO$ 交圆于点 $A$ ，以 $PA$ 为高构造等腰三角形。

本题参考代码如下：

#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);

    }

}