历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

蓝桥杯自用复习题单

作者：

肖炎药 , 2023-03-31 01:38:19 , 所有人可见 , 阅读 539

-1

1

前缀和：
截断数组：
给定一个长度为 n� 的数组 a1,a2,…,an�1,�2,…,��。
现在，要将该数组从中间截断，得到三个非空子数组。
要求，三个子数组内各元素之和都相等。
请问，共有多少种不同的截断方法？
输入格式
第一行包含整数 n�。
第二行包含 n� 个整数 a1,a2,…,an�1,�2,…,��。
输出格式
输出一个整数，表示截断方法数量。
数据范围
前六个测试点满足 1≤n≤101≤�≤10。
所有测试点满足 1≤n≤1051≤�≤105，−10000≤ai≤10000−10000≤��≤10000。
输入样例1：
4
1 2 3 3
输出样例1：
1
输入样例2：
5
1 2 3 4 5
输出样例2：
0
输入样例3：
2
0 0
输出样例3：
0

include [HTML_REMOVED]

using namespace std;

const int N = 110000;

int a[N], s[N];
int n;
long long sum;

int main()
{
scanf(“%d”, &n);
for(int i = 1; i <= n; i )
{
scanf(“%d”, &a[i]);
s[i] = s[i - 1] + a[i];
}
if(s[n] % 3 != 0)
{
printf(“%d”, 0);
return 0;
}
long long cnt = 0;
for(int i = 3; i <= n; i ) //先截第二刀，再选第一刀有多少种方案
{
if(s[i - 2] == s[n] /3) cnt ++;
if(s[n] - s[i - 1] == s[n] /3) sum += cnt;
}
printf(“%ld”, sum);
return 0;
}
前缀和：
输入一个长度为 n� 的整数序列。
接下来再输入 m� 个询问，每个询问输入一对 l,r�,�。
对于每个询问，输出原序列中从第 l� 个数到第 r� 个数的和。
输入格式
第一行包含两个整数 n� 和 m�。
第二行包含 n� 个整数，表示整数数列。
接下来 m� 行，每行包含两个整数 l� 和 r�，表示一个询问的区间范围。
输出格式
共 m� 行，每行输出一个询问的结果。
数据范围
1≤l≤r≤n1≤�≤�≤�,
1≤n,m≤1000001≤�,�≤100000,
−1000≤数列中元素的值≤1000−1000≤数列中元素的值≤1000
输入样例：
5 3
2 1 3 6 4
1 2
1 3
2 4
输出样例：
3
6
10

include [HTML_REMOVED]

using namespace std;

const int N = 100010;

int n, m;
int s[N], a[N];

int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++)
{
cin >> a[i];
s[i] = s[i - 1] + a[i];
}
while(m –)
{
int l, r;
cin >> l >> r;
cout << s[r] - s[l - 1] << endl;
}
return 0;
}
子矩阵的和：
输入一个 n� 行 m� 列的整数矩阵，再输入 q� 个询问，每个询问包含四个整数 x1,y1,x2,y2�1,�1,�2,�2，表示一个子矩阵的左上角坐标和右下角坐标。
对于每个询问输出子矩阵中所有数的和。
输入格式
第一行包含三个整数 n，m，q�，�，�。
接下来 n� 行，每行包含 m� 个整数，表示整数矩阵。
接下来 q� 行，每行包含四个整数 x1,y1,x2,y2�1,�1,�2,�2，表示一组询问。
输出格式
共 q� 行，每行输出一个询问的结果。
数据范围
1≤n,m≤10001≤�,�≤1000,
1≤q≤2000001≤�≤200000,
1≤x1≤x2≤n1≤�1≤�2≤�,
1≤y1≤y2≤m1≤�1≤�2≤�,
−1000≤矩阵内元素的值≤1000−1000≤矩阵内元素的值≤1000
输入样例：
3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4
输出样例：
17
27
21

include [HTML_REMOVED]

using namespace std;

const int N = 1100;
int n, m, q;
int a[N][N], s[N][N];

int main()
{
cin >> n >> m >> q;
for(int i = 1; i <= n; i )
{
for(int j = 1; j <= m; j )
{
cin >> a[i][j];
s[i][j] = s[i][j - 1] + s[i-1][j] - s[i - 1][j - 1] + a[i][j];
}
}
int x1, y1, x2, y2, sum;
while(q –)
{
cin >> x1 >> y1 >> x2 >> y2;
sum = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];
cout << sum << endl;
}
}
K倍区间（蓝桥杯辅导课）
给定一个长度为 N� 的数列，A1,A2,…AN�1,�2,…��，如果其中一段连续的子序列 Ai,Ai+1,…Aj��,��+1,…�� 之和是 K� 的倍数，我们就称这个区间 [i,j][�,�] 是 K� 倍区间。
你能求出数列中总共有多少个 K� 倍区间吗？
输入格式
第一行包含两个整数 N� 和 K�。
以下 N� 行每行包含一个整数 Ai��。
输出格式
输出一个整数，代表 K� 倍区间的数目。
数据范围
1≤N,K≤1000001≤�,�≤100000,
1≤Ai≤1000001≤��≤100000
输入样例：
5 2
1
2
3
4
5
输出样例：
6

include [HTML_REMOVED]

using namespace std;

const int N = 110000;

int a[N], s[N];

int n, m;
long long res, cnt[N];

int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i )
{
cin >> a[i];
s[i] = (s[i - 1] + a[i]) % m;
res += cnt[s[i]];
cnt[s[i]] ;
}
cout << res + cnt[0] << endl;
return 0;
}
激光炸弹（算法提高课）
地图上有 N� 个目标，用整数 Xi,Yi��,�� 表示目标在地图上的位置，每个目标都有一个价值 Wi��。
注意：不同目标可能在同一位置。
现在有一种新型的激光炸弹，可以摧毁一个包含 R×R�×� 个位置的正方形内的所有目标。
激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆炸范围，即那个正方形的边必须和 x，y�，� 轴平行。
求一颗炸弹最多能炸掉地图上总价值为多少的目标。
输入格式
第一行输入正整数 N� 和 R�，分别代表地图上的目标数目和正方形包含的横纵位置数量，数据用空格隔开。
接下来 N� 行，每行输入一组数据，每组数据包括三个整数 Xi,Yi,Wi��,��,��，分别代表目标的 x� 坐标，y� 坐标和价值，数据用空格隔开。
输出格式
输出一个正整数，代表一颗炸弹最多能炸掉地图上目标的总价值数目。
数据范围
0≤R≤1090≤�≤109
0<N≤100000<�≤10000,
0≤Xi,Yi≤50000≤��,��≤5000
0≤Wi≤10000≤��≤1000
输入样例：
2 1
0 0 1
1 1 1
输出样例：
1

include [HTML_REMOVED]

using namespace std;

const int N = 5100;

int a[N][N], s[N][N];

int k, r;

int cnt;

int main()
{
cin >> k >> r;
r = min(5001, r);
int n = r, m = r;
int x, y, w;
while(k –)
{
cin >> x >> y >> w;
x ; y ;
s[x][y] += w;
n = max(n, x); m = max(m, y);
}
for(int x = 1; x <= n; x )
for(int y = 1; y <= m; y )
{
s[x][y] = s[x][y - 1] + s[x - 1][y] - s[x - 1][y - 1] + s[x][y];
}
if(r > n && r > m) cnt = s[n][m];
else
{
for(int x = r; x <= n ; x )
for(int y = r; y <= m; y )
{
cnt = max(cnt, s[x][y] - s[x -r][y] - s[x][y - r] + s[x - r][y - r]);
}
}
cout << cnt << endl;
return 0;
}

差分：
改变数组元素（每日一题）
给定一个空数组 V� 和一个整数数组 a1,a2,…,an�1,�2,…,��。
现在要对数组 V� 进行 n� 次操作。
第 i� 次操作的具体流程如下：
1.从数组 V� 尾部插入整数 00。
2.将位于数组 V� 末尾的 ai�� 个元素都变为 11（已经是 11 的不予理会）。
注意：
ai�� 可能为 00，即不做任何改变。
ai�� 可能大于目前数组 V� 所包含的元素个数，此时视为将数组内所有元素变为 11。
请你输出所有操作完成后的数组 V�。
输入格式
第一行包含整数 T�，表示共有 T� 组测试数据。
每组数据第一行包含整数 n�。
第二行包含 n� 个整数 a1,a2,…,an�1,�2,…,��。
输出格式
每组数据输出一行结果，表示所有操作完成后的数组 V�，数组内元素之间用空格隔开。
数据范围
1≤T≤200001≤�≤20000,
1≤n≤2×1051≤�≤2×105,
0≤ai≤n0≤��≤�,
保证一个测试点内所有 n� 的和不超过 2×1052×105。
输入样例：
3
6
0 3 0 0 1 3
10
0 0 0 1 0 5 0 0 0 2
3
0 0 0
输出样例：
1 1 0 1 1 1
0 1 1 1 1 1 0 0 1 1
0 0 0

include [HTML_REMOVED]

using namespace std;

const int N = 210000;

int t, n;
int a[N], b[N];

void insert(int l, int r)
{
b[l] += 1;
b[r + 1] -= 1;
}

int main()
{
cin >> t;
while(t –)
{
cin >> n;
for(int i = 1; i <= n; i )
{
cin >> a[i];
}
for(int i = n; i >= 1; i –)
{
if(a[i] == 0)
{
continue;
}else if(a[i] > i)
{
insert(1, i);
break;
}else
{
insert(i - a[i] + 1, i);
//i = i - a[i] + 1;
}
}
for(int i = 1; i <= n; i )
{
b[i] += b[i - 1];
if(b[i] > 1) cout << 1 << ” “;
else cout << b[i] << ” “;
}
cout << endl;
//memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
}
return 0;
}
差分（算法基础课）
输入一个长度为 n� 的整数序列。
接下来输入 m� 个操作，每个操作包含三个整数 l,r,c�,�,�，表示将序列中 [l,r][�,�] 之间的每个数加上 c�。
请你输出进行完所有操作后的序列。
输入格式
第一行包含两个整数 n� 和 m�。
第二行包含 n� 个整数，表示整数序列。
接下来 m� 行，每行包含三个整数 l，r，c�，�，�，表示一个操作。
输出格式
共一行，包含 n� 个整数，表示最终序列。
数据范围
1≤n,m≤1000001≤�,�≤100000,
1≤l≤r≤n1≤�≤�≤�,
−1000≤c≤1000−1000≤�≤1000,
−1000≤整数序列中元素的值≤1000−1000≤整数序列中元素的值≤1000
输入样例：
6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1
输出样例：
3 4 5 3 4 2

include [HTML_REMOVED]

using namespace std;

const int N = 100100;

int a[N], b[N];
int n, m;

void insert(int l, int r, int a)
{
b[l] += a;
b[r + 1] -= a;
}
int main()
{
int r, l , c;
cin >> n >> m;
for(int i = 1; i <= n; i )
{
cin >> a[i];
insert(i, i, a[i]);
}
while(m – )
{
cin >> l >> r >> c;
insert(l , r , c);
}
for(int i = 1; i <= n; i )
{
b[i] += b[i - 1];
cout << b[i] << ” “;
}
return 0;
}
差分矩阵（算法基础课）
输入一个 n� 行 m� 列的整数矩阵，再输入 q� 个操作，每个操作包含五个整数 x1,y1,x2,y2,c�1,�1,�2,�2,�，其中 (x1,y1)(�1,�1) 和 (x2,y2)(�2,�2) 表示一个子矩阵的左上角坐标和右下角坐标。
每个操作都要将选中的子矩阵中的每个元素的值加上 c�。
请你将进行完所有操作后的矩阵输出。
输入格式
第一行包含整数 n,m,q�,�,�。
接下来 n� 行，每行包含 m� 个整数，表示整数矩阵。
接下来 q� 行，每行包含 55 个整数 x1,y1,x2,y2,c�1,�1,�2,�2,�，表示一个操作。
输出格式
共 n� 行，每行 m� 个整数，表示所有操作进行完毕后的最终矩阵。
数据范围
1≤n,m≤10001≤�,�≤1000,
1≤q≤1000001≤�≤100000,
1≤x1≤x2≤n1≤�1≤�2≤�,
1≤y1≤y2≤m1≤�1≤�2≤�,
−1000≤c≤1000−1000≤�≤1000,
−1000≤矩阵内元素的值≤1000−1000≤矩阵内元素的值≤1000
输入样例：
3 4 3
1 2 2 1
3 2 2 1
1 1 1 1
1 1 2 2 1
1 3 2 3 2
3 1 3 4 1
输出样例：
2 3 4 1
4 3 4 1
2 2 2 2

include [HTML_REMOVED]

using namespace std;

const int N = 1010;

int a[N][N], b[N][N];

int n, m, q;

void insert(int x1, int y1, int x2, int y2, int k)
{
b[x1][y1] += k;
b[x2 + 1][y1] -= k;
b[x1][y2 + 1] -= k;
b[x2 + 1][y2 + 1] += k;
}
int main()
{
cin >> n >> m >> q;
for(int i = 1; i <= n; i )
for(int j = 1; j <= m; j )
{
cin >> a[i][j];
insert(i, j, i, j, a[i][j]);
}
while(q –)
{
int x1, y1, x2, y2, k;
cin >> x1 >> y1 >> x2 >> y2 >> k;
insert(x1, y1, x2, y2, k);
}
for(int i = 1; i <= n; i )
{
for(int j = 1; j <= m; j )
{
b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
cout << b[i][j] << ” “;
}
cout << endl;
}
return 0;
}
增减序列（算法提高课）
给定一个长度为 n� 的数列 a1,a2,…,an�1,�2,…,��，每次可以选择一个区间 [l,r][�,�]，使下标在这个区间内的数都加一或者都减一。
求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。
输入格式
第一行输入正整数 n�。
接下来 n� 行，每行输入一个整数，第 i+1�+1 行的整数代表 ai��。
输出格式
第一行输出最少操作次数。
第二行输出最终能得到多少种结果。
数据范围
0<n≤1050<�≤105,
0≤ai<21474836480≤��<2147483648
输入样例：
4
1
1
2
2
输出样例：
1
2

include [HTML_REMOVED]

using namespace std;

const int N = 110000;

int a[N], b[N];
int n, m;

void insert(int l, int r, int c)
{
b[l] += c;
b[r + 1] -= c;
}
int main()
{
long long zheng = 0, fu = 0;
cin >> n;
for(int i = 1; i <= n; i )
{
cin >> a[i];
insert(i, i, a[i]);
}
for(int i = 2; i <= n; i )
{
if(b[i] > 0) zheng += b[i];
else fu -= b[i];
}
cout << min(zheng, fu) + abs(zheng - fu) << endl;
cout << abs(zheng - fu) + 1;
return 0;
}

