P9754 [CSP-S 2023] 结构体题解

KobeBeanBryantCox · 2023-10-28 12:23:55 · 题解

P9754 [CSP-S 2023] 结构体题解

update on 2024.8.23：修了点格式，并且针对这个帖子中的 hack 数据修改了代码。

感谢@Y204335 大佬提出了本题解的错误！

本题解有数据生成器！（虽然是转载的）

题目传送门。

~~CCF 太毒瘤了，竟然在第 3 题放大模拟。~~

题意

四种操作：

定义一个结构体，不占内存。输出该结构体的大小和对齐要求。
定义一个普通变量或结构体变量，占相应内存。输出这个变量在内存中的起始位置。
查询某个元素在内存中的起始位置。
查询内存中某个位置的元素是什么，如果这个位置没有元素，输出 ERR。

具体要求见题目描述。~~（因为我也不是很好解释）~~

分析

~~先说我之前的代码错在哪里，就错在没开 long double。（update on 2024.8.23）~~

数据范围：1\leq n\leq 100，1\leq k\leq 100，0\leq addr\leq 10^{18}，题目保证任意结构体大小及定义的元素占据的最高内存地址均不超过 10^{18}。

数据范围不大~~（而且这种题数据范围也不可能大）~~，于是这个题就一定是大模拟了。

ps：由于此题是个大模拟，所以接下来的解释有可能会很绕。我尽量解释得清楚一点，尽量把代码写得可读性更高一点。如果看不懂，欢迎讨论。

准备工作

由于最大数据达到了 10^{18} 的大小，所以要开 long long。

typedef long long ll; // 把 long long 换个名字，叫做 ll

先在代码里定义两个结构体：

表示题目中的单个变量或者结构体中的元素。

/***********************************************单个元素***********************************************/
struct yuansu
{
    string leixing,name; // 元素的 类型 和 名字
    ll daxiao,qishi; // 这个元素 占用内存大小 和 它在内存中的起始位置
    // qishi=-1 表示这个元素是在结构体里的元素
}yuan[N];
ll yuan_count=0; // 当前有多少个元素
map<string,ll>yingshe_yuan; // 名字为 string 的元素在 yuan 数组里的编号是多少，相当于映射
/***********************************************单个元素***********************************************/

表示题目中的结构体。

/************************************************结构体************************************************/
struct struc
{
    string name; // 结构体名字 
    ll geshu,daxiao,duiqiyaoqiu; // 成员个数、结构体大小 和 结构体对齐要求 
    vector<yuansu>member; // 成员，注意类型是 yuansu 
    vector<ll>pianyi; // 每个成员在结构体中的偏移量 
}str[N];
ll str_count=0; // 当前有多少个结构体 
map<string,ll>yingshe_str; // 名字是 string 的结构体在 str 数组里的编号是多少，相当于映射 
/************************************************结构体************************************************/

再定义几个函数：

ll big(string x) // 元素大小，x 是元素类型 
{
    if(x=="byte")return 1;
    else if(x=="short")return 2;
    else if(x=="int")return 4;
    else if(x=="long")return 8;
    else return str[yingshe_str[x]].daxiao;
}
yuansu find1(ll x) // 找在内存中不超过 x 的位置的元素 
{
    ll l=1,r=yuan_count,ans=1;
    while(l<=r) // 二分查找 
    {
        ll mid=(l+r)>>1;
        if(yuan[mid].qishi<=x)ans=mid,l=mid+1;
        else r=mid-1;
    }
    return yuan[ans];
}

除了这两个函数之外，还有 in，out，ins，outs，分别是快读整型、快输整型、快读字符串和快输字符串。

接下来是重点。

操作 1

定义一个结构体，不占内存。输出该结构体的大小和对齐要求。

