2020牛客寒假算法基础训练营5

---

A-模板

题目描述

牛牛，牛可乐和牛能组成了一只队伍参加ACM系列赛事，他们起了一个优雅的队名叫~“牛牛战队”。
牛牛战队在没有比赛的时候，会把各种板子放在密码柜里，防止弄丢。这一个密码由整个队伍掌管。其中牛牛和牛能有两个密钥，各自有一个仅由大写字母构成的字符串。牛可乐则掌握着解密方法。一天，你用一瓶可乐贿赂牛可乐，得到了解密的办法。
牛可乐将试图通过以下操作用尽可能少的步骤把一个密钥转换为另一个：
①将其中任意一个字母替换为另一个
②把最后一个字母删除
③在尾部添加一个字母
④得到的转化步数就是最后的密码。
一天，你和他们队员一起聚餐，你用可乐把他们灌倒了，从牛牛和牛能口中套出了两个密钥。你要趁他们醒之前拿到模板并复印一份再放回去。你能尽快的算出密码吗？

输入描述

输入数据共33行，第一行包括两个整数$n,m{\text{(1}} \leqslant n,m \leqslant {10^5})$，表示两个密钥的长度。
第二行包含一个长度为n的字符串${s_1}$，表示第一个密钥。
第三行包含一个长度为m的字符串${s_2}$，表示第二个密钥。

输出描述

在一行内输出一个整数，表示密码。

示例1

输入
4 3
WXYZ
WXY
输出
1

思路

题目看起来是编辑距离的模板题，其实就是一个很简单的题目，贪心地考虑问题。
先考虑两个字符串相同的部分，显然，只要把原字符串和新字符串不同的字符修改就行了；对于两个字符串后面不同的部分，如果原字符串比较长，就全部删掉；如果原字符串比较短，就对照第二个字符串添加字符。

代码

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
int n,m;
string s1,s2;
int main()
{
	scanf("%d%d",&n,&m);
	int i;
	int ans=0;
    cin>>s1>>s2;
	if(n>m)
	{
		ans=n-m;
		for(i=0;i<m;i++)
		{
			if(s1[i]!=s2[i]) ans++;
		}
	}
	else if(n<=m)
	{
		ans=m-n;
		for(i=0;i<n;i++)
		{
			if(s1[i]!=s2[i]) ans++;
		}
	}
	printf("%d",ans);
	return 0;
}

B-牛牛战队的比赛地

题目描述

由于牛牛战队经常要外出比赛，因此在全国各地建立了很多训练基地，每一个基地都有一个坐标$(x,y)$。
这周末，牛牛队又要出去比赛了，各个比赛的赛点都在$x$轴上。牛牛战队为了方便比赛，想找一个到达训练基地最大距离最小的地方作为比赛地。
这个问题对于牛牛战队太简单了，它就交给了你，你来帮他算一下~

输入描述

输入数据第一行包含一个整数$N(1≤N≤100000)$，表示牛牛战队训练基地的数量。
接下来$N$行，每行包括22个整数$x,y( - 10000 \leqslant x,y \leqslant 10000)$，表示每一个训练基地的坐标。

输出描述

输出一个小数，表示选择的比赛地距离各训练基地最大距离的最小值。
如果你的答案是$a$，标准答案是$b$，当$\frac{|a-b|}{max(1,|b|)}\leq 10^{-4}$时，你的答案将被判定为正确。

示例1

输入
3
0 0
2 0
0 2
输出
2
说明
当在$(0,0)$比赛时，到三个训练基地的最大距离是$2$。可以证明这是最小值。

思路

很容易想到，训练基地横坐标从负无穷到正无穷，所求值先减小后增大，具有两个单调区间，可以用四分法。

代码

#include<string>
#include<iostream>
#include<cmath>
#include<algorithm>
#define init 0x7fffffff
#define eps 1e-6
using namespace std;
struct node
{
    double x,y;
};
int n;
node p[100005];
double GetDis(node a, node b)
{
    return sqrt(pow(a.y-b.y, 2)+pow(a.x-b.x,2));
}
double GetMax(double a)//找到比赛地距训练基地的最大距离
{
    node temp;
    temp.x=a;
    temp.y=0;
    double res=0;
    int i;
    for (i=0;i<n;i++) res=max(res,GetDis(temp,p[i]));
    return res;
}
int main()
{  
    int i;
    cin>>n;
    double left=init;
    double right=-init;
    for (i=0;i<n;i++)
    {
        node temp;
        scanf("%lf%lf",&temp.x,&temp.y);
        p[i]=temp;
        //确定两个端点
        left=min(left,temp.x);
        right=max(right,temp.x);       
    }
    while(right-left>eps)
    {
        double mid=(left+right)/2;
        double left_mid=(left+mid)/2;
        double right_mid=(right+mid)/2;
        if (GetMax(left_mid)<GetMax(right_mid)) right=right_mid;
        else left=left_mid;
    }
    double mid=(left+right)/2;
    cout<<GetMax(mid);
    return 0;
}