二分：
我在哪？（每日一题）
农夫约翰出门沿着马路散步，但是他现在发现自己可能迷路了！
沿路有一排共 N� 个农场。
不幸的是农场并没有编号，这使得约翰难以分辨他在这条路上所处的位置。
然而，每个农场都沿路设有一个彩色的邮箱，所以约翰希望能够通过查看最近的几个邮箱的颜色来唯一确定他所在的位置。
每个邮箱的颜色用 A..Z�..� 之间的一个字母来指定，所以沿着道路的 N� 个邮箱的序列可以用一个长为 N� 的由字母 A..Z�..� 组成的字符串来表示。
某些邮箱可能会有相同的颜色。
约翰想要知道最小的 K� 的值，使得他查看任意连续 K� 个邮箱序列，他都可以唯一确定这一序列在道路上的位置。
例如，假设沿路的邮箱序列为 ABCDABC 。
约翰不能令 K=3�=3，因为如果他看到了 ABC，则沿路有两个这一连续颜色序列可能所在的位置。
最小可行的 K� 的值为 K=4�=4，因为如果他查看任意连续 44 个邮箱，那么可得到的连续颜色序列可以唯一确定他在道路上的位置。
输入格式
输入的第一行包含 N�，第二行包含一个由 N� 个字符组成的字符串，每个字符均在 A..Z�..� 之内。
输出格式
输出一行，包含一个整数，为可以解决农夫约翰的问题的最小 K� 值。
数据范围
1≤N≤1001≤�≤100
输入样例：
7
ABCDABC
输出样例：
4

include [HTML_REMOVED]

using namespace std;

const int N = 1010;

string str;
int n;

bool check(int mid)
{
unordered_set[HTML_REMOVED] hash;
for(int i = 0; i + mid - 1 < str.size(); i ++)
{
auto s = str.substr(i, mid);
if(hash.count(s)) return false;
hash.insert(s);
}
return true;
}
int main()
{
cin >> n;
cin >> str;
int l = 1, r = n;
while(l < r)
{
int mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
cout << l << endl;
return 0;
}
数的范围（算法基础课）
给定一个按照升序排列的长度为 n� 的整数数组，以及 q� 个查询。
对于每个查询，返回一个元素 k� 的起始位置和终止位置（位置从 00 开始计数）。
如果数组中不存在该元素，则返回 -1 -1。
输入格式
第一行包含整数 n� 和 q�，表示数组长度和询问个数。
第二行包含 n� 个整数（均在 1∼100001∼10000 范围内），表示完整数组。
接下来 q� 行，每行包含一个整数 k�，表示一个询问元素。
输出格式
共 q� 行，每行包含两个整数，表示所求元素的起始位置和终止位置。
如果数组中不存在该元素，则返回 -1 -1。
数据范围
1≤n≤1000001≤�≤100000
1≤q≤100001≤�≤10000
1≤k≤100001≤�≤10000
输入样例：
6 3
1 2 2 3 3 4
3
4
5
输出样例：
3 4
5 5-1 -1

include [HTML_REMOVED]

using namespace std;

const int N = 100100;

int n, m;
int a[N];

int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
}
while(m –)
{
int x;
cin >> x;
int l = 1, r = n;
while(l < r)
{
int mid =(l + r) / 2;
if(a[mid] >= x) r = mid;
else l = mid + 1;
}
if(a[r] == x)
{
cout << r - 1 << ” “;
r = n;
while(l < r)
{
int mid = (l + r + 1) / 2;
if(a[mid] <= x) l = mid;
else r = mid - 1;
}
cout << l - 1 << endl;

    }else
    {
        cout << "-1 -1" << endl;
    }
}
return 0;

}
四平方和
四平方和定理，又称为拉格朗日定理：
每个正整数都可以表示为至多 44 个正整数的平方和。
如果把 00 包括进去，就正好可以表示为 44 个数的平方和。
比如：
5=02+02+12+225=02+02+12+22
7=12+12+12+227=12+12+12+22
对于一个给定的正整数，可能存在多种平方和的表示法。
要求你对 44 个数排序：
0≤a≤b≤c≤d0≤�≤�≤�≤�
并对所有的可能表示法按 a,b,c,d�,�,�,� 为联合主键升序排列，最后输出第一个表示法。
输入格式
输入一个正整数 N�。
输出格式
输出4个非负整数，按从小到大排序，中间用空格分开。
数据范围
0<N<5∗1060<�<5∗106
输入样例：
5
输出样例：
0 0 1 2

include [HTML_REMOVED]

using namespace std;

const int N = 5000100;

int n, m;
struct Sum
{
int s, c, d;
bool operator< (const Sum &t) const{
if(s != t.s) return s < t.s;
if(c != t.c) return c < t.c;
return d < t.d;
}
}S[N];

int main()
{
cin >> n;
for(int c = 0; c * c <= n; c )
{
for(int d = c; d * d <= n; d )
{
int s = c* c + d * d;
S[m ] = {s, c, d};
}
}
sort(S, S + m);
for(int a = 0; a * a <= n; a )
{
for(int b = a; b * b <= n; b ++)
{
int sum = n - a * a - b * b;
int l = 0, r = n;
while(l < r)
{
int mid = l + r >> 1;
if(S[mid].s >= sum) r = mid;
else l = mid + 1;
}
if(S[l].s == sum)
{
cout << a << ” ” << b << ” ” << S[r].c << ” ” << S[r].d << endl;
return 0;
}
}
}
return 0;
}
分巧克力（蓝桥杯辅导课
儿童节那天有 K� 位小朋友到小明家做客。
小明拿出了珍藏的巧克力招待小朋友们。
小明一共有 N� 块巧克力，其中第 i� 块是 Hi×Wi��×�� 的方格组成的长方形。
为了公平起见，小明需要从这 N� 块巧克力中切出 K� 块巧克力分给小朋友们。
切出的巧克力需要满足：
1.形状是正方形，边长是整数
2.大小相同
例如一块 6×56×5 的巧克力可以切出 66 块 2×22×2 的巧克力或者 22 块 3×33×3 的巧克力。
当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？
输入格式
第一行包含两个整数 N� 和 K�。
以下 N� 行每行包含两个整数 Hi�� 和 Wi��。
输入保证每位小朋友至少能获得一块 1×11×1 的巧克力。
输出格式
输出切出的正方形巧克力最大可能的边长。
数据范围
1≤N,K≤1051≤�,�≤105,
1≤Hi,Wi≤1051≤��,��≤105
输入样例：
2 10
6 5
5 6
输出样例：
2

include [HTML_REMOVED]

using namespace std;

const int N = 100100;

int n, m, k;
int h[N], w[N];

bool check(int mid)
{
int res = 0;
for(int i = 1; i <= n; i )
{
res += (h[i] / mid) * (w[i] / mid) ;
}
if(res >= m) return true;
else return false;
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i )
{
cin >> h[i] >> w[i];
}
int l = 1, r = 1e5;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
cout << l << endl;
return 0;
}
双指针：
字符串删减（每日一题）
给定一个由 n� 个小写字母构成的字符串。
现在，需要删掉其中的一些字母，使得字符串中不存在连续三个或三个以上的 x。
请问，最少需要删掉多少个字母？
如果字符串本来就不存在连续的三个或三个以上 x，则无需删掉任何字母。
输入格式
第一行包含整数 n�。
第二行包含一个长度为 n� 的由小写字母构成的字符串。
输出格式
输出最少需要删掉的字母个数。
数据范围
3≤n≤1003≤�≤100
输入样例1：
6
xxxiii
输出样例1：
1
输入样例2：
5
xxoxx
输出样例2：
0
输入样例3：
10
xxxxxxxxxx
输出样例3：
8

include[HTML_REMOVED]

using namespace std;

const int N = 110;
int a[N];

int main()
{
int n;
string str;
int res = 0;
cin >> n >> str;
for(int i = 0; i < n; i )
{
if(str[i] != ‘x’) continue;
int j = i + 1;
while(j < n && str[j] == ‘x’) j ;
res += max(0, j - i - 2);
i = j - 1;
}
cout << res << endl;
return 0;
}
最长连续不重复子序列（算法基础课）
给定一个长度为 n� 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。
输入格式
第一行包含整数 n�。
第二行包含 n� 个整数（均在 0∼1050∼105 范围内），表示整数序列。
输出格式
共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。
数据范围
1≤n≤1051≤�≤105
输入样例：
5
1 2 2 3 5
输出样例：
3

include [HTML_REMOVED]

using namespace std;

const int N = 100100;

int n, a[N], s[N];

int main()
{
cin >> n;
int j = 1;
int res = 0;
for(int i = 1; i <= n; i )
{
cin >> a[i];
}
for(int i = 1; i <= n; i )
{
s[a[i]] ;
while(s[a[i]] > 1)
{
s[a[j]] –;
j ;
}
res = max(res, i - j + 1);
}
cout << res << endl;
return 0;
}AcWing 800. 数组元素的目标和（算法基础课）
给定两个升序排序的有序数组 A� 和 B�，以及一个目标值 x�。
数组下标从 00 开始。
请你求出满足 A[i]+B[j]=x�[�]+�[�]=� 的数对 (i,j)(�,�)。
数据保证有唯一解。
输入格式
第一行包含三个整数 n,m,x�,�,�，分别表示 A� 的长度，B� 的长度以及目标值 x�。
第二行包含 n� 个整数，表示数组 A�。
第三行包含 m� 个整数，表示数组 B�。
输出格式
共一行，包含两个整数 i� 和 j�。
数据范围
数组长度不超过 105105。
同一数组内元素各不相同。
1≤数组元素≤1091≤数组元素≤109
输入样例：
4 5 6
1 2 4 7
3 4 6 8 9
输出样例：
1 1

include [HTML_REMOVED]

using namespace std;

const int N = 100100;

int a[N], b[N], s[N];
int n, m, x;
long long str;

int main()
{
cin >> n >> m >> x;
int i = 1, j = m;
for(int i = 1; i <= n; i )
{
cin >> a[i];
}
for(int j = 1; j <= m; j )
{
cin >> b[j];
}
for(int i = 1; i <= n; i ++)
{
while(j >= 1 && a[i] + b[j] > x) j –;
if(a[i] + b[j] == x)
{
cout << i - 1 << ” ” << j - 1 << endl;
return 0;
}
}

return 0;

}
AcWing 2816. 判断子序列（算法基础课）
给定一个长度为 n� 的整数序列 a1,a2,…,an�1,�2,…,�� 以及一个长度为 m� 的整数序列 b1,b2,…,bm�1,�2,…,��。
请你判断 a� 序列是否为 b� 序列的子序列。
子序列指序列的一部分项按原有次序排列而得的序列，例如序列 {a1,a3,a5}{�1,�3,�5} 是序列 {a1,a2,a3,a4,a5}{�1,�2,�3,�4,�5} 的一个子序列。
输入格式
第一行包含两个整数 n,m�,�。
第二行包含 n� 个整数，表示 a1,a2,…,an�1,�2,…,��。
第三行包含 m� 个整数，表示 b1,b2,…,bm�1,�2,…,��。
输出格式
如果 a� 序列是 b� 序列的子序列，输出一行 Yes。
否则，输出 No。
数据范围
1≤n≤m≤1051≤�≤�≤105,
−109≤ai,bi≤109−109≤��,��≤109
输入样例：
3 5
1 3 5
1 2 3 4 5
输出样例：
Yes

include [HTML_REMOVED]

using namespace std;

const int N = 100100;

int n, m;
int a[N], b[N];

int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ) cin >> a[i];
for(int j = 1; j <= m; j ) cin >> b[j];
int j = 1, i = 1;
while(i <= n && j <= m)
{
if(a[i] == b[j]) i ;
j ;
//cout << i << “i ” << j << “J “;

}
//cout << i << j;
if(i == n + 1) 
    {
        cout << "Yes" << endl;
        return 0;
    }else 
cout << "No" << endl;
return 0;

}
AcWing 1238. 日志统计（蓝桥杯辅导课）
小明维护着一个程序员论坛。现在他收集了一份”点赞”日志，日志共有 N� 行。
其中每一行的格式是：
ts id
表示在 ts�� 时刻编号 id�� 的帖子收到一个”赞”。
现在小明想统计有哪些帖子曾经是”热帖”。
如果一个帖子曾在任意一个长度为 D� 的时间段内收到不少于 K� 个赞，小明就认为这个帖子曾是”热帖”。
具体来说，如果存在某个时刻 T� 满足该帖在 [T,T+D)[�,�+�) 这段时间内(注意是左闭右开区间)收到不少于 K� 个赞，该帖就曾是”热帖”。
给定日志，请你帮助小明统计出所有曾是”热帖”的帖子编号。
输入格式
第一行包含三个整数 N,D,K�,�,�。
以下 N� 行每行一条日志，包含两个整数 ts�� 和 id��。
输出格式
按从小到大的顺序输出热帖 id��。
每个 id�� 占一行。
数据范围
1≤K≤N≤1051≤�≤�≤105,
0≤ts,id≤1050≤��,��≤105,
1≤D≤100001≤�≤10000
输入样例：
7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3
输出样例：
1
3

include [HTML_REMOVED]

define x first

define y second

using namespace std;

const int N = 100010;

typedef pair[HTML_REMOVED] PII;

PII logs[N];
int s[N];
bool st[N];

int n, d, k;

int main()
{
cin >> n >> d >> k;
for(int i = 0; i < n; i )
{
scanf(“%d%d”, &logs[i].x, &logs[i].y);
}
sort(logs, logs + n);
for(int i = 0, j = 0; i < n; i )
{
int id = logs[i].y;
s[id] ;
while(logs[i].x - logs[j].x >= d)
{
s[logs[j].y] –;
j ;
}
if(s[id] >= k) st[id] = true;
}
for(int i = 0; i < 100000; i ++)
{
if(st[i]) cout << i << endl;
}
return 0;
}
AcWing 1240. 完全二叉树的权值（蓝桥杯辅导课）
给定一棵包含 N� 个节点的完全二叉树，树上每个节点都有一个权值，按从上到下、从左到右的顺序依次是 A1,A2,⋅⋅⋅AN�1,�2,···��，如下图所示：

现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点权值之和最大？
如果有多个深度的权值和同为最大，请你输出其中最小的深度。
注：根的深度是 11。
输入格式
第一行包含一个整数 N�。
第二行包含 N� 个整数 A1,A2,⋅⋅⋅AN�1,�2,···��。
输出格式
输出一个整数代表答案。
数据范围
1≤N≤1051≤�≤105,
−105≤Ai≤105−105≤��≤105
输入样例：
7
1 6 5 4 3 2 1
输出样例：
2

