大模拟。
首先的难度在于理解题意：
打电话的地点分为镇、地区、超级地区三级。其中，一些地区是被网络连接的。
电话号码的前缀由 地区号+镇号 组成。它们可以是不等长的，但是整个电话号码的长度是 \(d\)。一个镇可能有多个镇号，不同地区的镇可以拥有相同的镇号，但地区号是唯一的。
同时，电话分为四种来源：
- 从区域 \(h\)，出发
- 从 \(h\) 在同一个超级区域 且被网络覆盖的 区域出发。
- 从被网络覆盖的区域出发
- 从其他区域出发。
电话的距离分为四种：
- 从一个镇到自身
- 到同区域的镇
- 到被网络连接的区域的镇
- 到其他区域的镇。
按照来源和距离，我们把所有的电话分成 \(16\) 种，依次给出它们的开销。
然后，给出若干条电话，每一条给出打电话的来源镇和拨打的号码。如果号码无效则电话无效。然后给出打电话的时间，求最终的总开销。
我们发现，可以使用字典树存储所有的号码，看上去字典树的空间会炸，但是因为还有输入量不超过 512KB 的限制，所以字典树的大小也不太会超过 \(512000\)，至多多一点常数（因为 1KB=1024B）但是字典树也会省一些空间，还有其他输入部分，所以开 \(500000\) 足够了。
然后我们直接在字典树上插入，插入镇号的时候直接从区域号在字典序上的位置往后插入。最后对于当前号码查询，查询到镇就退出。
然后我们来看 I_love_Hoang_Yen 的程序。
struct Node {
Node* child[10];
int townId;
Node() {
memset(child, 0, sizeof child);
townId = 0;
}
} *root;
首先是指针形式的字典树，很明显这道题的时间瓶颈基本在字典树的插入和查询，所以字典树节点的优化非常重要，指针就比普通的数组快了一些。
struct Region {
string code;
int sup;
void read() {
cin >> sup >> code;
}
} regions[222];
bool covered[222];
struct Town {
vector<string> codes;
int reg;
void read(int id) {
int k;
cin >> reg >> k;
codes.resize(k);
Node*p = root;
for(char c : regions[reg].code) {
int t = c - '0';
if (!p->child[t]) {
p->child[t] = new Node();
}
p = p->child[t];
}
if (!k) p->townId = id;
auto savep = p;
REP(i,k) {
cin >> codes[i];
p = savep;
for(char c : codes[i]) {
int t = c - '0';
if (!p->child[t]) p->child[t] = new Node();
p = p->child[t];
}
p->townId = id;
}
}
} towns[10111];
分别封装 regions 和 towns，条例清晰，层次性好，有效的防止了各层次互相混乱导致最后打表挂掉的情况。
封装输入也同样简便了程序的书写，不用开很多的变量表达不同的意思，也不需要在主函数里面分清各个地区的作用。
int getTown(const string& phoneNum) {
Node*p = root;
for(char c : phoneNum) {
p = p->child[c - '0'];
if (!p) return -1;
if (p->townId) return p->townId;
}
return -1;
}
对于 town 的查询，就体现出各个变量名意义明显的好处。
int main() {
ios :: sync_with_stdio(false);
freopen("called.in", "r", stdin);
freopen("called.out", "w", stdout);
root = new Node();
cin >> nTown >> nRegion >> nSuper >> d;
FOR(i,1,nRegion) regions[i].read();
FOR(i,1,nTown) towns[i].read(i);
int k;
cin >> homeRegion >> k;
REP(i,k) {
int reg; cin >> reg;
covered[reg] = true;
}
assert(covered[homeRegion]);
REP(i,4) REP(j,4) cin >> cost[i][j];
ll sum = 0;
int q; cin >> q;
while (q--) {
int fromTown; string phoneNum; int len;
cin >> fromTown >> phoneNum >> len;
// DEBUG(phoneNum);
int a, b;
if (towns[fromTown].reg == homeRegion) a = 0;
else if (covered[towns[fromTown].reg]
&& regions[towns[fromTown].reg].sup == regions[homeRegion].sup) a = 1;
else if (covered[towns[fromTown].reg]) a = 2;
else a = 3;
int toTown = getTown(phoneNum);
if (toTown < 0) continue;
// DEBUG(toTown);
if (toTown == fromTown) b = 0;
else if (towns[toTown].reg == towns[fromTown].reg) b = 1;
else if (covered[ towns[toTown].reg ]) b = 2;
else b = 3;
sum += cost[a][b] * (ll) len;
// DEBUG(sum);
}
cout << sum << endl;
}
可以看到，在读入的大头被封装处理之后，主函数基本只剩下输出部分，简化了很多不必要的部分。
而在最后的部分，有意义的变量名给我们的打表提供了很大的便利，我们的程序基本是照着题面写的，有效避免了因为自己忘记变量含义而出锅的情况。