P9754题解

· · 题解

2023 CPS-S T3 题解

前言：

TE 来抢题解啦。

感谢 CCF 出了一道大模拟放在第三题，使得我逆天改命最后两分钟过了这题，然后变成两周后高贵的 LA 群友。

我发现题解普遍是写的和我思路几乎一模一样，是标准的结构体指针写法。我的同学们还说我写结构体指针是脑残发作，这下这下了。

本人评价该题为正常难度蓝题。

解法：

准备工作

首先搞个结构体。然后存自己的别名和类型名，按照形式化题意维护相对偏移量，对齐参数，长度。用一个 vector 存自己的儿子指针。

初始化的方式采用一个 map 来存储默认结构体。别忘了存他给的四种初始数据类型。

当我们需要创造一个新的结构体时，就先声明一个空的范例结构体，按照题意给他分配对应的儿子节点（别忘了改儿子的别名），然后不断更新儿子的偏移量和自己的对齐参数，最后更新自己的长度和类型名字，存到 map 中去。这中间不会动自己的别名和相对偏移量，默认为空，要注意。

代码：

struct jiegou{
    string name,typ; //别名和类型
    int len,dq,py; //长度，对齐，相对父亲的偏移量
    vector<jiegou *>son; //儿子（嵌套的结构体）
    jiegou(){ py=len=dq=0; name=typ="";}
    jiegou(int len,string typ){
        this->py=0; this->len=len; this->dq=len; this->typ=typ; 
    }
};
map<string,jiegou>mp; //用于初始化结构体的一个map
int sqz(int a,int b){ return a/b+(int)(a%b>0); } //顾名思义，上取整
void build(string x,int k){
    jiegou tmp;
    tmp.typ=x;
    int py=0;
    jiegou *lst;
    rep(i,1,k){
        string typ,alia; cin>>typ>>alia;
        jiegou *tmp1=new jiegou(mp[typ]); tmp1->name=alia;
        tmp.dq=max(tmp1->dq,tmp.dq);
        if(i>1){
            tmp1->py=tmp1->dq*sqz(lst->py+lst->len,tmp1->dq);
        }
        tmp.son.push_back(tmp1); lst=tmp1;
    }
    tmp.len=tmp.dq*sqz(lst->len+lst->py,tmp.dq);
    mp[x]=tmp;
    cout<<tmp.len<<" "<<tmp.dq<<endl;
}

加入至内存池

我们可以把内存池当做一个没有别名、类型、长度的树根，然后动态维护它的对齐参数并默认它的偏移量为 0。这样我们的操作将简单的多。

代码：

jiegou *tr=new jiegou();
void add(string typ,string nam){
    jiegou *tmp=new jiegou(mp[typ]); tmp->name=nam;
    int x,y,st=0;
    vector<jiegou *>vec=tr->son; //简化一下，呜呜
    if(vec.empty()) x=0,y=0;
    else x=(*--vec.end())->py,y=(*--vec.end())->len;
    st=sqz(x+y,tmp->dq)*tmp->dq;
    tmp->py=st;
    tr->son.push_back(tmp); 
    cout<<st<<endl;
}

索引找内存

直接暴力分割出来每一层索引的名字然后暴力一层一层跳就可以了。这个没啥难度。

int find(string x){
    vector<string>vec;
    int lst=0,len=x.length();
    rep(i,1,len)
        if(x[i-1]=='.') vec.push_back(x.substr(lst,i-lst-1)),lst=i;
    vec.push_back(x.substr(lst,len-lst)); //暴力分割索引
    jiegou *now=tr;
    int st=0,py;
    rep(i,1,vec.size()){ //暴力一层一层跳
        py=st;
        rep(j,1,now->son.size()){
            jiegou *k=now->son[j-1];
            py=st+k->py;
            if(k->name==vec[i-1]){
                st=py; now=k; break; 
            }
        }
    }
    return py;
}

内存找索引

递归找一下，暴力一层层跳，递归存一下目前的总偏移量，如果子节点包含这个区间就往下找。

一个小 trick：我的写法如果失配就会在最后一层正好返回一个 ERR，也就是 x.xx.xxx.ERR 的格式，我懒得手写判定就直接判里面有没有子串是 ERR，反正索引都是小写的。具体代码写主函数里面了。

代码：

string getbyadr(jiegou *now,int st,int tar){
    string ans="";
    rep(i,1,now->son.size()){
        jiegou *k=now->son[i-1];
        if(st+(k->py)<=tar&&tar<st+(k->py)+(k->len)){
            ans=k->name;
            if(k->son.size()) ans+="."+getbyadr(k,st+(k->py),tar);
            break;
        }
    }
    if(ans.empty()) return "ERR";
    else return ans;
}

主函数和宏定义

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define fi first
#define sc second
using namespace std;
#define int long long //为了保险开的，不少人没开ll痛失40分
/*
    结构体、变量的定义和各个函数的实现方式省略。
*/
signed main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n; cin>>n;
    mp["long"]=jiegou(8ll,"long");
    mp["int"]=jiegou(4ll,"int");
    mp["short"]=jiegou(2ll,"short");
    mp["byte"]=jiegou(1ll,"byte");
    rep(idk,1,n){
        int opt; cin>>opt;
        if(opt==1){
            string x; int y; cin>>x>>y;
            build(x,y);
        }
        else if(opt==2){
            string x,y; cin>>x>>y; add(x,y);
        }
        else if(opt==3){
            string x; cin>>x; cout<<find(x)<<endl;
        }
        else if(opt==4){
            int adr; cin>>adr;
            string ans=getbyadr(tr,0,adr);
            if(ans.find("ERR")!=-1) cout<<"ERR"<<endl;
            //一个取巧的方法（因为错误时其实上只有最后一层是ERR）
            else cout<<ans<<endl;
        }
    }
}

收尾：

感谢谷友们对我 OI 事业的支持，感谢家长和南外老师们对我 OI 事业的支持，希望你们看到的时候顶我上去，谢谢！

另外顺便提一句，赛后优化代码可以使代码最短用时小于 6 ms 并且长度小于 2.9 KiB。