A - Difference Max

题目大意

给定四个整数$a,b,c$和$d$。
我们要选择两个整数$x$和$y$（$a\le x\le b$；$c\le y\le d$）。输出最大的$x-y$。

$-100\le a\le b\le 100$
$-100\le c\le d\le 100$

输入格式

$a~~b$
$c~~d$

输出格式

输出最大的$x-y$。

样例

$a$	$b$	$c$	$d$	输出
$0$	$10$	$0$	$10$	$10$
$-100$	$-100$	$100$	$100$	$200$
$-100$	$100$	$-100$	$100$	$200$

分析

如果要$x-y$最大，那么$x$要尽可能大、$y$要尽可能小。因此，$x$取最大值$b$，$y$取最小值$c$。所以，我们直接输出$b-c$即可。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


#include <cstdio>
using namespace std;

int main()
{
	int a, b, c, d;
	scanf("%d%d%d%d", &a, &b, &c, &d);
	printf("%d\n", b - c);
	return 0;
}

B - Round Down

题目大意

给定一个数$X$，求$\lfloor X\rfloor$。

$0\le X\le 10^{100}$

输入格式

$X$

输出格式

输出$\lfloor X\rfloor$。

样例

$X$	输出
$5.90$	$5$
$0$	$0$
$84939825309432908832902189.9092309409809091329$	$84939825309432908832902189$

分析

只需找到小数点并将其及后面的数位删去再输出即可。例如：$5\sout{.90}$

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


#include <cstdio>
using namespace std;

int main()
{
	char c;
	while((c = getchar()) != '\n')
	{
		if(c == '.') return 0;
		putchar(c);
	}
	return 0;
}

C - Doubled

题目大意

$1$~$N$之间有多少个数是另一个正整数重复两遍得来的？

$1\le N < 10^{12}$

输入格式

$N$

输出格式

输出答案。

样例

$N$	输出
$33$	$3$
$1333$	$13$
$10000000$	$999$

分析

这道题说白了就是要找到最大的$X$，使得$X$重复两遍不超过$N$，并输出$X$。我们可以使用二分法求出最大的$X$。
注意：这里的二分右边界最好设置为$\sqrt N$，否则一不小心就会溢出！

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


#include <cstdio>
#include <cmath>
using namespace std;

typedef long long LL;

inline bool check(const LL& x, const LL& n)
{
	LL p = 1LL;
	while(p <= x) p *= 10LL;
	return x * p + x <= n;
}

int main()
{
	LL n;
	scanf("%lld", &n);
	LL l = 0LL, r = sqrt(n);
	while(l < r)
	{
		LL mid = l + r + 1LL >> 1LL;
		if(check(mid, n)) l = mid;
		else r = mid - 1;
	}
	printf("%lld\n", l);
	return 0;
}

D - Hanjo

题目大意

有一个$H\times W$的地板，请你在地板上铺砖。
有两种地砖：$a$和$b$。$a$地砖有$A$个，是$2\times1$的可旋转长方形。$b$地砖有$B$个，是$1\times1$的正方形。问要将这个地板正好铺满，总共有多少种铺法？

$1\le H,W,HW\le 16$
$0\le A,B$
$2A+B=HW$

输入格式

$H~W~A~B$

输出格式

输出答案。

样例

$H$	$W$	$A$	$B$	输出
$2$	$2$	$1$	$2$	$4$
$3$	$3$	$4$	$1$	$18$
$4$	$4$	$8$	$0$	$36$

分析

由于数据范围较小，我们可以用暴力搜索解决这道题。注意，这里搜索时为了避免重复计算，我们每次递归只尝试一个位置，这样还能有效加速。具体请看代码。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57


#include <cstdio>
#define maxn 20
using namespace std;

bool mat[maxn][maxn];
int h, w, a, b, ans;

inline bool valid(int x, int y)
{
	return !mat[x][y] && x >= 0 && x < h && y >= 0 && y < w;
}