挑战模式

include [HTML_REMOVED]

using namespace std;

typedef long long LL;

const int N = 100010;

int n;
int a[N];

int main()
{
cin >> n;
for(int i = 1; i <= n; i ) scanf(“%d”, &a[i]);
LL depth = 0;
LL max = -1e10;
for(int i = 1, d = 1; i <= n; i *= 2, d )
{
LL cnt = 0;
for(int j = i; j < i + (1 << d - 1) && j <= n; j ++)
{
cnt += a[j];
}
if(cnt > max)
{
max = cnt;
depth = d;
}
}
cout << depth << endl;
return 0;

}

递推：
AcWing 3777. 砖块（每日一题）
n� 个砖块排成一排，从左到右编号依次为 1∼n1∼�。
每个砖块要么是黑色的，要么是白色的。
现在你可以进行以下操作若干次（可以是 00 次）：
选择两个相邻的砖块，反转它们的颜色。（黑变白，白变黑）
你的目标是通过不超过 3n3� 次操作，将所有砖块的颜色变得一致。
输入格式
第一行包含整数 T�，表示共有 T� 组测试数据。
每组数据第一行包含一个整数 n�。
第二行包含一个长度为 n� 的字符串 s�。其中的每个字符都是 W 或 B，如果第 i� 个字符是 W，则表示第 i� 号砖块是白色的，如果第 i� 个字符是 B，则表示第 i� 个砖块是黑色的。
输出格式
每组数据，如果无解则输出一行 −1−1。
否则，首先输出一行 k�，表示需要的操作次数。
如果 k>0�>0，则还需再输出一行 k� 个整数，p1,p2,…,pk�1,�2,…,��。其中 pi�� 表示第 i� 次操作，选中的砖块为 pi�� 和 pi+1��+1 号砖块。
如果方案不唯一，则输出任意合理方案即可。
数据范围
1≤T≤101≤�≤10，
2≤n≤2002≤�≤200。
输入样例：
4
8
BWWWWWWB
4
BWBB
5
WWWWW
3
BWB
输出样例：
3
6 2 4-1
0
2
2 1

include [HTML_REMOVED]

using namespace std;

const int N = 210;

int n, m;
string str;

void turn(char& i)
{
if(i == ‘W’) i = ‘B’;
else i = ‘W’;
}

bool check(string str, char c)
{
vector[HTML_REMOVED] res;
string s = str;
for(int i = 0; i + 1 < m; i ++)
{
if(s[i] != c)
{
turn(s[i]);
turn(s[i + 1]);
res.push_back(i);
}

} if(s.back() != c) return false;
    cout << res.size() << endl;
    for(auto x : res) 
    {
        cout << x + 1 << " ";
    }
    if(res.size()) cout << endl;
    return true;

}
int main()
{
cin >> n;
while(n –)
{

    cin >> m >> str;
    if(!check(str, 'W') && !check(str, 'B')) cout << -1 << endl;
}

}
AcWing 1208. 翻硬币（蓝桥杯辅导课）
小明正在玩一个“翻硬币”的游戏。
桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零）。
比如，可能情形是：**oooooo
如果同时翻转左边的两个硬币，则变为：oooooooo
现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？
我们约定：把翻动相邻的两个硬币叫做一步操作。
输入格式
两行等长的字符串，分别表示初始状态和要达到的目标状态。
输出格式
一个整数，表示最小操作步数
数据范围
输入字符串的长度均不超过100。
数据保证答案一定有解。
输入样例1：

o*o
输出样例1：
5
输入样例2：
ooooo*o
输出样例2：
1

include [HTML_REMOVED]

using namespace std;

const int N = 110;

char a[N], b[N];

void turn(int i)
{
if(a[i] == ‘’)
{
a[i] = ‘o’;
}else a[i] = ‘’;
}

int main()
{
cin >> a >> b;
int k = 0;
for(int i = 0; a[i] != 0; i )
{
if(a[i] != b[i])
{
turn(i);
turn(i + 1);
k ;
}
}
cout << k << endl;
return 0;
}
AcWing 95. 费解的开关（算法提高课）
你玩过“拉灯”游戏吗？
2525 盏灯排成一个 5×55×5 的方形。
每一个灯都有一个开关，游戏者可以改变它的状态。
每一步，游戏者可以改变某一个灯的状态。
游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。
我们用数字 11 表示一盏开着的灯，用数字 00 表示关着的灯。
下面这种状态
10111
01101
10111
10000
11011
在改变了最左上角的灯的状态后将变成：
01111
11101
10111
10000
11011
再改变它正中间的灯后状态将变成：
01111
11001
11001
10100
11011
给定一些游戏的初始状态，编写程序判断游戏者是否可能在 66 步以内使所有的灯都变亮。
输入格式
第一行输入正整数 n�，代表数据中共有 n� 个待解决的游戏初始状态。
以下若干行数据分为 n� 组，每组数据有 55 行，每行 55 个字符。
每组数据描述了一个游戏的初始状态。
各组数据间用一个空行分隔。
输出格式
一共输出 n� 行数据，每行有一个小于等于 66 的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。
对于某一个游戏初始状态，若 66 步以内无法使所有灯变亮，则输出 −1−1。
数据范围
0<n≤5000<�≤500
输入样例：
3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111
输出样例：
3
2-1

include [HTML_REMOVED]

using namespace std;

const int N = 6;

int n;
char g[N][N], backup[N][N];
int dx[5] = {0, 0, -1, 1, 0};
int dy[5] = {0, -1, 0, 0, 1};

void turn(int x, int y)
{
for(int i = 0; i < 5; i )
{
int x1 = x + dx[i];
int y1 = y + dy[i];
if(x1 < 0 || x1 >= 5 || y1 < 0 || y1 >= 5) continue;
g[x1][y1] ^= 1;
}
}
int main()
{
cin >> n;
while(n –)
{
int res = 10;
for(int i = 0; i < 5; i )
{
cin >> g[i];
}

    for(int op = 0; op < 32; op ++)
    {
        memcpy(backup, g, sizeof(g));
        int step = 0;
        for(int i = 0; i < 5; i ++)
        {
            if(op >> i & 1)
            {
                step ++;
                turn(0, i);
            }
        }
        for(int i = 0; i < 4; i ++)
            for(int j = 0; j < 5; j ++)
            {
                if(g[i][j] == '0')
                {
                    step ++;
                    turn(i + 1, j);
                }
            }
            bool st = false;
        for(int i = 0; i < 5; i ++)
        {
            if(g[4][i] == '0') 
            {
                st = true; 
                break;
            }
        }
        if(!st) res = min(res, step);
        memcpy(g, backup, sizeof(g));
    }
    if(res > 6) res = -1;
    cout << res << endl;
}
return 0;

}
递归：
AcWing 1497. 树的遍历（每日一题）
一个二叉树，树中每个节点的权值互不相同。
现在给出它的后序遍历和中序遍历，请你输出它的层序遍历。
输入格式
第一行包含整数 N�，表示二叉树的节点数。
第二行包含 N� 个整数，表示二叉树的后序遍历。
第三行包含 N� 个整数，表示二叉树的中序遍历。
输出格式
输出一行 N� 个整数，表示二叉树的层序遍历。
数据范围
1≤N≤301≤�≤30,
官方并未给出各节点权值的取值范围，为方便起见，在本网站范围取为 1∼N1∼�。
输入样例：
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
输出样例：
4 1 6 3 5 7 2

include [HTML_REMOVED]

using namespace std;

const int N = 40;

int n;
int a[N], b[N], s[N];
vector[HTML_REMOVED] level[N];

void check(int hl, int hr, int zl, int zr, int d)
{
if(zl > zr) return;
int root = a[hr];
int k = s[root];
level[d].push_back(root);
check(hl, hl + k - zl - 1, zl, k - 1, d + 1);
check(hl + k - zl, hr - 1, k + 1, zr, d + 1);
}
int main()
{
cin >> n;
for(int i = 0; i < n; i ) cin >> a[i];
for(int i = 0; i < n; i ) cin >> b[i];
for(int i = 0; i < n; i ) s[b[i]] = i;
check(0, n - 1, 0, n - 1, 0);
for(int i = 0; i < n; i )
for(auto x : level[i])
{
cout << x << ” “;
}
return 0;
}
AcWing 97. 约数之和（算法提高课）
假设现在有两个自然数 A� 和 B�，S� 是 AB�� 的所有约数之和。
请你求出 Smod9901�mod9901 的值是多少。
输入格式
在一行中输入用空格隔开的两个整数 A� 和 B�。
输出格式
输出一个整数，代表 Smod9901�mod9901 的值。
数据范围
0≤A,B≤5×1070≤�,�≤5×107
输入样例：
2 3
输出样例：
15
注意: A� 和 B� 不会同时为 00。

挑战模式
并查集L:
AcWing 1249. 亲戚（每日一题）
或许你并不知道，你的某个朋友是你的亲戚。
他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子。
如果能得到完整的家谱，判断两个人是否是亲戚应该是可行的，但如果两个人的最近公共祖先与他们相隔好几代，使得家谱十分庞大，那么检验亲戚关系实非人力所能及。
在这种情况下，最好的帮手就是计算机。
为了将问题简化，你将得到一些亲戚关系的信息，如Marry和Tom是亲戚，Tom和Ben是亲戚，等等。
从这些信息中，你可以推出Marry和Ben是亲戚。
请写一个程序，对于我们的关于亲戚关系的提问，以最快的速度给出答案。
输入格式
输入由两部分组成。
第一部分以 N,M�,� 开始。N� 为问题涉及的人的个数。这些人的编号为 1,2,3,…,N1,2,3,…,�。下面有 M� 行，每行有两个数 ai,bi��,��，表示已知 ai�� 和 bi�� 是亲戚。
第二部分以 Q� 开始。以下 Q� 行有 Q� 个询问，每行为 ci,di��,��，表示询问 ci�� 和 di�� 是否为亲戚。
输出格式
对于每个询问 ci,di��,��，输出一行：若 ci�� 和 di�� 为亲戚，则输出“Yes”，否则输出“No”。
数据范围
1≤N≤200001≤�≤20000,
1≤M≤1061≤�≤106,
1≤Q≤1061≤�≤106
输入样例：
10 7
2 4
5 7
1 3
8 9
1 2
5 6
2 3
3
3 4
7 10
8 9
输出样例：
Yes
No
Yes

include [HTML_REMOVED]

using namespace std;

const int N = 20010;

typedef long long LL;

LL n, m;
int p[N];

include [HTML_REMOVED]

using namespace std;

const int N = 20010;

typedef long long LL;

LL n, m;
int p[N];

int find(int i)
{
if(p[i] != i) p[i] = find(p[i]);
return p[i];
}
int main()
{
scanf(“%ld%ld”, &n, &m);;
for(int i = 1; i <= n; i ++) p[i] = i;
while(m –)
{
int a, b;
scanf(“%ld%ld”, &a, &b);
p[find(a)] = find(b);
}
LL q;
scanf(“%ld”, &q);
while(q –)
{
int a, b;
scanf(“%ld%ld”, &a, &b);
if(find(a) == find(b)) printf(“Yes\n”);
else printf(“No\n”);
}
return 0;
}
合并集合一共有 n� 个数，编号是 1∼n1∼�，最开始每个数各自在一个集合中。
现在要进行 m� 个操作，操作共有两种：
1.M a b，将编号为 a� 和 b� 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
2.Q a b，询问编号为 a� 和 b� 的两个数是否在同一个集合中；
输入格式
第一行输入整数 n� 和 m�。
接下来 m� 行，每行包含一个操作指令，指令为 M a b 或 Q a b 中的一种。
输出格式
对于每个询问指令 Q a b，都要输出一个结果，如果 a� 和 b� 在同一集合内，则输出 Yes，否则输出 No。
每个结果占一行。
数据范围
1≤n,m≤1051≤�,�≤105
输入样例：
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4
输出样例：
Yes
No
Yes

include [HTML_REMOVED]

using namespace std;

const int N = 100100;

int n, m, p[N];

int find(int i)
{
if(p[i] != i) p[i] = find(p[i]);
return p[i];
}

int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++) p[i] = i;
while(m –)
{
int a, b;
char op;
cin >> op >> a >> b;
if(op == ‘M’)
{
p[find(a)] = find(b);
}else if(op == ‘Q’)
{
if(find(a) == find(b))
{
puts(“Yes”);
}else puts(“No”);
}
}
return 0;
}
AcWing 837. 连通块中点的数量（算法基础课）
给定一个包含 n� 个点（编号为 1∼n1∼�）的无向图，初始时图中没有边。
现在要进行 m� 个操作，操作共有三种：
1.C a b，在点 a� 和点 b� 之间连一条边，a� 和 b� 可能相等；
2.Q1 a b，询问点 a� 和点 b� 是否在同一个连通块中，a� 和 b� 可能相等；
3.Q2 a，询问点 a� 所在连通块中点的数量；
输入格式
第一行输入整数 n� 和 m�。
接下来 m� 行，每行包含一个操作指令，指令为 C a b，Q1 a b 或 Q2 a 中的一种。
输出格式
对于每个询问指令 Q1 a b，如果 a� 和 b� 在同一个连通块中，则输出 Yes，否则输出 No。
对于每个询问指令 Q2 a，输出一个整数表示点 a� 所在连通块中点的数量
每个结果占一行。
数据范围
1≤n,m≤1051≤�,�≤105
输入样例：
5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5
输出样例：
Yes23

include [HTML_REMOVED]

using namespace std;

const int N = 100100;

int n, m;
int p[N], st[N];

int find(int i)
{
if(p[i] != i) p[i] = find(p[i]);
return p[i];
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++) p[i] = i, st[i] = 1;
while(m –)
{
string q;
int a, b;
cin >> q;
if(q == “C”)
{
scanf(“%d%d”, &a, &b);
if (find(a) == find(b)) continue;//坑
st[find(b)] += st[find(a)];//坑
p[find(a)] = find(b);
}
else if(q == “Q1”)
{
scanf(“%d%d”, &a, &b);
if(find(a) == find(b)) printf(“Yes\n”);
else printf(“No\n”);
}
else
{
scanf(“%d”, &a);
printf(“%d\n”, st[find(a)]);
}
}
return 0;
}
哈希
AcWing 2058. 笨拙的手指（每日一题）
奶牛贝茜正在学习如何在不同进制之间转换数字。
但是她总是犯错误，因为她无法轻易的用两个前蹄握住笔。
每当贝茜将数字转换为一个新的进制并写下结果时，她总是将其中的某一位数字写错。
例如，如果她将数字 1414 转换为二进制数，那么正确的结果应为 11101110，但她可能会写下 01100110 或 11111111。
贝茜不会额外添加或删除数字，但是可能会由于写错数字的原因，写下包含前导 00 的数字。
给定贝茜将数字 N� 转换为二进制数字以及三进制数字的结果，请确定 N� 的正确初始值（十进制表示）。
输入格式
第一行包含 N� 的二进制表示，其中一位是错误的。
第二行包含 N� 的三进制表示，其中一位是错误的。
输出格式
输出正确的 N� 的值。
数据范围
0≤N≤1090≤�≤109，且存在唯一解。
输入样例：
1010
212
输出样例：
14
样例解释
1414 在二进制下的正确表示为 11101110，在三进制下的正确表示为 112112。

