• AtCoder Beginner Contest 319(D-G)

    D.Tasks - AtCoder Beginner Contest 319

            （1）题意

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

            （2）解题思路

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

            （3）代码实现

    1. #include 
    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
    5. #define fi first
    6. #define se second
    7. #define vi vector
    8. #define vl vector
    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 
    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
    5. #define fi first
    6. #define se second
    7. #define vi vector
    8. #define vl vector
    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 
    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
    5. #define fi first
    6. #define se second
    7. #define vi vector
    8. #define vl vector
    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<-1) {
    38.         if(dp[i] != -1) {
    39.             priority_queueint>,vectorint>>,greaterint>>> 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 
    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
    5. #define fi first
    6. #define se second
    7. #define vi vector
    8. #define vl vector
    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 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. }

  • 相关阅读:
    查找算法——二分查找
    机械工程基础笔记整理
    【数字IC验证快速入门】2、通过一个SoC项目实例，了解SoC的架构，初探数字系统设计流程
    【QT】点击按钮弹出对话框的注意事项
    密码学的基础:X.690和对应的BER CER DER编码
    TCP三握四挥手
    PHPstudy安装redis扩展
    08-Linux特殊权限
    什么是消息队列(Message Queue, MQ)？且有何用处？
    洞悉消费者心理：群狼调研帮您制定成功策略
  • 原文地址：https://blog.csdn.net/scanner___yw/article/details/132812863