2014-2015 ACM-ICPC, NEERC, Northern Subregional Contest I-Instruction(模拟)
题意：
给若干个开关和若干个站台共n个(n<=51)，以及其上属开关，如果是站台的话，还给出其字符标志。火车在开关以及站台之间移动只花费1min。然后给m个火车的到达时间以及要前往的站台(m<=1000)，初始时开关是连向编号较小的下属，问需要进行的开关切换时间以及其编号。
每个开关会有两个下属，站台没有下属。
思路：
贼难读...可以发现满足二叉树，因此建树进行模拟即可，即把所有开关作为分支节点，所有站台作为叶子节点，每个节点设立一个01状态，表示当前连向的下属是左子树还是右子树。模拟即可。。由于节点个数最多只有51个，暴力寻找目标叶节点就可以，不过我对建好的树先进行一次中序遍历，将树转化成排序二叉树，这样再寻找目标就方便了许多。
代码：
#include <bits/stdc++.h>
using namespace std;
struct node
{
int key;
int id, lson, rson;
} g[100];
int _ids[50];
char ch;
int n, m, cnt, fa, _time;
int bh;
vector<pair<int, int> > vt;
bool cmp(pair<int, int>p1, pair<int, int>p2)
{
return p1.second < p2.second;
}
void dfs(int rt)
{
if(g[rt].lson != -1) dfs(g[rt].lson);
g[rt].id = bh++;
if(g[rt].rson != -1) dfs(g[rt].rson);
}
void work(int rt, int dep, int val)
{
if(g[rt].id == val) return;
if(g[rt].id > val)
{
if(g[rt].key == 0)
vt.push_back(make_pair(rt, _time+dep));
g[rt].key = 1;
work(g[rt].lson, dep+1, val);
}
else
{
if(g[rt].key == 1)
vt.push_back(make_pair(rt, _time+dep));
g[rt].key = 0;
work(g[rt].rson, dep+1, val);
}
}
int main()
{
freopen("instruction.in","r",stdin);
freopen("instruction.out","w",stdout);
// freopen("in.txt", "r", stdin);
memset(_ids, 0, sizeof _ids);
vt.clear();
scanf("%d", &n);
cnt = 0, g[0].lson = g[0].rson = -1;
for(int i = 1; i <= n; ++i)
{
scanf(" %c %d", &ch, &fa);
g[++cnt].key = 1;
g[cnt].lson = g[cnt].rson = -1;
if(g[fa].lson == -1) g[fa].lson = cnt;
else g[fa].rson = cnt;
if(ch == 'p')
{
scanf(" %c", &ch);
_ids[ch-'a'] = cnt;
}
}
bh = 0; dfs(0);
scanf("%d", &m);
for(int i = 1; i <= m; ++i)
{
scanf("%d %c", &_time, &ch);
int t = _ids[ch-'a'];
work(1, 1, g[t].id);
}
sort(vt.begin(), vt.end(), cmp);
printf("%d\n", vt.size());
for(int i = 0; i < vt.size(); ++i)
printf("%d %d\n", vt[i].first, vt[i].second);
return 0;
}
继续加油~