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

    D Transitivity

    题解:

    根据题意可以推出结论: 如果存在连通块,那么这个连通块要满足条件,必然是满连通块.

    一共有两种情况

    1. 存在一个连通块不是满连通块

    设cnt表示连通块的节点个数, num表示连通块边的个数

    一个连通块的贡献 = cnt*(cnt-1)/2 - num;

    那么最终答案 =  连通块贡献之和

    2.所有连通块都是满连通块

    因为我们至少需要添加一条边，所以此时等价于我们需要把两个连通块合并.

    假设连通块A有x个节点,连通块B有y个节点,那么我们需要添加 x*y条边 才能满足条件.

    所以即找到 最小和次小的连通块即可,答案 = x*y

    AC代码：

    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. int sz[N];//连通块大小
    12. int cnt[N];//边的数量
    13. int vis[N];
    14. void solve()
    15. {
    16.     int n,m;
    17.     cin >> n >> m;
    18.     for(int i = 1; i<=m; i++)
    19.     {
    20.         int u,v;
    21.         cin >> u >> v;
    22.         g[u].push_back(v);
    23.         g[v].push_back(u);
    24.     }
    25.     int Min1 = inf;//最小值
    26.     int Min2 = inf;//次小
    27.     auto dfs = [&](auto self, int u, int fa,int root)-> void
    28.     {
    29.         vis[u] = 1;
    30.         sz[u] = 1;
    31.           cnt[root]+=g[u].size();
    32.         for(auto v: g[u])
    33.         {
    34.            
    35.             if(vis[v])
    36.             {
    37.                 continue;
    38.             }
    39.  
    40.             self(self,v,u,root);
    41.             sz[u]+=sz[v];
    42.         }
    43.     };
    44.     auto cal = [&](int now, int sum)//计算贡献
    45.     {
    46.         return sum*(sum-1)/2 - now;
    47.     };
    48.     int ans = 0;
    49.     int f = 0;
    50.     for(int i = 1; i<=n; i++)
    51.     {
    52.         if(vis[i])
    53.         {
    54.             continue;
    55.         }
    56.         dfs(dfs,i,-1,i);
    57.         cnt[i]/=2;
    58.         int val = cal(cnt[i],sz[i]);//连通块的贡献
    59.         if(val != 0)
    60.         {
    61.             ans+=val;
    62.             f = 1;
    63.         }
    64.         else
    65.         {
    66.             if(sz[i] < Min1)
    67.             {
    68.                 Min2 = Min1;
    69.                 Min1 = sz[i];
    70.             }
    71.             else if(sz[i] <=Min2)
    72.             {
    73.                 Min2 = sz[i];
    74.             }
    75.         }
    76.     }
    77.     if(f)
    78.     {
    79.         cout << ans << endl;
    80.     }
    81.     else
    82.     {
    83.         cout << Min1*Min2 << endl;
    84.     }
    85. }
    86.  
    87. signed main()
    88. {
    89.     ios_base::sync_with_stdio(0);
    90.     cin.tie(0);
    91.     cout.tie(0);
    92.     int t = 1;
    93.     //cin >> t;
    94.     while (t--)
    95.     {
    96.         solve();
    97.     }
    98.     return 0;
    99. }

    A Qualifiers Ranking Rules

    题解： 

    按照题意模拟即可

    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. struct node
    11. {
    12.     string s; // 学校名称
    13.     int rank; // 比赛名次
    14.     int t;
    15.     node(string x, int y, int _t)
    16.     {
    17.         s = x;
    18.         rank = y;
    19.         t = _t;
    20.     }
    21. };
    22. int cmp(node a, node b)
    23. {
    24.     if (a.rank == b.rank)
    25.     {
    26.         return a.t < b.t;
    27.     }
    28.     return a.rank < b.rank;
    29. }
    30. void solve()
    31. {
    32.     int n, t;
    33.     cin >> n >> t;
    34.     map<string, int> vis;
    35.     vector<node> pos1;
    36.     int cnt = 1;
    37.     for (int i = 1; i <= n; i++)
    38.     {
    39.         string s;
    40.         cin >> s;
    41.         if (vis.count(s))
    42.         {
    43.             continue;
    44.         }
    45.         pos1.push_back({s, cnt, 1});
    46.         vis[s] = 1;
    47.         cnt++;
    48.     }
    49.     cnt = 1;
    50.     vis.clear();
    51.     for (int i = 1; i <= t; i++)
    52.     {
    53.         string s;
    54.         cin >> s;
    55.         if (vis.count(s))
    56.         {
    57.             continue;
    58.         }
    59.         pos1.push_back({s, cnt, 2});
    60.         cnt++;
    61.         vis[s] = 1;
    62.     }
    63.     vis.clear();
    64.     sort(pos1.begin(), pos1.end(), cmp);
    65.     
    66.     for (int i = 0; i < pos1.size(); i++)
    67.     {
    68.         if (vis.count(pos1[i].s))
    69.         {
    70.             continue;
    71.         }
    72.         cout << pos1[i].s << endl;
    73.         vis[pos1[i].s] = 1;
    74.     }
    75. }
    76. signed main()
    77. {
    78.     ios_base::sync_with_stdio(0);
    79.     cin.tie(0);
    80.     cout.tie(0);
    81.     int t = 1;
    82.     // cin >> t;
    83.     while (t--)
    84.     {
    85.         solve();
    86.     }
    87.     return 0;
    88. }

    L KaChang!

    题解： 找到最大的数Max,输出  max(2ll,(int)ceil(1.0*Max/k)) 即可

    1. void solve()
    2. {
    3.     int n,k;
    4.     cin >> n >> k;
    5.     int Max = 0;
    6.     for(int i = 1; i<=n; i++)
    7.     {
    8.         int x;
    9.         cin >> x;
    10.         Max = max(Max,x);
    11.     }
    12.     cout << max(2ll,(int)ceil(1.0*Max/k)) << endl;;
    13. }

    I Pa?sWorD

    题解:

    设dp[i][S][ch] 表示只看前i个字母,且当前字符的出现状态为S,且最后一个字母是ch的方案数

    (下面这些事伪代码,看不懂的可以直接看代码,有详细注释)

    1.当前是 大写字母
    dp[i][S| bit(2)][ch1] += dp[i-1][S][ch2];//其中ch2 != ch1  即上一层所有字符的方案数 - 上一层ch1的方案数

    1.当前是 小写字母

    (1)大写字母
    dp[i][S| bit(2)][ch1] += dp[i-1][S][ch2];//其中ch2 != ch1  即上一层所有字符的方案数 - ch1的方案数


    (2)填小写字母
    dp[i][S| bit(1)][ch1] += dp[i-1][S][ch2];//其中ch2 != ch1  即上一层所有字符的方案数 - ch1的方案数

    1.当前是 数字
    dp[i][S| bit(0)][ch1] += dp[i-1][S][ch2];//其中ch2 != ch1  即上一层所有字符的方案数 - ch1的方案数


    1.当前是 问号
    枚举当前字符ch1,  t表示当前字母是谁
    dp[i][S| bit(t)][ch1] += dp[i-1][S][ch1];//其中ch2 != ch1  即上一层所有字符的方案数 - ch1的方案数

    AC代码:  

    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 MOD = 998244353;
    11. int add(int x, int y)
    12. {
    13.     x += y;
    14.     while (x >= MOD)
    15.         x -= MOD;
    16.     while (x < 0)
    17.         x += MOD;
    18.     return x;
    19. }
    20.  
    21. int sub(int x, int y)
    22. {
    23.     return add(x, MOD - y);
    24. }
    25.  
    26. int mul(int x, int y)
    27. {
    28.     return (x * 1ll * y) % MOD;
    29. }
    30.  
    31. int binpow(int x, int y)
    32. {
    33.     int z = 1;
    34.     while (y > 0)
    35.     {
    36.         if (y % 2 == 1)
    37.             z = mul(z, x);
    38.         x = mul(x, x);
    39.         y /= 2;
    40.     }
    41.     return z;
    42. }
    43.  
    44. int inv(int x)
    45. {
    46.     return binpow(x, MOD - 2);
    47. }
    48.  
    49. int divide(int x, int y)
    50. {
    51.     return mul(x, inv(y));
    52. }
    53.  
    54.  
    55. int my_hash(char ch)//对字符进行哈希
    56. {
    57.     if (ch >= 'a' && ch <= 'z')
    58.     {
    59.         return ch - 'a' + 10;
    60.     }
    61.     else if (ch >= 'A' && ch <= 'Z')
    62.     {
    63.         return ch - 'A' + 36;
    64.     }
    65.     else
    66.     {
    67.         return ch - '0';
    68.     }
    69. }
    70. int pos(int ch)//当前字符在二进制中的位置
    71. {
    72.     if (ch >= 10 && ch <= 35) // 小写表示第1位
    73.     {
    74.         return 1;
    75.     }
    76.     else if (ch >= 36 && ch <= 61) // 大写表示第2位
    77.     {
    78.         return 2;
    79.     }
    80.     else // 数字表示第0位
    81.     {
    82.         return 0;
    83.     }
    84. }
    85.  
    86. int dp[2][10][70]; // 当前状态为S且最后一个字符是 ch 的方案数
    87. int last[10];      // 状态为S时 所有的字符方案数之和
    88. void solve()
    89. {
    90.     int n;
    91.     cin >> n;
    92.     string s;
    93.     cin >> s;
    94.     s = " " + s;
    95.  
    96.     //初始化部分
    97.     int S = 0;
    98.     int now;
    99.     int ch; // 当前填入的字符编号
    100.     if (s[1] == '?')
    101.     {
    102.         for (ch = 0; ch <= 61; ch++) // 当前填入ch
    103.         {
    104.             now = S | bit(pos(ch)); // 填入s[i]后,当前的二进制状态
    105.             dp[1][now][ch] = 1;
    106.         }
    107.     }
    108.     else
    109.     {
    110.         now = S | bit(pos(my_hash(s[1]))); // 填入s[i]后,当前的二进制状态
    111.         ch = my_hash(s[1]);
    112.         dp[1][now][ch] = 1; // 加上全部的
    113.         if (s[1] >= 'a' && s[1] <= 'z')//如果是小写字母,还可以是大写字母
    114.         {
    115.             now = S | bit(pos(my_hash(s[1]) + 26)); // 填入s[i]后,当前的二进制状态
    116.             ch = my_hash(s[1]) + 26;                // 填大写字母
    117.             dp[1][now][ch] = 1;                     // 加上全部的
    118.         }
    119.     }
    120.  
    121.  
    122.     for (int i = 2; i <= n; i++)
    123.     {
    124.         for (int S = 0; S < 8; S++)//
    125.         {
    126.             int sum = 0;
    127.             for (int ch = 0; ch <= 61; ch++)
    128.             {
    129.                 dp[0][S][ch] = dp[1][S][ch]; // 滚动数组
    130.                 dp[1][S][ch] = 0;            // 进行初始化
    131.                 sum = add(sum, dp[0][S][ch]);//表示上一层状态为S的所有字符的方案数
    132.             }
    133.             last[S] = sum; // 表示上一层状态为S的所有字符的方案数
    134.         }
    135.  
    136.         for (int S = 0; S < 8; S++) // 枚举上一层的状态
    137.         {
    138.             int now;//表示填入字符后的状态
    139.             int ch; // 当前填入的字符编号
    140.             if (s[i] == '?')
    141.             {
    142.                 for (ch = 0; ch <= 61; ch++) // 当前填入ch
    143.                 {
    144.                     now = S | bit(pos(ch));                             // 填入s[i]后,当前的二进制状态
    145.                     dp[1][now][ch] = add(dp[1][now][ch], last[S]);      // 加上全部的
    146.                     dp[1][now][ch] = sub(dp[1][now][ch], dp[0][S][ch]); // 相邻不能相同，减去
    147.                 }
    148.             }
    149.             else
    150.             {
    151.                 now = S | bit(pos(my_hash(s[i]))); // 填入s[i]后,当前的二进制状态
    152.                 ch = my_hash(s[i]);
    153.                 dp[1][now][ch] = add(dp[1][now][ch], last[S]);      // 加上全部的
    154.                 dp[1][now][ch] = sub(dp[1][now][ch], dp[0][S][ch]); // 相邻不能相同，减去
    155.  
    156.                 if (s[i] >= 'a' && s[i] <= 'z') // 填入大写的
    157.                 {
    158.                     now = S | bit(pos(my_hash(s[i]) + 26)); // 填入s[i]后,当前的二进制状态
    159.                     ch = my_hash(s[i]) + 26;
    160.                     dp[1][now][ch] = add(dp[1][now][ch], last[S]);      // 加上全部的
    161.                     dp[1][now][ch] = sub(dp[1][now][ch], dp[0][S][ch]); // 相邻不能相同，减去
    162.                 }
    163.             }
    164.         }
    165.     }
    166.     int ans = 0;
    167.     for (int ch = 0; ch <= 61; ch++)
    168.     {
    169.         ans = add(ans, dp[1][7][ch]);
    170.     }
    171.     cout << ans << endl;
    172. }
    173. signed main()
    174. {
    175.     ios_base::sync_with_stdio(0);
    176.     cin.tie(0);
    177.     cout.tie(0);
    178.     int t = 1;
    179.     // cin >> t;
    180.     while (t--)
    181.     {
    182.         solve();
    183.     }
    184.     return 0;
    185. }

  • 相关阅读:
    码蹄集 - MT3251 - 多重回文
    BigDecimal常用API
    基于PyTorch的生成对抗网络实战（7）——利用Pytorch搭建SGAN（Semi-Supervised GAN）生成手写数字并分类
    VLAN trunk扩展 MUXVLAN 原理与实验
    深入理解数据库视图
    Spring-Spring之AOP底层源码解析（下）
    client-go gin的简单整合十-Update
    html02-标签继续学习
    ＜＜JavaEE＞＞ 线程安全问题
    CMake+CLion+Qt配置
  • 原文地址：https://blog.csdn.net/cs1414358917/article/details/132977088