2020牛客寒假算法基础集训营第一场

2020牛客寒假算法基础集训营第一场的题面与题解

A - honoka和格点三角形

题目描述

$honoka$最近在研究三角形计数问题。

她认为,满足以下三个条件的三角形是“好三角形”:

  1. 三角形的三个顶点均为格点,即横坐标和纵坐标均为整数。
  2. 三角形的面积为 $1$。
  3. 三角形至少有一条边和 $x$ 轴或 $y$ 轴平行。

$honoka$想知道,在平面中选取一个大小为 $n*m$ 的矩形格点阵,可以找到多少个不同的“好三角形”?

由于答案可能过大,请对 $1000000007$取模。

输入描述:

两个正整数 $n$ 和 $m$ $(2\leq n,m\leq 10^{9})$

输出描述:

面积为 $1$ 的格点三角形的数量,对$10^9+7$取模的结果

示例1

输入

1
2 3

输出

1
6

说明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
格点如下:

* * *

* * *
不妨设左下角坐标为(1,1),右上角坐标为到(3,2)。
那么三点坐标可选:
(1,1)(1,2)(3,1)
(1,1)(1,2)(3,2)
(1,1)(2,2)(3,1)
(1,1)(3,1)(3,2)
(1,2)(2,1)(3,2)
(1,2)(3,1)(3,2)
所以共有6个。

示例2

输入

1
100 100

输出

1
7683984

说明

1
这里太小写不下啦-. -

题解

题意

先把点阵看成笛卡尔坐标系,令$x$方向长为$n$,$y$方向长为$m$

面积为一的、有一条边平行与轴的三角形列举一下:

  1. 底为$1$,高为$2$
  2. 底为$2$,高为$1$

这里我们可以预测肯定会出现重复的情况,重复的情况就是底和高都平行于轴

思路

有边平行于$x$轴的三角形

当底为$2$的时候:

每一行有$n-2$个底,对于高,我们先默认从下往上看,比底高一个单位那一整行都可以作为它的高,所以高有$n$个,并且有$m-1$个这种从下往上看的高成立,所以一共有$(n-2)\times n\times (m-1)$个三角形成立,从上往下也是一样所以乘个$2$就行

当底为$1$的时候:

每一行有$n-1$个底,对于高,我们先默认从下往上看,比底高两个单位那一整行都可以作为它的高,所以高有$n$个,并且有$m-2$个这种从下往上看的高成立,所以一共有$(n-1)\times n\times (m-2)$个三角形成立,从上往下也是一样所以乘个$2$就行

有边平行于$y$轴的三角形

把上述n和m对调一下就行,但是要去掉相同的部分

对于每个底来说,只有两个高会让这个三角形底和高同时平行于坐标轴,所以每行的高只用$m-2$个就行

$(m-2)\times (m-2)\times (n-1)$

$(m-1)\times (m-2)\times (n-2)$

代码

1
2
3
4
5
6
7
8
9
10
11
#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
#define mod 1000000007
ll n, m, ans;
int main(){
scanf("%lld%lld", &n, &m);
ans=((n-2)%mod*2%mod*(m-1)%mod*n%mod+(n-1)%mod*2%mod*n%mod*(m-2)%mod+2*(m-2)%mod*(m-2)%mod*(n-1)%mod+2*(n-2)%mod*(m-1)%mod*(m-2)%mod)%mod;
printf("%lld\n",ans);
return 0;
}

C - umi和弓道

题目描述

$umi$对弓道非常痴迷。

有一天,她在研究一个射箭问题:

在一个无限大的平面中,她站在 $(x_0,y_0)$ 这个坐标。

有 $n$ 个靶子,第 $i$ 个靶子的坐标是 $(x_i,y_i)$

$umi$准备在 $x$ 轴或 $y$ 轴上放置一块挡板来挡住弓箭的轨迹,使得她可以射中的靶子数量不超过 $k$个。

她想知道挡板的最短长度是多少?

注:假定弓箭的轨迹是一条起点是$umi$坐标,长度无穷大的射线

umi和靶子的体积可以无视,挡板的边缘碰到弓箭轨迹也可视为挡住弓箭。

注:挡板不能弯折,起始和终点必须在同一坐标轴上。

输入描述:

第一行两个整数$x_0,y_0$代表$umi$的坐标。

第二行两个正整数 $n$ 和 $k$,分别代表靶子的总数量、放置挡板后可射中靶子的最大值。

接下来的 $n$ 行,每行两个整数$x_i$和$y_i$,代表每个靶子的坐标。

保证没有任何一个点在坐标轴上(无论$umi$还是靶子),保证没有任何两点重合。