D-牛牛与牛妹的约会

题目描述

牛牛在辛苦的一天的比赛之后，要去找牛妹玩，其实牛妹那天也在比赛。他为了找到牛妹，要尽快的从自己的比赛地到她的比赛地。
还记得吗，比赛地都是只在$x$轴上的，所以两个人的坐标都满足$y=0$。牛牛除了可以以1单位距离/单位时间的速度移动任意时间以外，还可以花费1单位时间进行闪现。每次闪现时，如果当前他的坐标是$x=k$，他将闪现到$x=\sqrt[3]{k}$的位置。
请帮他算算，最短需要多少时间，他可以找到牛妹~

输入描述

输入数据包括多组用例，输入第一行包含一个数字$T(1 \leq T \leq 5 \times 10^5)$，表示数据组数。
接下来$T$行，每行包括两个整数$a,b(|a|,|b|\leq 10^6)$，表示牛牛所在的位置和牛妹所在的位置。

输入描述

输出共$T$行，每行包括一个实数，表示牛牛所花费的最短时间。
如果你的答案是$a$，标准答案是$b$，当$|a-b|\leq 10^{-6}$ 时，你的答案将被判定为正确。

示例1

输入
2
3 -1
1 2
输出
3.442249570
1.000000000

思路

本题采用贪心的方法，看闪现和前进哪一步更优。具体过程见代码注释。

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#define eps 1e-6
using namespace std;
void solve()
{
	const double p=1.0/3;
	double ans=0;
	double a,b;
    cin>>a>>b;
	while(1)
	{
		double na;
		if(a<0) na=-pow(-a,p);//负数直接pow会乱码
		else na=pow(a,p); 
        //abs(a-b)-abs(na-b)就是闪现一次走过的路程
		if(abs(a-b)-abs(na-b)>1.0+eps||abs(a-b)-abs(na-b)>1.0-eps)
		{
            /*
            此if包含两层递进的关系：
            ①开三次根号后两者接近了；          
            ②花一秒闪现比花一秒前进一个单位走过的路程长。
            */
			ans+=1.0;
			a=na;
		}
		else
		{
			ans+=abs(a-b);
			break;
		}
	}
	printf("%.9lf\n",ans);
}
int main()
{
	ios::sync_with_stdio(false);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

E-Enjoy the game

题目描述

牛牛战队的三个队员在训练之余会自己口胡了一些题当做平时的益智游戏。有一天牛可乐想出了一个小游戏给另外两名队员玩，游戏规则如下：

• 初始一共有nn张卡牌
• 先手第一步最少要拿$1$张牌，最多要拿$n$$−$$1$张牌。
• 接下来每一步，双方最少要拿$1$张牌，最多拿等同于上一步对方拿的牌数的牌。
• 拿走最后一张牌的人将取得游戏的胜利。
  你作为旁观者，看着他们玩的很开心，想参与到这场游戏中来，赌一赌谁会能赢。

输入描述

输入数据包含一个整数$n(2 \leq n \leq 10^{18})$，表示初始卡牌张数。

输出描述

如果先手有必胜策略，输出Bob，否则输出Alice。

示例1

输入
2
输出
Alice
说明
先手必须拿走一张牌，然后后手拿走了另一张牌，游戏结束。

思路

找找规律。
若牌数为奇数则Bob赢。若为偶数，偶数中含有（除$1$以外）奇数因子，则Bob赢；
偶数中（除$1$以外）不含奇数因子，则Alice赢（即牌数为2的n次幂）。
于是只需要判断n是不是2的n次幂就可以了。有个很骚气的方法，${2^n} = k \Leftrightarrow k\& (k - 1) = 0,(n \in N)$。

代码

#include<iostream>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    long long n;
    cin>>n;
    if(!(n&(n-1))) cout<<"Alice";
    else cout<<"Bob";
    return 0;
}

F-碎碎念

题目描述

