A.TAT
Descriptiion:
给定一个字符串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.计算表达式
Descriptiion:
给定一个形如 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.飞行棋
Descriptiion:
飞行棋是一款十分有趣的游戏
不过在这里, 我们只考虑如下的简化重制版本:
-
棋盘为一个数轴 (−∞,+∞)
-
如果玩家当前在 x, 那么下一步他可以走到 x−1 或 x+1
-
特殊地, 在某些位置 ai 上, 玩家可以从当前位置直接一步跳到另一个位置 bi 上
-
玩家一开始在 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.求和问题
Descriptiion:
你现在有一个数组 A
我们定义如下的两种操作:
- 修改: 形如 0 l r ,效果为对所有 $ l <= i <=r $ 执行 $ A_i += (i-l+1) $
直观地说就是 Al+=1,Al+1+=2,Al+2+=3 ... Ar+=r−l+1 这个样子
- 查询: 形如 1 l 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:
没错又是大家熟悉的斐波那契数列~
什么你不知道? 没关系我们来给你定义:
F1=1,F2=1,Fi=Fi−1+Fi−2(i>2)
然后你需要求出 $ \sum_{i=l}^{r} F_i$ 的值, l,r 会由题目给出
由于答案可能很大, 你只需答案输出对1000000009 取膜的结果即可~
Input:
第一行一个整数T表示询问次数
接下来T行每行两个整数 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;
}
京公网安备 11010502036488号