AYITOJ ROUND #3

A.TAT

Descriptiion:

给定一个字符串s, 问"TAT"是否为s的子串

一个字符串 s 被称作另一个字符串 S 的子串，表示 s 在 S 中出现了。比如，“中出”是“我们中出了一个叛徒”的子串。

注意子串和子序列是不同的：“苹机”是“苹果手机”的子序列，而不是子串。

前缀和后缀是两种特殊的子串：一个前缀在原串的开始位置出现，而一个后缀在原串的末端出现。

例如，“苹果手机”的所有子串是：“”（空串），“苹”，“果”，“手”，“机”，“苹果”，“果手”，“手机”，“苹果手”，“果手机”，“苹果手机”。

以上摘自维基百科~

Input:

仅一行, 一个字符串s

保证该字符串中仅含有大写字母

数据范围

∣ s ∣ |s| ∣s∣ <= 100000 100000 100000

Output:

仅一行, 一个字符串"Yes"表示"TAT"是s的子串, 否则输出"No"

Sample Input:

TATATAT

Sample Output:

Yes

Sample Input:

TAAT

Sample Output:

No

题目链接

直接用C++ STL的string.find!=string::npos就可以查找判断子串。

手写KMP也可。

AC代码:

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

int main(int argc, char *argv[]) {
    string Str;
    cin >> Str;
    if (Str.find("TAT") != string::npos) {
        printf("Yes\n");
    }
    else {
        printf("No\n");
    }
    return 0;
}

B.计算表达式

Descriptiion:

给定一个形如 a # b a \# b a#b 的表达式

求这个表达式所代表的值

#可以为+(加),*(乘),^(幂)三种运算符的任意一种

由于结果可能很大, 你只需输出其对1000000007取膜的结果即可

Input:

第一行两个整数 T T T 表示表达式的总数

接下来 T T T 行每行一个表达式 a a a # b b b

数据范围

$ 0 < T <= 10 ​$

$ 0 <= a , b <= 10^9$

Output:

共T行, 每行一个整数, 表示对应表达式所表示的值

Sample Input:

3
1 + 1
2 * 2
2 ^ 3

Sample Output:

2
4
8

题目链接

两个数的运算，幂运算写了个快速幂，不过最后好像没卡？

AC代码:

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

const int mod = 1e9 + 7;

long long QuickMul(long long A, long long B) {
    long long Ans = 0;
    while (B) {
        if (B & 1) {
            Ans = (Ans + A) % mod;
        }
        A = (A + A) % mod;
        B >>= 1;
    }
    return Ans;
}

long long QuickPow(long long A, long long B) {
    long long Ans = 1;
    while (B) {
        if (B & 1) {
            Ans = QuickMul(Ans, A) % mod;
        }
        A = QuickMul(A, A) % mod;
        B >>= 1;
    }
    return Ans;
}

int main(int argc, char *argv[]) {
    long long A, B;
    char Op;
    int T;
    cin >> T;
    while (T--) {
        cin >> A >> Op >> B;
        if (Op == '+') {
            cout << (A + B) % mod << endl;
        }
        else if (Op == '*') {
            cout << QuickMul(A, B) << endl;
        }
        else if (Op == '^') {
            cout << QuickPow(A, B) << endl;
        }
    }
    return 0;
}

C.飞行棋

Descriptiion:

飞行棋是一款十分有趣的游戏

不过在这里, 我们只考虑如下的简化重制版本:

  1. 棋盘为一个数轴 ( − ∞ , + ∞ ) (-∞,+∞) (−∞,+∞)

  2. 如果玩家当前在 x x x, 那么下一步他可以走到 x − 1 x-1 x−1 或 x + 1 x+1 x+1

  3. 特殊地, 在某些位置 a i a_i ai​ 上, 玩家可以从当前位置直接一步跳到另一个位置 b i b_i bi​ 上

  4. 玩家一开始在 S S S, 请问玩家走到 T T T 至少需要走多少步?

Input:

第一行三个整数 n , S , T n,S,T n,S,T 分别表示可以直接跳跃的点数和玩家的起点与终点

