- 3745. 牛的学术圈 I（双指针）
- 1683. 困牛放牧（思维题+分类讨论）
- 1749. 阻挡广告牌 II（模拟）
- 1921. 重新排列奶牛（好题，数组循环排序/1到N排列，环图模型）
- 1912. 里程表（逆向思维枚举）
由于对计算机科学的热爱，以及有朝一日成为 「Bessie 博士」的诱惑，奶牛 Bessie 开始攻读计算机科学博士学位。
经过一段时间的学术研究，她已经发表了
Bessie 听说学术成就可以用
例如，如果一名研究员有
为了提升她的
由于页数限制，她至多可以在这篇综述中引用
请帮助 Bessie 求出在写完这篇综述后她可以达到的最大
注意 Bessie 的导师可能会告知她纯粹为了提升
输入的第一行包含
第二行包含
输出写完综述后 Bessie 可以达到的最大
-
$1 \le N \le 10^5$ , -
$0 \le c_i \le 10^5$ , $0 \le L \le 10^5$
4 0
1 100 2 3
2
Bessie 不能引用任何她曾经写过的论文。上文中提到，$(1,100,2,3)$ 的
4 1
1 100 2 3
3
如果 Bessie 引用她的第三篇论文，引用数会变为
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, L;
int q[N];
int main()
{
scanf("%d%d", &n, &L);
for (int i = 1; i <= n; ++ i) scanf("%d", &q[i]);
sort(q + 1, q + n + 1, greater<int>());
int res = 0;
for (int h = 1, j = n; h <= n; ++ h)
{
// 找到最引用量最小的，但大于等于 h 的文献
while (j && q[j] < h) -- j;
// 如果此时第 h 小的文献引用量大于等于 h - 1
// 并且需要额外引用的文献数量小于等于 L
if (q[h] >= h - 1 && h - j <= L)
res = h;
}
printf("%d\n", res);
}Farmer John 的三头获奖奶牛 Bessie、Elsie 和 Mildred，总是会迷路走到农场上遥远的地方去！
他需要你帮助将她们一起赶回来。
农场的草地大体是一块狭长的区域——我们可以将其想象成一条数轴，奶牛可以占据数轴上的任意整数位置。
这
不幸的是，奶牛们现在很困，Farmer John 要让她们集中精力听从命令移动并不容易。
任意时刻，他只能使得一头处在“端点”（在所有奶牛中位置最小或最大）位置的奶牛移动。
当他移动奶牛时，他可以命令她走到任意一个未被占用的整数位置，只要在新的位置上她不再是一个端点。
可以看到随着时间的推移，这样的移动可以使奶牛们趋向越来越近。
请求出使得奶牛们集中到相邻位置所进行的移动次数的最小和最大可能值。
输入包含一行，包括三个空格分隔的整数，为 Bessie、Elsie 和 Mildred 的位置。
输出的第一行包含 Farmer John 需要将奶牛们聚集起来所需进行的最小移动次数。
第二行包含他将奶牛聚集起来能够进行的最大移动次数。
每个位置均为一个范围
4 7 9
1
2
最小移动次数为
最大移动次数为
// 分类讨论，最小值的时候，如果三个挨着就是 0
// 如果两头牛差一个就是 1 ，否则是 2
// 最大值时候，一定有方法可以构造 max(x[2] - x[1] - 1, x[1] - x[0] - 1);
// （让两头牛贴着走）
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
int x[3];
for (int i = 0; i < 3; ++ i) cin >> x[i];
if (x[2] - x[0] == 2) puts("0");
else if (x[2] - x[1] == 2 || x[1] - x[0] == 2) puts("1");
else puts("2");
cout << max(x[2] - x[1] - 1, x[1] - x[0] - 1);
return 0;
}奶牛贝茜曾经从农场中向外看去，可以看到两个刊登着美味的牛饲料广告的广告牌，这令她非常满意。
不幸的是，其中一个广告牌最近已更新，现在刊登着广告“农民拉里的割草机”。
但是贝茜可不喜欢割草机，这些割草机只会把她爱吃的草割的一干二净。
幸运的是，剩下的牛饲料广告牌位于割草机广告牌的前面，有可能将其遮挡住。
贝茜希望这个讨厌的割草机广告牌能够完全从自己的视线中消失，并为此制定了一个冒险计划。
她计划从谷仓里偷一个大的矩形防水布，并在深夜偷偷溜走，用它覆盖割草机广告牌的其余部分，使得她能完全看不到割草机广告牌。
给定两个广告牌的位置，请帮助贝茜计算她所需要的防水布的最小面积。
由于谷仓中只有矩形的防水布，因此贝茜发现为了将割草机广告牌完全遮盖，所需的防水布面积可能会大于割草机广告牌的裸露面积，如下例所示。
防水布在放置时，其边必须与广告牌的边平行，即不能倾斜放置。
第一行包含四个整数
第二行按照如上形式，包含四个整数，表示牛饲料广告牌的左下角和右上角坐标。
牛饲料广告牌可能完全遮盖了割草机广告牌，或部分遮盖了割草机广告牌，也可能完全没有遮盖割草机广告牌。
输出用来遮盖割草机广告牌的防水布的最小面积。
2 1 7 4
5 -1 10 3
15
虽然牛饲料广告牌遮盖住了割草机广告牌的右下角的一部分，但这并没有起到作用。
想要完全遮盖割草机广告牌，仍然需要一块和它尺寸相同的防水布。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2010, B = N / 2;
bool st[N][N];
int main()
{
int a, b, c, d;
cin >> a >> b >> c >> d;
a += B, b += B, c += B, d += B;
for (int i = a; i < c; i ++ )
for (int j = b; j < d; j ++ )
st[i][j] = true;
cin >> a >> b >> c >> d;
a += B, b += B, c += B, d += B;
for (int i = a; i < c; i ++ )
for (int j = b; j < d; j ++ )
st[i][j] = false;
a = b = N, c = d = 0; // a 是小矩形中的最上边， b 左边， c 下边， d 右边
for (int i = 0; i < N; i ++ )
for (int j = 0; j < N; j ++ )
if (st[i][j])
{
a = min(a, i), c = max(c, i);
b = min(b, j), d = max(d, j);
}
int w = max(0, c - a + 1), h = max(0, d - b + 1);
cout << w * h << endl;
return 0;
}农夫约翰的
它们的排序可以由一个数组
约翰希望将它们重新排列为一个不同的顺序。
新顺序用数组
假设奶牛开始时的顺序为：
A = 5 1 4 2 3
并假设约翰希望它们重新排列为：
B = 2 5 3 1 4
为了从
所谓循环移位，是指挑选排列中的若干头奶牛分在一组，组中奶牛进行循环移动位置，即第一头奶牛移动至第二头奶牛的位置，第二头奶牛移动至第三头奶牛的位置，...，最后一头奶牛移动至第一头奶牛的位置。
如上例中，将
每头奶牛都恰好参与一组循环移位，除非其在
请计算奶牛们完成重新排列，共需多少组循环移位，最长的一组循环移位的长度是多少。
第一行包含整数
接下来
再接下来
输出循环移位的组数，以及最长的一组循环移位的长度。
如果不存在循环移位，则第二个数输出
-
$1 \le N \le 100$ , $1 \le A(i),B(i) \le N$
5
5
1
4
2
3
2
5
3
1
4
2 3
一定存在循环移位，或大或小。换句话说，循环移位一定可以构造出答案。因此暴力找循环移位就行了。时间复杂度O(n)。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n, a[N], b[N], pos[N]; // pos[x] = i 即 x 在 b 数组哪里
int res, st[N]; // st[i] i 是否已经进入了一个循环数组
int cycle(int sta)
{
int k = sta, cnt = 0;
do
{
st[k] = 1;
k = pos[a[k]];
++ cnt;
}
while (k != sta);
return cnt;
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; ++ i) scanf("%d", &a[i]);
for (int i = 0; i < n; ++ i)
{
scanf("%d", &b[i]);
pos[b[i]] = i;
}
int maxv = -1;
for (int i = 0; i < n; ++ i)
{
if (a[i] == b[i]) continue;
if (st[i]) continue;
maxv = max(maxv, cycle(i));
++ res;
}
printf("%d %d", res, maxv);
}下面是 y 总对环图模型讲解。
因为每个数的值是 1 到 N ，因此每个数可以视为一个点，每个点可以视为有一个入度一个出度，这样就构成了环图模型。
环图模型：对于有向图，则是每个点都出度为1、入度为1；对于无向图，则是每个点的度都为2。 环图则是一个图由若干环构成的。
因此本题可以用并查集来做。以下是 y 总代码。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int n;
int a[N], b[N], p[N], s[N];
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
for (int i = 1; i <= n; i ++ )
{
int x;
cin >> x;
// b[x] = i 表示 x 应该 i 位置
b[x] = i;
}
for (int i = 1; i <= n; i ++ ) p[i] = i, s[i] = 1;
for (int i = 1; i <= n; i ++ )
{
int x = a[i], y = a[b[x]];
if (find(x) != find(y))
{
s[find(y)] += s[find(x)];
p[find(x)] = find(y);
}
}
int cnt = 0, mx = 0;
for (int i = 1; i <= n; i ++ )
if (p[i] == i && s[i] > 1)
{
cnt ++ ;
mx = max(mx, s[i]);
}
if (!cnt) mx = -1;
cout << cnt << ' ' << mx << endl;
return 0;
}约翰的奶牛正在公路上旅行。
他们汽车上的里程表显示的是整数里程值。
旅途开始时里程表显示的里程值为
每当里程表显示“有趣的”数字（包括开始和结束时显示的数字）时，奶牛们就会发出愉快的叫声。
如果一个数除去前导零以外的所有数字中，除了一个数字不同以外，其他所有数字都是相同的，那么这个数就是“有趣的”。
例如，$33323$ 和
请帮助约翰计算奶牛们在旅途中发出叫声的次数。
共一行，包含两个整数
输出奶牛们在旅途中发出叫声的次数。
110 133
13
直接枚举每一个数并且判读会超时，可以换个思路枚举： 一共数字可以有 1 到 17 位，数字组合一共只有 10 × 9 种，特殊数字可以在 17 位种任挑一个，因此符合条件的数字一共只有 2 万个左右，因此我们可以求出所有数字，然后看哪些在范围里。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
int main()
{
LL x, y;
cin >> x >> y;
int res = 0;
for (int i = 3; i <= 17; i ++ )
for (int j = 0; j < 10; j ++ )
for (int k = 0; k < 10; k ++ )
if (k != j)
for (int u = 0; u < i; u ++ )
{
string str(i, '0' + j);
str[u] = '0' + k;
if (str[0] != '0')
{
LL v = stoll(str);
if (v >= x && v <= y)
res ++ ;
}
}
cout << res << endl;
return 0;
}