2020牛客寒假算法基础集训营1

A honoka和格点三角形

Description：
honoka最近在研究三角形计数问题。
她认为，满足以下三个条件的三角形是“好三角形”。
1.三角形的三个顶点均为格点，即横坐标和纵坐标均为整数。
2.三角形的面积为 。
3.三角形至少有一条边和 轴或 轴平行。
honoka想知道，在平面中选取一个大小为 的矩形格点阵，可以找到多少个不同的“好三角形”？由于答案可能过大，请对取模。
输入描述:
两个正整数和
输出描述:
面积为1的格点三角形的数量，对取模的结果。
示例1
输入
2 3
输出
6
说明
格点如下：

*  *  *
*  *  *

不妨设左下角坐标为(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
输入
100 100
输出
7683984
说明
这里太小写不下啦。

Problem solving:
这道题的意思就是给你一个n*m的矩形，让你在里面找面积为1并且三角形顶点都处于端点的三角形的个数。
分情况考虑：

  • 两条边都与坐标轴平行
    一个的矩形中有个这样的好三角形，所以我们只需要统计这样的矩形有多少即可。即
  • 只有一条边与坐标轴平行
    底边为高为时
    底边与x轴平行时，每一条与x轴平行的边有种情况满足底边为2，并且它对应的满足条件的三角形的顶点会有或种,如果这条边在中间，那么它可以组成的三角形个数就是，如果是上下底边就是种。这个挺好理解的，因为中间的边顶点可以在上面也可以在下面。所以总数是
    底边与y轴平行时，跟与x轴的情况是一样的，我们换一下nm即可，就是
    底边为高为时
    底边与x轴平行时，每一条与x轴平行的边有种情况满足底边为1，并且它对应的满足条件的三角形的顶点会有或种，如果这两边是上下底边或者紧挨上下底边的四条边之一，顶点数是，否则就是。所以总数就是
    底边与y轴平行时，跟与x轴的情况是一样的，我们换一下nm即可，就是

将上面三种情况加在一起化简后变成

直接计算即可。注意取模

Code：

#include<bits/stdc++.h>>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
int main()
{
    ll m,n;
    cin>>m>>n;
    ll ans=(2*(m+n-2)%mod*((n-2)%mod*(m-1)%mod+(m-2)%mod*(n-1)%mod))%mod;
    cout<<ans<<endl;
    return 0;
}

B kotori和bangdream

Description:
有一天，kotori发现了一个和lovelive相似的游戏：bangdream。令她惊讶的是，这个游戏和lovelive居然是同一个公司出的！
kotori经过一段时间的练习后已经变得非常触，每个音符 的概率perfect，获得分， 概率great，获得分。
已知一首歌有个音符。kotori想知道，不考虑连击加成的话，一首歌得分的期望是多少？

输入描述:
一行个整数，用空格隔开。分别是。

输出描述:
一首歌得分的期望，保留两位小数。
示例1
输入
100 50 500 400
输出
45000.00
说明
如果全perfect是50000分，全great是40000分。由于它们的概率都是50%，即perfect和great五五开，所以期望是45000分。

Problem solving:
这道题的意思就是会有两种情况的得分，每种情况的得分数和概率都给出来了。直接相乘就行了，注意精度

#include<bits/stdc++.h>
using namespace std;
int main()
{
    double n,x,a,b;
    cin>>n>>x>>a>>b;
    double ans=a*n*x/100+b*(100-x)*n/100;
    printf("%.2lf\n",ans);
}

C umi和弓道

Description:
umi对弓道非常痴迷。
有一天，她在研究一个射箭问题：
在一个无限大的平面中，她站在这个坐标。
有个靶子，第个靶子的坐标是
umi准备在轴或轴上放置一块挡板来挡住弓箭的轨迹，使得她可以射中的靶子数量不超过个。
她想知道挡板的最短长度是多少？
注：假定弓箭的轨迹是起点为umi坐标、长度无穷大的射线。umi和靶子的体积可以无视。挡板的边缘碰到弓箭轨迹也可视为挡住弓箭。
注2：挡板不能弯折，起始和终点必须在同一坐标轴上。
输入描述:
第一行两个整数,代表umi的坐标。
第二行两个正整数和，分别代表靶子的总数量、放置挡板后可射中靶子的最大值。
接下来的行，每行两个整数和 。代表每个靶子的坐标。
保证没有任何一个点在坐标轴上（无论umi还是靶子），保证没有任何两点重合。

输出描述:
若无论如何无法保证可以射中的靶子数量不超过个，则输出。
否则输出挡板的最小长度。如果你和正确答案的误差不超过，则视为答案正确。
示例1
输入
1 1
2 0
-1 2
-2 1
输出
0.50000000
说明
umi要保证能射中的靶子不超过0个，即全部挡住。在y轴上选区间[1,1.5]放置一个长度为0.5的挡板即可。

Problem solving:
这道题比赛的时候没看。发现还是挺简单的一道题。
这道题的就是给你一个坐标作为起点，然后会有n个点的坐标。问你能否通过挡住x轴或者y轴上的某一部分使得，从起点的射线所能到达的点的个数不超过个。首先如果在一个象限内是肯定挡不住的，然后我们把每个点（除了与起点同象限的点）和起点的连线与x轴，y轴的交点记录下来。记录完之后排序，然后每隔k个做差统计最小值即可。

注意下标

Code:

#include <bits/stdc++.h>
using namespace std;
const int    maxn = 1e5 + 10;
const double INF = 0x3f3f3f3f3f3f3f3f;
double       xx[maxn], yy[maxn];
int main()
{
    double x, y;
    int    n, k, pos1 = 0, pos2 = 0;
    cin >> x >> y >> n >> k;
    k = n - k;
    for (int i = 0, a, b; i < n; i++)
    {
        cin >> a >> b;
        if (a * x < 0)
            xx[pos1++] = y - x * (b - y) / (a - x);
        if (b * y < 0)
            yy[pos2++] = x - y * (a - x) / (b - y);
    }
    sort(xx, xx + pos1); sort(yy, yy + pos2);
    double ans = INF;
    for (int i = 0; i < pos1; i++)
    {
        if (i + k > pos1)
            break;
        ans = min(ans, xx[i + k - 1] - xx[i]);
    }
    for (int i = 0; i < pos2; i++)
    {
        if (i + k > pos2)
            break;
        ans = min(ans, yy[i + k - 1] - yy[i]);
    }
    if (ans == INF)
        cout << "-1\n";
    else
        printf("%.6lf\n",ans);
    return 0;
}

D hanayo和米饭

Description:
hanayo很喜欢吃米饭。
有一天，她拿出了个碗，第一个碗装了粒米饭，第二个碗装了粒米饭，以此类推，第个碗装了粒米饭。
然而，爱搞恶作剧的rin把所有的碗的顺序打乱，并拿走了一个碗。hanayo想知道，rin拿走的碗里有多少粒米饭？
输入描述:
第一行输入一个正整数。代表原始的总碗数。
第二行输入正整数代表目前每碗里米饭数量。
保证输入合法。

输出描述:
输出一个正整数，代表rin拿走的碗里米饭数量。
示例1
输入
5
2 5 1 3
输出
4
说明
开始共有5个碗，每个碗内分别有1、2、3、4、5粒米饭。rin拿走的是第四碗。这么简单的样例连tairitsu都看得懂好伐~

Problem solving:
这道题没什么好说的，签到

Code:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n,a,b,sum=0;
    cin>>n;
    a=(n+1)*n/2;
    for(int i=1;i<n;i++)    cin>>b,sum+=b;
    cout<<a-sum<<endl;
}