接下来 n n n 行每行2个整数 a i , b i a_i ,b_i ai​,bi​ 表示从 a i a_i ai​ 可以直接一步跳到 b i b_i bi​

数据范围

$ 0 <= n <= 2 * 10^{5} $

$ 0 <= |a_i| , |b_i| , |S| , |T| <= 10^{18}$

保证 a i <mpadded width="0px"> ̸ </mpadded> = a j ( i <mpadded width="0px"> ̸ </mpadded> = j ) , a i <mpadded width="0px"> ̸ </mpadded> = b i a_i \not= a_j (i \not= j), a_i \not= b_i ai​̸​=aj​(i̸​=j),ai​̸​=bi​

友情提示: 请注意坐标可以为负数!

Output:

仅一行, 一个整数, 表示玩家从 S S S 走到 T T T 最少需要的步数

Sample Input:

3 1 20
1 11
10 5
6 20

Sample Output:

5

题目链接

最开始没想到是个图论题，一直在Bfs搜索，不过数据有点大，正解是建图跑最短路。

只有跳跃点有用，先把所有点离散化，之后把每个跳跃点与左右最近的跳跃点建权值为其距离的边，把跳跃两点建权值为1的边用Dijkstra求起点到终点的最短路即可。

AC代码:

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

const int maxn = 2e5 + 5;

struct Edge {
    long long V, Dis, Next;
};

Edge edges[maxn << 4];
int Head[maxn << 1];
int Tot;

void Init() {
    Tot = 0;
    memset(Head, -1, sizeof(Head));
}

void AddEdge(int U, int V, long long Weight) {
    edges[Tot] = Edge {V, Weight, Head[U]};
    Head[U] = Tot++;
}

long long Dis[maxn << 1];

struct Cmp {
    bool operator () (const int &A, const int &B) {
        return Dis[A] > Dis[B];
    }
};

long long Dijkstra(int Start, int End) {
    priority_queue<int, vector<int>, Cmp> Que;
    memset(Dis, 0x3f, sizeof(Dis));
    Dis[Start] = 0;
    Que.push(Start);
    while (!Que.empty()) {
        int Cur = Que.top(); Que.pop();
        if (Cur == End) {
            return Dis[End];
        }
        for (int i = Head[Cur]; ~i; i = edges[i].Next) {
            if (Dis[edges[i].V] > Dis[Cur] + edges[i].Dis) {
                Dis[edges[i].V] = Dis[Cur] + edges[i].Dis;
                Que.push(edges[i].V);
            }
        }
    }
    return -1 * 1LL;
}

long long N, S, T;
long long U[maxn], V[maxn];
long long numbers[maxn << 1];
long long Cnt, Size;

int Disperse(long long X) {
    return lower_bound(numbers, numbers + Size, X) - numbers + 1;
}

int main(int argc, char *argv[]) {
    Init();
    scanf("%lld%lld%lld", &N, &S, &T);
    Cnt = 0;
    numbers[Cnt++] = S; numbers[Cnt++] = T;
    for (long long i = 1; i <= N; ++i) {
        scanf("%lld%lld", &U[i], &V[i]);
        numbers[Cnt++] = U[i]; numbers[Cnt++] = V[i];
    }
    sort(numbers, numbers + Cnt);
    Size = unique(numbers, numbers + Cnt) - numbers;
    for (int i = 0; i < Size - 1; ++i) {
        AddEdge(i + 1, i + 2, numbers[i + 1] - numbers[i]);
        AddEdge(i + 2, i + 1, numbers[i + 1] - numbers[i]);
    }
    for (int i = 1; i <= N; ++i) {
        AddEdge(Disperse(U[i]), Disperse(V[i]), 1);
    }
    printf("%lld\n", Dijkstra(Disperse(S), Disperse(T)));
    return 0;
}

E.求和问题

Descriptiion:

你现在有一个数组 A A A

我们定义如下的两种操作:

  1. 修改: 形如 0 0 0 l l l r r r ,效果为对所有 $ l <= i <=r $ 执行 $ A_i += (i-l+1) $