string name=ins(); // 读入结构体名字 
ll geshu=in(); // 读入成员个数 
str[++str_count].geshu=geshu;
str[str_count].name=name;
yingshe_str[name]=str_count; // 映射值 
ll pianyi=0; // 每个成员在结构体中的地址偏移量 
for(ll i=1;i<=geshu;i++)
{
    string leixing=ins(),name=ins(); // 成员的类型和名字 
    ll bigg=0; // 计算对齐要求 
    if(leixing=="byte")bigg=1;
    else if(leixing=="short")bigg=2;
    else if(leixing=="int")bigg=4;
    else if(leixing=="long")bigg=8;
    else bigg=str[yingshe_str[leixing]].duiqiyaoqiu;
    str[str_count].member.push_back((yuansu){leixing,name,big(leixing),(ll)(-1)}); // 添加一个成员 
    str[str_count].duiqiyaoqiu=max(str[str_count].duiqiyaoqiu,bigg); // 对齐要求取成员对齐要求的最大值 
    pianyi=ceil((long double)pianyi/bigg)*bigg; // 地址偏移，见题目提示，自行理解 
    // update on 2024.8.23：开 long double
    str[str_count].pianyi.push_back(pianyi);
    pianyi+=big(leixing); // 偏移量加上大小就是下一个成员的偏移量 
}
pianyi=ceil((long double)pianyi/str[str_count].duiqiyaoqiu)*str[str_count].duiqiyaoqiu; // 偏移量增加，见题目提示，自行理解 
// update on 2024.8.23：开 long double
str[str_count].daxiao=pianyi; // 结构体大小就是总的偏移量 
out(pianyi),putchar(' '),out(str[str_count].duiqiyaoqiu); // 按要求输出

操作 2

定义一个普通变量或结构体变量，占相应内存。输出这个变量在内存中的起始位置。

string leixing=ins(),name=ins(); // 变量的类型和名字 
yuan[++yuan_count].leixing=leixing;
yuan[yuan_count].name=name;
ll daxiao=big(leixing),bigg=0; // 该变量的大小和对齐要求
// 这里题目没有要求计算对齐要求，但是这是为了地址偏移量而计算的 
if(leixing=="byte")bigg=1;
else if(leixing=="short")bigg=2;
else if(leixing=="int")bigg=4;
else if(leixing=="long")bigg=8;
else bigg=str[yingshe_str[leixing]].duiqiyaoqiu;
yuan[yuan_count].daxiao=daxiao;
neicun=ceil((long double)neicun/bigg)*bigg; // 内存偏移 
// update on 2024.8.23：开 long double
yuan[yuan_count].qishi=neicun; // 起始位置 
yingshe_yuan[name]=yuan_count; // 映射 
out(neicun),neicun+=daxiao; // 按要求输出，内存加上变量大小就是下一个变量的起始位置

操作 3

查询某个元素在内存中的起始位置。

从操作 3 开始就会稍微有点难以理解，请仔细阅读代码。

string y=ins();y+='.'; // 输入查询的元素，末尾加上 . 方便处理 
string name="",leixing=""; // 循环查找时 元素的名字和类型 
ll ans=0,i=0;
// 由于元素是 变量 + 多个结构体中的成员 组成的，所以分两个循环写 
for(i=0;i<y.size();i++) // 找变量 
    if(y[i]=='.')
    {
        yuansu t=yuan[yingshe_yuan[name]]; // 找到这个变量 
        ans=t.qishi;
        leixing=t.leixing;
        name="";
        break;
    }
    else name+=y[i];
for(i++;i<y.size();i++) // 这个循环有递归的思想，不懂的话可以拿样例模拟一下 
    if(y[i]=='.')
    {
        struc t=str[yingshe_str[leixing]];
        for(ll j=0;j<t.geshu;j++) // 找成员 
            if(t.member.at(j).name==name) // 找到成员 
            {
                ans+=t.pianyi.at(j); // 加上偏移量 
                leixing=t.member.at(j).leixing; // 类型改变，准备下一次在新的类型中查找
                break;
            }
        name="";
    }
    else name+=y[i];
out(ans); // 按要求输出

操作 4

查询内存中某个位置的元素是什么，如果这个位置没有元素，输出 ERR。

这个操作是最难写的也是最难读懂代码的。

