ABC 257 A-C 题解

ABC 257 A-C题解

[A - A to Z String 2](https://atcoder.jp/contests/abc257/tasks/abc257_a)
- 代码：
- 题意疏通：
- 输入格式：
- 输出格式：
- 思路点拨：
[B - 1D Pawn](https://atcoder.jp/contests/abc257/tasks/abc257_b)
- 代码：
- 题意疏通（稍有改动）：
- 输入格式：
- 输出格式：
- 思路点拨：
[C - Robot Takahashi](https://atcoder.jp/contests/abc257/tasks/abc257_c)
- 代码：
- 题意疏通：
- 输入格式：
- 输出格式：
- 思路点拨：
尾声：

题解来喽！！！

A - A to Z String 2 代码：

#include 
using namespace std;

int n, k;

int main()
{
	cin >> n >> k;
	for(char i = 'A'; i <= 'Z'; i++)
	{
		k -= n;
		if(k <= 0)
		{
			cout << i;
			return 0;
		}
	}
	return 0;
}

题意疏通：

很水。
字符串由N个A、N个B … N个Z组成，问其第K个字母是什么

输入格式：

N K

输出格式：

ans

思路点拨：

我用的是数学方法，即：

依次将N减去当前字母（A~Z）的个数，若N ≤ 0 则说明答案为当前字母，输出之。

方法二：

直接构造该字符串，并输出对应字母。（因为复杂度较小，所以不会TLE）

B - 1D Pawn 代码：

#include 
#include 
using namespace std;

int n, k, q, pic[210];
map mp;

int main()
{
	cin >> n >> k >> q;
	for(int i = 1; i <= k; i++) 
	{
		cin >> pic[i];
		mp[pic[i]] = true;
	}
	while(q--)
	{
		int l;
		cin >> l;
		if(pic[l] == n) continue;
		if(mp[pic[l] + 1]) continue;
		pic[l]++;
		mp[pic[l] - 1] = false;
		mp[pic[l]] = true;
	}
	for(int i = 1; i <= k; i++) cout << pic[i] << " ";
	return 0;
}

题意疏通（稍有改动）：

有一个长度为N的列表，其中有K个（A 1 _1 1, A 2 _2 2…A K _K K）值为1，其余为0。
执行如下Q次(L 1 _1 1, L 2 _2 2…L Q _Q Q)操作：

输入L i _i i
若第L i _i i个1的下标为N：continue
否则：
- 若ls[L i _i i + 1] 为 0则：
- - ls[L i _i i + 1] 设为1，且 ls[L i _i i] 设为 0
- 否则：continue

输入格式：

N K Q
A 1 _1 1, A 2 _2 2…A K _K K
L 1 _1 1, L 2 _2 2…L Q _Q Q

输出格式：

所有值为1的格子的下表（从小到大）

思路点拨：

没啥好说的，大模拟即可。

C - Robot Takahashi 代码：

#include 
#include 
#include 
using namespace std;

const int N = 200010;

void setmax(int& x, int y)
{
	if(x < y) x = y;
}

vector a, c; 
int w[N]; char s[N];

int f(int x)
{
	int ax = a.end() - lower_bound(a.begin(), a.end(), x);
	int cx = lower_bound(c.begin(), c.end(), x) - c.begin();
	return ax + cx;
}

int main()
{
	int n;
	cin >> n >> s;
	for(int i=0; i
		cin >> w[i];
		if(s[i] == '0') c.push_back(w[i]);
		else a.push_back(w[i]);
	}
	sort(a.begin(), a.end());
	sort(c.begin(), c.end());
	
	int ans = 0;
	for(int i=0; i
		int c = w[i];
		setmax(ans, f(c));
		setmax(ans, f(c + 1));
	}
	cout << ans;
	return 0;
}

题意疏通：

有N个人，他们被分为小孩（0）和大人（1）第 i i i个人体重为W i _i i。
高桥认为体重 Q e s : Qes: Qes: 高桥最多将多少个人判断正确？

输入格式：

N
S（有0 和 1组成）
W 1 _1 1, W 2 _2 2 … W N _N N

输出格式：

一个整数，表示高桥最多判断正确的人数。

思路点拨：

输入时就根据S将人分成小孩和大人两个vector存储。
根据体重将其sort
可以发现：所有X必定等于一个体重或者它加1。
暴力枚举上述范围，并加以计算。
计算过程如下：

通过二分算法，找到符合条件的儿童与成人的个数
取其较大值
更新ans

最后，输出ans

尾声：

P . S . P.S. P.S. 感谢GoodCoder666提醒C题代码的错误（~~我是抄的他的~~）

写完了。
我决定了！你们没有看见我昨天写的内容！！！我决定了！你们没有看见我昨天写的内容！！！我决定了！你们没有看见我昨天写的内容！！！
之后我可能会把D的题解也加上。
~~似乎好像可能也许说不定会加的。~~
M a y b e Maybe Maybe

ABC 257 A-C 题解

C/C++/C#相关栏目本月热门文章