E rin和快速迭代

Description:
rin最近喜欢上了数论。
然而数论实在太复杂了，她只能研究一些简单的问题。
这天，她在研究正整数因子个数的时候，想到了一个“快速迭代”算法。设为的因子个数，将迭代下去，rin猜想任意正整数最终都会变成。
例如：。
她希望你帮她验证一下。她会给你一个正整数，让你输出它在迭代过程中，第一次迭代成的迭代次数。
输入描述:
一个正整数
输出描述:
一个正整数，为迭代至的次数。
示例1
输入
12
输出
4
说明
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次。

Problem solving:
这道题直接跟着题目的描述模拟暴力写即可。

Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll n, ans = 0, mid = 0;
    cin >> n;
    for (ll i = 1; i * i < n; i++)
        if (n % i == 0)
            mid += 2;
    if ((ll) sqrt(n) * (ll) sqrt(n) == n)
        mid++;
    if (mid == 2)
    {
        cout << "1\n"; return 0;
    }
    else
        ans = 1;
    while (mid != 2)
    {
        ll mm = 0;
        ans++;
        for (ll i = 1; i * i < mid; i++)
            if (mid % i == 0)
                mm += 2;
        if ((ll) sqrt(mid) * (ll) sqrt(mid) == mid)
            mm++;
        mid = mm;
    }
    cout << ans << endl;
    return 0;
}

F maki和tree

Description:
有一天，maki拿到了一颗树。所谓树，即没有自环、重边和回路的无向连通图。
这个树有个顶点，条边。每个顶点被染成了白色或者黑色。
maki想知道，取两个不同的点，它们的简单路径上有且仅有一个黑色点的取法有多少？
注：

  1. 树上两点简单路径指连接两点的最短路。
  2. 和的取法视为同一种。

输入描述:
第一行一个正整数。代表顶点数量。
第二行是一个仅由字符'B'和'W'组成的字符串。第个字符是B代表第个点是黑色，W代表第个点是白色。
接下来的行，每行两个正整数 ，，代表点和点有一条边相连