include [HTML_REMOVED]

using namespace std;

string a, b;

int turn(string a, int d)
{
int res = 0;
for(auto c : a)
{
res = res * d + c - ‘0’;
}
return res;
}
int main()
{
cin >> a >> b;
unordered_set[HTML_REMOVED] S;

for(auto& c : a)
{
    c ^= 1;
    S.insert(turn(a, 2));
    c ^= 1;
}
for(auto& c : b)
{
    char t = c;
    for(int i = 0; i < 3; i ++)
    {
        if(i != t - '0')
        {
            c = i + '0';
            int x = turn(b, 3);
            if(S.count(x))
            {
                cout << x << endl;
                return 0;
            }
        }
    }
    c = t;
}
return 0;

}
AcWing 840. 模拟散列表（算法基础课）
维护一个集合，支持如下几种操作：
1.I x，插入一个数 x�；
2.Q x，询问数 x� 是否在集合中出现过；
现在要进行 N� 次操作，对于每个询问操作输出对应的结果。
输入格式
第一行包含整数 N�，表示操作数量。
接下来 N� 行，每行包含一个操作指令，操作指令为 I x，Q x 中的一种。
输出格式
对于每个询问指令 Q x，输出一个询问结果，如果 x� 在集合中出现过，则输出 Yes，否则输出 No。
每个结果占一行。
数据范围
1≤N≤1051≤�≤105
−109≤x≤109−109≤�≤109
输入样例：
5
I 1
I 2
I 3
Q 2
Q 5
输出样例：
Yes
No

include [HTML_REMOVED]

using namespace std;

const int N = 2000003, null = 0x3f3f3f3f;

int n;
int h[N];

int find(int x)
{
int k = (x % N + N ) % N;
while(h[k] != null && h[k] != x)
{
k ++;
if(k == N) k = 0;
}
return k;
}

int main()
{
cin >> n;
memset(h, 0x3f, sizeof(h));
while(n –)
{
char op[2];
int x;
scanf(“%s%d”, &op, &x);
int k = find(x);
if(*op == ‘I’)
{
h[k] = x;
}
else{
if(h[k] != null) puts(“Yes”);
else puts(“No”);
}
}
return 0;
}
AcWing 841. 字符串哈希（算法基础课
给定一个长度为 n� 的字符串，再给定 m� 个询问，每个询问包含四个整数 l1,r1,l2,r2�1,�1,�2,�2，请你判断 [l1,r1][�1,�1] 和 [l2,r2][�2,�2] 这两个区间所包含的字符串子串是否完全相同。
字符串中只包含大小写英文字母和数字。
输入格式
第一行包含整数 n� 和 m�，表示字符串长度和询问次数。
第二行包含一个长度为 n� 的字符串，字符串中只包含大小写英文字母和数字。
接下来 m� 行，每行包含四个整数 l1,r1,l2,r2�1,�1,�2,�2，表示一次询问所涉及的两个区间。
注意，字符串的位置从 11 开始编号。
输出格式
对于每个询问输出一个结果，如果两个字符串子串完全相同则输出 Yes，否则输出 No。
每个结果占一行。
数据范围
1≤n,m≤1051≤�,�≤105
输入样例：
8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2
输出样例：
Yes
No
Yes

挑战模式

include [HTML_REMOVED]

using namespace std;

typedef unsigned long long ULL;
const int N = 100010, P = 131;

int n, m;
char str[N];
ULL h[N], p[N];

ULL get(int l, int r)
{
return h[r] - h[l - 1] * p[r - l + 1];
}

int main()
{
scanf(“%d%d”, &n, &m);
scanf(“%s”, str + 1);

p[0] = 1;
for(int i = 1; i <= n; i ++)
{
    h[i] = h[i - 1] * P + str[i];
    p[i] = p[i - 1] * P;
}
while(m --)
{
    int l1, r1, l2, r2;
    cin >> l1 >> r1 >> l2 >> r2;

    if(get(l1, r1) == get(l2, r2)) puts("Yes");
    else puts("No");
}
return 0;

}
单调队列
AcWing 299. 裁剪序列（每日一题）
给定一个长度为 N� 的序列 A�，要求把该序列分成若干段，在满足“每段中所有数的和”不超过 M� 的前提下，让“每段中所有数的最大值”之和最小。
试计算这个最小值。
输入格式
第一行包含两个整数 N� 和 M�。
第二行包含 N� 个整数，表示完整的序列 A�。
输出格式
输出一个整数，表示结果。
如果结果不存在，则输出 −1−1。
数据范围
0≤N≤1050≤�≤105,
0≤M≤10110≤�≤1011,
序列A中的数非负，且不超过106106
输入样例：
8 17
2 2 2 8 1 8 2 1
输出样例：
12

挑战模式
AcWing 830. 单调栈（算法基础课）
给定一个长度为 N� 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1−1。
输入格式
第一行包含整数 N�，表示数列长度。
第二行包含 N� 个整数，表示整数数列。
输出格式
共一行，包含 N� 个整数，其中第 i� 个数表示第 i� 个数的左边第一个比它小的数，如果不存在则输出 −1−1。
数据范围
1≤N≤1051≤�≤105
1≤数列中元素≤1091≤数列中元素≤109
输入样例：
5
3 4 2 7 5
输出样例：
-1 3 -1 2 2

挑战模式

include [HTML_REMOVED]

using namespace std;

const int N = 100100;

int a[N];

int main()
{
int n;
deque[HTML_REMOVED] q;
cin >> n;
for(int i = 1; i <= n; i )
{
cin >> a[i];
}
for(int i = 1; i <= n; i )
{
while(q.size() && q.back() >= a[i]) q.pop_back();
if(!q.size()) cout << -1 << ” “;
else cout << q.back() << ” “;
q.push_back(a[i]);
}
}
AcWing 154. 滑动窗口（算法基础课）
给定一个大小为 n≤106�≤106 的数组。
有一个大小为 k� 的滑动窗口，它从数组的最左边移动到最右边。
你只能在窗口中看到 k� 个数字。
每次滑动窗口向右移动一个位置。
以下是一个例子：
该数组为 [1 3 -1 -3 5 3 6 7]，k� 为 33。
窗口位置最小值最大值
[1 3 -1] -3 5 3 6 7 -1 3
1 [3 -1 -3] 5 3 6 7 -3 3
1 3 [-1 -3 5] 3 6 7 -3 5
1 3 -1 [-3 5 3] 6 7 -3 5
1 3 -1 -3 [5 3 6] 7 3 6
1 3 -1 -3 5 [3 6 7] 3 7
你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。
输入格式
输入包含两行。
第一行包含两个整数 n� 和 k�，分别代表数组长度和滑动窗口的长度。
第二行有 n� 个整数，代表数组的具体数值。
同行数据之间用空格隔开。
输出格式
输出包含两个。
第一行输出，从左至右，每个位置滑动窗口中的最小值。
第二行输出，从左至右，每个位置滑动窗口中的最大值。
输入样例：
8 3
1 3 -1 -3 5 3 6 7
输出样例：
-1 -3 -3 -3 3 3
3 3 5 5 6 7

挑战模式

include [HTML_REMOVED]

using namespace std;

const int N = 1000100;

int n, m;
int a[N], q[N];

int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i )
{
cin >> a[i];
}
deque[HTML_REMOVED] q;
for(int i = 1; i <= n; i )
{
while(q.size() && q.back() > a[i]) q.pop_back();
q.push_back(a[i]);
if(i - m >= 1 && q.front() == a[i - m]) q.pop_front();
if(i >= m) cout << q.front() << ” “;
}
cout << endl;
q.clear();
for(int i = 1; i <= n; i ++)
{
while(q.size() && q.back() < a[i]) q.pop_back();
q.push_back(a[i]);
if(i - m >= 1 && q.front() == a[i - m]) q.pop_front();
if(i >= m) cout << q.front() << ” “;
}
cout << endl;
return 0;
}
AcWing 135. 最大子序和（算法提高课）
输入一个长度为 n� 的整数序列，从中找出一段长度不超过 m� 的连续子序列，使得子序列中所有数的和最大。
注意：子序列的长度至少是 11。
输入格式
第一行输入两个整数 n,m�,�。
第二行输入 n� 个数，代表长度为 n� 的整数序列。
同一行数之间用空格隔开。
输出格式
输出一个整数，代表该序列的最大子序和。
数据范围
1≤n,m≤3000001≤�,�≤300000,
保证所有输入和最终结果都在 int 范围内。
输入样例：
6 4
1 -3 5 1 -2 3
输出样例：
7

include [HTML_REMOVED]

using namespace std;

const int N = 300100;
typedef long long LL;

int n, m;
LL s[N];

int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i )
{
cin >> s[i];
s[i] += s[i - 1];
}
deque[HTML_REMOVED] hash;
LL res = INT_MIN;
hash.push_back(0);
for(int i = 1; i <= n; i )
{
while(hash.size() && hash.front() < i - m) hash.pop_front();
res = max(res, s[i] - s[hash.front() ]);
while(hash.size() && s[hash.back()] >= s[i]) hash.pop_back();
hash.push_back(i);
//cout << res << ” ” << hash.front() << ” ” << s[i] << ” ” << hash.back() << “res” << endl;
}
cout << res << endl;
return 0;
}
KMP
AcWing 141. 周期（每日一题
一个字符串的前缀是从第一个字符开始的连续若干个字符，例如 abaab 共有 55 个前缀，分别是 a，ab，aba，abaa，abaab。
我们希望知道一个 N� 位字符串 S� 的前缀是否具有循环节。
换言之，对于每一个从头开始的长度为 i�（i>1�>1）的前缀，是否由重复出现的子串 A� 组成，即 AAA…A��…� （A� 重复出现 K� 次,K>1�>1）。
如果存在，请找出最短的循环节对应的 K� 值（也就是这个前缀串的所有可能重复节中，最大的 K� 值）。
输入格式
输入包括多组测试数据，每组测试数据包括两行。
第一行输入字符串 S� 的长度 N�。
第二行输入字符串 S�。
输入数据以只包括一个 00 的行作为结尾。
输出格式
对于每组测试数据，第一行输出 Test case # 和测试数据的编号。
接下来的每一行，输出具有循环节的前缀的长度 i� 和其对应 K�，中间用一个空格隔开。
前缀长度需要升序排列。
在每组测试数据的最后输出一个空行。
数据范围
2≤N≤10000002≤�≤1000000
输入样例：
3
aaa
4
abcd
12
aabaabaabaab
0
输出样例：
Test case #1
2 2
3 3

Test case #2

Test case #3
2 2
6 2
9 3
12 4

include [HTML_REMOVED]

using namespace std;

const int N = 10000100;

char q[N];
int n;
int ne[N];

int main()
{
int T = 1;
while(scanf(“%d”, &n), n)
{
cin >> q + 1;
for(int i = 2, j = 0; i <= n; i )
{
while(j && q[i] != q[j + 1]) j = ne[j];
if(q[i] == q[j + 1]) j ;
ne[i] = j;
}
cout << “Test case #” << T << endl;
for(int i = 1; i <= n; i )
{
int k = i - ne[i];
if(i % k == 0 && i / k > 1)
cout << i << ” ” << i / k << endl;
}
cout << endl;
}
return 0;
}
AcWing 831. KMP字符串（算法基础课）
给定一个字符串 S�，以及一个模式串 P�，所有字符串中只包含大小写英文字母以及阿拉伯数字。
模式串 P� 在字符串 S� 中多次作为子串出现。
求出模式串 P� 在字符串 S� 中所有出现的位置的起始下标。
输入格式
第一行输入整数 N�，表示字符串 P� 的长度。
第二行输入字符串 P�。
第三行输入整数 M�，表示字符串 S� 的长度。
第四行输入字符串 S�。
输出格式
共一行，输出所有出现位置的起始下标（下标从 00 开始计数），整数之间用空格隔开。
数据范围
1≤N≤1051≤�≤105
1≤M≤1061≤�≤106
输入样例：
3
aba
5
ababa
输出样例：
0 2

include [HTML_REMOVED]

using namespace std;

const int N = 100010, M = 1000100;

char p[N], s[M];
int ne[M];
int n, m;

int main()
{
cin >> n >> p + 1 >> m >> s + 1;
for(int i = 2, j = 0; i <= n; i )
{
while(j && p[i] != p[j + 1]) j = ne[j];
if(p[i] == p[j + 1]) j ;
ne[i] = j;
}
for(int i = 1, j = 0; i <= m; i )
{
while(j && s[i] != p[j + 1]) j = ne[j];
if(s[i] == p[j + 1]) j ;
if(j == n)
{
cout << i - n << ” “;
j = ne[j];
}
}
return 0;
}
Trie
AcWing 3485. 最大异或和（每日一题）
给定一个非负整数数列 a�，初始长度为 N�。
请在所有长度不超过 M� 的连续子数组中，找出子数组异或和的最大值。
子数组的异或和即为子数组中所有元素按位异或得到的结果。
注意：子数组可以为空。
输入格式
第一行包含两个整数 N,M�,�。
第二行包含 N� 个整数，其中第 i� 个为 ai��。
输出格式
输出可以得到的子数组异或和的最大值。
数据范围
对于 20%20% 的数据，1≤M≤N≤1001≤�≤�≤100
对于 50%50% 的数据，1≤M≤N≤10001≤�≤�≤1000
对于 100%100% 的数据，1≤M≤N≤105,0≤ai≤231−11≤�≤�≤105,0≤��≤231−1
输入样例：
3 2
1 2 4
输出样例：
6

include [HTML_REMOVED]

using namespace std;

const int M = 3100010;

int son[M][2], idx, n, cnt[M], m, s[M], a[M];

void insert(int x, int v)
{
int p = 0;
for(int i = 30; i >= 0; i –)
{
int u = x >> i & 1;
if(!son[p][u]) son[p][u] = ++ idx;
p = son[p][u];
cnt[p] += v;
}
}

int query(int x)
{
int p = 0, res = 0;
for(int i = 30; i >= 0; i –)
{
int u = x >> i & 1;
if(cnt[son[p][!u]]) p = son[p][!u], res = res * 2 + 1;
else p = son[p][u], res = res * 2;
}
return res;
}