ll addr=in();
if(addr>=neicun) // 如果输入的内存大于当前的内存，那肯定是没有元素的 
{
    outs("ERR"),putchar('\n');
    continue;
}
yuansu t=find1(addr); // 找到最接近且不超过 查询的内存 的单个变量 
// 由于内存是按顺序分配的，所以满足单调性，可以二分查找 
string ans="";
ans+=t.name;
string leixing=t.leixing;
ll weizhi=t.qishi; // 现在循环到内存的位置 
bool ff=true;
if(leixing=="byte"||leixing=="short"||leixing=="int"||leixing=="long") // 注意这个特判，删了只有 85 分 
    if(weizhi+big(leixing)<=addr)ff=false; // 这个特判的意思是，如果找到的变量的类型不是结构体（即普通变量）
    // 那么如果变量起始位置加上变量的大小，没有到达查询的位置，说明查询的位置在当前变量与下一个变量的空隙中，输出 ERR 
while(leixing!="byte"&&leixing!="short"&&leixing!="int"&&leixing!="long"&&ff) // 一直找，找到成员是普通元素为止 
// 这个循环可以参照操作 3 的循环来思考，也是有递归的思想 
{
    struc tt=str[yingshe_str[leixing]]; // 找到这个结构体 
    ll i;
    for(i=0;i<tt.geshu;i++) // 遍历成员 
    {
        if(weizhi+tt.pianyi.at(i)>addr) // 如果当前成员的位置已经大于查询的位置，说明在前面没有找到相应的元素
        //（即查询的位置在当前成员和上一个成员的空隙中），输出 ERR 
        {
            ff=false;
            break;
        }
        ll daxiao=tt.member.at(i).daxiao;
        if(weizhi+tt.pianyi.at(i)+daxiao>addr) // 如果当前成员的位置小于查询位置，加上大小后又大于查询位置
        // 说明这个元素包裹了查询位置，于是就进入下一个结构体中继续细分 
        // 注意这里的大于号如果写成大于等于就只有 15 分 
        {
            string lx=tt.member.at(i).leixing;
            leixing=lx; // 改变类型，继续细分，找到不能找为止 
            weizhi+=tt.pianyi.at(i); // 记得加上偏移量 
            ans+="."+tt.member.at(i).name;
            break;
        }
    }
    if(i==tt.geshu)ff=false; // 这个删了就会死循环超时
    // 1. 从代码角度来解释：在循环中没有找到相应的元素，是 i 超过范围退出循环的，不是 break 的
    // 所以类型一直没有改变，所以最外层的循环会死循环
    // 2. 从题目角度来解释：循环中没找到，查询位置肯定是在 当前元素的最后一个成员 与 内存中下一个元素
    // （如果下一个元素是结构体的话，那就是下一个元素的第一个成员）的空隙中，输出 ERR 
}
if(!ff)outs("ERR"); // 不符合要求，输出 ERR 
else outs(ans);

完整 AC 代码（赛后重构代码）

非赛时代码，考场上我没写出来，喜提 5 pts。

由于代码较长，就放云剪贴板里面。

Code。

鬼知道我调了多久代码。

另：附上 @zymooll 大佬写的数据生成器，可以用来对拍。~~（我就是用这个东西与正解对拍才把我的代码改成正解的）~~

// Author:zymooll

#include<bits/stdc++.h>

#if defined(__linux__)
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#elif defined(_WIN32)
#define getchar _getchar_nolock
#define putchar _putchar_nolock
#endif

#define int long long
using namespace std;

const int n = 100;
const int k = 100;
const int slen = 10;
const bool A = 0;
const bool B = 0;
const bool C = 0;
const bool D = 0;

int tot1 = 0;//记录 1 操作的总次数
map<string, int>mp;//结构体名称映射
map<string, bool>vis;//标记成员的出现情况

struct S{
  string nam;
  vector<pair<int, string> >mem;
};
vector<S>stru;//记录随机出的

random_device rd;
mt19937_64 mt;

