CF935B Fafa and the Gates 题解

2024-10-19 17:49:29

Content

一个动点 \(F\) 一开始在平面直角坐标系上原点的位置，随后它会移动 \(n\) 次，每次只能向上走或者向右走 \(1\) 个单位，求经过直线 \(y=x\) 的次数。

数据范围：\(1\leqslant n\leqslant 10^5\)。

Solution

注意，这里是经过直线 \(y=x\) 的次数而不是到达直线 \(y=x\) 的次数！比如说你上次操作往上走 \(1\) 个单位，到了 \((3,3)\)，但随后你又往右走了 \(1\) 个单位，这就不算经过了！必须要到达直线 \(y=x\) 并且下一步操作和到直线前的上一步操作的方向相同！

其他的不用多说了，直接模拟每一步操作就好。

Code

int n, curx, cury, ans;

string s; 

int main() {

	getint(n);

	cin >> s;

	_for(i, 0, n - 1)	curx += (s[i] == 'R'), cury += (s[i] == 'U'), ans += (curx == cury && s[i + 1] == s[i]);

	writeint(ans);

	return 0;

}

最新文章

热门文章