$(1\leq n \leq 100000, 0\leq k \leq n-2, -2 \times 10^9 \leq x_i,y_i \leq 2 \times 10^9)$

输出描述:

若无论如何无法保证可以射中的靶子数量不超过$k$个,则输出$-1$。
否则输出挡板的最小长度。如果你和正确答案的误差不超过$10^{-6}$,则视为答案正确。

示例1

输入

1
2
3
4
1 1
2 0
-1 2
-2 1

输出

1
0.50000000

说明

1
umi要保证能射中的靶子不超过0个,即全部挡住。在y轴上选区间[1,1.5]放置一个长度为0.5的挡板即可。

题解

题意

二维图上有一个特殊点,所有点都与它相连,现在只能在x轴或者y轴上面放一个板子隔断他们之间的线

问如何保证最多只剩k条线,板子越小越好

思路

首先确定$umi$所在位置的象限。

对于不在一个象限的点,与$umi$连线,找出线段和 $x$ 轴或 $y$ 轴的交点,记录坐标位置。

之后双指针维护 $x$ 轴上或者 $y$ 轴挡住 $n−k$ 个点的挡板长度最小值。

注意 $x$ 轴和 $y$ 轴要分开计算。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<double> v1,v2;
int main(){
double x0, y0;
int n, k;
cin>>x0>>y0>>n>>k;
k = n - k;
for(int i = 0; i < n; i++){
double x, y;
cin>>x>>y;
if(x*x0<0)
v2.push_back(y0-x0*(y-y0)/(x-x0));
if(y*y0<0)
v1.push_back(x0-y0*(x-x0)/(y-y0));
}
double mi = 1e18;
sort(v1.begin(), v1.end());
if(v1.size()>=k){
double head = 0, tail = k-1; //双指针,用mi维护x轴上的最小值
while(tail<v1.size()){
mi = min(mi, v1[tail]-v1[head]);
tail++, head++;
}
}
sort(v2.begin(), v2.end());
if(v2.size()>=k){
double head = 0, tail = k-1; //双指针,用mi维护y轴上的最小值
while(tail<v2.size()){
mi = min(mi, v2[tail]-v2[head]);
tail++, head++;
}
}
if(mi==1e18) printf("-1\n");
else printf("%.7lf\n", mi);
return 0;
}

E - rin和快速迭代

题目描述

”数论真的太好玩了喵~“——hoshizora rin

$rin$最近喜欢上了数论。

然而数论实在太复杂了,她只能研究一些简单的问题。

这天,她在研究正整数因子个数的时候,想到了一个“快速迭代”算法。

设 $f(x)$ 为 $x$ 的因子个数,将其迭代下去,$rin$猜想任意正整数最终都会变成 $2$ 。

例如:$f(12)=6,f(6)=4,f(4)=3,f(3)=2$

她会给你一个正整数 $n$ ,让你输出它在迭代过程中,第一次迭代成 $2$ 的迭代次数。

输入描述:

一个正整数 $n$ $(3 \leq n \leq 10^{12})$

输出描述:

一个正整数,为 $n$ 迭代至 $2$ 的次数。

示例1

输入

1
12

输出

1
4

说明

1
2
3
4
5
12的因子:1,2,3,4,6,12。共6个。
6的因子:1,2,3,6。共4个。
4的因子:1,2,4。共3个。
3的因子:1,3。共2个。
12 → 6 → 4 → 3 → 2 , 故迭代了4次。

题解

题意

求迭代次数

思路

约数个数定理

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
#define mod 1000000007
ll n, m, ans, num;
void f(){
ll time = 0;
while (ans!=2){
ans = 1;
for (int i = 2; i*i <= m; i++){
num = 0;
while (m%i == 0){
num++; //记录这个因数有多少个
m = m / i; //直接去掉已记录的因数
}
if (num > 0){ //因数存在
num++;
/*
存在num+1种情况:
如果一开始输入的是12,那现在就是有了两个2
我们构造因数的时候就会有三种方法:
1、内含0个2
2、内含1个2
3、内含2个2
*/
ans = ans * num; //现在就有ans * num个因数了
}
}
if (m > 1) ans = ans * 2; //还有剩下的一个质数,因数有两种情况,含它和不含它
m = ans; //迭代
time++;
}
printf("%lld\n",time);
}
int main(){
scanf("%lld", &m);
f();
return 0;
}

F - maki和tree

题目描述

有一天,$maki$拿到了一颗树。所谓树,即没有自环、重边和回路的无向连通图。

这个树有 $n$ 个顶点, $n-1$ 条边。每个顶点被染成了白色或者黑色。