直观地说就是 A l + = 1 , A l + 1 + = 2 , A l + 2 + = 3 <mtext>   </mtext> . . . <mtext>   </mtext> A r + = r − l + 1 A_l+=1, A_{l+1}+=2, A_{l+2}+=3 \ ... \ A_{r}+=r-l+1 Al​+=1,Al+1​+=2,Al+2​+=3 ... Ar​+=r−l+1 这个样子

  1. 查询: 形如 1 1 1 l l l r r r , 要求输出此时的 $ \sum_{i=l}^{r}A_i $ 的值

一开始当然整个数组都是0啦

Input:

第一行一个整数Q表示操作总数

接下来Q行, 每行一个操作(格式参考题目描述)

Output:

对于每个查询, 输出一行, 表示此时的 $ \sum_{i=l}^{r}A_i $ 的值

Sample Input:

3
0 1 2
0 3 4
1 1 4

Sample Output:

6

题目链接

这个题用两个Lazy惰性数组标记进行等差数列的相加，Tql……

Lazy1：当前区间上的未下传的要加的值

Lazy2：当前区间上的未下穿的等差数列的数量

Lazy1和普通线段树的Lazy一样，而Lazy2则改为了等差数列的下传数量

Example:若要加{1,2,3,4}，则把它拆为{1,2},{3,4}，其中{1,2}传给其左子树的Lazy2(一份等差数列)，而{3,4}拆开为{1,2}和{2,2}，其中{2,2}传给其右子树的Lazy1，{1,2}传给其右子树的Lazy2(一份等差数列)

AC代码:

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

const long long maxn = 1e5 + 5;

struct Node {
    long long Left, Right;
    long long Lazy1, Lazy2;
    long long Sum;
};

Node SegmentTree[maxn << 2];

void PushDown(long long Root) {
    if (SegmentTree[Root].Lazy1) {
        SegmentTree[Root].Sum += SegmentTree[Root].Lazy1 * (SegmentTree[Root].Right - SegmentTree[Root].Left + 1);
        if (SegmentTree[Root].Left < SegmentTree[Root].Right) {
            SegmentTree[Root << 1].Lazy1 += SegmentTree[Root].Lazy1;
            SegmentTree[Root << 1 | 1].Lazy1 += SegmentTree[Root].Lazy1;
        }
        SegmentTree[Root].Lazy1 = 0;
    }
    if (SegmentTree[Root].Lazy2) {
        SegmentTree[Root].Sum += SegmentTree[Root].Lazy2 * (SegmentTree[Root].Right - SegmentTree[Root].Left + 1) * (SegmentTree[Root].Right - SegmentTree[Root].Left + 2) / 2;
        if (SegmentTree[Root].Left < SegmentTree[Root].Right) {
            SegmentTree[Root << 1].Lazy2 += SegmentTree[Root].Lazy2;
            SegmentTree[Root << 1 | 1].Lazy2 += SegmentTree[Root].Lazy2;
            SegmentTree[Root << 1 | 1].Lazy1 += SegmentTree[Root].Lazy2 * (SegmentTree[Root << 1].Right - SegmentTree[Root << 1].Left + 1);
        }
        SegmentTree[Root].Lazy2 = 0;
    }
}

void PushUp(long long Root) {
    PushDown(Root << 1); PushDown(Root << 1 | 1);
    SegmentTree[Root].Sum = SegmentTree[Root << 1].Sum + SegmentTree[Root << 1 | 1].Sum;
}

void Build(long long Left, long long Right, long long Root) {
    SegmentTree[Root] = Node {Left, Right, 0, 0, 0};
    if (Left == Right) {
        return;
    }
    long long Mid = (Left + Right) >> 1;
    Build(Left, Mid, Root << 1);
    Build(Mid + 1, Right, Root << 1 | 1);
}

