牛客网OJ题解--20210131

两条斜线

https://ac.nowcoder.com/acm/problem/18951

本系列记录翀翀😐痛苦的刷题日志，所有题目均来自于牛客网OJ题目，坚持刷题谈起来容易做起来难，希望我可以坚持下去，这里仍然分享一段励志文案：每个人都有梦想，然而有些人把梦想变成了现实，有些人的梦想依旧是梦想，只因为他们为梦想付出的努力程度不一样，他们坚持的时间不一样，最终才有这样的结果。

NC18951-两条斜线

题目链接

https://ac.nowcoder.com/acm/problem/18951

题目描述

平面上有N个点，用两个斜率分别为1和-1的斜线，尽可能的穿过更多的点，输出这个最大数量值。保证1<=N<=1000,0<=x[i],y[i]<=999。第一行是N，第二行是N个点的横坐标，第三行是N个点的纵坐标。

测试样例

输入

4
1 4 4 5
3 0 2 3

输出

说明

(1,3) (4,0) (4,2) (5,3)四个点都可以被经过

解题思路

我们假设两个斜线分别是y=x+r1和y=-x+r2，我们每次都任取两个点分别求出r1,r2,然后统计在这两个斜线上的顶点的总数量，记录最大值。

解题代码

#include <bits/stdc++.h>
using namespace std;

//假设y=x+r1,y=-x+r2
int main()
{
    int n;
    int sum = 0;
    cin >> n;
    int x[1000] = {};
    int y[1000] = {};
    int vis[1000] = {};
    for (int i = 0; i < n; i++)
    {
        cin >> x[i];
    }
    for (int i = 0; i < n; i++)
    {
        cin >> y[i];
    }
    int r1, r2;
    int tmp = 0;
    for (int i = 0; i < n; i++)
    {
        r1 = y[i] - x[i];
        //任取一个点计算出斜率为1的r1值
        for (int j = 0; j < n; j++)
        {
            tmp = 0;
            r2 = y[j] + x[j];
            //任取一个点计算出斜率为-1的r2值
            for (int k = 0; k < n; k++)
            {
                if (x[k] + y[k] == r2 || y[k] - x[k] == r1)
                {
                    //统计在这两条上的点
                    tmp++; 
                }
            }
            if (sum < tmp)
            {
                //记录最大值
                sum = tmp; 
            }
        }
    }
    cout << sum << endl;
    system("pause");
    return 0;
}

NC21297-手机号码

题目链接

https://ac.nowcoder.com/acm/problem/21297

题目描述

第一行给出一个数字n和m，n表示一个电话号码的位数，m表示接下来给出的mg个号码前缀（注意，可能会出现1,12,123这样有重复的前缀)。接下来给出m行是m个号码前缀。

测试样例

样例1

输入

输出

样例2

输入

输出

7990000000

样例3

输入

输出

90000000

样例4

输入

输出

970000000

样例5

输入

3 1
411

输出

解题思路

我们知道实际上就是先默认有10^n中情况（每一位都是0~9十个取值）。对于一个前缀为123长度为3，那么以123开头的情况(一共有10^(n-3)个情况)就都排除了，但是同时要完成去重1前缀和12前缀的这种情况即可。

解题代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, m;
    cin >> n >> m;
    string a[55];
    int vis[55];                //1代表不是另一个前缀的一部分
    long long sum = pow(10, n); //一共有10^n个情况
    for (int i = 1; i <= m; i++)
    {
        cin >> a[i], vis[i] = 1;
    }
    for (int i = 1; i <= m; i++)
    {
        int s = a[i].size(); //前缀的长度
        for (int j = 1; j <= m; j++)
        //检验这个前缀是否是另一个前缀的一部分
        {
            //string的find函数，返还a[j]在a[i]的起始位置，没有则返还为-1
            int d = a[i].find(a[j]);
            if (d == 0 && i != j)
            {
                //是另一个前缀的一部分，比如1是12的前缀的一部分
                vis[i] = 0; //那么他就不是一个前缀了
                break;
            }
        }
        if (vis[i])
        {
            //如果是一个前缀，那么后面的所有情况都是符合前缀开头的，剪掉这种情况
            sum -= (long long)pow(10, n - s);
        }
    }
    cout << sum;
    return 0;
}