$maki$想知道,取两个不同的点,它们的简单路径上有且仅有一个黑色点的取法有多少?

$Tips$:

  1. 树上两点简单路径指连接两点的最短路
  2. $(q,p),(p,q)$视为同一个路径

输入描述:

第一行一个正整数 $n$,代表顶点数量。$(3 \leq n \leq 10^{5})$

第二行是一个仅由字符$’B’$和$’W’$组成的字符串。第$i$个字符是$B$代表第 $i$ 个点是黑色,$W$代表第$i$个点是白色。

接下来的 $n-1$ 行,每行两个正整数 $x$ ,$y$ ,代表 $x$ 点和 $y$ 点有一条边相连

$(1\leq x,y \leq n)$

输出描述:

一个正整数,表示只经过一个黑色点的路径数量。

示例1

输入

1
2
3
4
3
WBW
1 2
2 3

输出

1
3

说明

1
2
3
只有2号是黑色点。

<1,2>、<2,3>、<1,3>三种取法都只经过一个黑色点。

题解

题意

只有一个黑色点的路径数

思路

路径有两种:

黑点在中间或者端点

在中间的时候:联通块白点数*其他联通块白点数

在端点的时候:联通块白点数*一个黑点

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 100005
ll n,m,k,ans;
ll head[N],col[N],num[N];
bool vis[N];
string s;
ll ans1;
struct node{
ll v,next;
}a[N*2];
void add(ll u,ll v){
a[++k].v=v,a[k].next=head[u];
head[u]=k;
}
void dfs(int x,int fa){
if(col[x]) return;
ans1++;
for(int i=head[x];i;i=a[i].next){
if(a[i].v!=fa)
dfs(a[i].v,x);
}
}
int main(){
scanf("%lld",&n);
cin>>s;
for(int i=1;i<=n;i++) //上色
if(s[i-1]=='B') col[i]=1;
else col[i]=0;
for(int i=1;i<n;i++){
ll u,v;
scanf("%lld%lld",&u,&v);
//无向图
add(u,v);
add(v,u);
}
for(int i=1;i<=n;i++){
if(s[i-1]=='B'){
ll cnt=0,res=0;
for(int j=head[i];j;j=a[j].next){
ans1=0;
dfs(a[j].v,i);
num[++cnt]=ans1;
res+=ans1;
}
for(int j=1;j<=cnt;j++)
ans+=num[j]*(res-num[j]+1),res-=num[j];
}
}
cout<<ans<<endl;
return 0;
}

G - eli和字符串

题目描述

$eli$拿到了一个仅由小写字母组成的字符串。

她想截取一段连续子串,这个子串包含至少 $k$ 个相同的某个字母

她想知道,子串的长度最小值是多少?

注:所谓连续子串,指字符串删除头部和尾部的部分字符(也可以不删除)剩下的字符串。

例如:对于字符串$“arcaea”$而言,$“arc”、“rcae”$都是其子串,而$“car”、“aa”$则不是它的子串。

输入描述:

第一行输入两个正整数$n$和$k$ $(1 \leq n,k \leq 200000)$

输入仅有一行,为一个长度为$n$的、仅由小写字母组成的字符串。

输出描述:

如果无论怎么取都无法满足条件,输出 $-1$ 。
否则输出一个正整数,为满足条件的子串长度最小值。

示例1

输入

1
2
5 2
abeba

输出

1
3

说明

1
选择“beb”子串,长度为3,其中包含相同的两个'b'

题解

题意

仅含$k$个相同字母的最短连续子序列长度

思路

一共就$26$个字母,记录个数和分别的位置,跑$26$次就行了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
struct zm
{
int wz[200000];
int num;
} a[26];
int main()
{
int n, k;
cin >> n >> k;
char ch[200005];
cin >> ch;
int flag = 0;
for (int i = 0; i < n; i++)
{
a[ch[i] - 'a'].wz[a[ch[i] - 'a'].num] = i;
a[ch[i] - 'a'].num++;
if (a[ch[i] - 'a'].num >= k)
flag = 1;
}
if (flag == 0)
{
cout << -1;
return 0;
}
else
{
int mi = 1e18;
int l;
for (int i = 0; i < 26; i++)
{
int head = 0, tail = k - 1;
if (a[i].num >= k)
{
while (tail < a[i].num)
{
l = a[i].wz[tail] - a[i].wz[head] + 1;
mi = min(l, mi);
head++;
tail++;
}
}
}
cout << mi;
}
}

H - nozomi和字符串

题目描述

$nozomi$ 看到 $eli$ 在字符串的“花园”里迷路了,决定也去研究字符串问题。

