2022京东春招笔试4-2

2022京东春招笔试4-2

Tans 2,289 2022-04-02

T1:树上走路

第一题开unsigned long long也会超时,因此用数组模拟位运算,

  • 当发生2*2操作的时候,尾部插入0
  • 发生2+1*2+1操作的时候,尾部插入1
  • 当发生/2/2操作的时候,删除尾部元素
    最后结果,构造答案即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s,val) memset(s, val, sizeof(s))
const int inf = INT_MAX;

int T;
int main(int argc, char * argv[]){
	long long n, x;
	string s;
	cin >> n >> x;
	cin >> s;
	vector<int> v;
	while(x){
		v.push_back(x & 1);
		x = x >> 1;
	}
	reverse(v.begin(), v.end());
	for(auto &ch : s){
		if(ch == 'U') v.pop_back();
		if(ch == 'L') v.push_back(0);
		if(ch == 'R') v.push_back(1);
	}
	reverse(v.begin(), v.end());
	unsigned long long power = 1, ans = 0;
	for(auto bit : v){
		ans += power * bit;
		power = power * 2; 
	}
	cout << ans;

    return 0;
}

T2:粉刷

不太理解,应该是DP?
注意最多3次,除了判断 00的情况,可以直接 rand()mod3+1rand()mod 3+1返回,看运气了。。。