devbox
笔触狂放9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

AtCoder Beginner Contest 319(D-G)_abc319gcounting shortest pathsc++

作者：笔触狂放9 | 2024-02-10 13:56:11

赞

踩

abc319gcounting shortest pathsc++

D.Tasks - AtCoder Beginner Contest 319

        （1）题意

                给你一个M行得框框和N个单词，每个单词有一个宽度，每个单词之间应该用一个空格隔开，首位单词不需要，问至少需要多宽才能使得单词不会超过M行。

        （2）解题思路

                直接二分宽度，然后check即可。

        （3）代码实现

  1. #include <bits/stdc++.h>
  2. #define rep(i,z,n) for(int i = z;i <= n; i++)
  3. #define per(i,n,z) for(int i = n;i >= z; i--)
  4. #define PII pair<int,int>
  5. #define fi first
  6. #define se second
  7. #define vi vector<int>
  8. #define vl vector<ll>
  9. #define pb push_back
  10. #define sz(x) (int)x.size()
  11. #define all(x) (x).begin(),(x).end()
  12. using namespace std;
  13. using ll = long long;
  14. const int N = 2e5 + 10;
  15. int L[N];
  16. int n,m;
  17. bool check(ll k)
  18. {
  19.     int cnt = 0;
  20.     ll cur = 0;
  21.     rep(i,1,n) {
  22.         if(k < L[i]) {
  23.             return false;
  24.         }
  25.     }
  26.     rep(i,1,n) {
  27.         if(cur - L[i] - 1 >= 0) {
  28.             cur -= L[i] + 1;
  29.         }
  30.         else {
  31.             cur = k - L[i];
  32.             cnt ++;
  33.         }
  34.     }
  35.     // cout << "???" << k << '\n';
  36.     return cnt <= m;
  37. }
  38. void solve()
  39. {
  40.     cin >> n >> m;
  41.     for(int i = 1;i <= n;i ++) {
  42.         cin >> L[i];
  43.     }
  44.     ll l = 1,r = 1e18;
  45.     while(l <= r) {
  46.         ll mid = (l + r) >> 1;
  47.         if(check(mid)) r = mid - 1;
  48.         else l = mid + 1;
  49.     }
  50.     cout << l << endl;
  51. }
  52. int main()
  53. {
  54.     ios::sync_with_stdio(false);
  55.     cin.tie(0),cout.tie(0);
  56.     int T = 1;
  57.     // cin >> T;
  58.     while(T --) solve();
  59.     return 0;
  60. }

E - Bus Stops (atcoder.jp)

        （1）题意

                A要从自己家到B家，中间得路段构成是A先走一段路到达站点1，然后做公交到站点n，最后走一段路到B家，每一个站点得公交车会在P[i]倍数得时间发车，需要T[i]得时间才能到达下一个站，现在有q个询问，每个询问给定你起始时间，问最后达到B家得最小时间是多少。

        （2）解题思路

                考虑每一个P[i]得倍数都会有一些余数，不妨把他们得最小公倍数求出来，然后预处理出0-最小公倍数得起始时间需要花费多少时间到达B家。

        （3）代码实现

  1. #include <bits/stdc++.h>
  2. #define rep(i,z,n) for(int i = z;i <= n; i++)
  3. #define per(i,n,z) for(int i = n;i >= z; i--)
  4. #define PII pair<int,int>
  5. #define fi first
  6. #define se second
  7. #define vi vector<int>
  8. #define vl vector<ll>
  9. #define pb push_back
  10. #define sz(x) (int)x.size()
  11. #define all(x) (x).begin(),(x).end()
  12. using namespace std;
  13. using ll = long long;
  14. const int N = 2e5 + 10;
  15. int p[N],t[N];
  16. ll Ans[N];
  17. int n,x,y;
  18. ll calc(ll st)
  19. {
  20.     st += x;
  21.     for(int i = 1;i < n;i ++) {
  22.         int z = st % p[i];
  23.         if(!z) z = p[i];
  24.         st += p[i] - z;
  25.         st += t[i];
  26.     }
  27.     return st + y;
  28. }
  29. void solve()
  30. {
  31.     cin >> n >> x >> y;
  32.     set<int> pt;
  33.     for(int i = 1;i < n;i ++) {
  34.         cin >> p[i] >> t[i];
  35.         pt.insert(p[i]);
  36.     }
  37.     int cur = 0;
  38.     for(auto x : pt) {
  39.         if(!cur) cur = x;
  40.         else cur = cur * x / __gcd(cur,x);
  41.     }
  42.     for(int i = 0;i < cur;i ++) {
  43.         Ans[i] = calc(i);
  44.     }
  45.     int q;
  46.     cin >> q;
  47.     for(int i = 1;i <= q;i ++) {
  48.         ll v;
  49.         cin >> v;
  50.         int p = v % cur;
  51.         cout << v - p + Ans[p] << '\n';
  52.     }
  53. }
  54. int main()
  55. {
  56.     ios::sync_with_stdio(false);
  57.     cin.tie(0),cout.tie(0);
  58.     int T = 1;
  59.     // cin >> T;
  60.     while(T --) solve();
  61.     return 0;
  62. }