void init(){
  mt.seed(rd());
  stru.push_back((S){ "", vector<pair<int, string> >() });
  stru.push_back((S){ "byte", vector<pair<int, string> >() }); mp["byte"] = 1;
  stru.push_back((S){ "short", vector<pair<int, string> >() }); mp["short"] = 2;
  stru.push_back((S){ "int", vector<pair<int, string> >() }); mp["int"] = 3;
  stru.push_back((S){ "long", vector<pair<int, string> >() }); mp["long"] = 4;
}
int getOperation(){//获取随机的操作
  if(A || (B && tot1)){
    if(stru[0].mem.empty()){//2,4
      int ret = mt() % 2;
      if(ret == 0)ret = 2;
      else ret = 4;
      return ret;//define element
    }
    else{//2,3,4
      return 2 + mt() % 3;
    }
  }
  else if(stru[0].mem.empty()){//1,2,4
    int ret = 1 + mt() % 2;
    if(ret == 3)ret = 4;
    if(ret == 1)tot1++;
    return ret;
  }
  else{//1,2,3,4
    int ret = 1 + mt() % 4;
    if(ret == 1)tot1++;
    return ret;
  }
}
int getType(bool _instru){//获取随机的元素，其中返回值代表结构体 id （_instru 代表是否获取的是结构体内元素）
  if(D)return 4 + mt() % (stru.size() - 4);
  if(C && _instru)return 1 + mt() % 4;
  return 1 + mt() % (stru.size() - 1);
}
string getRamdomString(){//获得一个未出现过的字符串
  string ret;
  for(int i = 0; i < slen; i++){
    ret += 'a' + mt() % 26;
  }
  while(mp[ret] || vis[ret]){
    int pos = mt() % slen;
    ret[pos] = 'a' + mt() % 26;
  }
  return ret;
}

signed main(){
  // freopen(".in", "r", stdin);
  freopen("data.out", "w", stdout);
  init();
  cout << n << endl;
  for(int kk = 1; kk <= n; kk++){
    int opt = getOperation();
    cout << opt << " ";
    // cerr << kk << " " << opt << endl;
    if(opt == 1){
      vis.clear();
      S ls;//临时
      string name = getRamdomString();
      int num = 1 + mt() % k;
      cout << name << " " << num << endl;
      ls.nam = name;
      for(int i = 1; i <= num; i++){
        int type = getType(true);
        string elename = getRamdomString();
        vis[elename] = 1;
        cout << stru[type].nam << " " << elename << endl;
        ls.mem.push_back(make_pair(type, elename));
      }
      stru.push_back(ls);
    }
    else if(opt == 2){
      int type = getType(false);
      string name = getRamdomString();
      stru[0].mem.push_back(make_pair(type, name));
      cout << stru[type].nam << " " << name << endl;
    }
    else if(opt == 3){
      int u = 0;
      string outp = "";
      while(1){
        int pos = mt() % stru[u].mem.size();
        if(u)outp += ".";
        outp += stru[u].mem[pos].second;
        // cerr << " - " << pos << " " << outp << endl;
        if(stru[u].mem[pos].first <= 4){//是基本元素
          break;
        }
        u = stru[u].mem[pos].first;
      }
      cout << outp << endl;
    }
    else{
      cout << mt() % (8 * kk) << endl;
    }
    cout << endl;
  }
  return 0;
}

注意事项：

十年 OI 一场空，不开 long long 见祖宗！

十年 OI 一场空，不考 long double 见祖宗！（update on 2024.8.23）

大模拟非常考验码力，要养成良好习惯，包括命名规范，代码可读性，风格等等，不要出现 代码写着写着自己都不知道某行代码或者某个变量什么意思 之类的情况，必要时可以在代码中添加注释，让自己理解代码含义。

后记 2：写代码的习惯一定要好，代码不要乱七八糟，优秀的码风是很醉人的 QWQ。

注：数据生成器转载与此。

顺便推荐一下本蒟蒻的游记。

P9754 [CSP-S 2023] 结构体 题解

P9754 [CSP-S 2023] 结构体 题解

本题解有数据生成器！（虽然是转载的）

题意

分析

准备工作

操作 1

操作 2

操作 3

操作 4

完整 AC 代码（赛后重构代码）

P9754 [CSP-S 2023] 结构体题解

P9754 [CSP-S 2023] 结构体题解