输出描述:
一个正整数，表示只经过一个黑色点的路径数量。
示例1
输入

3
WBW
1 2
2 3
输出

3
说明
树表示如下：


其中只有2号是黑色点。

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

Problem solving:
这道题就是给了你一棵树，每个节点都有颜色，黑色或者白色。问你有多少条路径经过黑色节点。
我们可以把白点当成连通块处理，并且把这一块百点中的任意一个百点的值赋为连通块中节点的数量。
然后每遇到一个黑点计算一次。对与黑点相连的点，如果是白色，答案加上这个白色的所处连通块的节点数量。但是有可能存在一个黑点连接好几个白点的情况，这个时候同时也得计算两个端点都是白色节点的路径数，统计一下之前相连的所有白色节点的个数相乘即可。

注意会爆int

这道题也可以用带权并查集，bfs写，但是dfs会简洁一点。

Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb    push_back
const ll  maxn = 1e5 + 10;
ll        n, ans, p[maxn]; char s[maxn];
bool        vis[maxn];
vector<int> V[maxn];
vector<int> mid;
void dfs(ll x)
{
    mid.pb(x), vis[x] = 1;
    for (ll i = 0; i < V[x].size(); i++)
    {
        if (s[V[x][i]] == 'W' && !vis[V[x][i]])
            dfs(V[x][i]);
    }
}
int main()
{
    cin >> n;
    scanf("%s", s + 1);
    for (ll i = 1, u, v; i < n; i++)
    {
        cin >> u >> v;
        V[u].pb(v); V[v].pb(u);
    }
    for (ll i = 1; i <= n; i++)
    {
        if (vis[i] || s[i] == 'B')
            continue;
        mid.clear(); dfs(i);
        ll mi = mid.size();
        for (ll i = 0; i < mi; i++)
            p[mid[i]] = mi;
    }
    for (ll i = 1; i <= n; i++)
    {
        ll m = 0;
        if (s[i] == 'B')
        {
            for (ll j = 0; j < V[i].size(); j++)
            {
                if (s[V[i][j]] == 'W')
                {
                    ans += m * p[V[i][j]] + p[V[i][j]];
                    m   += p[V[i][j]];
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

G eli和字符串

Description:
eli拿到了一个仅由小写字母组成的字符串。
她想截取一段连续子串，这个子串包含至少个相同的某个字母。
她想知道，子串的长度最小值是多少？
注：所谓连续子串，指字符串删除头部和尾部的部分字符（也可以不删除）剩下的字符串。例如：对于字符串“arcaea”而言，“arc”、“rcae”都是其子串。而“car”、“aa”则不是它的子串。
输入描述:
第一行输入两个正整数和
输入仅有一行，为一个长度为的、仅由小写字母组成的字符串。
输出描述:
如果无论怎么取都无法满足条件，输出。
否则输出一个正整数，为满足条件的子串长度最小值。
示例1
输入
5 2
abeba
输出
3
说明
选择“beb”子串，长度为3，其中包含相同的两个'b'

Problem solving:
这道题的意思是给你一个字符串，让你找一个最短的子串里面包含k个相同字母。
因为保证只有小写字母，所以我们统计每个字母出现的位置，然后每次计算k个相邻字母的距离，直接位置相减即可。并且每次更新最小值。

Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int   maxn = 2e5 + 10;
vector<int> V[30];
int main()
{
    int n, k, ans = 1e9; string s;
    cin >> n >> k >> s;
    if (k == 1)
    {
        cout << "1\n"; return 0;
    }
    for (int i = 0; i < n; i++)
        V[s[i] - 'a'].push_back(i);
    for (int i = 0; i < 26; i++)
    {
        int l = V[i].size();
        if (l < k)
            continue;
        for (int j = 0; j < l; j ++)
        {
            if (j + k - 1 >= l)
                break;
            ans = min(V[i][j + k - 1] - V[i][j] + 1, ans);
        }
    }
    if (ans == 1e9)
        ans = -1;
    cout << ans << endl;
    return 0;
}

H nozomi和字符串

Description:
nozomi看到eli在字符串的“花园”里迷路了，决定也去研究字符串问题。
她想到了这样一个问题：
对于一个 “01”串而言，每次操作可以把 字符改为 字符，或者把 字符改为 字符。所谓“01”串，即只含字符 和字符 的字符串。
nozomi有最多次操作的机会。她想在操作之后找出一个尽可能长的连续子串，这个子串上的所有字符都相同。
nozomi想问问聪明的你，这个子串的长度最大值是多少？
注：次操作机会可以不全部用完。
如果想知道连续子串的说明，可以去问问eli，nozomi不想再讲一遍。
输入描述:
第一行输入两个正整数和
输入仅有一行，为一个长度为 的、仅由字符 和 组成的字符串。
输出描述:
一个正整数，为满足条件的子串长度最大值。
示例1
输入
5 1
10101
输出
3
说明
只有次操作机会。
将第二个位置的 改成 ，字符串变成 ，可以选出 “111”子串，长度为。
如果修改第三个或者第四个位置的字符也可以选出长度为的子串。

Problem solving:
这道题跟上一道题很像，这道题的意思是给你一个只有01组成的字符串，你有k次机会可以把0变成1，或者把1变成0.问你可以找到的最大的子串长度，要求子串中的每一个元素都相等，即都是1或者都是0
我们仍然统计0和1的出现位置，现在假如我们考虑把1换成0，那我们只需要看1的位置中，中间有k个1的两个1之间的距离就是此时可以达到的最大子串长度。
把0换成1也是一样的。每次更新最大值即可

注意有一些细节需要处理，具体可以看代码去理解。
Code:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 10;
typedef long long ll;
#define pb    push_back
vector<ll> v[5];
int main()
{
    ll x = 0, y = 0, n, k, ans = 1; string s;
    cin >> n >> k >> s;
    for (int i = 0; i < n; i++)
        v[s[i] - '0'].pb(i);
    v[0].pb(n),v[1].pb(n);
    x = v[0].size(), y = v[1].size();
    if (k >= x-1 || k >= y-1)
    {
        cout << n << endl;
        return 0;
    }
    for (int i = 0; i < x; i++)
    {
        if (i + k >= x)
            break;
        ans = max(ans, v[0][i + k+1] - v[0][i] -1);
    }
    for (int i = 0; i < y; i++)
    {
        if (i + k >= y)
            break;
        ans = max(ans, v[1][i + k+1 ] - v[1][i] -1);
    }
    cout << ans << endl;
}

I nico和niconiconi

Description:
nico平时最喜欢说的口头禅是niconiconi~。
有一天nico在逛著名弹幕网站"niconico"的时候惊异的发现，n站上居然有很多她的鬼畜视频。其中有一个名为《让nico为你洗脑》的视频吸引了她的注意。
她点进去一看，就被洗脑了:"niconicoh0niconico*^vvniconicoG(vniconiconiconiconiconicoG(vniconico......"
弹幕中刚开始有很多“nico1 nico2”等计数菌，但到后面基本上都是“计数菌阵亡”的弹幕了。
nico也想当一回计数菌。她认为："nico" 计分，"niconi" 计分，"niconiconi" 计分。
她拿到了一个长度为 的字符串，请帮她算出最大计数分数。
注：已被计数过的字符不能重复计数！如"niconico"要么当作"nico"+"nico"计分，要么当作"niconi"+"co"计分。
输入描述:
第一行四个正整数 .
第二行是一个长度为的字符串。
输出描述:
一个整数，代表最大的计数分数。
示例1
输入
19 1 2 5
niconiconiconiconi~
输出
7
说明
"niconi"co"niconiconi"~
故为2+5=7分

Problem solving:
这道题的意思就是给你一个字符串，不同的子串可以有不同的分数，问你最多可以得多少分。
就是一个dp，找到状态转移方程就可以了。

状态转移方程：

Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 3e5 + 10;
ll       dp[maxn];
int main()
{
    string s; ll n, a, b, c;
    cin >> n >> a >> b >> c >> s;
    for (ll i = 0; i < n; i++)
    {
        if (i > 0)
            dp[i] = dp[i - 1];
        if (i >= 3 && s.substr(i - 3, 4) == "nico")
            dp[i] = max(dp[i], dp[i - 3] + a);
        if (i >= 5 && s.substr(i - 5, 6) == "niconi")
            dp[i] = max(dp[i], dp[i - 5] + b);
        if (i >= 9 && s.substr(i - 9, 10) == "niconiconi")
            dp[i] = max(dp[i], dp[i - 9] + c);
    }
    cout << dp[n - 1] << endl;
    return 0;
}

J u's的影响力

μ's在九人齐心协力下，影响力越来越大了！
已知第一天影响力为 ，第二天影响力为 ，从第三天开始，每一天的影响力为前两天影响力的乘积再乘以 的 次方。 用数学语言描述是：
设第 天的影响力为 ，那么 ， ，对于 ，
她们想知道第天影响力是多少？
由于这个数可能非常大，只需要输出其对取模的值就可以了。
输入描述:
一行五个正整数:。

输出描述:
第天的影响力对取模的值。
示例1
输入
4 2 3 2 1
输出
72
说明
f(1)=2，f(2)=3，f(3)=f(1)f(2)2=12，f(4)=f(2)f(3)2=72
备注:
1000000007是素数。

Problem solving:
题意挺明确的，就是一个递推式，让你求第n项，但是这第n项求起来就很难。
待补

官方题解

赏