AtCoder Beginner Contest 196 A~E题解

文章目录

A - Difference Max

题目大意

给定四个整数 a , b , c a,b,c a,b,c和 d d d。
我们要选择两个整数 x x x和 y y y( a ≤ x ≤ b a\le x\le b a≤x≤b; c ≤ y ≤ d c\le y\le d c≤y≤d)。输出最大的 x − y x-y x−y。

− 100 ≤ a ≤ b ≤ 100 -100\le a\le b\le 100 −100≤a≤b≤100
− 100 ≤ c ≤ d ≤ 100 -100\le c\le d\le 100 −100≤c≤d≤100

输入格式

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

输出格式

输出最大的 x − y x-y x−y。

样例

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

分析

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

代码

#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 X X,求 ⌊ X ⌋ \lfloor X\rfloor ⌊X⌋。

0 ≤ X ≤ 1 0 100 0\le X\le 10^{100} 0≤X≤10100

输入格式

X X X

输出格式

输出 ⌊ X ⌋ \lfloor X\rfloor ⌊X⌋。

样例

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

分析

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

代码

#include <cstdio>
using namespace std;

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

C - Doubled

题目大意

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

1 ≤ N < 1 0 12 1\le N<10^{12} 1≤N<1012

输入格式

N N N

输出格式

输出答案。

样例

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

分析

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

代码

#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 × W H\times W H×W的地板,请你在地板上铺砖。
有两种地砖: a a a和 b b b。 a a a地砖有 A A A个,是 2 × 1 2\times1 2×1的可旋转长方形。 b b b地砖有 B B B个,是 1 × 1 1\times1 1×1的正方形。问要将这个地板正好铺满,总共有多少种铺法?

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

输入格式

H   W   A   B H~W~A~B H W A B

输出格式

输出答案。

样例

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

分析

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

代码

#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 , … , a N ) A = (a_1, a_2, \dots, a_N) A=(a1​,a2​,…,aN​)、 T = ( t 1 , t 2 , … , t N ) T = (t_1, t_2, \dots, t_N) T=(t1​,t2​,…,tN​)和 X = ( x 1 , x 2 , … , x Q ) X = (x_1, x_2, \dots, x_Q) X=(x1​,x2​,…,xQ​)。
我们如下定义 N N N个函数 f 1 ( x ) , f 2 ( x ) , … , f N ( x ) f_1(x), f_2(x), \dots, f_N(x) f1​(x),f2​(x),…,fN​(x):
f i ( x ) = { x + a i ( t i = 1 ) max ⁡ ( x , a i ) ( t i = 2 ) min ⁡ ( x , a i ) ( t i = 3 ) 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} fi​(x)=⎩⎪⎨⎪⎧​x+ai​max(x,ai​)min(x,ai​)​(ti​=1)(ti​=2)(ti​=3)​
对于每个 i = 1 , 2 , … , Q i = 1, 2, \dots, Q i=1,2,…,Q,求 f N ( … f 2 ( f 1 ( x i ) ) …   ) f_N( \dots f_2(f_1(x_i)) \dots ) fN​(…f2​(f1​(xi​))…)。

1 ≤ N , Q ≤ 2 × 1 0 5 1 \le N,Q \le 2 \times 10^5 1≤N,Q≤2×105
∣ a i ∣ , ∣ x i ∣ ≤ 1 0 9 |a_i|,|x_i|\le 10^9 ∣ai​∣,∣xi​∣≤109
1 ≤ t i ≤ 3 1 \le t_i \le 3 1≤ti​≤3

输入格式

N N N
a 1   t 1 a_1~t_1 a1​ t1​
a 2   t 2 a_2~t_2 a2​ t2​
⋮ \vdots ⋮
a N   t N a_N~t_N aN​ tN​
Q Q Q
x 1   x 2   …   x q x_1~x_2~\dotsx x_q x1​ x2​ …xq​

输出格式

输出 Q Q Q行。第 i i i行应该包含 f N ( … f 2 ( f 1 ( x i ) ) …   ) f_N( \dots f_2(f_1(x_i)) \dots ) fN​(…f2​(f1​(xi​))…)。

样例

样例输入

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

样例输出

0
0
5
10
10

在这里, f 1 ( x ) = max ⁡ ( x , − 10 ) , f 2 ( x ) = x + 10 , f 3 ( x ) = min ⁡ ( x , 10 ) f_1(x) = \max(x, -10), f_2(x) = x + 10, f_3(x) = \min(x, 10) f1​(x)=max(x,−10),f2​(x)=x+10,f3​(x)=min(x,10),则有:

  • f 3 ( f 2 ( f 1 ( − 15 ) ) ) = 0 f_3(f_2(f_1(-15))) = 0 f3​(f2​(f1​(−15)))=0
  • f 3 ( f 2 ( f 1 ( − 10 ) ) ) = 0 f_3(f_2(f_1(-10))) = 0 f3​(f2​(f1​(−10)))=0
  • f 3 ( f 2 ( f 1 ( − 5 ) ) ) = 5 f_3(f_2(f_1(-5))) = 5 f3​(f2​(f1​(−5)))=5
  • f 3 ( f 2 ( f 1 ( 0 ) ) ) = 10 f_3(f_2(f_1(0))) = 10 f3​(f2​(f1​(0)))=10
  • f 3 ( f 2 ( f 1 ( 5 ) ) ) = 10 f_3(f_2(f_1(5))) = 10 f3​(f2​(f1​(5)))=10

分析

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

  • 当 t i = 1 t_i=1 ti​=1, f i f_i fi​是将图整体平移的操作;
  • 当 t i = 2 t_i=2 ti​=2, f i f_i fi​是将图的最小值设为 a i a_i ai​;
  • 当 t i = 3 t_i=3 ti​=3, f i f_i fi​是将图的最大值设为 a i a_i ai​。

所以,我们可以得到下图:
AtCoder Beginner Contest 196 A~E题解
或者说,存在三个数 a , b , c a,b,c a,b,c使得 F ( x ) = min ⁡ ( c , max ⁡ ( b , x + a ) ) F(x)=\min(c,\max(b,x+a)) F(x)=min(c,max(b,x+a))。
关于 a , b , c a,b,c a,b,c的具体计算请看代码。

代码

注意:这里的代码中的 ∞ \infty ∞(INF)一定不能直接设为long long的最大值,否则会溢出!

#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;
}
上一篇:AcWing 196. 质数距离


下一篇:Linux 命令ps aux命令解析