在ACM比赛里，除了CE以外都是有效的提交。每一个提交都会有其评测的结果，或是AC，或是RJ（Rejected，包含各种不通过的情况）。往往一个人上去提交的时候，总有一个队友会坐在边上等着结果。那个人，往往都是只读题不写题的云选手~
牛牛战队里也有这样的云选手——牛能。当牛能看到有效提交得到了AC以后，都会大呼一声“你好能啊！”，反之，如果得到了RJ的话，就会化身为喷子，说xx句“你能不能行啊！”。大家比赛的都十分紧张，这样的大声呼喊未免会引起旁边队伍的注意。
当然牛牛战队交题的时候也很小心，一旦这一发出现了RJ，下一发有效提交一定能获得AC。
比赛结束了以后，旁边的一支队伍愤怒的跑过来说：你们比赛的时候吵不吵啊，一直在这大吼，吼了这么多句！
激烈的争吵引起了吃瓜群众的注意，吃瓜群众问道：吼了多少句啊，这么讨厌的吗！
“啊……我也记不清了，大概是在[L,R]这个区间吧。”
作为吃瓜群众的你，想根据这个信息算出，这个队伍有多少种有效提交结果序列的可能呢？

输入描述

输入数据包括单组数据、多组询问。输入第一行包含一个整数$x(2 \leq x \leq 100\,000)$，表示牛能在RJ状态下会说“你能不能行啊！”的句子数量。
第二行包括一个整数$Q(1 \leq Q \leq 10^5)$，表示询问数量。
接下来$Q$行，每行包括两个整数$L,R(1 \leq L \leq R \leq 100\,000)$，表示每次询问下句子的区间数。

输出描述

对于每组数据，在一行内输出一个整数，表示牛牛战队提交结果的可能性。由于结果可能很大，请对
$1000000007$取模。

示例1

输入
3
3
3 3
1 4
1 5
输出
2
7
11
说明
第一组询问：可以是三个AC，或者一个RJ。
第二组询问：可以是1~4个AC，一个AC和一个RJ（共2种顺序），或者一个RJ。
第三组询问：可以有1~5个AC，两个AC和一个RJ（共3种顺序），一个AC和一个RJ（共2种顺序），或者一个RJ。

思路

考虑到了第$i$句话时候，这种状态可能由两种状态转移而来。
直接一发AC，从第$i-1i$句话直接到达第$i$句。
如果$i>=k$,可以由一发RJ从$i-k$句到达第i句。
可以构造$DP[i][0/1]$，$DP[i][0]$表示到了第$i$句话，是从$i-1$句话AC到达的方案数。$DP[i][1]$表示到了第$i$句话，是由$i-k$句话RJ过来的方案数。
由此可知转移条件
$DP[i][0]=DP[i-1][0]+DP[i-1][1]$
$DP[i][1]=DP[i-k][0](i>=k)$
易确定边界条件$DP[0][0]=1,DP[0][1]=0$。
由于有$Q$次查询 ，查询数目较多，我们可以线性时间内预处理前nn项和即前缀和，然后用第$R$项减去第$L-1$项即可。

代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100009;
const int mod=1000000007;
void solve()
{
        int dp[N][2]={0};
        int q,x;
        cin>>x>>q;
        dp[0][0]=1;
        int i;
        for(i=1;i<N;i++)
        {
            dp[i][0]=(dp[i-1][0]+dp[i-1][1])%mod;
            if(i>=x) dp[i][1]=dp[i-x][0];
        }
        int ans[N]={0};
        for(i=1;i<N;i++)
        {
            ans[i]=(dp[i][0]+dp[i][1])%mod;
            ans[i]=(ans[i]+ans[i-1])%mod;//构造前缀和
        }
        int l,r;
        while(q--)
        {
            cin>>l>>r;
            int res=(ans[r]-ans[l-1]+mod)%mod;
            printf("%d\n",res);
        }
}
int main()
{
        ios::sync_with_stdio(false);
        solve();
        return 0;
}

H-Hash

题目描述

这里有一个hash函数。

const int LEN = 6;
int mod;
int Hash(char str[])
{
        int res = 0;
        for (int i = 0; i < LEN; i++)
        {
            res = (res * 26 + str[i] - 'a') % mod; 
        }
        return res;
}

现给定一个长度为$6$的仅由小写字母构成的字符串$s$和模数$mod$，请找到字典序最小且大于$s$的一个长度为$6$的仅由小写字母构成的字符串$s'$，使得其hash值和$s$的hash相等。

输入描述

多组用例，请处理到文件结束。（用例组数大约为1000组左右）
对于每组用例，输入一行，包含一个长度为$6$的仅由小写字母构成的字符串$s$和模数$mod(2 \leq mod \leq 10^7)$，用空格隔开。

输出描述

对于每组用例，如果存在如题目所述的$s'$，请输出$s'$，否则输出-1。

示例1

输入
abcdef 11
输出
abcdeq

思路

卡哈希。
观察给的哈希函数可以轻松看出，这个哈希函数就仅仅是把一个只由小写字符组成的字符串当成了一个26进制的数，不取模的情况下，任意小写字符串和自然数是一一对应的。因此，只要把给的字符串转换成对应的26进制整数，加上模数后转换回字符串，一定可以得到一个最小字典序大于原串的字符串。只要这个新字符串长度为6即是满足要求的字符串。
需要知道的是怎么把哈希值转化成字符串。

