前言：第一次打\(CF\)，因为经验不足以及英语水平很烂，即便在机房大佬的带领下也是花了好久才读懂题目。。\(A\)题直到\(11\)分钟才\(A\)，题目一共才做了\(4\)题，太菜了。。
A. Heist
Description
有\(n\)个正整数，设最小的数为\(minn\)，最大的数为\(maxn\)，求\(minn\sim maxn\)的正整数连续区间里有多少数不属于这\(n\)个正整数。
Solution
显然答案就是\(maxn-minn-n+1\)
#include<cstdio>
using namespace std;
inline int re()
{
int x = 0;
char c = getchar();
bool p = 0;
for (; c < '0' || c > '9'; c = getchar())
p |= c == '-';
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - '0';
return p ? -x : x;
}
inline int maxn(int x, int y)
{
return x > y ? x : y;
}
inline int minn(int x, int y)
{
return x < y ? x : y;
}
int main()
{
int i, n, mi = 1e9, ma = 0, x;
n = re();
for (i = 1; i <= n; i++)
{
x = re();
mi = minn(mi, x);
ma = maxn(ma, x);
}
printf("%d", ma - mi + 1 - n);
return 0;
}
B. Buying a TV Set
Description
给出\(4\)个正整数\(a,b,x,y\)，求满足\(\dfrac{w}{h}=\dfrac{x}{y},1\leqslant w\leqslant a,1\leqslant h\leqslant b\)的二元组\((w,h)\)有几组。
Solution
对\(x,y\)进行约分，而答案显然是\(\min\{ \left\lfloor\dfrac{a}{x}\right\rfloor , \left\lfloor\dfrac{b}{y}\right\rfloor\}\)
#include<cstdio>
using namespace std;
typedef long long ll;
inline ll re()
{
ll x = 0;
char c = getchar();
bool p = 0;
for (; c < '0' || c > '9'; c = getchar())
p |= c == '-';
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - '0';
return p ? -x : x;
}
inline ll minn(ll x, ll y)
{
return x < y ? x : y;
}
ll gcd(ll x, ll y)
{
if (!y)
return x;
return gcd(y, x % y);
}
int main()
{
ll a, b, x, y, g;
a = re();
b = re();
x = re();
y = re();
g = gcd(x, y);
x /= g;
y /= g;
printf("%I64d", minn(a / x, b / y));
return 0;
}
C. Coffee Break
Description
一天有\(m\)个时间点，现有\(n\)个时间点是\(Monocarp\)想喝咖啡的时间点（保证不重复），但他的老板不让他一直喝咖啡，所以要求他每次喝咖啡的时间点必须和上一次喝咖啡的时间点间隔\(d\)个时间点。
试问\(Monocarp\)至少需要几天才能在这\(n\)个时间点中的每一个点都喝过咖啡。
Solution
贪心+二分查找
对时间点从小到大排序，枚举每个时间点。
设枚举到第\(i\)个时间点\(a_i\)，用二分查找第一个满足\(\geqslant a_i + d +1\)且没有喝过咖啡的时间点，然后继续查找，直到没有满足条件的时间点为止，显然这些点可以在同一天喝咖啡。
最后继续枚举时间点并查找，直到\(n\)个点全喝过咖啡。
这里的二分查找使用\(C++\ STL\ Set\)更方便。
#include<cstdio>
#include<set>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 2e5 + 10;
struct dd {
int id, x;
bool operator < (const dd &o) const
{
return x < o.x;
}
};
dd a[N], X;
int bl[N];
set<dd>se;
inline int re()
{
int x = 0;
char c = getchar();
bool p = 0;
for (; c < '0' || c > '9'; c = getchar())
p |= c == '-';
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - '0';
return p ? -x : x;
}
int main()
{
int i, n, m, d, k = 0, s;
n = re();
m = re();
d = re();
for (i = 1; i <= n; i++)
{
a[i].x = re();
a[i].id = i;
se.insert(a[i]);
}
sort(a + 1, a + n + 1);
for (i = 1; i <= n; i++)
if (!bl[a[i].id])
{
bl[a[i].id] = ++k;
X.x = a[i].x;
s = 1;//这个s可以忽略，因为题目保证ai小于m，当时比赛时脑抽没看到就打上了，实际上这s没有什么用。
se.erase(X);
X.x = a[i].x + d + 1;
set<dd>::iterator it = se.lower_bound(X);
while (it != se.end() && s < m)
{
s++;
bl[it->id] = k;
X.x = it->x + d + 1;
se.erase(it);
it = se.lower_bound(X);
if (it == se.end())
break;
}
}
printf("%d\n", k);
for (i = 1; i <= n; i++)
printf("%d ", bl[i]);
return 0;
}
D. Glider
Description
一架滑翔机在一个平面直角坐标系上飞行，坐标为\((x,h)\)，每次滑翔一秒会使得\(x+1,h-1\)，当\(h=0\)时滑翔机已经落地，无法继续滑翔。
而在飞行过程中会有\(n\)个上升气流（不会重叠，是一个关于\(x\)的区间），当滑翔机在上升气流中飞行时，只会使得\(x+1\)，而\(h\)不变。
现告诉你这\(n\)个上升气流两端的坐标和滑翔机初始的高度\(h\)，\(x\)由你选择，求滑翔机最远能滑翔多少距离。
（下图为原题中所附图）
如果从\(1\)开始滑翔，最远到\(10\)，而从\(2\)开始滑翔，最远到\(12\)。
Solution
官方正解是二分+前缀和。
而我机房里有大佬写了倍增的做法（传送门）。
至于我写的就更加奇葩。。类似单调队列的维护+贪心，不过复杂度比上述两种方法都要优，为\(O(n)\)。
这题有个很明显的贪心策略，从上升气流的左端开始飞行更优。
所以我用一个类似单调队列的东西来维护两个参数\(k,s\)，\(k\)表示从当前队首的上升气流左端开始滑翔到队尾需要消耗多少高度，\(s\)表示从当前队首的上升气流左端开始滑翔到队尾飞行的总距离。
若\(k\)加上到下一个上升气流的距离已经大于等于\(m\)了，就说明无法飞到下一个气流，将队首弹出，同时维护\(s,k\)的值，并对新的队首继续判断；若能到达则直接将下一个气流加入队列，同时维护\(s,k\)的值。
而在维护过程中不断对\(s+m-k\)取\(\max\)即可。
#include<cstdio>
#include<set>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 2e5 + 10;
struct dd{
int x, y, z;
};
dd a[N];
int q[N];
inline int re()
{
int x = 0;
char c = getchar();
bool p = 0;
for (; c < '0' || c > '9'; c = getchar())
p |= c == '-';
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - '0';
return p ? -x : x;
}
inline int maxn(int x, int y)
{
return x > y ? x : y;
}
int main()
{
int i, n, m, k = 0, s = 0, head = 1, tail = 1, ma;
n = re();
m = re();
for (i = 1; i <= n; i++)
{
a[i].x = re();
a[i].y = re();
a[i].z = a[i].y - a[i].x;
}
q[1] = 1;
ma = s = a[1].z;
for (i = 2; i <= n; i++)
{
while (head < tail && k + a[i].x - a[i - 1].y >= m)
{
ma = maxn(ma, s + m - k);
k -= a[q[head] + 1].x - a[q[head]].y;
s -= a[q[head] + 1].x - a[q[head]].x;
head++;
}
if (k + a[i].x - a[i - 1].y >= m)
{
ma = maxn(s + m - k, ma);
s = a[i].z;
ma = maxn(s, ma);
q[++tail] = i;
head++;
continue;
}
k += a[i].x - a[i - 1].y;
s += a[i].y - a[i - 1].y;
ma = maxn(ma, s);
q[++tail] = i;
}
ma = maxn(ma, s + m - k);
printf("%d", ma);
return 0;
}