A.TAT

De iion:

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

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

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

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

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

以上摘自维基百科~

Input:

仅一行, 一个字符串s

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

数据范围

∣s∣ <= 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.计算表达式

De iion:

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

求这个表达式所代表的值

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

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

Input:

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

接下来 T 行每行一个表达式 a # 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.飞行棋

De iion:

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

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

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

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

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

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

Input:

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

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

数据范围

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

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

保证 ai​̸​=aj​(i̸​=j),ai​̸​=bi​

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

Output:

仅一行, 一个整数, 表示玩家从 S 走到 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.求和问题

De iion:

你现在有一个数组 A

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

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

直观地说就是Al​+=1,Al+1​+=2,Al+2​+=3 ... Ar​+=r