• 2023 ICPC 网络赛 第二场 部分题解 （待完善）

    D Project Manhattan

    思路：

    最终选中的下标,必然包含n个行或者n个列.

    所以答案 = n行的最小值之和或者n列的最小值之和

    注意坑点： 当存在负数时，应该把负数全部选上,答案只会更优.

    代码：

    1. #include <bits/stdc++.h>
    2. typedef long long ll;
    3. typedef unsigned long long ull;
    4. #define int long long
    5. #define endl '\n'
    6. #define bit(x) (1ll << x)
    7. using namespace std;
    8. const int N = 1e6 + 5;
    9. const int inf = 1e16;
    10. void solve()
    11. {
    12.     int n;
    13.     cin >> n;
    14.     vector<vector<int>> a(n + 1, vector(n + 1));
    15.     for (int i = 1; i <= n; i++)
    16.     {
    17.         for (int j = 1; j <= n; j++)
    18.         {
    19.             cin >> a[i][j];
    20.         }
    21.     }
    22.  
    23.     int ans1 = 0;
    24.     int ans2 = 0;
    25.     for (int i = 1; i <= n; i++)
    26.     {
    27.         vector<int> c(n + 1);
    28.         for (int j = 1; j <= n; j++)
    29.         {
    30.             c[j] = a[i][j];
    31.         }
    32.         sort(c.begin() + 1, c.end());
    33.         ans1 += c[1];
    34.         int now = 2;
    35.         while (c[now] < 0)
    36.         {
    37.             ans1 += c[now];
    38.             now++;
    39.         }
    40.     }
    41.  
    42.     for (int i = 1; i <= n; i++)
    43.     {
    44.         vector<int> c(n + 1);
    45.         for (int j = 1; j <= n; j++)
    46.         {
    47.             c[j] = a[j][i];
    48.         }
    49.         sort(c.begin() + 1, c.end());
    50.         ans2 += c[1];
    51.         int now = 2;
    52.         while (c[now] < 0)
    53.         {
    54.             ans2 += c[now];
    55.             now++;
    56.         }
    57.     }
    58.     cout << min(ans1,ans2) << endl;
    59. }
    60. signed main()
    61. {
    62.     ios_base::sync_with_stdio(0);
    63.     cin.tie(0);
    64.     cout.tie(0);
    65.     int t = 1;
    66.     cin >> t;
    67.     while (t--)
    68.     {
    69.         solve();
    70.     }
    71.     return 0;
    72. }

    E Another Bus Route Problem

    题解：

    下面这些话比较抽象, 具体看代码.

    记忆化BFS.

    对于一条路径(u,v), 不断的找他们的LCA，并标记中途经过的点,如果途中经过的点是线路的话,就加入队列中，然后把步数+1即可.

    会有两种情况:

    1.整条路径（u,v）都没有被访问过:直接标记即可

    2.找LCA的过程中，已经有顶点被标记过了.那么说明他们的LCA也必然被标记过了,否则不可能出现这种状态.没被标记的那个条路径继续往上找.

    1. #include <bits/stdc++.h>
    2. typedef long long ll;
    3. typedef unsigned long long ull;
    4. #define int long long
    5. #define endl '\n'
    6. #define bit(x) (1ll << x)
    7. using namespace std;
    8. const int N = 1e6 + 5;
    9. const int inf = 1e16;
    10. vector<int> g[N];
    11. vector<int> fa(N);
    12. vector<int> dep(N);
    13. map<int, vector<pair<int, int>>> path;
    14. vector<int> vis(N); // 标记
    15. void dfs(int u)
    16. {
    17.     dep[u] = dep[fa[u]] + 1;
    18.     for (auto v : g[u])
    19.     {
    20.         fa[v] = u;
    21.         dfs(v);
    22.     }
    23. }
    24. void solve()
    25. {
    26.     int n, m;
    27.     cin >> n >> m;
    28.     for (int i = 2; i <= n; i++)
    29.     {
    30.         int x;
    31.         cin >> x;
    32.         g[x].push_back(i);
    33.     }
    34.     dfs(1);//LCA需要得到每个顶点的深度,
    35.     for (int i = 1; i <= m; i++)//把路径存到两个端点上
    36.     {
    37.         int u, v;
    38.         cin >> u >> v;
    39.         path[u].push_back({u, v});
    40.         path[v].push_back({u, v});
    41.     }
    42.     queue<array<int, 3>> q;
    43.     for (int i = 0; i < path[1].size(); i++)//起点肯定是从1号开始的
    44.     {
    45.         q.push({path[1][i].first, path[1][i].second, 1});
    46.     }
    47.     vis[0] = 1e5;//无效状态,直接标记
    48.     while (q.size())
    49.     {
    50.         int left = q.front()[0];
    51.         int right = q.front()[1];
    52.         int step = q.front()[2];//到当前路径（left,right）的转站步数
    53.         q.pop();
    54.         while (left != right && !vis[left] && !vis[right])//找LCA,如果出现已经访问过的点，直接停止
    55.         {
    56.             if (dep[left] < dep[right])
    57.             {
    58.                 vis[right] = step;//标记路径
    59.                 for (int i = 0; i < path[right].size(); i++)//该点存在路径直接存进去
    60.                 {
    61.                     q.push({path[right][i].first, path[right][i].second, step + 1});
    62.                 }
    63.                 right = fa[right];//往上走
    64.             }
    65.             else
    66.             {
    67.                 vis[left] = step;
    68.                 for (int i = 0; i < path[left].size() ; i++)
    69.                 {
    70.                     q.push({path[left][i].first, path[left][i].second, step + 1});
    71.                 }
    72.                 left = fa[left];
    73.             }
    74.         }
    75.         //如果还没到LCA就终止了，说明他们的LCA已经被访问过了.
    76.         while (!vis[left])//如果没被访问过，就一直往上标记，到达LCA或标记过的点就会停止
    77.         {
    78.             vis[left] = step;
    79.             for (int i = 0; i < path[left].size() ; i++)
    80.             {
    81.  
    82.                 q.push({path[left][i].first, path[left][i].second, step + 1});
    83.             }
    84.             left = fa[left];
    85.         }
    86.         while (!vis[right])//如果没被访问过，就一直往上找
    87.         {
    88.             vis[right] = step;
    89.             for (int i = 0; i < path[right].size() ; i++)
    90.             {
    91.  
    92.                 q.push({path[right][i].first, path[right][i].second, step + 1});
    93.             }
    94.             right = fa[right];
    95.         }
    96.     }
    97.     for (int i = 2; i <= n; i++)
    98.     {
    99.         if (!vis[i])
    100.         {
    101.             cout << -1 << " ";
    102.             continue;
    103.         }
    104.         cout << vis[i] << " ";
    105.     }
    106.     cout << endl;
    107. }
    108. signed main()
    109. {
    110.     ios_base::sync_with_stdio(0);
    111.     cin.tie(0);
    112.     cout.tie(0);
    113.     int t = 1;
    114.     // cin >> t;
    115.     while (t--)
    116.     {
    117.         solve();
    118.     }
    119.     return 0;
    120. }

    M Dirty Work

    题解:

    写完一道题的期望时间是 ai + bi*pi

    把n道题的期望时间从小到大排序,然后按顺序完成题目即可.

    1. #include <bits/stdc++.h>
    2. typedef long long ll;
    3. typedef unsigned long long ull;
    4. #define int long long
    5. #define endl '\n'
    6. #define bit(x) (1ll << x)
    7. using namespace std;
    8. const int N = 1e6 + 5;
    9. const int inf = 1e16;
    10. void solve()
    11. {
    12.     int n;
    13.     cin >> n;
    14.     vector<double> ans(n+1);
    15.     for(int i = 1; i<=n; i++)
    16.     {
    17.         double a,b,p;
    18.         cin >> a >> b >> p;
    19.         ans[i] = a + 1.0*b*p;
    20.     }
    21.     sort(ans.begin()+1,ans.end());
    22.     double sum =0;
    23.     for(int i=1; i<=n; i++)
    24.     {
    25.         ans[i]+=ans[i-1];
    26.         sum+=ans[i];
    27.     }
    28.     printf("%.10lf\n",sum);
    29. }
    30. signed main()
    31. {
    32.     int t = 1;
    33.     cin >> t;
    34.     while (t--)
    35.     {
    36.         solve();
    37.     }
    38.     return 0;
    39. }

    I Impatient Patient

    题解：

    标签：期望方程.

    设dp[i]表示从i直接到达终点的期望天数

    1. 成功的概率是 pi,直接到达终点

    贡献是 :pi*1

    2.失败的概率是 1-pi,那么从i点回到a[i]点,然后从a[i]点再到 i号点

    贡献是 :(1-pi) * (i- a[i] +1 + dp[i])

    综上，得到期望方程

    dp[i] = pi + (1-pi) * (i- a[i] +1 + dp[i])

    化简得:   dp[i] = ( p + (1-p)*(i-a[i]+1) )  /p;  

    1. #include <bits/stdc++.h>
    2. typedef long long ll;
    3. typedef unsigned long long ull;
    4. #define int long long
    5. #define endl '\n'
    6. #define bit(x) (1ll << x)
    7. using namespace std;
    8. const int N = 1e6 + 5;
    9. const int inf = 1e16;
    10.  
    11. void solve()
    12. {
    13.     int n;
    14.     cin >> n;
    15.     vector<int> a(n + 2), q(n + 2);
    16.     for (int i = 1; i <= n; i++)
    17.     {
    18.         cin >> a[i];
    19.         a[i]++;
    20.     }
    21.     for (int i = 1; i <= n; i++)
    22.     {
    23.         cin >> q[i];
    24.     }
    25.     vector<double> dp(n + 2);
    26.     double ans = n;
    27.     for (int i = 1; i <= n; i++)
    28.     {
    29.         double p = q[i]/(1.0*100000);//成功概率
    30.         dp[i] = ( p + (1-p)*(i-a[i]+1) )  /p;//从i到n+1点的期望天数
    31.         ans = min(ans,i-1+dp[i]);
    32.     }
    33.     printf("%.12lf\n", ans);
    34. }
    35. signed main()
    36. {
    37.     int t = 1;
    38.     cin >> t;
    39.     while (t--)
    40.     {
    41.         solve();
    42.     }
    43.     return 0;
    44. }

    L Super-palindrome

    题解:

    先陈述一下最小公共前后缀的概念

    比如字符串 :abc]defabcabcdef abc 

    该字符串的最小公共前后缀为3:[abc] defabcabcdef [abc]  

    字符串: ababababab

    该字符串的最小公共前后缀为2: [ab]ababab[ab]

    样例字符串： pbbp

    该字符串的最小公共前后缀为2: [pb][pb]

    设dp[l][r]表示区间[l,r] 是否是超级字符串.

    nxt[id][i]表示在字符串 s[id]...s[n]中 以第i个字母为右端点的最小公共前后缀.

    转移方程:

    dp[l][r] |= dp[l+ Min][r-Min];  //其中 Min表示 字符串s [l,r]的最小公共前后缀.

    举例说明:

    样例说明:

    问字符串[pb]pbpb[pb]是否是超级回文串?

    最小公共前后缀[pb]可以成功匹配，所以只要看里面 pbpb 是否是超级回文串即可.

    代码：

    1. #include <bits/stdc++.h>
    2. typedef long long ll;
    3. typedef unsigned long long ull;
    4. #define int long long
    5. #define endl '\n'
    6. #define bit(x) (1ll << x)
    7. using namespace std;
    8. const int N = 1e6 + 5;
    9. const int inf = 1e16;
    10. const int maxn = 5e3 + 10;
    11. // nxt数组表示 以i为右端点的最短公共前后缀
    12. int nxt[maxn][maxn];
    13. void Min_kmp(string a, int id) // 传入的下标一定是从0开始的
    14. {
    15.  
    16.     a = " " + a;
    17.     int n = a.size() - 1;
    18.     for (int i = 0; i <= n; i++)
    19.     {
    20.         nxt[id][i] = 0;
    21.     }
    22.     for (int i = 2, j = 0; i <= n; i++)
    23.     {
    24.         while (j && a[i] != a[j + 1])
    25.             j = nxt[id][j];
    26.         if (a[i] == a[j + 1])
    27.             j++;
    28.         nxt[id][i] = j;
    29.     }
    30.     for (int i = 2, j = 2; i <= n; i++, j = i)
    31.     {
    32.         while (nxt[id][j])
    33.             j = nxt[id][j];
    34.         if (nxt[id][i])
    35.             nxt[id][i] = j;
    36.     }
    37.     for (int i = 0; i < n; i++)
    38.     {
    39.         nxt[id][i] = nxt[id][i + 1];
    40.     }
    41.     nxt[id][n] = 0;
    42. }
    43. int dp[maxn][maxn];
    44. void solve()
    45. {
    46.  
    47.     string s;
    48.     cin >> s;
    49.     int n = s.size();
    50.     for(int i = 0; i<=n; i++)
    51.     {
    52.         for(int j = 0; j<=n; j++)
    53.         {
    54.             dp[i][j] = 0;
    55.         }
    56.     }
    57.     for (int i = 0; i < s.size(); i++)
    58.     {
    59.         string t = s.substr(i);
    60.         Min_kmp(t, i);//找到以s[i]为起点字符串的最小公共前后缀
    61.     }
    62.     int ans = 0;
    63.     for (int len = 2; len <= n; len++)
    64.     {
    65.         for (int l = 0; l < n; l++)
    66.         {
    67.             int r = l + len - 1;
    68.             int Min = nxt[l][r - l];//以s[l...r]中以r为右端点的最小公共前后缀
    69.             if (Min * 2 == len)//直接拼接即可
    70.             {
    71.                 dp[l][r] |= 1;
    72.             }
    73.             dp[l][r] |= dp[l + Min][r - Min];
    74.             if (dp[l][r])
    75.             {
    76.                 ans++;
    77.             }
    78.         }
    79.     }
    80.     cout << ans << endl;
    81. }
    82. signed main()
    83. {
    84.     ios_base::sync_with_stdio(0);
    85.     cin.tie(0);
    86.     cout.tie(0);
    87.     int t = 1;
    88.     cin >> t;
    89.     while (t--)
    90.     {
    91.         solve();
    92.     }
    93.     return 0;
    94. }

  • 相关阅读:
    「解决BUG」WIndows 开机进入桌面后一直闪屏刷新，无法打开资源管理器，菜单等界面
    多元函数的微分法
    GB28181 编码规则说明
    LeetCode50天刷题计划第二季（Day 2 — 格雷编码（12.30-13.00）子集 II（13.00-14.00）
    【兔子机器人】项目资料汇总及任务流程
    nginx-日志处理
    Spring Boot 接口数据加解密，so easy!
    【Linux】Top命令Load average及相关CPU检查查询
    Sentinel授权规则和规则持久化
    Linux中安装MySQL_图解_2023新
  • 原文地址：https://blog.csdn.net/cs1414358917/article/details/133272098