F - Fighter Takahashi (atcoder.jp)

        （1）题意

                你在一颗树上战斗，起初你的战斗力是1，树上每个点要么是药剂，要么是怪兽，如果是怪兽，你的战斗力大于等于他就可以击败他获取奖励战斗力，如果是药剂你可以使你得战斗力翻g[i]倍，现在问你是否可以从1号节点战败所有怪兽。

        （2）解题思路

                首先，若是你当前得实力够打怪兽，那么一定是先打得，如果不够了才考虑用药剂。那么一个很明显得思路是，确定一个吃药得顺序，然后bfs一遍看看能不能打完所有怪兽，那么时间复杂度显然是不太行得。所以我们考虑使用状压dp优化这个枚举吃药顺序得过程，状态dp[i]表示吃了i这些药最高能到得战斗力是多少，最后判一下是否大于等于最高战斗力得怪兽即可。

        （3）代码实现

  1. #include <bits/stdc++.h>
  2. #define rep(i,z,n) for(int i = z;i <= n; i++)
  3. #define per(i,n,z) for(int i = n;i >= z; i--)
  4. #define PII pair<int,int>
  5. #define fi first
  6. #define se second
  7. #define vi vector<int>
  8. #define vl vector<ll>
  9. #define pb push_back
  10. #define sz(x) (int)x.size()
  11. #define all(x) (x).begin(),(x).end()
  12. using namespace std;
  13. using ll = long long;
  14. const int N = 505;
  15. int t[N],s[N],g[N],p[N];
  16. vector<int> e[N];
  17. ll dp[1<<(10)];
  18. void solve()
  19. {
  20.     int n,tot = 0;
  21.     cin >> n;
  22.     vector<int> med,pos(n + 1,0);
  23.     int master = 0;
  24.     rep(i,2,n) {
  25.         cin >> p[i] >> t[i] >> s[i] >> g[i];
  26.         if(t[i] == 2) {
  27.             med.pb(i);
  28.             pos[i] = sz(med) - 1;
  29.             tot ++;
  30.         }
  31.         master = max(master,s[i]);
  32.         e[p[i]].pb(i);
  33.     }
  34.     memset(dp,-1,sizeof(dp));
  35.     //dp[i]：表示吃了这些药能达到最大得能量值
  36.     dp[0] = 1;
  37.     rep(i,0,(1<<tot)-1) {
  38.         if(dp[i] != -1) {
  39.             priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> q;
  40.             q.push({-1,1});
  41.             vector<bool> used(sz(med),false);
  42.             int cnt = 0;
  43.             ll S = 0;
  44.             while(!q.empty()) {
  45.                 auto [val,ver] = q.top();
  46.                 q.pop();
  47.                 if(val > dp[i]) break;
  48.                 cnt ++;
  49.                 if(t[ver] == 2 && !(i >> pos[ver] & 1)) {
  50.                     used[pos[ver]] = true;
  51.                     continue;
  52.                 }
  53.                 if(t[ver] == 1) {
  54.                     dp[i] += g[ver];
  55.                     S += g[ver];
  56.                 }
  57.                 for(auto v : e[ver]) {
  58.                     if(t[v] == 2) q.push({-1,v});
  59.                     else q.push({s[v],v}); 
  60.                 }
  61.             }
  62.             // cout << i << ' ' << dp[i] << '\n';
  63.             if(dp[i] >= master || cnt == n) {
  64.                 cout << "Yes" << '\n';
  65.                 return;
  66.             }
  67.             rep(j,0,tot-1) {
  68.                 if(used[j]) {
  69.                     dp[i | (1 << j)] = max(dp[i | (1 << j)],dp[i] * g[med[j]] - S);
  70.                 }
  71.             }
  72.         }
  73.     }
  74.     cout << "No" << '\n';
  75. }
  76. int main()
  77. {
  78.     ios::sync_with_stdio(false);
  79.     cin.tie(0),cout.tie(0);
  80.     int T = 1;
  81.     // cin >> T;
  82.     while(T --) solve();
  83.     return 0;
  84. }

