锐客网

  1. 首页 > it技术 > >

#|【牛客】牛客练习赛67-E-牛妹游历城市——位运算优化

图论#ACM

【#|【牛客】牛客练习赛67-E-牛妹游历城市——位运算优化】题面链接
大致题意 给出n n n 个节点的权值，如果两个点的权值a n d and and 的结果不为0 0 0 则认为这两个点之间有边相连，且边权为l o w b i t ( a & b ) lowbit(a \& b) lowbit(a&b) 求问从1 1 1 走到n n n 点，最短路径为多少
分析 首先不能暴力 因为点数有1 0 5 10^5 105 个，所有可能的边的数量为1 0 5 ? ( 1 0 5 ? 1 ) / 2 ≈ 1 0 10 10^5 * (10^5-1) / 2 \approx 10^{10} 105?(105?1)/2≈1010
考虑位运算优化 我们准备出 32 个组，对于每一个值，如果这个值a a a 在位置i i i 上有值，即a & ( 1 < < i ) ≠ 0 a \& (1 << i ) \neq 0 a&(1< 对于每个组，我们再定义一个变量表示到达组i i i 中的值需要的边权价值t t t， t ≥ ( 1 < < i ) t \geq (1 << i) t≥(1< 对于起点1 1 1 ，我们考虑它的每一个位，如果位i i i 上有值，则认为到达这个位置的组中的其他所有值需要花费( 1 < < i ) (1 << i) (1< 最后考虑最终点的每一位，找出花费最少的位并输出即可
注意特判起点和终点相同的时候
AC code

#include using namespace std; typedef long long ll; // NOLINTNEXTLINE ll lowBit(ll x) { return x & (-x); }void solve() { ll _; cin >> _; for (ll ts = 0; ts < _; ++ts) { ll n; cin >> n; vector data[40]; vector cost(40, LONG_LONG_MAX); vector a(n); for (ll i = 0; i < n; ++i) { cin >> a[i]; for (ll j = 0; j < 40; ++j) // NOLINTNEXTLINE if (a[i] & (1ll << j)) data[j].push_back(i); } if (n == 1) { cout << 0 << endl; continue; } queue q; for (ll i = 0; i < 40; ++i) { // NOLINTNEXTLINE if (a[0] & (1ll << i)) { q.push(i); // NOLINTNEXTLINE cost[i] = 1ll << i; } }while (!q.empty()) { ll cur = q.front(); q.pop(); for (auto item : data[cur]) { for (ll i = 0; i < 40; ++i) { // NOLINTNEXTLINE if ((a[item] & (1ll << i)) && cost[i] > (1ll << i) + cost[cur]) { q.push(i); // NOLINTNEXTLINE cost[i] = (1ll << i) + cost[cur]; } } } }ll ans = LONG_LONG_MAX; for (ll i = 0; i < 40; ++i) { // NOLINTNEXTLINE if (a[n - 1] & (1ll << i)) { ans = min(ans, cost[i]); } }if (ans == LONG_LONG_MAX) cout << "Impossible" << endl; else cout << ans << 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; }

    推荐阅读


    上一篇：牛牛与牛妹的游戏

    下一篇：【LeetCode】搜索插入位置