void IntervalUpdate(long long Left, long long Right, long long Root) {
    if (SegmentTree[Root].Left >= Left && SegmentTree[Root].Right <= Right) {
        SegmentTree[Root].Lazy1 += SegmentTree[Root].Left - Left;
        SegmentTree[Root].Lazy2++;
        return;
    }
    long long Mid = (SegmentTree[Root].Left + SegmentTree[Root].Right) >> 1;
    if (Left <= Mid) {
        PushDown(Root);
        IntervalUpdate(Left, Right, Root << 1);
    }
    if (Right > Mid) {
        PushDown(Root);
        IntervalUpdate(Left, Right, Root << 1 | 1);
    }
    if (SegmentTree[Root].Left < SegmentTree[Root].Right) {
        PushUp(Root);
    }
}

long long Query(long long Left, long long Right, long long Root) {
    long long Ans = 0;
    PushDown(Root);
    if (SegmentTree[Root].Left >= Left && SegmentTree[Root].Right <= Right) {
        return SegmentTree[Root].Sum;
    }
    long long Mid = (SegmentTree[Root].Left + SegmentTree[Root].Right) >> 1;
    if (Left <= Mid) {
        Ans += Query(Left, Right, Root << 1);
    }
    if (Right > Mid) {
        Ans += Query(Left, Right, Root << 1 | 1);
    }
    return Ans;
}

long long T;
long long Op, Left, Right;
const long long Max = 1e5;

int main(int argc, char *argv[]) {
    Build(1, Max, 1);
    scanf("%lld", &T);
    for (long long Case = 1; Case <= T; ++Case) {
        scanf("%lld%lld%lld", &Op, &Left, &Right);
        if (Op == 0) {
            IntervalUpdate(Left, Right, 1);
        }
        else {
            printf("%lld\n", Query(Left, Right, 1));
        }
    }
    return 0;
}

F.斐波那契数列

Descriptiion:

没错又是大家熟悉的斐波那契数列~

什么你不知道? 没关系我们来给你定义:

F 1 = 1 , F 2 = 1 , F i = F i − 1 + F i − 2 ( i &gt; 2 ) F_1=1, F_2=1, F_i=F_{i-1}+F_{i-2}(i&gt;2) F1​=1,F2​=1,Fi​=Fi−1​+Fi−2​(i>2)

然后你需要求出 $ \sum_{i=l}^{r} F_i$ 的值, l , r l,r l,r 会由题目给出

由于答案可能很大, 你只需答案输出对1000000009 取膜的结果即可~

Input:

第一行一个整数T表示询问次数

接下来T行每行两个整数 l , r l,r l,r 表示询问 $ \sum_{i=l}^{r} F_i$ 的值

Output:

共T行, 每行一个整数表示对应的询问的答案

Sample Input:

3
1 2
3 5
233 456

Sample Output:

2
10
623800639

题目链接

毒瘤题石锤了……！

蒟蒻只能用矩阵快速幂+斐波那契数列前n项和公式+读写挂拿到200分(4个任务点)。

200分(未AC)代码:

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

const int mod = 1e9 + 9;

namespace FastIO {
    const int MX = 4e7;
    char buf[MX];
    int c, sz;
    void begin() {
        c = 0;
        sz = fread(buf, 1, MX, stdin);
    }
    template <class T>
    inline bool read(T &t) {
        while (c < sz && buf[c] != '-' && (buf[c] < '0' || buf[c] > '9')) {
            c++;
        }
        if (c >= sz) {
            return false;
        }
        bool flag = 0;
        if (buf[c] == '-') {
            flag = 1;
            c++;
        }
        for (t = 0; c < sz && '0' <= buf[c] && buf[c] <= '9'; ++c) {
            t = t * 10 + buf[c] - '0';
        }
        if (flag) {
            t = -t;
        }
        return true;
    }
};

struct Matrix {
    unsigned long long Mat[2][2];
    Matrix() {}
    Matrix operator * (Matrix const &A) const {
        Matrix Res;
        memset(Res.Mat, 0, sizeof(Res.Mat));
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 2; ++j) {
                for (int k = 0; k < 2; ++k) {
                    Res.Mat[i][j] = (Res.Mat[i][j] + Mat[i][k] * A.Mat[k][j] % mod) % mod;
                }
            }
        }
        return Res;
    }
};