int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i )
{
cin >> a[i];
s[i] = s[i - 1] ^ a[i];
}
insert(s[0], 1);
int res = 0;
for(int i = 1; i <= n; i )
{
if(i - m - 1 >= 0 ) insert(s[i - m - 1], -1);
res = max(query(s[i]), res);
insert(s[i], 1);
}
cout << res << endl;
return 0;
}
AcWing 835. Trie字符串统计（算法基础课）
维护一个字符串集合，支持两种操作：
1.I x 向集合中插入一个字符串 x�；
2.Q x 询问一个字符串在集合中出现了多少次。
共有 N� 个操作，所有输入的字符串总长度不超过 105105，字符串仅包含小写英文字母。
输入格式
第一行包含整数 N�，表示操作数。
接下来 N� 行，每行包含一个操作指令，指令为 I x 或 Q x 中的一种。
输出格式
对于每个询问指令 Q x，都要输出一个整数作为结果，表示 x� 在集合中出现的次数。
每个结果占一行。
数据范围
1≤N≤2∗1041≤�≤2∗104
输入样例：
5
I abc
Q abc
Q ab
I ab
Q ab
输出样例：
1
0
1

include [HTML_REMOVED]

using namespace std;

const int N = 100010;

int son[N][26], cnt[N], n, idx;
char s[N], op[2];

void insert(char s[])
{
int p = 0;
for(int i = 0; s[i]; i )
{
int j = s[i] - ‘a’;
if(!son[p][j]) son[p][j] = idx;
p = son[p][j];
}
cnt[p] ++;
}

int query(char s[])
{
int p = 0;
for(int i = 0; s[i]; i ++)
{
int j = s[i] - ‘a’;
if(!son[p][j]) return 0;
p = son[p][j];
}
return cnt[p];
}

int main()
{
cin >> n;
while(n –)
{
cin >> op >> s;
if(*op == ‘I’)
{
insert(s);
}else cout << query(s) << endl;
}
return 0;
}
AcWing 143. 最大异或对（算法基础课）
在给定的 N� 个整数 A1，A2……AN�1，�2……�� 中选出两个进行 xor��（异或）运算，得到的结果最大是多少？
输入格式
第一行输入一个整数 N�。
第二行输入 N� 个整数 A1�1～AN��。
输出格式
输出一个整数表示答案。
数据范围
1≤N≤1051≤�≤105,
0≤Ai<2310≤��<231
输入样例：
3
1 2 3
输出样例：
3

include [HTML_REMOVED]

using namespace std;

const int N = 100010, M = 30 * N;

int son[M][2], s[N], idx, n, res;

void insert(int x)
{
int p = 0;
for(int i = 30; i >= 0; i –)
{
int u = x >> i & 1;
if(!son[p][u]) son[p][u] = ++ idx;
p = son[p][u];
}
}

int query(int x)
{
int p = 0, res = 0;
for(int i = 30; i >= 0; i –)
{
int u = x >> i & 1;
if(son[p][!u])
{
p = son[p][!u];
res = res * 2 + 1;
}
else
{
res = res * 2 + 0;
p = son[p][u];
}
}
return res;
}

int main()
{
cin >> n;
for(int i = 0; i < n; i )
{
cin >> s[i];
insert(s[i]);
}
for(int i = 0; i < n; i )
{
res = max(res, query(s[i]));
}
cout << res << endl;
return 0;
}
BFS
AcWing 1562. 微博转发（每日一题）
微博被称为中文版的 Twitter。
微博上的用户既可能有很多关注者，也可能关注很多其他用户。
因此，形成了一种基于这些关注关系的社交网络。
当用户在微博上发布帖子时，他/她的所有关注者都可以查看并转发他/她的帖子，然后这些人的关注者可以对内容再次转发…
现在给定一个社交网络，假设只考虑 L� 层关注者，请你计算某些用户的帖子的最大可能转发量。
补充
如果 B� 是 A� 的关注者，C� 是 B� 的关注者，那么 A� 的第一层关注者是 B�，第二层关注者是 C�。
输入格式
第一行包含两个整数，N� 表示用户数量，L� 表示需要考虑的关注者的层数。
假设，所有的用户的编号为 1∼N1∼�。
接下来 N� 行，每行包含一个用户的关注信息，格式如下：
M[i] user_list[i]
M[i] 是第 i� 名用户关注的总人数，user_list[i] 是第 i� 名用户关注的 M[i] 个用户的编号列表。
最后一行首先包含一个整数 K�，表示询问次数，然后包含 K� 个用户编号，表示询问这些人的帖子的最大可能转发量。
输出格式
按顺序，每行输出一个被询问人的帖子最大可能转发量。
假设每名用户初次看到帖子时，都会转发帖子，只考虑 L� 层关注者。
数据范围
1≤N≤10001≤�≤1000,
1≤L≤61≤�≤6,
1≤M[i]≤1001≤�[�]≤100,
1≤K≤N1≤�≤�
输入样例：
7 3
3 2 3 4
0
2 5 6
2 3 1
2 3 4
1 4
1 5
2 2 6
输出样例：
4
5

include [HTML_REMOVED]

using namespace std;

const int N = 1010, M = 100010;

int h[N], ne[M], e[M], idx;
bool st[N];
int n, L;

void add(int j, int i)
{
e[idx] = i;
ne[idx] = h[j];
h[j] = idx ++;
}

int bfs(int x)
{
//cout << “x:” << x << endl;
queue[HTML_REMOVED] q;
q.push(x);
memset(st, 0, sizeof st);
st[x] = true;

int res = 0;
for(int i = 0; i < L; i ++)
{
    int sz = q.size();
    while(sz --)
    {
        auto t = q.front();
        q.pop();
        for(int j = h[t]; j != -1; j = ne[j])
        {
            int x = e[j];
            if(!st[x])
            {
                res ++;
                q.push(x);
                st[x] = true;
            }
        }
    }
}
return res;

}

int main()
{
memset(h, -1, sizeof(h));
cin >> n >> L;
for(int i = 1; i <= n; i ++)
{
int x;
cin >> x;
while(x –)
{
int j;
cin >> j;
add(j, i);
}
}
int m;
cin >> m;
while(m –)
{
int x;
cin >> x;
cout << bfs(x) << endl;
}
return 0;
}
AcWing 844. 走迷宫（算法基础课）
给定一个 n×m�×� 的二维整数数组，用来表示一个迷宫，数组中只包含 00 或 11，其中 00 表示可以走的路，11 表示不可通过的墙壁。
最初，有一个人位于左上角 (1,1)(1,1) 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。
请问，该人从左上角移动至右下角 (n,m)(�,�) 处，至少需要移动多少次。
数据保证 (1,1)(1,1) 处和 (n,m)(�,�) 处的数字为 00，且一定至少存在一条通路。
输入格式
第一行包含两个整数 n� 和 m�。
接下来 n� 行，每行包含 m� 个整数（00 或 11），表示完整的二维数组迷宫。
输出格式
输出一个整数，表示从左上角移动至右下角的最少移动次数。
数据范围
1≤n,m≤1001≤�,�≤100
输入样例：
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出样例：
8

include [HTML_REMOVED]

using namespace std;

const int N = 110;
typedef pair[HTML_REMOVED] PII;

int g[N][N], n, m;
int d[N][N];

int bfs()
{
queue[HTML_REMOVED] q;
memset(d, -1, sizeof(d));
d[0][0] = 0;
q.push({0, 0});
while(q.size())
{
auto t = q.front();
q.pop();
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
for(int i = 0; i < 4; i ++)
{
int x = dx[i] + t.first;
int y = dy[i] + t.second;
if(d[x][y] == -1 && g[x][y] == 0 && x >= 0 && x < n && y >= 0 && y < m)
{
d[x][y] = d[t.first][t.second] + 1;
q.push({x, y});
}
}
}
return d[n - 1][m - 1];
}

int main()
{
cin >> n >> m;
for(int i = 0; i < n; i )
for(int j = 0; j < m; j )
cin >> g[i][j];
cout << bfs() << endl;
return 0;
}
AcWing 845. 八数码（算法基础课）
在一个 3×33×3 的网格中，1∼81∼8 这 88 个数字和一个 x 恰好不重不漏地分布在这 3×33×3 的网格中。
例如：
1 2 3
x 4 6
7 5 8
在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。
我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：
1 2 3
4 5 6
7 8 x
例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。
交换过程如下：
1 2 3 1 2 3 1 2 3 1 2 3
x 4 6 4 x 6 4 5 6 4 5 6
7 5 8 7 5 8 7 x 8 7 8 x
现在，给你一个初始网格，请你求出得到正确排列至少需要进行多少次交换。
输入格式
输入占一行，将 3×33×3 的初始网格描绘出来。
例如，如果初始网格如下所示：
1 2 3
x 4 6
7 5 8
则输入为：1 2 3 x 4 6 7 5 8
输出格式
输出占一行，包含一个整数，表示最少交换次数。
如果不存在解决方案，则输出 −1−1。
输入样例：
2 3 4 1 5 x 7 6 8
输出样例
19

挑战模式

include [HTML_REMOVED]

using namespace std;

int bfs(string state)
{
string end = “12345678x”;
queue[HTML_REMOVED] q;
unordered_map[HTML_REMOVED] d;
q.push(state);
d[state] = 0;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
while(q.size())
{
auto t = q.front();
q.pop();
if(t == end) return d[t];
int distance = d[t];
int k = t.find(‘x’);
int a = k / 3, b = k % 3;
for(int i = 0; i < 4; i ++)
{
int x = a + dx[i], y = b + dy[i];

        if(x >= 0 && x < 3 && y >= 0 && y < 3)
        {
            swap(t[k], t[x * 3 + y]);
            if(!d.count(t))
            {
                q.push(t);
                d[t] = distance + 1;
            }
            swap(t[k], t[x * 3 + y]);
        }
    }
}
return -1;

}

int main()
{
string state;
char c;
for(int i = 0; i < 9; i ++)
{
cin >> c;
state += c;
}
cout << bfs(state) << endl;
return 0;
}
AcWing 1233. 全球变暖（蓝桥杯辅导课）
你有一张某海域 N×N�×� 像素的照片，”.”表示海洋、”#”表示陆地，如下所示：
.......
.##....
.##....
....##.
..####.
…###.
.......
其中”上下左右”四个方向上连在一起的一片陆地组成一座岛屿，例如上图就有 22 座岛屿。
由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。
具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。
例如上图中的海域未来会变成如下样子：
.......
.......
.......
.......
....#..
.......
.......
请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。
输入格式
第一行包含一个整数N。
以下 N� 行 N� 列，包含一个由字符”#”和”.”构成的 N×N�×� 字符矩阵，代表一张海域照片，”#”表示陆地，”.”表示海洋。
照片保证第 11 行、第 11 列、第 N� 行、第 N� 列的像素都是海洋。
输出格式
一个整数表示答案。
数据范围
1≤N≤10001≤�≤1000
输入样例1：
7
.......
.##....
.##....
....##.
..####.
…###.
.......
输出样例1：
1
输入样例2：
9
.........
.##.##…
.#####…
.##.##…
.........
.##.#....
.#.###…
.#..#....
.........
输出样例2：
1

挑战模式

include [HTML_REMOVED]

using namespace std;
typedef pair[HTML_REMOVED] PII;

const int N = 1100;

char g[N][N];
int n;
bool st[N][N];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

void bfs(int sx, int sy, int &total, int &bound)
{
queue[HTML_REMOVED] q;
q.push({sx, sy});
st[sx][sy] = true;

while(q.size())
{
    auto t = q.front();
    q.pop();
    total ++;
    bool is_bound = false;
    for(int i = 0; i < 4; i ++)
    {
        int x = dx[i] + t.first;
        int y = dy[i] + t.second;
        if(st[x][y]) continue;
        if(g[x][y] == '.') 
        {
            is_bound = true;
            continue;
        }
        if(x < 0 || x >= n || y < 0 || y >= n) continue;
        st[x][y] = true;
        q.push({x, y});
    }
    if(is_bound) bound ++;
}

}

