题目链接这题我能过全因为出题人的英语水平高(滑稽
题目大意
算了我也懒得写大意了,慢慢看吧
分析
这道题的关键在于理解下面两句话
for every object o accessible via A, the member variable f of o can point to every object accesible via B
for every object o accessible via B, A can point to every object accessible via the member variable f of o
直接翻译过来就是
对于用指针A指向的所有对象o,对象o的成员变量f指向所有指针B所指向的对象
对于用指针B指向的所有对象o,指针A可以指向所有的对象o的成员变量f所指向的对象
好的我被绕晕了
加个括号
对于(用指针A指向的所有对象o),(对象o的成员变量f)指向所有(指针B所指向的对象)
对于(用指针B指向的所有对象o),(指针A)可以指向{所有的【(对象o的成员变量f)所指向的对象】}
分析两个例子
A = a
B.f = A
C = B.f
这个例子的结果应该是仅有
虽然 且 但是 指针没有指向任何东西,所以,对于第二条规则中“(用指针B指向的所有对象o)”这一条无法成立,即对象 不存在
第二个例子
A = a
B = a
B.f = A
C = A.f
这个例子的结果应该是
首先是第三行 而 ,根据第一条规则,对象 即为 ,即 ,所以到 处, 所以 也可以指向
方法
建立类似图的结构,不断的更新所有指针能够指向的内容,同时将指针的指向下推至对象的成员函数
AC code
#include<bits/stdc++.h> using namespace std; struct Obj { set<int> member[26]; } obj[26]; struct var { bitset<26> asset; vector<int> member[26]; vector<int> liVa; vector<pair<int, int>> liOb; } var[26]; bool check(int cur) { bool flag = false; // A = B for (auto item : var[cur].liVa) { for (int i = 0; i < 26; ++i) { if (!var[cur].asset.test(i) && var[item].asset.test(i)) { flag = true; var[cur].asset.set(i); } } } // A = B.a for (auto item : var[cur].liOb) { // 对于每一个 o in B for (int i = 0; i < 26; ++i) { if (var[item.first].asset.test(i)) { auto &o = obj[i]; for (auto toLink : o.member[item.second]) { for (int j = 0; j < 26; ++j) { if (!var[cur].asset.test(j) && var[toLink].asset.test(j)) { flag = true; var[cur].asset.set(j); } } } } } } return flag; } void push(int cur) { for (int i = 0; i < 26; ++i) { if (var[cur].asset.test(i)) { for (int j = 0; j < 26; ++j) { for (auto item : var[cur].member[j]) { obj[i].member[j].insert(item); } } } } } void solve() { int n; cin >> n; for (int i = 0; i < n; ++i) { string a, b, c; cin >> a >> b >> c; if (a.size() == 1 && c.size() == 1) { if (c[0] >= 'a' && c[0] <= 'z') { // A = a var[a[0] - 'A'].asset.set(c[0] - 'a'); } else { // A = B var[a[0] - 'A'].liVa.push_back(c[0] - 'A'); } } else if (a.size() == 3) { // A.a = B var[a[0] - 'A'].member[a[2] - 'a'].push_back(c[0] - 'A'); } else { // A = B.a var[a[0] - 'A'].liOb.push_back({c[0] - 'A', c[2] - 'a'}); } } bool flag = true; while (flag) { flag = false; for (int i = 0; i < 26; ++i) push(i); for (int i = 0; i < 26; ++i) if (check(i)) flag = true; } for (int i = 0; i < 26; ++i) { cout << (char) (i + 'A') << ": "; auto &A = var[i]; for (int j = 0; j < 26; ++j) if (A.asset.test(j)) cout << (char) (j + 'a'); cout << endl; } } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); #ifdef ACM_LOCAL freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); signed localTestCount = 1, localReadPos = cin.tellg(); char localTryReadChar; do { if (localTestCount > 20) throw runtime_error("Check the stdin!!!"); auto startClockForDebug = clock(); solve(); auto endClockForDebug = clock(); cout << "Test " << localTestCount << " successful" << endl; cerr << "Test " << localTestCount++ << " Run Time: " << double(endClockForDebug - startClockForDebug) / CLOCKS_PER_SEC << "s" << endl; cout << "--------------------------------------------------" << endl; } while (localReadPos != cin.tellg() && cin >> localTryReadChar && localTryReadChar != '$' && cin.putback(localTryReadChar)); #else solve(); #endif return 0; }