子串查询

Description:
给出一个长度为n的字符串s和q个查询。对于每一个查询，会输入一个字符串t，你需要判断这个字符串t是不是s的子串。子串的定义就是存在任意下标a<b<c<d<e，那么”s[a]s[b]s[c]s[d]s[e]”就构成s的一个子串。如”abc”的子串有”a”、”b”、”c”、”ab”、”ac”、”bc”、”abc”。
输入描述:
第一行两个数n，q。1<=n，q<=1e5。

第二行一个长度为n的字符串s,所有字符都为小写拉丁字符。

接下来q行每行一个字符串t。1<=|t|<=50。
输出描述:
对于每个查询，如果t是s的字串，输出”YES”,否则输出”NO”。每个答案占一行。
示例1
输入
8 4
ababcbaa
abac
accb
aaaa
abcba
输出
YES
NO
YES
YES

Problem solving:
这道题我一看还以为是跟之前暑假集训时候的一到积分赛的题一样。然后直接暴力着写，T了4发。后来才发现暴力的话是1e5乘1e5。然后学长说序列自动机。百度了一下。发现就是序列自动机裸题
说一下我对序列自动机的理解吧。nxt[i][j]就是用一个二维数组存一下以当前位置i为起点的第一次出现j(j可以用0-26表示a-z)的位置。具体的我也说不清，看代码悟吧。
Code:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int       nxt[maxn][30], now[30];
int main()
{
    memset(now, -1, sizeof(now));
    int    n, q, flag, ans;
    string a, b;
    cin >> n >> q >> a;
    for (int i = a.size() - 1; i >= 0; i--)
    {
        for (int j = 0; j < 26; j++)
        {
            nxt[i][j] = now[j];
        }
        now[a[i] - 'a'] = i;//用now数组存一下当前字母的位置。
    }
    for (int i = 0; i < a.size(); i++)
    {
        cout << now[a[i] - 'a'];
        for (int j = 0; j < 26; j++)
        {
            cout << nxt[i][j] << endl;
        }
    }
    while (q--)
    {
        flag = 0;
        cin >> b;
        int mid = now[b[0] - 'a'];
        if (mid == -1)
        {
            puts("NO");
            continue;
        }
        for (int i = 1; i < b.size(); i++)
        {
            mid = nxt[mid][b[i] - 'a'];
            if (mid == -1)
            {
                flag = 1;
                break;
            }
        }
        if (!flag)
            puts("YES");
        else
            puts("NO");
    }
}

勾股定理

Description:
给出直角三角形其中一条边的长度n，你的任务是构造剩下的两条边，使这三条边能构成一个直角三角形。
输入描述:
一个整数n。
输出描述:
另外两条边b,c。答案不唯一，只要输出任意一组即为合理，如果无法构造请输出-1。
示例1
输入
3
输出
4 5
示例2
输入
4
输出
3 5
备注:
0<=n<=1e9

1<=b,c<=1e18

n,b,c均为整数
Problem solving:
这道题没什么意思。是个规律，我也没找到。把这个题放在这就是为了记一下这个规律，万一以后有用呢。

对小范围数据进行打表，即可发现存在以下规律：
1.当n>2时总有方法可以构造
2.当n是奇数总存在两条边b,c使得c-b==1并且n^2+b^2=c^2
3.当n是偶数总存在两条边b,c使得c-b==2并且n^2+b^2=c^2
因此我们可以设边c=x,分n是奇数和偶数的情况，有
1.n是奇数，b=x-1->n^2+(x-1)^2=x^2->x=(n^2+1)/2
2.n是偶数，b=x-2->n^2+(x-2)^2=x^2->x=(n^2+4)/4

源于：牛客练习赛51题解

Code:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n;
    cin>>n;
    if(n<=2)    puts("-1");
    else if(n&1)    cout<<(n*n+1)/2-1<<" "<<(n*n+1)/2<<endl;
    else    cout<<(n*n+4)/4-2<<" "<<(n*n+4)/4<<endl;
    return 0;
}

羊吃草

链接：https://ac.nowcoder.com/acm/contest/1083/D
来源：牛客网

有一个草原可以用一个1~400的数轴表示。有n头羊和q个查询。每头羊的编号分别是1，2，3…n。第i头羊只喜爱数轴上[ai，bi]这样的一个闭区间，每一时刻每头羊只可能在自己喜爱的区间的某个点上吃草。现在给出q个查询，每个查询两个整数l，r。你需要计算出在同一时刻，最多能有多少头羊同时在这个区间内吃草。数轴上每一个整点同一时刻只能容纳一只羊，羊只会在整点吃草。

输入描述:
第一行三个数n q。

第二行n个数a1 a2…an。

第三行n个数b1 b2…bn。

接下来q行每行两个数l，r。表示询问的区间。
输出描述:
对于每个查询，输出一个整数表示答案。
示例1
输入
5 3
1 1 1 2 4
1 1 1 3 5
1 5
2 5
1 3
输出
3
2
2
备注:
1<=n，q<=400

1<=ai<=bi<=400

1=l<=r<=400

Problem solving:
这道题我看题解里面写了一堆看不懂的东西。但是看通过代码的时候看到一个巨佬用贪心过了。
把每只羊能吃的草的范围用结构体存一下。然后以左端点升序排序。保证当前位置能来的羊尽可能的不去干扰下一个羊。感觉有点类似于看电视的那道题了。没个地方最多只能有一只羊，所以需要一个标记数组。
Code:

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int l, r;
}    p[500];
bool vis[500];
bool cmp(node a, node b)
{
    if (a.r == b.r)
        return a.l < b.l;
    return a.r < b.r;
}
int main()
{
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; i++)
        cin >> p[i].l;
    for (int j = 0; j < n; j++)
        cin >> p[j].r;
    sort(p, p + n, cmp);
    while (q--)
    {
        memset(vis, 0, sizeof(vis));
        int l, r, ans = 0;
        cin >> l >> r;
        for (int i = 0; i < n; i++)
        {
            for (int j = p[i].l; j <= p[i].r; j++)
            {
                if (j >= l && j <= r && !vis[j])
                {
                    ans++, vis[j] = 1;
                    break;
                }
            }
        }
        cout << ans << endl;
    }

    return 0;
}
赏