int main()
{
cin >> n;
for(int i = 0; i < n; i ) scanf(“%s”, &g[i]);
int cnt = 0;
for(int i = 0; i < n; i )
for(int j = 0; j < n; j )
{
if(!st[i][j] && g[i][j] == ‘#’)
{
int total = 0, bound = 0;
bfs(i, j, total, bound);
if(total == bound) cnt ;
}
}
cout << cnt << endl;
return 0;
}
DFS
给定一个 n×m�×� 的二维矩阵，其中的每个元素都是一个 [1,9][1,9] 之间的正整数。
从矩阵中的任意位置出发，每次可以沿上下左右四个方向前进一步，走过的位置可以重复走。
走了 k� 次后，经过的元素会构成一个 (k+1)(�+1) 位数。
请求出一共可以走出多少个不同的 (k+1)(�+1) 位数。
输入格式
第一行包含三个整数 n,m,k�,�,�。
接下来 n� 行，每行包含 m� 个空格隔开的整数，表示给定矩阵。
输出格式
输出一个整数，表示可以走出的不同 (k+1)(�+1) 位数的个数。
数据范围
对于 30%30% 的数据, 1≤n,m≤2,0≤k≤21≤�,�≤2,0≤�≤2
对于 100%100% 的数据，1≤n,m≤5,0≤k≤5,m×n>11≤�,�≤5,0≤�≤5,�×�>1
输入样例：
3 3 2
1 1 1
1 1 1
2 1 1
输出样例：
5
样例解释
一共有 55 种可能的 33 位数：
111
112
121
211
212
给定一个 n×m�×� 的二维矩阵，其中的每个元素都是一个 [1,9][1,9] 之间的正整数。
从矩阵中的任意位置出发，每次可以沿上下左右四个方向前进一步，走过的位置可以重复走。
走了 k� 次后，经过的元素会构成一个 (k+1)(�+1) 位数。
请求出一共可以走出多少个不同的 (k+1)(�+1) 位数。
输入格式
第一行包含三个整数 n,m,k�,�,�。
接下来 n� 行，每行包含 m� 个空格隔开的整数，表示给定矩阵。
输出格式
输出一个整数，表示可以走出的不同 (k+1)(�+1) 位数的个数。
数据范围
对于 30%30% 的数据, 1≤n,m≤2,0≤k≤21≤�,�≤2,0≤�≤2
对于 100%100% 的数据，1≤n,m≤5,0≤k≤5,m×n>11≤�,�≤5,0≤�≤5,�×�>1
输入样例：
3 3 2
1 1 1
1 1 1
2 1 1
输出样例：
5
样例解释
一共有 55 种可能的 33 位数：
111
112
121
211
212
AcWing 842. 排列数字（算法基础课）
给定一个整数 n�，将数字 1∼n1∼� 排成一排，将会有很多种排列方法。
现在，请你按照字典序将所有的排列方法输出。
输入格式
共一行，包含一个整数 n�。
输出格式
按字典序输出所有排列方案，每个方案占一行。
数据范围
1≤n≤71≤�≤7
输入样例：
3
输出样例：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

include [HTML_REMOVED]

using namespace std;

const int N = 8;

int path[N];
bool st[N];
int n;

void dfs(int u)
{
if(u == n)
{
for(int i = 0; i < n; i ++)
{
cout << path[i] + 1 << ” “;
}
cout << endl;
return ;
}

for(int i = 0; i < n; i ++)
{
    if(!st[i])
    {
        st[i] = true;
        path[u] = i;
        dfs(u + 1);
        st[i] = false;
    }
}

}

int main()
{
cin >> n;
dfs(0);
return 0;
}
AcWing 843. n-皇后问题（算法基础课）
n−�−皇后问题是指将 n� 个皇后放在 n×n�×� 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

现在给定整数 n�，请你输出所有的满足条件的棋子摆法。
输入格式
共一行，包含整数 n�。
输出格式
每个解决方案占 n� 行，每行输出一个长度为 n� 的字符串，用来表示完整的棋盘状态。
其中 . 表示某一个位置的方格状态为空，Q 表示某一个位置的方格上摆着皇后。
每个方案输出完成后，输出一个空行。
注意：行末不能有多余空格。
输出方案的顺序任意，只要不重复且没有遗漏即可。
数据范围
1≤n≤91≤�≤9
输入样例：
4
输出样例：
.Q..
…QQ…
..Q.

..Q.Q…
…Q.Q..

include [HTML_REMOVED]

using namespace std;

const int N = 20;

char g[N][N];
bool lie[N], dg[N], udg[N];
int n;

void dfs(int u)
{
if(u == n)
{
for(int i = 0; i < n; i ) cout << g[i] << endl;
cout << endl;
return ;
}
for(int i = 0; i < n; i )
{
if(!dg[u + i] && !udg[n - u + i] && !lie[i])
{
lie[i] = dg[u + i] = udg[n - u + i] = true;
g[u][i] = ‘Q’;
dfs(u + 1);
g[u][i] = ‘.’;
lie[i] = dg[u + i] = udg[n - u + i] = false;
}
}
}

int main()
{
cin >> n;
for(int i = 0; i < n; i )
for(int j = 0; j < n; j )
{
g[i][j] = ‘.’;
}
dfs(0);
return 0;
}AcWing 165. 小猫爬山（算法提高课）
翰翰和达达饲养了 N� 只小猫，这天，小猫们要去爬山。
经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了（呜咕>_<）。
翰翰和达达只好花钱让它们坐索道下山。
索道上的缆车最大承重量为 W�，而 N� 只小猫的重量分别是 C1、C2……CN�1、�2……��。
当然，每辆缆车上的小猫的重量之和不能超过 W�。
每租用一辆缆车，翰翰和达达就要付 11 美元，所以他们想知道，最少需要付多少美元才能把这 N� 只小猫都运送下山？
输入格式
第 11 行：包含两个用空格隔开的整数，N� 和 W�。
第 2..N+12..�+1 行：每行一个整数，其中第 i+1�+1 行的整数表示第 i� 只小猫的重量 Ci��。
输出格式
输出一个整数，表示最少需要多少美元，也就是最少需要多少辆缆车。
数据范围
1≤N≤181≤�≤18,
1≤Ci≤W≤1081≤��≤�≤108
输入样例：
5 1996
1
2
1994
12
29
输出样例：
2

include [HTML_REMOVED]

using namespace std;

const int N = 20;

int n, m, ans;
int cnt[N], sum[N];

void dfs(int u, int k)
{
if(k >= ans) return ;
if(u == n)
{
ans = k;
return ;
}
for(int i = 0; i < k; i ++)
{
if(sum[i] + cnt[u] <= m)
{
sum[i] += cnt[u];
dfs(u + 1, k);
sum[i] -= cnt[u];
}
}
sum[k] += cnt[u];
dfs(u + 1, k + 1);
sum[k] = 0;
}

int main()
{
cin >> n >> m;
ans = n;
for(int i = 0; i < n; i ++) cin >> cnt[i];
sort(cnt, cnt + n);
reverse(cnt, cnt + n);
dfs(0, 0);
cout << ans << endl;
return 0;
}
AcWing 1209. 带分数（蓝桥杯辅导课）
100100 可以表示为带分数的形式：100=3+69258/714
还可以表示为：100=82+3546197100=82+3546197
注意特征：带分数中，数字 1∼91∼9 分别出现且只出现一次（不包含 00）。
类似这样的带分数，100100 有 1111 种表示法。
输入格式
一个正整数。
输出格式
输出输入数字用数码 1∼91∼9 不重复不遗漏地组成带分数表示的全部种数。
数据范围
1≤N<1061≤�<106
输入样例1：
100
输出样例1：
11
输入样例2：
105
输出样例2：
6

include [HTML_REMOVED]

using namespace std;

const int N = 1000100;

int n, k;
int num[15];

int cal(int l, int r)
{
int ans = 0;
for(int i = l; i <= r; i ++)
{
ans = ans * 10 + num[i];
}
return ans;
}

int main()
{
cin >> n;
for(int i = 1; i <= 9; i )
{
num[i] = i;
}
do
{
for(int i = 1; i <= 9; i )
for(int j = i + 1; j <= 9; j )
{
int a = cal(1, i);
int b = cal(i + 1, j);
int c = cal(j + 1, 9);
//if(a == 0 || b == 0 || c ==0) continue;
if(a * c + b == n * c) k ;
}

}while(next_permutation(num + 1, num + 10));
cout << k << endl;
return 0;

}
拓扑排序
AcWing 848. 有向图的拓扑序列（算法基础课）
给定一个 n� 个点 m� 条边的有向图，点的编号是 11 到 n�，图中可能存在重边和自环。
请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 −1−1。
若一个由图中所有点构成的序列 A� 满足：对于图中的每条边 (x,y)(�,�)，x� 在 A� 中都出现在 y� 之前，则称 A� 是该图的一个拓扑序列。
输入格式
第一行包含两个整数 n� 和 m�。
接下来 m� 行，每行包含两个整数 x� 和 y�，表示存在一条从点 x� 到点 y� 的有向边 (x,y)(�,�)。
输出格式
共一行，如果存在拓扑序列，则输出任意一个合法的拓扑序列即可。
否则输出 −1−1。
数据范围
1≤n,m≤1051≤�,�≤105
输入样例：
3 3
1 2
2 3
1 3
输出样例：
1 2 3
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]

// using namespace std;

// const int N = 100100;

// int ne[N], e[N], h[N], idx;
// int n, m;
// int top[N], d[N], cnt = 1;

// void add(int a, int b)
// {
// e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
// }

// int topsort()
// {
// queue[HTML_REMOVED] q;
// for(int i = 1; i <= n; i )
// {
// if(!d[i]) q.push(i);
// }
// while(q.size())
// {
// int t = q.front();
// top[cnt] = t;
// cnt ;
// q.pop();
// for(int i = h[t]; i != -1; i = ne[i])
// {
// int j = e[i];
// d[j] –;
// if(!d[i]) q.push(j);
// }
// }
// if(cnt < n) return 0;
// else return 1;
// }

// int main()
// {
// memset(h, -1, sizeof(h));
// cin >> n >> m;
// for(int i = 0; i < m; i )
// {
// int a, b;
// cin >> a >> b;
// add(a, b);
// d[b] ;
// }
// if(topsort())
// {
// for(int i = 1; i <= n; i ++)
// {
// cout << top[i]<< ” “;
// }
// }else cout << -1 << endl;
// return 0;
// }

include [HTML_REMOVED]

using namespace std;

const int N = 100010;

int ne[N], e[N], h[N], idx;
int n, m;
int top[N], d[N], cnt = 1;

void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int topsort()
{
queue[HTML_REMOVED] q;
int t;
for(int i = 1;i <= n; i)// 将所有入度为0的点加入队列
if(d[i] == 0) q.push(i);
while(q.size()){
t = q.front();//每次取出队列的首部
top[cnt] = t;//加入到拓扑序列中
cnt ; // 序列中的元素 ++
q.pop();
for(int i = h[t];i != -1; i = ne[i]){
// 遍历 t 点的出边
int j = e[i];
d[j] –;// j 的入度 –
if(d[j] == 0) q.push(j); //如果 j 入度为0，加入队列当中
}
}
if(cnt < n) return 0;
else return 1;

}

int main()
{
memset(h, -1, sizeof(h));
cin >> n >> m;
for(int i = 0; i < m; i )
{
int a, b;
cin >> a >> b;
add(a, b);
d[b] ;
}
if(topsort())
{
for(int i = 1; i <= n; i ++)
{
cout << top[i]<< ” “;
}
}else cout << -1 << endl;
return 0;
}
Floyd
AcWing 4074. 铁路与公路（每日一题）
某国家有 n� 个城市（编号 1∼n1∼�）和 m� 条双向铁路。
每条铁路连接两个不同的城市，没有两条铁路连接同一对城市。
除了铁路以外，该国家还有公路。
对于每对不同的城市 x,y�,�，当且仅当它们之间没有铁路时，它们之间会存在一条双向公路。
经过每条铁路或公路都需要花费 11 小时的时间。
现在有一列火车和一辆汽车同时离开城市 11，它们的目的地都是城市 n�。
它们不会在途中停靠（但是可以在城市 n� 停靠）。
火车只能沿铁路行驶，汽车只能沿公路行驶。
请你为它们规划行进路线，每条路线中可重复经过同一条铁路或公路，但是为了避免发生事故，火车和汽车不得同时到达同一个城市（城市 n� 除外）。
请问，在这些条件的约束下，两辆车全部到达城市 n� 所需的最少小时数，即求更慢到达城市 n� 的那辆车所需的时间的最小值。
注意，两辆车允许但不必要同时到达城市 n�。
输入格式
第一行包含整数 n� 和 m�。
接下来 m� 行，每行包含两个整数 u,v�,�，表示城市 u� 和城市 v� 之间存在一条铁路。
输出格式
一个整数，表示所需的最少小时数。
如果至少有一辆车无法到达城市 n�，则输出 −1−1。
数据范围
前 66 个测试点满足 2≤n≤102≤�≤10，0≤m≤100≤�≤10。
所有测试点满足 2≤n≤4002≤�≤400，0≤m≤n(n−1)20≤�≤�(�−1)2，1≤u,v≤n1≤�,�≤�。
输入样例1：
4 2
1 3
3 4
输出样例1：
2
输入样例2：
4 6
1 2
1 3
1 4
2 3
2 4
3 4
输出样例2：
-1
输入样例3：
5 5
4 2
3 5
4 5
5 1
1 2
输出样例3：
3

include [HTML_REMOVED]

using namespace std;

const int N = 410, INF = 0x3f3f3f;
int n, m;
int g[N][N], t[N][N];

int floyd(int d[][N])
{
for(int m = 1; m <= n; m )
for(int i = 1; i <= n; i )
for(int j = 1; j <= n; j ++)
{
d[i][j] = min(d[i][j], d[i][m] + d[m][j]);
}
//cout << d[1][n] << “den” << endl;
return d[1][n];
}

int main()
{
cin >> n >> m;
memset(t, 0x3f, sizeof t);
memset(g, 0x3f, sizeof g);
while(m –)
{
int a, b;
cin >> a >> b;
t[a][b] = t[b][a] = 1;
}
for(int i = 1; i <= n; i )
for(int j = 1; j <= n; j )
{
if(j != i && t[i][j] != 1)
g[i][j] = g[j][i] = 1;
}
int a = floyd(g);
int b = floyd(t);
//cout << a << b << ” ” << endl;
int c = max(a, b);
if(c >= INF) cout << -1 << endl;
else cout << c << endl;
return 0;
}
AcWing 854. Floyd求最短路（算法基础课）
给定一个 n� 个点 m� 条边的有向图，图中可能存在重边和自环，边权可能为负数。
再给定 k� 个询问，每个询问包含两个整数 x� 和 y�，表示查询从点 x� 到点 y� 的最短距离，如果路径不存在，则输出 impossible。
数据保证图中不存在负权回路。
输入格式
第一行包含三个整数 n,m,k�,�,�。
接下来 m� 行，每行包含三个整数 x,y,z�,�,�，表示存在一条从点 x� 到点 y� 的有向边，边长为 z�。
接下来 k� 行，每行包含两个整数 x,y�,�，表示询问点 x� 到点 y� 的最短距离。
输出格式
共 k� 行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出 impossible。
数据范围
1≤n≤2001≤�≤200,
1≤k≤n21≤�≤�2
1≤m≤200001≤�≤20000,
图中涉及边长绝对值均不超过 1000010000。
输入样例：
3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3
输出样例：
impossible1

挑战模式

include [HTML_REMOVED]

using namespace std;

const int N = 20010, INF = 1e9;

int n, m, k;
int d[N][N];

void floyd()
{
for(int m = 1; m <= n; m )
for(int i = 1; i <= n; i )
for(int j = 1; j <= n; j ++)
{
d[i][j] = min(d[i][j], d[i][m] + d[m][j]);
}
}

int main()
{
cin >> n >> m >> k;
for(int i = 1; i <= n; i )
for(int j = 1; j <= m; j )
{
if(j == i) d[i][j] = 0;
else d[i][j] = INF;
}
for(int i = 1; i <= m; i ++)
{
int a, b, c;
cin >> a >> b >> c;
d[a][b] = min(d[a][b], c);
}
floyd();
while(k –)
{
int a, b;
cin >> a >> b;
if(d[a][b] > INF / 2) cout << “impossible” << endl;
else cout << d[a][b] << endl;
}
return 0;
}
AcWing 1125. 牛的旅行（算法提高课）
农民John的农场里有很多牧区，有的路径连接一些特定的牧区。
一片所有连通的牧区称为一个牧场。
但是就目前而言，你能看到至少有两个牧区不连通。
现在，John想在农场里添加一条路径（注意，恰好一条）。
一个牧场的直径就是牧场中最远的两个牧区的距离（本题中所提到的所有距离指的都是最短的距离）。
考虑如下的两个牧场，每一个牧区都有自己的坐标：

