有谁会这题图论的？

常规
,
1

6. 小信跳房子

XJOI - 题目ID：8442必做题100分

最新提交：0 分

历史最高：0 分

时间限制: 1000ms

空间限制: 262144kB

题目描述

时间：1s 空间：256M

题目描述：

小信在玩跳房子游戏，已知跳房子游戏的图表现为一颗完美的具有2^{10^{100}}-1210100−1个节点的二叉树。从根节点依次编号为1,2,…,2^{10^{100}}-11,2,…,210100−1。节点i(1\le i \le 2^{10^{100}-1})i(1≤i≤210100−1)的左子节点编号为2i2i，右子节点编号为2i+12i+1。

小信从从节点xx出发，共跳nn步，用一个长度为nn的字符串表示小信的移动方向，“U”表示跳到当前所在节点的父节点，“L”表示跳到当前节点的左子节点，“R”表示跳到当前节点的右子节点。

输出小信在跳了nn步之后所处的节点编号，保证最终答案不超过10^{18}1018。

提示：在跳的过程中节点编号可能超过10^{18}1018。

输入格式：

第一行包含两个整数n,xn,x，表示小信移动次数和初始所在节点编号。

第二行包含一个只含“U”，“L”和“R”的长为nn的字符串SS。

输出格式：

输出一个整数，表示小信在跳了nn步之后所处的节点编号。

样例1输入：

3 2
URL

样例1输出：

6

样例2输入：

6 500000000000000000
RRRUUU

样例2输出：

500000000000000000

约定与提示：

对于100%的数据，1 \leq n \leq 10^6; 1 \le x \le 10^{18}1≤n≤106;1≤x≤1018。

样例1：小信的移动路径是2 → 1 → 3 → 6

2 个赞
2 
#include<bits/stdc++.h>
using namespace std;
long long n,x;
vector<char>v;
void fangru(char a){
	if(v.size()==0){
		v.push_back(a);
		return ;
	}
	if(a=='U' && v.back()!='U'){
		v.pop_back();
		return ;
	}
	v.push_back(a);
}
int main(){
	cin>>n>>x;
	for(int i=1;i<=n;i++){
		char a;
		cin>>a;
		fangru(a);
	}
	for(int i=0;i<v.size();i++){
		if(v[i]=='U'){
			x/=2;
		}
		else if(v[i]=='L'){
			x*=2;
		}
		else{
			x=2*x+1;
		}
	}
	cout<<x<<endl;
	return 0;
}
1 个赞
3

image
image1345×1061 155 KB

1 个赞
4

这题是二分，提醒一下

1 个赞
5

你这都不是一道题

1 个赞
6

你提交成小信的数组了

1 个赞
7

o。。

1 个赞
8

谢谢