S 组 T3 正解 95pts 求调(有注释)
  • 板块学术版
  • 楼主picha
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/10/22 15:50
  • 上次更新2023/11/2 11:53:09
查看原帖
S 组 T3 正解 95pts 求调(有注释)
677124
picha楼主2023/10/22 15:50

洛谷上 9595 pts,云斗 8585 pts,都是 17∼2017 \sim 20 测试点里面有 WA 的,求调。马蜂有点奇怪,请不要介意。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 1000;
const ll N = maxn + 10;
ll n, m, cnt, l; // cnt 是类型编号的最大值,l 是最大地址 + 1
unordered_map<string, ll> bianhao; // 给类型编号
struct jiedian{ // 存储结构体里面的元素
	string p, q; // p 是类型名,q 是变量名
};
vector<jiedian> erzi[N]; // 存储结构体里面的元素
ll duiqi[N], daxiao[N]; // duiqi[i] 是编号为 i 的类型的对齐要求,daxiao[i] 是编号为 i 的类型所占据的大小。
struct jiedian1{ // 处理 opt3, opt4 时用,比 jiedian 额外存储起始地址
	string p, q; // p 是类型名,q 是变量名
	ll x; // x 是起始地址
};
vector<jiedian1> f; // 最外层定义的元素(即 opt2 定义的元素)
string ans, a[N]; // ans 存储 opt4 的答案,a 存储 opt3 中输入的字符串拆分开来
ll calc(ll x, ll y) { // 当前第一个空的地址为 x,下一个要放的元素的对其要求为 y,求下一个要放的元素的起始地址
	return (x + y - 1) / y * y;
}
ll rd() {
	char ch = getchar();
	ll s = 0, w = 1;
	while (ch < '0' || ch > '9') {
		if (ch == '-') {
			w = -1;
		}
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		s = (s << 3) + (s << 1) + (ch ^ 48);
		ch = getchar();
	}
	return (s * w);
}
void rd_str(string &s) { // 字符串快读
	char ch = getchar();
	s = "";
	while (!((ch >= 'a' && ch <= 'z') || ch == '.')) {
		ch = getchar();
	}
	while ((ch >= 'a' && ch <= 'z') || ch == '.') {
		s += ch;
		ch = getchar();
	}
}
void print(ll x) {
	if (x < 0) {
		putchar('-');
		x = -x;
	}
	if (x <= 9) {
		putchar(x + 48);
		return;
	}
	print(x / 10);
	putchar(x % 10 + 48);
}
ll fenjie(string s) { // opt3 中将读入的字符串按 '.' 拆分成若干个字符串
	ll t = 1;
	a[1] = "";
	for (ll i = 0; i < (ll)(s.length()); ++i) {
		if (s[i] == '.') {
			++t;
			a[t] = "";
		}
		else {
			a[t] += s[i];
		}
	}
	return t;
}
int main() {
	n = rd();
	// 给 4 种基本类型编号
	bianhao["byte"] = 1;
	duiqi[1] = 1;
	daxiao[1] = 1;
	bianhao["short"] = 2;
	duiqi[2] = 2;
	daxiao[2] = 2;
	bianhao["int"] = 3;
	duiqi[3] = 4;
	daxiao[3] = 4;
	bianhao["long"] = 4;
	duiqi[4] = 8;
	daxiao[4] = 8;
	cnt = 4;
	l = 0;
	{ll opt, k;
	string s, t, u;
	for (ll qq = 1; qq <= n; ++qq) {
		opt = rd();
		if (opt == 1) {
			rd_str(s); k = rd();
			bianhao[s] = ++cnt; // 对其进行编号
			duiqi[cnt] = 0;
			daxiao[cnt] = 0;
			ll y = 0;
			for (ll i = 1; i <= k; ++i) { // 读入结构体内部的元素
				rd_str(t); rd_str(u);
				erzi[cnt].push_back((jiedian){t, u}); // 用 vector 存储
				ll x = bianhao[t]; // x 表示这个元素的类型的编号
				duiqi[cnt] = max(duiqi[cnt], duiqi[x]);
				ll v = calc(y, duiqi[x]); // 计算这个元素的起始地址
				y = v + daxiao[x]; // 更新地址最大值 + 1
			}
			daxiao[cnt] = calc(y, duiqi[cnt]); // 计算整个结构体的大小
			printf("%lld %lld\n", daxiao[cnt], duiqi[cnt]);
		}
		else if (opt == 2) {
			rd_str(s); rd_str(t);
			ll y = bianhao[s];
			ll x = calc(l, duiqi[y]); // 计算这个元素的起始地址
			f.push_back((jiedian1){s, t, x}); // 将这个元素插入 f,留给 opt3, opt4 备用
			l = x + daxiao[y]; // 更新 l
			printf("%lld\n", x);
		}
		else if (opt == 3) {
			rd_str(s);
			ll y;
			y = fenjie(s); // 将读入的字符串拆开来
			jiedian1 p;
			for (auto i : f) { // 找到名称相符的元素,存到 p 里面
				if (i.q == a[1]) {
					p = i;
					break;
				}
			}
			ll w = p.x; // w 存储起始地址
			for (ll i = 2; i <= y; ++i) { // 一层一层处理
				jiedian1 q;
				ll x = bianhao[p.p];
				for (auto j : erzi[x]) { // 找到名称相符的元素并计算起始地址,存储到 q 里面
					ll pp = bianhao[j.p];
					ll v = calc(w, duiqi[pp]); // 计算新的起始地址
					if (j.q == a[i]) {
						q = (jiedian1){j.p, j.q, v};
						break;
					}
					w = v + daxiao[pp];
				}
				p = q;
			}
			cout << p.x << endl;
		}
		else {
			k = rd();
			jiedian1 p;
			for (auto i : f) { // 找到这个地址所在的元素,根据起始地址判断,找到最后一个起始地址小于 k 的元素
				if (i.x <= k) {
					p = i;
				}
				else {
					break;
				}
			}
			if (p.x + daxiao[bianhao[p.p]] - 1 < k) { // 在空洞里或超出了最大地址
				printf("ERR\n");
				continue;
			}
			ll w = p.x; // w 表示起始地址
			ll x = bianhao[p.p]; // x 表示这个元素的类型的编号
			ans = p.q; // 处理 ans
			bool z = 0;
			while (x > 4) { // 这个元素的类型不是基础类型
				jiedian1 q;
				for (auto j : erzi[x]) { // 找到这个地址所在的元素并重新计算起始地址,存储到 q 里面
					ll pp = bianhao[j.p];
					ll v = calc(w, duiqi[pp]); // 计算新的起始地址
					if (v <= k) {
						q = (jiedian1){j.p, j.q, v};
					}
					else {
						break;
					}
					w = v + daxiao[pp];
				}
				p = q;
				x = bianhao[p.p];
				if (p.x + daxiao[x] - 1 < k) { // 在空洞里或超出了结构体内部的最大地址
					z = 1;
					break;
				}
				ans += "."; // 处理 ans
				ans += p.q;
				w = p.x;
			}
			if (z) {
				printf("ERR\n");
				continue;
			}
			cout << ans << endl;
		}
	}}
	return 0;
}
2023/10/22 15:50
加载中...