T3 结构体
考完试后补题，才发现这玩意不难搞出来。
这篇题解用了较多代码块，可以依需要看每一部分的代码。
题面好长看不懂，看提示。
【提示】
对于结构体类型的对齐要求和大小，形式化的定义方式如下：
- 设该结构体内有 \(k\) 个成员，其大小分别为 \(s_1,...,s_k\)，对齐要求分别为 \(a_1,...,a_k\);
- 则该结构体的对齐要求为 \(a=\max\{a_1,...,a_k\}\)；
- 再设这些成员排布时的地址偏移量分别为 \(o_1,...,o_k\)，则：
- \(o_1 = 0\);
- 对于 \(i=2,...,k\)，\(o_i\) 为满足 \(o_{i-1}+s_{i-1}\le o_i\) 且 \(a_i\) 整除 \(o_i\) 的最小值；
- 则该结构体的大小 \(s\) 为满足 \(o_k+s_k\le s\) 且 \(a\) 整除 \(s\) 的最小值；
对于定义元素时的内存排布，形式化的定义方式如下：
- 设第 \(i\) 个被定义的元素大小为 \(s_i\)，对齐要求为 \(a_i\)，起始地址为 \(b_i\);
- 则 \(b_1 = 0\)，对于 \(2\le i\)， \(b_i\) 为满足 \(b_{i-1} + s_{i-1}\le b_i\) 且 \(a_i\) 整除 \(b_i\) 的最小值。
直接看题面做会很乱，形式化的提示相当于告诉了我们要记录哪些项目，根据提示做题能够更好的理清思路。
先看结构体。
容易发现结构体形成了一棵树形结构，考虑每个节点记录的信息。根据提示，首先肯定要记录大小和对齐要求，成员数量和子节点的编号。还要记录每个成员的名字和地址偏移量。并且有了这些信息，我们已经可以表示一个结构体了。这里我用如下定义：
struct Type{
int k, s, a, son[105], o[105];
string call[105];
}st[505];
这里的 \(k, s, a, o\) 和题目的定义一致，\(son\) 记录了子节点的编号，\(call\) 记录了成员的名字。
那么我们可以做操作一了。把定义结构体分成两步，第一步把节点插入，即处理出 \(k, son, call\)。第二步就是把 \(s, a, o\) 给处理出来。
第一步不用说，直接插入即可。第二步按照提示的内容模拟即可，因为我们已经有了子节点的 \(s, a\)，所以很容易处理出来。
然后把结构体的名字和结构体的节点编号扔到 \(map\) 里备用。
操作一就做完了。
操作一代码
int geto(int u){
if(!k(u)) return 0;
o(u)[1] = 0;
for(int i = 2; i <= k(u); i ++){
int lst = o(u)[i - 1] + s(son(u)[i - 1]);
int pos = lst;
for(int j = lst; j <= lst + a(son(u)[i]); j ++)
if(j % a(son(u)[i]) == 0){
pos = j;
break;
}
o(u)[i] = pos;
}
int lst = o(u)[k(u)] + s(son(u)[k(u)]);
int pos = lst;
for(int j = lst; j <= lst + a(u); j ++)
if(j % a(u) == 0){
pos = j;
break;
}
s(u) = pos;
return 0;
}
int insert(int u, int v, string nm){
k(u) ++;
a(u) = max(a(u), a(v));
son(u)[k(u)] = v;
call(u)[k(u)] = nm;
return 0;
}
int run1(){
string nam;
int k;
cin >> nam >> k;
cnt ++;
hsh[nam] = cnt;
for(int i = 1; i <= k; i ++){
string c, d;
cin >> c >> d;
int ids = hsh[c];
insert(cnt, ids, d);
}
geto(cnt);
cout << s(cnt) << " " << a(cnt) << "\n";
return 0;
}
然后看元素。
继续看提示，我们需要记录大小，对齐要求和地址。同时也要记录元素的类型，即在结构体树中的节点编号，以及每个元素的名字。这里我用如下定义。
int s[505], a[505], b[505], type[505];
string name[505];
其中 \(s, a, b\) 和题目定义相同，\(type\) 表示类型，\(name\) 表示名字。
对于操作二，在插入新元素时，\(s\) 和 \(a\) 已经通过 \(type\) 可以直接确定。而 \(b\) 的计算直接按照提示内容模拟即可。
操作二代码
int insertnode(string nam, int typ){
name[++ tot] = nam;
type[tot] = typ;
s[tot] = s(typ);
a[tot] = a(typ);
int lst = b[tot - 1] + s[tot - 1];
int pos = lst;
for(int i = lst; i <= lst + a[tot]; i ++)
if(i % a[tot] == 0){
pos = i;
break;
}
b[tot] = pos;
return 0;
}
int run2(){
string c, d;
cin >> c >> d;
int ids = hsh[c];
insertnode(d, ids);
cout << b[tot] << "\n";
return 0;
}
接下来看操作三。
操作三可以拆成先找到一个元素的起始地址，然后在结构体中找到一个元素的地址。
容易发现第二部分可以递归实现的。定义 \(f(u, mode)\) 表示现在在结构体树的结点 \(u\)，当前需要访问的字符串为 \(mode\)。先把 \(mode\) 按第一个点的前后拆成两部分 \(fst\) 和 \(sec\)，然后在 \(u\) 的子节点的 \(call\) 中找到 \(fst\)，节点编号为 \(v\)，其地址偏移量为 \(o\)。那么只需要继续在节点 \(v\) 中访问字符串 \(sec\) 即可，即求出 \(f(v, sec)\)。设得到的答案为 \(w\)，那么这一层的答案即为 \(w + o\)。
边界条件是 \(mode\) 为空串的时候，这个时候答案为 \(0\)。
然后我们再在元素中寻找 \(name\)，找到具体的元素，设其起始地址为 \(b\)，答案就是 \(b\) 加上第二部分的答案。
操作三代码
int visit(int u, string mode){
string fst, sec;
bool flg = false;
for(int i = 0; i < (int)mode.length(); i ++){
if(mode[i] != '.' && (!flg))
fst = fst + mode[i];
else if(mode[i] == '.' && !flg)
flg = true;
else sec = sec + mode[i];
}
int pos = 0;
for(int i = 1; i <= k(u); i ++)
if(call(u)[i] == fst){
pos = i;
break;
}
int v = son(u)[pos];
int w = o(u)[pos];
if(sec.empty())
return w;
return w + visit(v, sec);
}//这样就递归完成了找到一个结构体中的某个元素的位置
int run3(){
string mode;
cin >> mode;
string fst, sec;
bool flg = false;
for(int i = 0; i < (int)mode.length(); i ++){
if(mode[i] != '.' && (!flg))
fst = fst + mode[i];
else if(mode[i] == '.' && !flg)
flg = true;
else sec = sec + mode[i];
}
int pos = 0;
for(int i = 1; i <= tot; i ++){
if(name[i] == fst){
pos = i;
break;
}
}
if(sec.empty())
cout << b[pos] << "\n";
else cout << b[pos] + visit(type[pos], sec) << "\n";
return 0;
}
最后看操作四。
同理，操作四可以拆成先找这个地址所在的元素，然后再在结构体树中找到其所在的最底层的节点。假设要找的地址是 \(x\)。
第一部分，一个一个元素去翻，我们需要翻到一个满足 \(b_i \le x < b_i + s_i\) 的位置，找到了就进入第二步，失败了就是 ERR。
第二部分一样是可以递归完成。设 \(g(u, x)\) 表示现在在节点 \(u\)，需要寻找的地址是 \(x\) 的答案。同理，一个一个成员翻，去找一个 \(o_i \le x < o_i + s_i\) 的位置。找不到为 ERR。设找到了节点 \(v\)，地址偏移量为 \(o\)，那么继续递归得到 \(g(v, x - o)\)。如果这个答案是 ERR，那么返回 ERR，否则把 \(v\) 的 \(call\) 和一个 . 拼到答案的前面然后返回即可。
边界条件是 \(u\) 是一个基础类型节点。这个时候返回空串。返回的时候特判返回值是否是空串，如果是则不需要把 . 拼到答案前面。
操作四代码
string find(int u, int x){
//一个一个元素去翻，翻到一个满足 o_i <= x < o_i + s_i 的位置，失败了就是 ERR
if(k(u) == 0)
return "";
int pos = 0;
for(int i = 1; i <= k(u); i ++)
if(o(u)[i] <= x && x < o(u)[i] + s(son(u)[i])){
pos = i;
break;
}
if(pos == 0) return "ERR";
string ans = find(son(u)[pos], x - o(u)[pos]);
if(ans == "ERR") return "ERR";
string c = call(u)[pos];
if(ans == "")
return c;
c += ".", c += ans;
return c;
}
int run4(){
int x;
cin >> x;
int pos = 0;
for(int i = 1; i <= tot; i ++)
if(b[i] <= x && x < b[i] + s[i]){
pos = i;
break;
}
if(pos == 0){
cout << "ERR\n";
return 0;
}
string c = name[pos];
string ans = find(type[pos], x - b[pos]);
if(ans == "ERR"){
cout << "ERR\n";
return 0;
}
if(ans == "") cout << c << "\n";
else cout << (c + "." + ans) << "\n";
return 0;
}
然后就做完了。对于大模拟题，有足够清晰的思路后，模块化的写代码，写起来不难的。
完整代码
//10/24 20:48 start
//10/24 21:53 done
//开始调代码
//10/24 22:03 过第一个小样例
//10/25参加体艺节
//10/26 8:48开始调
//10/26 9:12 Accept
#include<iostream>
#include<fstream>
#include<algorithm>
#include<cstring>
#include<string>
#include<map>
#define int long long
using namespace std;
namespace solve1{
int n;
int clear(){
return 0;
}
struct Type{
int k, s, a, son[105], o[105];
string call[105];
#define k(u) st[u].k
#define s(u) st[u].s
#define a(u) st[u].a
#define son(u) st[u].son
#define o(u) st[u].o
#define call(u) st[u].call
}st[505];
int cnt;
int geto(int u){
if(!k(u)) return 0;
o(u)[1] = 0;
for(int i = 2; i <= k(u); i ++){
int lst = o(u)[i - 1] + s(son(u)[i - 1]);
int pos = lst;
for(int j = lst; j <= lst + a(son(u)[i]); j ++)
if(j % a(son(u)[i]) == 0){
pos = j;
break;
}
o(u)[i] = pos;
}
int lst = o(u)[k(u)] + s(son(u)[k(u)]);
int pos = lst;
for(int j = lst; j <= lst + a(u); j ++)
if(j % a(u) == 0){
pos = j;
break;
}
s(u) = pos;
return 0;
}
int insert(int u, int v, string nm){
k(u) ++;
a(u) = max(a(u), a(v));
son(u)[k(u)] = v;
call(u)[k(u)] = nm;
return 0;
}
int s[505], a[505], b[505];
int type[505], tot;
string name[505];
int insertnode(string nam, int typ){
name[++ tot] = nam;
type[tot] = typ;
s[tot] = s(typ);
a[tot] = a(typ);
int lst = b[tot - 1] + s[tot - 1];
int pos = lst;
for(int i = lst; i <= lst + a[tot]; i ++)
if(i % a[tot] == 0){
pos = i;
break;
}
b[tot] = pos;
return 0;
}
map<string, int> hsh;
int run1(){
string nam;
int k;
cin >> nam >> k;
cnt ++;
hsh[nam] = cnt;
for(int i = 1; i <= k; i ++){
string c, d;
cin >> c >> d;
int ids = hsh[c];
insert(cnt, ids, d);
}
geto(cnt);
cout << s(cnt) << " " << a(cnt) << "\n";
return 0;
}
int run2(){
string c, d;
cin >> c >> d;
int ids = hsh[c];
insertnode(d, ids);
cout << b[tot] << "\n";
return 0;
}
//接下来有什么要实现的呢？
//操作3实质是
//递归的在一个结构体中访问成员
//其中第一个.之前的是元素
int visit(int u, string mode){
string fst, sec;
bool flg = false;
for(int i = 0; i < (int)mode.length(); i ++){
if(mode[i] != '.' && (!flg))
fst = fst + mode[i];
else if(mode[i] == '.' && !flg)
flg = true;
else sec = sec + mode[i];
} //fst 是第一个元素 sec 是第二个元素
int pos = 0;
for(int i = 1; i <= k(u); i ++)
if(call(u)[i] == fst){
pos = i;
break;
}
int v = son(u)[pos];
int w = o(u)[pos];
if(sec.empty())
return w;
return w + visit(v, sec);
}
//这样就递归完成了找到一个结构体中的某个元素的位置
int run3(){
string mode;
cin >> mode;
string fst, sec;
bool flg = false;
for(int i = 0; i < (int)mode.length(); i ++){
if(mode[i] != '.' && (!flg))
fst = fst + mode[i];
else if(mode[i] == '.' && !flg)
flg = true;
else sec = sec + mode[i];
} //fst 是第一个元素 sec 是第二个元素
int pos = 0;
for(int i = 1; i <= tot; i ++){
if(name[i] == fst){
pos = i;
break;
}
}
if(sec.empty())
cout << b[pos] << "\n";
else cout << b[pos] + visit(type[pos], sec) << "\n";
return 0;
}
//接下来要实现的是4操作
//4操作其实分两步
//第一步是找到对应的元素
//第二步是从一个结构体中找出对应的位置
//先实现第二步
string find(int u, int x){
//一个一个元素去翻，翻到一个满足 o_i <= x < o_i + s_i 的位置，失败了就是 ERR
if(k(u) == 0)
return "";
int pos = 0;
for(int i = 1; i <= k(u); i ++)
if(o(u)[i] <= x && x < o(u)[i] + s(son(u)[i])){
pos = i;
break;
}
if(pos == 0) return "ERR";
string ans = find(son(u)[pos], x - o(u)[pos]);
if(ans == "ERR") return "ERR";
string c = call(u)[pos];
if(ans == "")
return c;
c += ".", c += ans;
return c;
}
int run4(){
int x;
cin >> x;
int pos = 0;
for(int i = 1; i <= tot; i ++)
if(b[i] <= x && x < b[i] + s[i]){
pos = i;
break;
}
if(pos == 0){
cout << "ERR\n";
return 0;
}
string c = name[pos];
string ans = find(type[pos], x - b[pos]);
if(ans == "ERR"){
cout << "ERR\n";
return 0;
}
if(ans == "") cout << c << "\n";
else cout << (c + "." + ans) << "\n";
return 0;
}
int solve(){
clear();
cnt = 4, s(1) = a(1) = 1, s(2) = a(2) = 2, s(3) = a(3) = 4, s(4) = a(4) = 8;
hsh["byte"] = 1, hsh["short"] = 2, hsh["int"] = 3, hsh["long"] = 4;
int T;
cin >> T;
while(T --){
int opt;
cin >> opt;
if(opt == 1) run1();
if(opt == 2) run2();
if(opt == 3) run3();
if(opt == 4) run4();
}
return 0;
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T = 1;
while(T --)
solve1::solve();
return 0;
}