前言：第一次打(CF)，因为经验不足以及英语水平很烂，即便在机房大佬的带领下也是花了好久才读懂题目。。(A)题直到(11)分钟才(A)，题目一共才做了(4)题，太菜了。。
A. Heist
Description
有(n)个正整数，设最小的数为(minn)，最大的数为(maxn)，求(minnsim 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},1leqslant wleqslant a,1leqslant hleqslant b)的二元组((w,h))有几组。
Solution
对(x,y)进行约分，而答案显然是(min{ leftlfloordfrac{a}{x} ight floor , leftlfloordfrac{b}{y} ight floor})
#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
", 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;
}