图 1 是有 5 个牧区的牧场，牧区用“”表示，路径用直线表示。
图 1 所示的牧场的直径大约是 12.07106, 最远的两个牧区是 A 和 E，它们之间的最短路径是 A-B-E。
图 2 是另一个牧场。
这两个牧场都在John的农场上。
John将会在两个牧场中各选一个牧区，然后用一条路径连起来，使得连通后这个新的更大的牧场有最小的直径。
注意，如果两条路径中途相交，我们不认为它们是连通的。
只有两条路径在同一个牧区相交，我们才认为它们是连通的。
现在请你编程找出一条连接两个不同牧场的路径，使得连上这条路径后，所有牧场（生成的新牧场和原有牧场）中直径最大的牧场的直径尽可能小。
输出这个直径最小可能值。
输入格式
第 1 行：一个整数 N, 表示牧区数；
第 2 到 N+1 行：每行两个整数 X,Y，表示 N 个牧区的坐标。每个牧区的坐标都是不一样的。
第 N+2 行到第 2N+1 行：每行包括 N 个数字 ( 0或1 ) 表示一个对称邻接矩阵。
例如，题目描述中的两个牧场的矩阵描述如下：
A B C D E F G H
A 0 1 0 0 0 0 0 0
B 1 0 1 1 1 0 0 0
C 0 1 0 0 1 0 0 0
D 0 1 0 0 1 0 0 0
E 0 1 1 1 0 0 0 0
F 0 0 0 0 0 0 1 0
G 0 0 0 0 0 1 0 1
H 0 0 0 0 0 0 1 0
输入数据中至少包括两个不连通的牧区。
输出格式
只有一行，包括一个实数，表示所求答案。
数字保留六位小数。
数据范围
1≤N≤1501≤�≤150,
0≤X,Y≤1050≤�,�≤105
输入样例：
8
10 10
15 10
20 10
15 15
20 15
30 15
25 10
30 10
01000000
10111000
01001000
01001000
01110000
00000010
00000101
00000010
输出样例：
22.071068

include [HTML_REMOVED]

using namespace std;

const int N = 210;
const double INF = 1e20;

typedef pair[HTML_REMOVED] PII;

PII g[N];
char st[N][N];
int n;
double maxd[N];
double d[N][N];

double get_dist(PII a, PII b)
{
double da = a.first - b.first;
double db = a.second - b.second;
return sqrt(da * da + db * db);
}

int main()
{
cin >> n;
for(int i = 0; i < n; i ) cin >> g[i].first >> g[i].second;
for(int i = 0; i < n; i ) cin >> st[i];
for(int i = 0; i < n; i )
for(int j = 0; j < n; j )
{
if(j == i) d[i][j] = 0;
else if(st[i][j] == ‘1’) d[i][j] = get_dist(g[i], g[j]);
else d[i][j] = INF;
}
for(int k = 0; k < n; k )
for(int i = 0; i < n; i )
for(int j = 0; j < n; j )
{
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
double res1 = 0;
for(int i = 0; i < n; i )
{
for(int j = 0; j < n; j )
{
if(d[i][j] < INF / 2)
{
maxd[i] = max(d[i][j], maxd[i]);
}
}
res1 = max(res1, maxd[i]);
}
double res2 = INF;
for(int i = 0; i < n; i )
for(int j = 0; j < n; j ++)
{
if(d[i][j] > INF / 2)
{
//cout << maxd[i] << ” << ” << maxd[j] << endl;
res2 = min(res2, maxd[i] + maxd[j] + get_dist(g[i], g[j]));
}
}
// cout << res1 << ” ” << res2 << endl;
printf(“%lf\n”, max(res1, res2));
return 0;
}
筛质数
AcWing 3792. 质数问题（每日一题）
给定两个整数 n� 和 k�，请你判断在 [2,n][2,�] 的范围内是否存在不少于 k� 个质数，满足可以表示为两个相邻质数与 11 的和。
例如，1919 满足条件，因为 19=7+11+119=7+11+1。
输入格式
第一行包含整数 T�，表示共有 T� 组测试数据。
每组数据占一行，包含两个整数 n� 和 k�。
输出格式
每组数据输出占一行，如果存在不少于 k� 个质数满足条件则输出 YES，否则输出 NO。
数据范围
1≤T≤301≤�≤30,
2≤n≤10002≤�≤1000,
0≤k≤10000≤�≤1000
输入样例：
5
27 2
45 7
2 0
15 1
17 1
输出样例：
YESNOYESYESYES

include [HTML_REMOVED]

using namespace std;

const int N = 1010;

int pr[N], st[N], n, k, t;

int prime(int n, int k)
{
int cnt = 0;
int num = 0;
for(int i = 2; i <= n; i )
{
if(!st[i])
{
pr[cnt ] = i;
for(int j = i; j <= n; j += i)
{
st[j] = 1;
}
}
}
for(int i = 0; i < cnt; i )
{
//cout << pr[i] << “Pr” << endl;
k = pr[i] + pr[i + 1] + 1;
{
for(int j = i ; j < cnt; j )
{
if(pr[j] == k)
{
num ++;
break;
}
}
}
}
//cout << num << endl;
return num;

}

int main()
{
cin >> t;
while(t –)
{
memset(st, 0, sizeof(st));
memset(pr, 0, sizeof(pr));
cin >> n >> k;
int mazu = prime(n, k);
//cout << mazu << endl;
if(mazu >= k) cout << “YES” << endl;
else cout << “NO” << endl;
}
}
AcWing 868. 筛质数（算法基础课）
给定一个正整数 n�，请你求出 1∼n1∼� 中质数的个数。
输入格式
共一行，包含整数 n�。
输出格式
共一行，包含一个整数，表示 1∼n1∼� 中质数的个数。
数据范围
1≤n≤1061≤�≤106
输入样例：
8
输出样例：
4

include [HTML_REMOVED]

using namespace std;

const int N = 1000100;

int n, cnt;
int pr[N];
bool st[N];

void prime(int n)
{
for(int i = 2; i <= n; i )
{
if(!st[i])
{
pr[cnt ] = i;
for(int j = i; j <= n; j += i)
{
st[j] = true;
}
}
}
}

int main()
{
cin >> n;
prime(n);
cout << cnt << endl;
return 0;
}
1292. 哥德巴赫猜哥德巴赫猜想的内容如下：
任意一个大于 44 的偶数都可以拆成两个奇素数之和。
例如：
8=3+58=3+5
20=3+17=7+1320=3+17=7+13
42=5+37=11+31=13+29=19+2342=5+37=11+31=13+29=19+23
现在，你的任务是验证所有小于一百万的偶数能否满足哥德巴赫猜想。
输入格式
输入包含多组数据。
每组数据占一行，包含一个偶数 n�。
读入以 00 结束。
输出格式
对于每组数据，输出形如 n = a + b，其中 a,b�,� 是奇素数。
若有多组满足条件的 a,b�,�，输出 b−a�−� 最大的一组。
若无解，输出 Goldbach’s conjecture is wrong.。
数据范围
6≤n<1066≤�<106
输入样例：
8
20
42
0
输出样例：
8 = 3 + 520 = 3 + 1742 = 5 + 37
想#include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

const int N = 1000100;

int st[N], pr[N], cnt, n;
unordered_set[HTML_REMOVED] hash1;
void prime(int n)
{

for(int i = 2; i <= n; i ++)
{
    if(!st[i])
    {
        hash1.insert(i);
        pr[cnt ++] = i;
        for(int j = i; j <= n; j += i)
        {
            st[j] = 1;
        }
    }
}

}

int main()
{
prime(1000000);
cin >> n;int k;
while(n != 0)
{
for(int i = 0; i < cnt; i ++)
{
//cout << pr[i] << “pr” << endl;
if(pr[i] % 2 != 0)
{

            int k = pr[i];
            int b = n - k;
            if(hash1.count(b))
            {
                cout << n << " = " << k << " + " << n - k<< endl;
                break;
            }

        }
    }
    cin >> n;
}
return 0;

}
・最大公约数
AcWing 4309. 消灭老鼠（每日一题）
约翰的农场可以看作一个二维平面。
农场中有 n� 个老鼠，在毁坏着农田。
第 i� 个老鼠的位置坐标为 (xi,yi)(��,��)。
不同老鼠可能位于同一位置。
在 (x0,y0)(�0,�0) 处，装有一个双向发射的激光枪，该位置没有老鼠。
激光枪每次发射都可以将穿过点 (x0,y0)(�0,�0) 的某一条直线上的所有老鼠都消灭掉。
请问，为了消灭所有老鼠，至少需要激光枪发射几次。
输入格式
第一行包含三个整数 n,x0,y0�,�0,�0，表示共有 n� 只老鼠，激光枪的位置为 (x0,y0)(�0,�0)。
接下来 n� 行，每行包含两个整数 xi,yi��,��，表示第 i� 只老鼠的位置为 (xi,yi)(��,��)。
输出格式
一个整数，表示激光枪的最少发射次数。
数据范围
前 55 个测试点满足 1≤n≤51≤�≤5。
所有测试点满足 1≤n≤10001≤�≤1000，−104≤xi,yi≤104−104≤��,��≤104。
输入样例1：
4 0 0
1 1
2 2
2 0-1 -1
输出样例1：
2
输入样例2：
2 1 2
1 1
1 0
输出样例2：
1

include [HTML_REMOVED]

using namespace std;
typedef pair[HTML_REMOVED] PII;

int n, x0, y0;
set[HTML_REMOVED] s;

int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}

int main()
{
cin >> n >> x0 >> y0;
while(n –)
{
int x, y;
cin >> x >> y;
x -= x0, y -= y0;
int d = gcd(x, y);
x = x / d, y = y / d;
if(x < 0) x = - x, y = - y;
s.insert({x, y});
}
cout << s.size() << endl;
return 0;
}
AcWing 872. 最大公约数（算法基础课）
给定 n� 对正整数 ai,bi��,��，请你求出每对数的最大公约数。
输入格式
第一行包含整数 n�。
接下来 n� 行，每行包含一个整数对 ai,bi��,��。
输出格式
输出共 n� 行，每行输出一个整数对的最大公约数。
数据范围
1≤n≤1051≤�≤105,
1≤ai,bi≤2×1091≤��,��≤2×109
输入样例：
2
3 6
4 6
输出样例：
3
2

挑战模式

include [HTML_REMOVED]

using namespace std;

int n;

int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}

int main()
{
cin >> n;
while(n –)
{
int a, b;
cin >> a >> b;
cout << gcd(a, b) << endl;
}
return 0;
}
快速幂
AcWing 3625. 幂次方（每日一题）
对任意正整数 N�，计算 XNmod233333��mod233333 的值。
输入格式
共一行，两个整数 X� 和 N�。
输出格式
共一行，一个整数，表示 XNmod233333��mod233333 的值。
数据范围
1≤X,N≤1091≤�,�≤109
输入样例：
2 5
输出样例：
32

include [HTML_REMOVED]

using namespace std;

typedef long long LL;

LL qsm(LL x, LL n)
{
LL res = 1;
while(n)
{
if(n & 1) res = res * x % 233333;
n >>= 1;
x = x * x % 233333;
}
return res;
}

int main()
{
LL x, n;
scanf(“%lld%lld”, &x, &n);
printf(“%lld\n”, qsm(x, n));
return 0;
}
AcWing 875. 快速幂（算法基础课）
给定 n� 组 ai,bi,pi��,��,��，对于每组数据，求出 abiimodpi��mod�� 的值。
输入格式
第一行包含整数 n�。
接下来 n� 行，每行包含三个整数 ai,bi,pi��,��,��。
输出格式
对于每组数据，输出一个结果，表示 abiimodpi��mod�� 的值。
每个结果占一行。
数据范围
1≤n≤1000001≤�≤100000,
1≤ai,bi,pi≤2×1091≤��,��,��≤2×109
输入样例：
2
3 2 5
4 3 9
输出样例：
4
1

挑战模式

include [HTML_REMOVED]

using namespace std;

typedef long long LL;

int n;

LL qsm(LL a, LL b, LL p)
{
LL res = 1;
while(b)
{
if(b & 1) res = res * a % p;
b >>= 1;
a = a * a % p;
}
return res;
}

int main()
{
cin >> n;
while(n –)
{
LL a, b, p;
scanf(“%lld%lld%lld”, &a, &b, &p);
printf(“%lld\n”, qsm(a, b, p));
}
return 0;
}
AcWing 876. 快速幂求逆元（算法基础课）
给定 n� 组 ai,pi��,��，其中 pi�� 是质数，求 ai�� 模 pi�� 的乘法逆元，若逆元不存在则输出 impossible。
注意：请返回在 0∼p−10∼�−1 之间的逆元。
乘法逆元的定义
若整数 b，m�，� 互质，并且对于任意的整数 a�，如果满足 b|a�|�，则存在一个整数 x�，使得 a/b≡a×x(modm)�/�≡�×�(mod�)，则称 x� 为 b� 的模 m� 乘法逆元，记为 b−1(modm)�−1(mod�)。
b� 存在乘法逆元的充要条件是 b� 与模数 m� 互质。当模数 m� 为质数时，bm−2��−2 即为 b� 的乘法逆元。
输入格式
第一行包含整数 n�。
接下来 n� 行，每行包含一个数组 ai,pi��,��，数据保证 pi�� 是质数。
输出格式
输出共 n� 行，每组数据输出一个结果，每个结果占一行。
若 ai�� 模 pi�� 的乘法逆元存在，则输出一个整数，表示逆元，否则输出 impossible。
数据范围
1≤n≤1051≤�≤105,
1≤ai,pi≤2∗1091≤��,��≤2∗109
输入样例：
3
4 3
8 5
6 3
输出样例：
1
2
impossible

include [HTML_REMOVED]

using namespace std;
typedef long long LL;

LL qsm(int a, int k, int q)
{
LL res = 1;
while(k)
{
if(k & 1) res = res * (LL)a % q;
k >>= 1;
a = (LL)a * a % q;
}
return res;
}

int main()
{
int n;
cin >> n;
while(n –)
{
int a, p;
scanf(“%d%d”, &a, &p);
if(a % p)printf(“%lld\n”, qsm(a, p - 2, p));
else cout << “impossible” << endl;
}
return 0;
}
组合计数
AcWing 4496. 吃水果（每日一题
n� 个小朋友站成一排，等着吃水果。
一共有 m� 种水果，每种水果的数量都足够多。
现在，要给每个小朋友都发一个水果，要求：在所有小朋友都拿到水果后，恰好有 k� 个小朋友拿到的水果和其左边相邻小朋友拿到的水果不同（最左边的小朋友当然不算数，即最左边的小朋友不包含在 k� 个小朋友内）。
请你计算，一共有多少种不同的分发水果的方案。
输入格式
一行，三个整数 n,m,k�,�,�。
输出格式
一个整数，表示合理的分发水果的方案总数量对 998244353998244353 取模后的结果。
数据范围
前 55 个测试点满足 1≤n,m≤51≤�,�≤5。
所有测试点满足 1≤n,m≤20001≤�,�≤2000，0≤k≤n−10≤�≤�−1。
输入样例1：
3 3 0
输出样例1：
3
输入样例2：
3 2 1
输出样例2：
4

