1单选题
2判断题
3编程题
树上游走
题目分析
- 当前结点编号为 u，父节点 u/2，左孩子 u*2，右孩子 u*2 1
- 但是数据范围非常大，虽然题目说明最后结点编号不超过1012，但是中间过程可能会超过，例如，连续 105 个 L，再连续 105 个 U，实际结点编号没变，但是数据量是巨大的。
- 解决方案就是将序列中所有的 U 都去掉，然后再计算 u 的值。
参考程序
#include <bits/stdc .h>
using namespace std;
typedef long long LL;
LL n, s;
deque<char> dq;
int main() {
cin >> n >> s;
while(n--){
char op;
cin >> op;
if(op == 'U'){
if(dq.size())
dq.pop_back();
else if(s != 1)
s >>= 1;
}
else
dq.push_back(op);
}
while(dq.size()){
if(dq.front() == 'L')
s <<= 1;
else
s = (s << 1) 1;
dq.pop_front();
}
cout << s;
return 0;
}
运送物资
题目分析
贪心算法，如果a-b>0，则尽量选择靠左侧的站点，按照 a-b 从大到小排序。
如果 b-a>0，则尽量选择靠右侧站点。
注意将给定站点按照位置从小到大排好序。
参考程序
#include <bits/stdc .h>
using namespace std;
typedef long long LL;
const int N = 1e5 10;
struct Node1{
int p, c;
}P[N];
struct Node2{
int a, b;
}f[N], g[N];
int cf = 0, cg = 0;
bool cmp(Node1& x, Node1& y){
return x.p < y.p;
}
bool cmp1(Node2& x, Node2& y){
return x.a - x.b > y.a - y.b;
}
bool cmp2(Node2& x, Node2& y){
return x.b - x.a > y.b - y.a;
}
int n, m, s;
int main() {
cin >> n >> m >> s;
for(int i = 1; i <= n; i ) // n 站点数量
cin >> P[i].p >> P[i].c; // 位置 数量
for(int i = 1; i <= m; i ){ // m 货车数量
int x, y;
cin >> x >> y;
if(x >= y) f[ cf] = {x, y};
else g[ cg] = {x, y};
}
sort(P 1, P n 1, cmp);
sort(f 1, f cf 1, cmp1); // a>b: a-b 从大到小
sort(g 1, g cg 1, cmp2); // a<b: b-a 从大到小
LL res = 0;
int cur = 1;
for(int i = 1; i <= cf; i ){
if(P[cur].c == 0) cur ;
res = 2ll * f[i].a * P[cur].p 2ll * f[i].b * (s - P[cur].p);
P[cur].c--;
}
cur = n;
for(int i = 1; i <= cg; i ){
if(P[cur].c == 0) cur--;
res = 2ll * g[i].a * P[cur].p 2ll * g[i].b * (s - P[cur].p);
P[cur].c--;
}
cout << res;
return 0;
}