Matrix operator ^ (Matrix Base, long long K) {
    Matrix Res;
    memset(Res.Mat, 0, sizeof(Res.Mat));
    Res.Mat[0][0] = Res.Mat[1][1] = 1;
    while (K) {
        if (K & 1) {
            Res = Res * Base;
        }
        Base = Base * Base;
        K >>= 1;
    }
    return Res;
}

unsigned long long Fib(unsigned long long X) {
    Matrix Base;
    Base.Mat[0][0] = Base.Mat[1][0] = Base.Mat[0][1] = 1;
    Base.Mat[1][1] = 0;
    return (Base ^ X).Mat[0][1];
}

unsigned long long Sum(unsigned long long N) {
    return Fib(N + 2) - 1;
}

unsigned long long T;
unsigned long long Left, Right;
long long Ans;

int main(int argc, char *argv[]) {
    FastIO::begin();
    FastIO::read(T);
    for (unsigned long long Case = 1; Case <= T; ++Case) {
        FastIO::read(Left); FastIO::read(Right);
        Ans = Sum(Right) - Sum(Left - 1);
        while (Ans < 0) {
            Ans += mod;
        }
        printf("%lld\n", Ans);
    }
    return 0;
}
全部评论

相关推荐

02-14 19:34
已编辑
哈尔滨工业大学（威海） Java
【面经】货拉拉 深圳 Java日常实习
时间线24.11.12&nbsp;一面24.11.13&nbsp;二面24.11.15&nbsp;口头oc&nbsp;没有去11.12&nbsp;深圳货拉拉一面&nbsp;30min八股操作系统：进程与线程？计算机网络：http&nbsp;和&nbsp;https&nbsp;什么区别tcp&nbsp;和&nbsp;udp&nbsp;什么区别JUC：线程池的参数？Java&nbsp;有哪些重要的锁？有哪些机制可以实现线程安全？知道乐观锁与悲观锁吗？MySQL：最左匹配原则？什么情况下索引失效？&nbsp;分页会导致索引失效吗？消息队列：如何实现消费顺序？微服务：Dubbo&nbsp;用过吗？（没用过，用过SpringCloud）注册中心用的是？（Nacos）分布式：分布式ID了解过吗？雪花算法获取的唯一的ID在分布式的情况会确保唯一吗？如果让...
查看25道真题和解析
点赞 评论 收藏
分享
02-14 11:11
牛客运营
点赞 评论 收藏
分享
2024-12-30 11:25
南京信息工程大学 前端工程师
前端 简历求指点
老方子：英语等级cet写错了吧
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 读研or工作，哪个性价比更高？ #
23943次浏览 323人参与
# 科大讯飞求职进展汇总 #
258800次浏览 2594人参与
# 如果重来一次你还会读研吗 #
154330次浏览 1691人参与
# 秋招感动瞬间 #
10676次浏览 101人参与
# 你最满意的offer薪资是哪家公司？ #
11783次浏览 109人参与
# 阿里巴巴创始人马云回国 #
13995次浏览 87人参与
# 文科生还参加今年的春招吗 #
3263次浏览 29人参与
# 长光卫星求职进展汇总 #
27552次浏览 183人参与
# 选择和努力，哪个更重要？ #
41837次浏览 471人参与
# 职场新人生存指南 #
194933次浏览 5368人参与
# 打工人的工作餐日常 #
24684次浏览 221人参与
# 招聘要求与实际实习内容不符怎么办 #
40551次浏览 465人参与
# 机械制造岗投递时间线 #
19303次浏览 324人参与
# 机械人选offer，最看重什么？ #
68543次浏览 433人参与
# 机械人怎么评价今年的华为 #
180276次浏览 1484人参与
# 影石Insta360求职进展汇总 #
107558次浏览 967人参与
# 如果再来一次，你还会学硬件吗 #
102676次浏览 1231人参与
# 正在实习的你，有转正机会吗？ #
336107次浏览 2690人参与
# 如果公司降薪，你会跳槽吗？ #
44439次浏览 349人参与
# 滴！实习打卡 #
554064次浏览 6003人参与
牛客网
牛客企业服务