代码

#include<iostream>
#include<string>
using namespace std;
const int len=6,base=26;
int mod;
string s;
void solve()
{
        long long res=0;
        int i;
        for(i=0;i<len;i++)
        {
            res=res*base+s[i]-'a';
        }
        res+=mod;
        for(i=len-1;i>=0;i--)//还原
        {
            s[i]=res%base+'a';
            res/=base;
        }
        if(res) cout<<-1<<endl;
        else cout<<s<<endl;
}
int main()
{
        ios::sync_with_stdio(false);
        while(cin>>s>>mod) 
        {
            solve();
        }
        return 0;
}

I-I题是个签到题

题目描述

经过2019一年的比赛，牛牛战队的队员发现了一个重大规律：I题是个签到题！
签到题的定义是：通过人数大于等于全场人数的$80$$$或者通过人数是所有题目前三多的题（也就是最多有两个题目通过人数严格比它多）叫做签到题。
2020赛季就要到了，牛牛战队要去验证这个规律了，已知现在每个题的过题情况，看一看I题是不是一个签到题。

输入描述

输入数据共$2$行。第一行包括两个整数$n,m(9 \leq n \leq 13, 100 \leq m \leq 1\,000)$，表示比赛的总题数和比赛的总人数。
第二行包括以空格分隔的$n$个整数$a_1,a_2,\cdots,a_n(a_i >0)$，表示每个题通过的人数。

输出描述

如果I题是个签到题，则输出Yes，否则输出No。（不区分大小写）

示例1

输入
9 100
100 100 100 100 100 100 100 100 100
输出
Yes

思路

I是签到题的条件：
①超过$80$$$的人做出I题；
②做出的人数超过I题的题目至多2个。
两个条件满足其一即可。

代码

#include<iostream>
#include<algorithm>
using namespace std;
int sc[15];
int main()
{
        int n,m;
        cin>>n>>m;
        int i;
        for(i=0;i<n;i++) cin>>sc[i];
        if(sc[8]>=0.8*m) cout <<"Yes";
        else
        {
            int rank=0;
            for(i=0;i<n;i++)
            {
                if(sc[i]>sc[8]) rank++;
            }
            if(rank>2) cout<<"No";
            else cout <<"Yes";
        }
        return 0;
}

J-牛牛战队的秀场

题目描述

牛牛战队里，不仅有训练，也有追逐。
牛牛和牛能总是想知道谁更秀一点，他们通常会去比谁的代码更秀，谁的成绩更秀……
这一次，他们开始比谁的走位更秀。他们来到一个半径为$r$的圆上，画了圆内接的正$n$边形。为了秀走位，他们只允许自己在多边形的边上移动。
同时，他们随便选取正$n$边形的一个顶点为$1$号顶点，按顺时针的顺序把其他的点叫做$2$号顶点，$3$号顶点……一开始，两人分别在$i$号顶点和$j$号顶点。
现在，牛牛要一边沿着多边形的边秀走位，一边走向牛能。他想知道，他最短要走多少距离才能走到牛能的旁边？

输入描述

输入数据共$2$行，第一行有两个整数$n,r(3 \leq n \leq 1000, 1 \leq r \leq 10^6)$，表示在半径为$r$的圆上画了一个内接$n$边形。
第二行有两个整数$i,j(1 \leq i, j \leq n)$，表示牛牛一开始在$i$号顶点，牛能一开始在$j$号顶点。

输出描述

一个小数$x$，表示牛牛要移动的最短距离。
如果你的答案是$a$，标准答案是$b$，如果$\frac{|a-b|}{max(1,|b|)}\leq 10^{-6} max(1,∣b∣)$
，你的答案将被判定为正确。

示例1

输入
4 1
1 2
输出
1.414214

思路

关键问题是求正n边形的边长。

把正$n$边形分割为$n$个全等的等腰三角形，每个等腰三角形顶角为$\frac{{2\pi }}{n}$，腰为$r$。由余弦定理，易得，边长为$\sqrt {2{r^2}(1 - \cos \frac{{2\pi }}{n})} $。

代码

#include<iostream>
#include<cmath>
#include<cstdio>
#define pi 3.14159265
using namespace std;
int main()
{
	int n;
	int a,b;
	int r;
	scanf("%d%d%d%d",&n,&r,&a,&b);
	int dis=min(abs(a-b),n-abs(a-b));
	double p=(pi*2)/n;
	double ans=(double)sqrt(2*(double)r*r*(1-cos(p)))*dis;
	printf("%.7lf",ans);
	return 0;
}