void dfs(int i, int j, int usedA, int usedB)
{
	if((usedA << 1) + usedB == h * w)
	{
		ans ++;
		return;
	}
	if(i == h) return;
	int ni, nj;
	if(j == w - 1) ni = i + 1, nj = 0;
	else ni = i, nj = j + 1;
	if(mat[i][j])
	{
		dfs(ni, nj, usedA, usedB);
		return;
	}
	mat[i][j] = true;
	// Rectangle (A)
	if(usedA < a)
	{
		if(valid(i, j + 1))
		{
			mat[i][j + 1] = true;
			dfs(ni, nj, usedA + 1, usedB);
			mat[i][j + 1] = false;
		}
		if(valid(i + 1, j))
		{
			mat[i + 1][j] = true;
			dfs(ni, nj, usedA + 1, usedB);
			mat[i + 1][j] = false;
		}
	}
	// Square (B)
	if(usedB < b) dfs(ni, nj, usedA, usedB + 1);
	mat[i][j] = false;
}

int main()
{
	scanf("%d%d%d%d", &h, &w, &a, &b);
	dfs(0, 0, 0, 0);
	printf("%d\n", ans);
	return 0;
}

E - Filters

题目大意

给定三个整数序列$A = (a_1, a_2, \dots, a_N)$、$T = (t_1, t_2, \dots, t_N)$和$X = (x_1, x_2, \dots, x_Q)$。
我们如下定义$N$个函数$f_1(x), f_2(x), \dots, f_N(x)$：
$f_i(x) = \begin{cases} x + a_i & (t_i = 1)\\ \max(x, a_i) & (t_i = 2)\\ \min(x, a_i) & (t_i = 3)\\ \end{cases}$
对于每个$i = 1, 2, \dots, Q$，求$f_N( \dots f_2(f_1(x_i)) \dots )$。

$1 \le N,Q \le 2 \times 10^5$
$|a_i|,|x_i|\le 10^9$
$1 \le t_i \le 3$

输入格式

$N$
$a_1~t_1$
$a_2~t_2$
$\vdots$
$a_N~t_N$
$Q$
$x_1~x_2~\dotsx x_q$

输出格式

输出$Q$行。第$i$行应该包含$f_N( \dots f_2(f_1(x_i)) \dots )$。

样例

样例输入

1
2
3
4
5
6


3
-10 2
10 1
10 3
5
-15 -10 -5 0 5

样例输出

在这里，$f_1(x) = \max(x, -10), f_2(x) = x + 10, f_3(x) = \min(x, 10)$，则有：

$f_3(f_2(f_1(-15))) = 0$
$f_3(f_2(f_1(-10))) = 0$
$f_3(f_2(f_1(-5))) = 5$
$f_3(f_2(f_1(0))) = 10$
$f_3(f_2(f_1(5))) = 10$

分析

（参考AtCoder官方题解）
很容易想到，我们可以直接照做，即分别计算每个$f_N( \dots f_2(f_1(x_i)) \dots )$。但是，这样做的时间复杂度是$\mathcal O(NQ)$，所以肯定会TLE。
我们考虑它们的复合函数$F(x)=f_N( \dots f_2(f_1(x_i)) \dots )$在图上怎么表示。

当$t_i=1$，$f_i$是将图整体平移的操作；
当$t_i=2$，$f_i$是将图的最小值设为$a_i$；
当$t_i=3$，$f_i$是将图的最大值设为$a_i$。

所以，我们可以得到下图：
F(x)和x的关系

或者说，存在三个数$a,b,c$使得$F(x)=\min(c,\max(b,x+a))$。
关于$a,b,c$的具体计算请看代码。

代码

注意：这里的代码中的$\infty$（INF）一定不能直接设为long long的最大值，否则会溢出！

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


#include <cstdio>
#include <algorithm>
#include <climits>
using namespace std;

typedef long long LL;
const LL INF = LLONG_MAX >> 1LL;

int main()
{
	LL l = -INF, r = INF, add = 0LL;
	int n, q;
	scanf("%d", &n);
	while(n--)
	{
		LL a, t;
		scanf("%lld%lld", &a, &t);
		if(t == 1) l += a, r += a, add += a;
		else if(t == 2) l = max(l, a), r = max(r, a);
		else l = min(l, a), r = min(r, a);
	}
	scanf("%d", &q);
	while(q--)
	{
		LL x;
		scanf("%lld", &x);
		printf("%lld\n", clamp(x + add, l, r));
	}
	return 0;
}