G - Counting Shortest Paths (atcoder.jp)

        （1）题意

                给你一个完全图，删除一些边后，问你是否能从1-N，如果能，请给出最短路径数量。

        （2）解题思路

               P1. 首先对于最短路径，我们考虑01bfs得特性，一旦有一个点进入了则不会再进入一次，因此我们可以用一个set维护一下未进入得点集，每次对于一个进入得点，扫描一下未进入得点集，若这个点和进入得点之间得边未删除，则可以把这个点加入队列，这样就可以很快得求得最短路径。

               P2.现在我们需要考虑路径数量得问题了，考虑将图分成如下形式。

                考虑dp[i]，表示i为最短路径上的点的方案数是多少。那么显然对于点集为2的点dp[i]等价于所有点集为1的点的方案和-i不能到达的点集为1的点的方案,依次类推求出dp[n]即可。

        （3）代码实现

  1. #include <bits/stdc++.h>
  2. #define rep(i,z,n) for(int i = z;i <= n; i++)
  3. #define per(i,n,z) for(int i = n;i >= z; i--)
  4. #define PII pair<int,int>
  5. #define fi first
  6. #define se second
  7. #define vi vector<int>
  8. #define vl vector<ll>
  9. #define pb push_back
  10. #define sz(x) (int)x.size()
  11. #define all(x) (x).begin(),(x).end()
  12. using namespace std;
  13. using ll = long long;
  14. const int N = 2e5 + 10;
  15. set<int> e[N],g[N],pos;
  16. int dis[N];
  17. using i64 = long long;
  18.  
  19. constexpr int P = 998244353;
  20. // assume -P <= x < 2P
  21. int Vnorm(int x) {
  22.     if (x < 0) {
  23.         x += P;
  24.     }
  25.     if (x >= P) {
  26.         x -= P;
  27.     }
  28.     return x;
  29. }
  30. template<class T>
  31. T power(T a, i64 b) {
  32.     T res = 1;
  33.     for (; b; b /= 2, a *= a) {
  34.         if (b % 2) {
  35.             res *= a;
  36.         }
  37.     }
  38.     return res;
  39. }
  40. struct Mint {
  41.     int x;
  42.     Mint(int x = 0) : x(Vnorm(x)) {}
  43.     Mint(i64 x) : x(Vnorm(x % P)) {}
  44.     int val() const {
  45.         return x;
  46.     }
  47.     Mint operator-() const {
  48.         return Mint(Vnorm(P - x));
  49.     }
  50.     Mint inv() const {
  51.         assert(x != 0);
  52.         return power(*this, P - 2);
  53.     }
  54.     Mint &operator*=(const Mint &rhs) {
  55.         x = i64(x) * rhs.x % P;
  56.         return *this;
  57.     }
  58.     Mint &operator+=(const Mint &rhs) {
  59.         x = Vnorm(x + rhs.x);
  60.         return *this;
  61.     }
  62.     Mint &operator-=(const Mint &rhs) {
  63.         x = Vnorm(x - rhs.x);
  64.         return *this;
  65.     }
  66.     Mint &operator/=(const Mint &rhs) {
  67.         return *this *= rhs.inv();
  68.     }
  69.     friend Mint operator*(const Mint &lhs, const Mint &rhs) {
  70.         Mint res = lhs;
  71.         res *= rhs;
  72.         return res;
  73.     }
  74.     friend Mint operator+(const Mint &lhs, const Mint &rhs) {
  75.         Mint res = lhs;
  76.         res += rhs;
  77.         return res;
  78.     }
  79.     friend Mint operator-(const Mint &lhs, const Mint &rhs) {
  80.         Mint res = lhs;
  81.         res -= rhs;
  82.         return res;
  83.     }
  84.     friend Mint operator/(const Mint &lhs, const Mint &rhs) {
  85.         Mint res = lhs;
  86.         res /= rhs;
  87.         return res;
  88.     }
  89.     friend std::istream &operator>>(std::istream &is, Mint &a) {
  90.         i64 v;
  91.         is >> v;
  92.         a = Mint(v);
  93.         return is;
  94.     }
  95.     friend std::ostream &operator<<(std::ostream &os, const Mint &a) {
  96.         return os << a.val();
  97.     }
  98. };
  99. void solve()
  100. {
  101.     int n,m;
  102.     cin >> n >> m;
  103.     for(int i = 1;i <= m;i ++) {
  104.         int u,v;
  105.         cin >> u >> v;
  106.         e[u].insert(v);
  107.         e[v].insert(u);
  108.     }
  109.     for(int i = 2;i <= n;i ++) {
  110.         pos.insert(i);
  111.     }
  112.     memset(dis,0x3f,sizeof(dis));
  113.     dis[1] = 0;
  114.     queue<int> q;
  115.     q.push(1);
  116.     while(!q.empty()) {
  117.         int v = q.front();
  118.         q.pop();
  119.         auto nps = pos;
  120.         for(auto x : nps) {
  121.             if(!e[v].count(x) && pos.count(x)) {
  122.                 dis[x] = dis[v] + 1;
  123.                 pos.erase(x);
  124.                 q.push(x);
  125.             }
  126.         }
  127.     }
  128.     if(dis[n] >= n) {
  129.         cout << -1 << '\n';
  130.         return;
  131.     }
  132.     for(int i = 1;i <= n;i ++) {
  133.         if(dis[i] <= n) g[dis[i]].insert(i);
  134.     }
  135.     vector<Mint> dp(n + 1,0),s(n + 1,0);
  136.     dp[1] = 1;
  137.     for(int i = 0;i < n;i ++) {
  138.         if(i >= 1) {
  139.             for(auto x : g[i]) {
  140.                 dp[x] += s[i];
  141.             }
  142.         }
  143.         for(auto x : g[i]) {
  144.             s[i + 1] += dp[x];
  145.             for(auto y : e[x]) {
  146.                 if(dis[y] == dis[x] + 1) {
  147.                     dp[y] -= dp[x];
  148.                 }
  149.             }
  150.         }
  151.     }
  152.     cout << dp[n];
  153. }
  154. int main()
  155. {
  156.     ios::sync_with_stdio(false);
  157.     cin.tie(0),cout.tie(0);
  158.     int T = 1;
  159.     // cin >> T;
  160.     while(T --) solve();
  161.     return 0;
  162. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/74405
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号