她想到了这样一个问题:

对于一个 $“01”$ 串而言,每次操作可以把 $0$ 字符改为 $1$ 字符,或者把 $1$ 字符改为 $0$ 字符。

所谓 $“01”$ 串,即只含字符 $0$ 和字符 $1$ 的字符串。

$nozomi$ 有最多 $k$ 次操作的机会。

她想在操作之后找出一个尽可能长的连续子串,这个子串上的所有字符都相同。

$nozomi$ 想问问聪明的你,这个子串的长度最大值是多少?

注: $k$ 次操作机会可以不全部用完。

如果想知道连续子串的说明,可以去问问 $eli,nozomi$ 不想再讲一遍。

输入描述:

第一行输入两个正整数 $n$ 和 $k$

输入仅有一行,为一个长度为$n$的、仅由字符 $0$ 和 $1$ 组成的字符串。

输出描述:

一个正整数,为满足条件的子串长度最大值。

示例1

输入

1
2
5 1
10101

输出

1
3

说明

1
2
3
只有 1 次操作机会。
将第二个位置的 0 改成 1 ,字符串变成"11101",可以选出“111”子串,长度为3。
如果修改第三个或者第四个位置的字符也可以选出长度为3的子串。

题解

题意

原题

思路

类似滑动窗口

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;
char c[200010];
int n, m;
int main(){
scanf("%d%d", &n, &m);
for(int i=0;i<n;i++) scanf("%c", &c[i]);
int maxl=0, l=0, r=0, an=0, bn=0;
while(r<=n){
if(c[r]=='0') an++;
else bn++;
if(an<=m||bn<=m){
r++;
}else{
if((r-l)>maxl) maxl=r-l;
if(c[l]=='0'){
l++;
an--;
}else{
l++;
bn--;
}
r++;
}
}
if((r-l)>maxl) maxl=r-l;
printf("%d", maxl);
return 0;
}

I - nico和niconiconi

题目描述

“にっこにっこにー” ——nico

$nico$平时最喜欢说的口头禅是$niconi~$。

有一天$nico$在逛著名弹幕网站$”niconico”$的时候惊异的发现,$n$站上居然有很多她的鬼畜视频。

其中有一个名为《让$nico$为你洗脑》的视频吸引了她的注意。

她点进去一看,就被洗脑了:

$”niconicoh0niconico*^vvniconicoG(vniconiconiconiconiconicoG(vniconico……”$

弹幕中刚开始有很多$“nico \times 1 nico \times 2”$等计数菌,但到后面基本上都是“计数菌阵亡”的弹幕了。

nico也想当一回计数菌。她认为:$”nico”$ 计 $a$ 分,$”niconi”$ 计 $b$ 分,$”niconiconi”$ 计 $c$ 分。
她拿到了一个长度为 $n$ 的字符串,请帮她算出最大计数分数。
注:已被计数过的字符不能重复计数!如$”niconico”$要么当作$”nico”+”nico”$计 $2a$ 分,要么当作$”niconi”+”co”$计 $b$ 分。

输入描述:

第一行四个正整数$n,a,b,c$ 。 $(1\leq n \leq 300000, 1\leq a,b,c \leq 10^{19})$
第二行是一个长度为 $n$ 的字符串。

输出描述:

一个整数,代表最大的计数分数。

示例1

输入

1
2
19 1 2 5
niconiconiconiconi~

输出

1
7

说明

1
2
"niconi"co"niconiconi"~
故为2+5=7分

题解

题意

计数菌死的很惨

思路

如下代码

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
#define N 300010
#define ll long long
ll n, a, b, c;
char s[N];
ll f[N];
bool check(int x, int len) {
char sc[12] = "aniconiconi";
for (int i = 1; i <= len; i++)
if (s[x + i] != sc[i]) return false;
return true;
}
int main() {
scanf("%lld%lld%lld%lld%s", &n, &a, &b, &c, s + 1);
for (int i = 1; i <= n; i++) {
if (i >= 4 && check(i - 4, 4)) f[i] = max(f[i], f[i - 4] + a);
if (i >= 6 && check(i - 6, 6)) f[i] = max(f[i], f[i - 6] + b);
if (i >= 10 && check(i - 10, 10)) f[i] = max(f[i], f[i - 10] + c);
f[i] = max(f[i], f[i - 1]); //继承下去
}
printf("%lld\n", f[n]);
return 0;
}

J - u’s的影响力

题目描述

μ’s在九人齐心协力下,影响力越来越大了!

已知第一天影响力为 $x$ ,第二天影响力为 $y$ ,从第三天开始,每一天的影响力为前两天影响力乘上 $a$ 的 $b$ 次方。 用数学语言描述是:
设第 $i$ 天的影响力为 $f(i)$ ,那么 $f(1)=x$ ,$f(2)=y$,对于 $3 \leq i$ ,$f(i)=f(i-1) \times f(i-2) \times a^b $
她们想知道第 $n$ 天影响力是多少?
由于这个数可能非常大,只需要输出其对 $1000000007$ 取模的值就可以了。

输入描述:

一行五个正整数:$n,x,y,a,b$。

$(1\leq n,x,y,a,b \leq 10^{12})$

输出描述:

第$n$天的影响力对 $1000000007$ 取模的值。

示例1

输入

1
4 2 3 2 1

输出

1
72

说明

1
f(1)=2,f(2)=3,f(3)=f(1)*f(2)*2=12,f(4)=f(2)*f(3)*2=72

题解

题意

推公式

思路

$f(1) = x$

$f(2)=y$

$f(3)=x \ast y\ast a^b$

$f(4)=x\ast y^2\ast a^{2b}$

$f(5)=x^2\ast y^3\ast a^{4b}$

$f(6)=x^{3}\ast y^{5}\ast a^{7b}$

$f(7)=x^{5}\ast y^{8}\ast a^{12b}$

直接观察可以看出从第三项开始:

$x$的变化趋势是$1,1,2,3,5$

$y$的变化趋势是$1,2,3,5,8$

是很明显的斐波那契数列,用矩阵快速幂处理。

$a$的幂就是前两项的幂加$1$

1
2
3
4
//n从0开始,对幂来说满足以下公式
f[n] = f[n-1] + f[n-2] ,f[0] = 1,f[1] = 0;//x
f[n] = f[n-1] + f[n-2] ,f[0] = 0,f[1] = 1;//y
f[n] = f[n-1] + f[n-2] + b , f[0] = 0,f[1] = 0;//a

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 1000000007
struct matrix
{
ll x[3][3];
matrix() { memset(x, 0, sizeof(x)); }
};
matrix multi(matrix a, matrix b, int matrixN) //矩阵相乘
{
matrix temp;
for (int i = 0; i < matrixN; i++)
for (int j = 0; j < matrixN; j++)
for (int k = 0; k < matrixN; k++)
{
temp.x[i][j] += (a.x[i][k] * b.x[k][j] % (mod - 1));
//mod-1:费马小定理
temp.x[i][j] %= (mod - 1);
}
return temp;
}
matrix quick_multi(matrix a, ll n, int matrixN) //矩阵快速幂
{
matrix temp = a;
n--;
while (n)
{
if (n & 1) //处理奇数
temp = multi(temp, a, matrixN);
a = multi(a, a, matrixN);
n >>= 1;
}
return temp;
}
ll qpow(ll a, ll b) //a^b
{
if (b == 0)
return 1;
a %= mod;
ll ans = 1, temp = a;
while (b)
{
if (b & 1)
ans = (ans * temp) % mod;
temp = (temp * temp) % mod;
b >>= 1;
}
return ans % mod;
}
int main()
{
ll n, x, y, a, b;
cin >> n >> x >> y >> a >> b;
n--;
//从0开始
if (n == 0)
cout << x % mod << endl;
else if (n == 1)
cout << y % mod << endl;
//特判一下底数为0
else if (x % mod == 0 || y % mod == 0 || a % mod == 0)
cout << 0 << endl;
else
{
//斐波那契
matrix ans;
ans.x[0][0] = ans.x[0][1] = ans.x[1][0] = 1; //初始矩阵
ans = quick_multi(ans, n - 1, 2);
matrix tmp, tmp2;
//x的幂
tmp.x[1][0] = 1;
tmp = multi(ans, tmp, 2);
//y的幂
tmp2.x[0][0] = 1;
tmp2 = multi(ans, tmp2, 2);
//a的幂
memset(ans.x, 0, sizeof(ans.x));
ans.x[0][0] = ans.x[0][1] = ans.x[0][2] = ans.x[1][0] = ans.x[2][2] = 1;
ans = quick_multi(ans, n - 2, 3);
matrix tmp3;
tmp3.x[0][0] = tmp3.x[2][0] = b % (mod - 1);
tmp3 = multi(ans, tmp3, 3);
//快速幂计算
ll res = qpow(x, tmp.x[0][0] % (mod - 1));
res = res * ((qpow(y, tmp2.x[0][0] % (mod - 1))) % mod) % mod;
res = res * ((qpow(a, tmp3.x[0][0] % (mod - 1))) % mod) % mod;
cout << res << endl;
}
return 0;
}