include [HTML_REMOVED]

using namespace std;

const int N = 2010, mod = 998244353;
typedef long long LL;

int c[N][N];

int qsm(int a, int k)
{
int res = 1;
while(k)
{
if(k & 1) res = (LL)res * a % mod;
a = a *(LL)a % mod;
k >>= 1;
}
return res;
}

int main()
{
int n, m, k;
cin >> n >> m >> k;
for(int i = 0; i < N; i )
for(int j = 0; j <= i && j <= k; j )
if(!j) c[i][j] = 1;
else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;

// int res = qsm(m - 1, k);
// cout << res << " res" << endl;
// cout << c[n - 1][k] * m << endl;

printf("%d\n", (LL)c[n - 1][k] * m % mod * qsm(m - 1, k) % mod);
return 0;

}
AcWing 885. 求组合数 I（算法基础课）
给定 n� 组询问，每组询问给定两个整数 a，b�，�，请你输出 Cbamod(109+7)��mod(109+7) 的值。
输入格式
第一行包含整数 n�。
接下来 n� 行，每行包含一组 a� 和 b�。
输出格式
共 n� 行，每行输出一个询问的解。
数据范围
1≤n≤100001≤�≤10000,
1≤b≤a≤20001≤�≤�≤2000
输入样例：
3
3 1
5 3
2 2
输出样例：
3
10
1

include [HTML_REMOVED]

using namespace std;

const int N = 2010, mod = 1e9 + 7;

int c[N][N];

void zuhe()
{
for(int i = 0; i < N; i )
for(int j = 0; j <= i; j )
if(!j) c[i][j] = 1;
else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}

int main()
{
zuhe();
int n;
cin >> n;
while(n –)
{
int a, b;
scanf(“%d%d”, &a, &b);
printf(“%d\n”, c[a][b]);
}
return 0;
}
AcWing 886. 求组合数 II（算法基础课）
给定 n� 组询问，每组询问给定两个整数 a，b�，�，请你输出 Cbamod(109+7)��mod(109+7) 的值。
输入格式
第一行包含整数 n�。
接下来 n� 行，每行包含一组 a� 和 b�。
输出格式
共 n� 行，每行输出一个询问的解。
数据范围
1≤n≤100001≤�≤10000,
1≤b≤a≤1051≤�≤�≤105
输入样例：
3
3 1
5 3
2 2
输出样例：
3
10
1

include [HTML_REMOVED]

using namespace std;

const int N = 100010, mod = 1e9 + 7;
typedef long long LL;

LL fact[N], infact[N];

LL qsm(int a, int k, int p)
{
LL res = 1;
while(k)
{
if(k & 1) res = res * a % mod;
a = (LL)a * a % mod;
k >>= 1;
}
return res;
}

int main()
{
fact[0] = infact[0] = 1;
for(int i = 1; i < N; i ++)
{
fact[i] = fact[i - 1] * i % mod;
infact[i] = infact[i - 1] * qsm(i, mod - 2, mod) % mod;
}
int n;
cin >> n;
while(n –)
{
int a, b;
scanf(“%d%d”, &a, &b);
printf(“%lld\n”, fact[a] * infact[b] % mod * infact[a - b] % mod);
}
return 0;
}博弈论
AcWing 891. Nim游戏（算法基础课
给定 n� 堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。
输入格式
第一行包含整数 n�。
第二行包含 n� 个数字，其中第 i� 个数字表示第 i� 堆石子的数量。
输出格式
如果先手方必胜，则输出 Yes。
否则，输出 No。
数据范围
1≤n≤1051≤�≤105,
1≤每堆石子数≤1091≤每堆石子数≤109
输入样例：
2
2 3
输出样例：
Yes

include [HTML_REMOVED]

using namespace std;

int main()
{
int n;
cin >> n;
int res = 0;
while(n –)
{
int num;
scanf(“%d”, &num);
res ^= num;
}
if(res) cout << “Yes”;
else cout << “No”;
return 0;
}AcWing 893. 集合-Nim游戏（算法基础课）
给定 n� 堆石子以及一个由 k� 个不同正整数构成的数字集合 S�。
现在有两位玩家轮流操作，每次操作可以从任意一堆石子中拿取石子，每次拿取的石子数量必须包含于集合 S�，最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。
输入格式
第一行包含整数 k�，表示数字集合 S� 中数字的个数。
第二行包含 k� 个整数，其中第 i� 个整数表示数字集合 S� 中的第 i� 个数 si��。
第三行包含整数 n�。
第四行包含 n� 个整数，其中第 i� 个整数表示第 i� 堆石子的数量 hiℎ�。
输出格式
如果先手方必胜，则输出 Yes。
否则，输出 No。
数据范围
1≤n,k≤1001≤�,�≤100,
1≤si,hi≤100001≤��,ℎ�≤10000
输入样例：
2
2 5
3
2 4 7
输出样例：
Yes

include [HTML_REMOVED]

using namespace std;

const int N = 110, M = 10010;

int n, k[N], s, h[M];
int f[M];

int sg(int x)
{
if(f[x] != -1) return f[x];
unordered_set[HTML_REMOVED] hash;
for(int i = 0; i < n; i )
{
if(x >= k[i]) hash.insert(sg(x - k[i]));
}
for(int i = 0; ; i )
{
if(!hash.count(i)) return f[x] = i;
}
}

int main()
{
cin >> n;
for(int i = 0; i < n; i )
{
cin >> k[i];
}
memset(f, -1, sizeof f);
int res = 0;
cin >> s;
for(int i = 0; i < s; i )
{
cin >> h[i];
res ^= sg(h[i]);
}
if(res) cout << “Yes” << endl;
else cout << “No” << endl;
return 0;
}
背包DP
AcWing 3382. 整数拆分（每日一题）
一个整数总可以拆分为 22 的幂的和。
例如：77 可以拆分成
7=1+2+4,7=1+2+2+2,7=1+1+1+4,7=1+1+1+2+2,7=1+2+4,7=1+2+2+2,7=1+1+1+4,7=1+1+1+2+2,
7=1+1+1+1+1+2,7=1+1+1+1+1+1+17=1+1+1+1+1+2,7=1+1+1+1+1+1+1
共计 66 种不同拆分方式。
再比如：44 可以拆分成：4=4,4=1+1+1+1,4=2+2,4=1+1+24=4,4=1+1+1+1,4=2+2,4=1+1+2。
用 f(n)�(�) 表示 n� 的不同拆分的种数，例如 f(7)=6�(7)=6。
要求编写程序，读入 n�，输出 f(n)mod109�(�)mod109。
输入格式
一个整数 n�。
输出格式
一个整数，表示 f(n)mod109�(�)mod109。
数据范围
1≤N≤1061≤�≤106
输入样例：
7
输出样例：
6

include [HTML_REMOVED]

using namespace std;

const int N = 1000100, MOD = 1e9;

int f[N];
int v[N], w[N];

int main()
{
int n;
cin >> n;
f[0] = 1;
for(int i = 1; i <= n; i *= 2)
for(int j = i; j <= n; j ++)
{
f[j] = (f[j] + f[j - i]) % MOD;
}
cout << f[n] << endl;
return 0;
}
AcWing 2. 01背包问题（算法基础课）
有 N� 件物品和一个容量是 V� 的背包。每件物品只能使用一次。
第 i� 件物品的体积是 vi��，价值是 wi��。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V�，�，用空格隔开，分别表示物品数量和背包容积。
接下来有 N� 行，每行两个整数 vi,wi��,��，用空格隔开，分别表示第 i� 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤10000<�,�≤1000
0<vi,wi≤10000<��,��≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
8

include [HTML_REMOVED]

using namespace std;

const int N = 1010;

int v[N], w[N];
int f[N];

int main()
{
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i ) cin >> v[i] >> w[i];
for(int i = 1; i <= n; i )
for(int j = m; j >= v[i]; j –)
{
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
cout << f[m] << endl;
return 0;
}
3.完全背包问题
有 N� 种物品和一个容量是 V� 的背包，每种物品都有无限件可用。
第 i� 种物品的体积是 vi��，价值是 wi��。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V�，�，用空格隔开，分别表示物品种数和背包容积。
接下来有 N� 行，每行两个整数 vi,wi��,��，用空格隔开，分别表示第 i� 种物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤10000<�,�≤1000
0<vi,wi≤10000<��,��≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
10

include [HTML_REMOVED]

using namespace std;

const int N = 1010;
int f[N], v[N], w[N];

int main()
{
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i ) cin >> v[i] >> w[i];
for(int i = 1; i <= n; i )
for(int j = v[i]; j <= m; j ++)
{
if(j >= v[i]) f[j] = max(f[j], f[j - v[i]] + w[i]);
}
cout << f[m];
return 0;
}
AcWing 9. 分组背包问题（算法基础课）
有 N� 组物品和一个容量是 V� 的背包。
每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 vij��，价值是 wij��，其中 i� 是组号，j� 是组内编号。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行有两个整数 N，V�，�，用空格隔开，分别表示物品组数和背包容量。
接下来有 N� 组数据：
每组数据第一行有一个整数 Si��，表示第 i� 个物品组的物品数量；
每组数据接下来有 Si�� 行，每行有两个整数 vij,wij��,��，用空格隔开，分别表示第 i� 个物品组的第 j� 个物品的体积和价值；
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000<�,�≤100
0<Si≤1000<��≤100
0<vij,wij≤1000<��,��≤100
输入样例
3 5
2
1 2
2 4
1
3 4
1
4 5
输出样例：
8

include [HTML_REMOVED]

using namespace std;

const int N = 110;

int v[N], w[N];
int f[N];

int main()
{
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i )
{
int s;
cin >> s;
for(int i = 1; i <= s; i )
{
cin >> v[i] >> w[i];
}
for(int j = m; j >= 1; j –)
for(int i = 1; i <= s; i ++)
{
if(j >= v[i]) f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
cout << f[m] << endl;
return 0;
}
AcWing 1214. 波动数列（蓝桥杯辅导课）
观察这个数列：
1 3 0 2 -1 1 -2 …
这个数列中后一项总是比前一项增加2或者减少3，且每一项都为整数。
栋栋对这种数列很好奇，他想知道长度为 n� 和为 s� 而且后一项总是比前一项增加 a� 或者减少 b� 的整数数列可能有多少种呢？
输入格式
共一行，包含四个整数 n,s,a,b�,�,�,�，含义如前面所述。
输出格式
共一行，包含一个整数，表示满足条件的方案数。
由于这个数很大，请输出方案数除以 100000007100000007 的余数。
数据范围
1≤n≤10001≤�≤1000,
−109≤s≤109−109≤�≤109,
1≤a,b≤1061≤�,�≤106
输入样例：
4 10 2 3
输出样例：
2
样例解释
两个满足条件的数列分别是2 4 1 3和7 4 1 -2。

include [HTML_REMOVED]

using namespace std;

const int N = 1010, MOD = 100000007;

int f[N][N];

int mod(int a, int b)
{
return (a % b + b ) % b;
}

int main()
{
int n, s, a, b;
cin >> n >> s >> a >> b;
f[0][0] = 1;
for(int i = 1; i < n; i )
for(int j = 0; j < n; j )
{
f[i][j] = (f[i - 1][mod(j - (n - i) * a, n)] + f[i - 1][mod(j + (n - i) * b, n)]) % MOD;
}
cout << f[n - 1][mod(s, n)] << endl;
return 0;
}
线性DP
AcWing 898. 数字三角形（算法基础课）
给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输入格式
第一行包含整数 n�，表示数字三角形的层数。
接下来 n� 行，每行包含若干整数，其中第 i� 行表示数字三角形第 i� 层包含的整数。
输出格式
输出一个整数，表示最大的路径数字和。
数据范围
1≤n≤5001≤�≤500,
−10000≤三角形中的整数≤10000−10000≤三角形中的整数≤10000
输入样例：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出样例：
30

include [HTML_REMOVED]

using namespace std;

const int N = 510;

int f[N][N];

int main()
{
int n;
cin >> n;
for(int i = 1; i <= n; i )
for(int j = 1; j <= i; j )
{
cin >> f[i][j];
}
for(int i = n - 1; i; i –)
for(int j = 1; j <= i; j ++)
{
f[i][j] += max(f[i + 1][j], f[i + 1][j + 1]);
}
cout << f[1][1] << endl;
return 0;
}
AcWing 895. 最长上升子序列（算法基础课）
给定一个长度为 N� 的数列，求数值严格单调递增的子序列的长度最长是多少。
输入格式
第一行包含整数 N�。
第二行包含 N� 个整数，表示完整序列。
输出格式
输出一个整数，表示最大长度。
数据范围
1≤N≤10001≤�≤1000，
−109≤数列中的数≤109−109≤数列中的数≤109
输入样例：
7
3 1 2 1 8 5 6
输出样例：
4

include [HTML_REMOVED]

using namespace std;

const int N = 1010;

int f[N], a[N];
int n;

int main()
{
cin >> n;
for(int i = 1; i <= n; i )
{
cin >> a[i];
}
for(int i = 1; i <= n; i )
{
f[i] = 1;
for(int j = 1; j < i; j )
{
if(a[j] < a[i]) f[i] = max(f[j] + 1, f[i]);
}
}
int res = 0;
for(int i = 1; i <= n; i )
{
res = max(res, f[i]);
}
cout << res << endl;
return 0;
}
AcWing 897. 最长公共子序列（算法基础课）
给定两个长度分别为 N� 和 M� 的字符串 A� 和 B�，求既是 A� 的子序列又是 B� 的子序列的字符串长度最长是多少。
输入格式
第一行包含两个整数 N� 和 M�。
第二行包含一个长度为 N� 的字符串，表示字符串 A�。
第三行包含一个长度为 M� 的字符串，表示字符串 B�。
字符串均由小写字母构成。
输出格式
输出一个整数，表示最大长度。
数据范围
1≤N,M≤10001≤�,�≤1000
输入样例：
4 5
acbd
abedc
输出样例：
3

include [HTML_REMOVED]

using namespace std;

const int N = 1010;

int f[N][N];
char a[N], b[N];
int n, m;

int main()
{
cin >> n >> m >> a + 1 >> b + 1;
for(int i = 1; i <= n; i )
for(int j = 1; j <= m; j )
{
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
if(a[i] == b[j]) f[i][j] = f[i - 1][j - 1] + 1;
}
cout << f[n][m] << endl;
return 0;
}

1 评论

stay_01 2023-03-31 01:47

给我刷到了，复习题单是我的了😀

App 内打开