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

D Transitivity

题解:

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

一共有两种情况

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

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

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

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

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

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

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

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

AC代码：

#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define int long long
#define endl '\n'
#define bit(x) (1ll << x)
using namespace std;
const int N = 1e6 + 5;
const int inf = 1e16;
vector<int> g[N];
int sz[N];//连通块大小
int cnt[N];//边的数量
int vis[N];
void solve()
{int n,m;cin >> n >> m;for(int i = 1; i<=m; i++){int u,v;cin >> u >> v;g[u].push_back(v);g[v].push_back(u);}int Min1 = inf;//最小值int Min2 = inf;//次小auto dfs = [&](auto self, int u, int fa,int root)-> void{vis[u] = 1;sz[u] = 1;cnt[root]+=g[u].size();for(auto v: g[u]){if(vis[v]){continue;}self(self,v,u,root);sz[u]+=sz[v];}};auto cal = [&](int now, int sum)//计算贡献{return sum*(sum-1)/2 - now;};int ans = 0;int f = 0;for(int i = 1; i<=n; i++){if(vis[i]){continue;}dfs(dfs,i,-1,i);cnt[i]/=2;int val = cal(cnt[i],sz[i]);//连通块的贡献if(val != 0){ans+=val;f = 1;}else{if(sz[i] < Min1){Min2 = Min1;Min1 = sz[i];}else if(sz[i] <=Min2){Min2 = sz[i];}}}if(f){cout << ans << endl;}else{cout << Min1*Min2 << endl;}
}signed main()
{ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t = 1;//cin >> t;while (t--){solve();}return 0;
}

A Qualifiers Ranking Rules

题解： 

按照题意模拟即可

#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define int long long
#define endl '\n'
#define bit(x) (1ll << x)
using namespace std;
const int N = 1e6 + 5;
const int inf = 1e16;
struct node
{string s; // 学校名称int rank; // 比赛名次int t;node(string x, int y, int _t){s = x;rank = y;t = _t;}
};
int cmp(node a, node b)
{if (a.rank == b.rank){return a.t < b.t;}return a.rank < b.rank;
}
void solve()
{int n, t;cin >> n >> t;map<string, int> vis;vector<node> pos1;int cnt = 1;for (int i = 1; i <= n; i++){string s;cin >> s;if (vis.count(s)){continue;}pos1.push_back({s, cnt, 1});vis[s] = 1;cnt++;}cnt = 1;vis.clear();for (int i = 1; i <= t; i++){string s;cin >> s;if (vis.count(s)){continue;}pos1.push_back({s, cnt, 2});cnt++;vis[s] = 1;}vis.clear();sort(pos1.begin(), pos1.end(), cmp);for (int i = 0; i < pos1.size(); i++){if (vis.count(pos1[i].s)){continue;}cout << pos1[i].s << endl;vis[pos1[i].s] = 1;}
}
signed main()
{ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t = 1;// cin >> t;while (t--){solve();}return 0;
}

L KaChang!

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

void solve()
{int n,k;cin >> n >> k;int Max = 0;for(int i = 1; i<=n; i++){int x;cin >> x;Max = max(Max,x);}cout << max(2ll,(int)ceil(1.0*Max/k)) << endl;;
}

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代码:  

#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define int long long
#define endl '\n'
#define bit(x) (1ll << x)
using namespace std;
const int N = 1e6 + 5;
const int inf = 1e16;
const int MOD = 998244353;
int add(int x, int y)
{x += y;while (x >= MOD)x -= MOD;while (x < 0)x += MOD;return x;
}int sub(int x, int y)
{return add(x, MOD - y);
}int mul(int x, int y)
{return (x * 1ll * y) % MOD;
}int binpow(int x, int y)
{int z = 1;while (y > 0){if (y % 2 == 1)z = mul(z, x);x = mul(x, x);y /= 2;}return z;
}int inv(int x)
{return binpow(x, MOD - 2);
}int divide(int x, int y)
{return mul(x, inv(y));
}int my_hash(char ch)//对字符进行哈希
{if (ch >= 'a' && ch <= 'z'){return ch - 'a' + 10;}else if (ch >= 'A' && ch <= 'Z'){return ch - 'A' + 36;}else{return ch - '0';}
}
int pos(int ch)//当前字符在二进制中的位置
{if (ch >= 10 && ch <= 35) // 小写表示第1位{return 1;}else if (ch >= 36 && ch <= 61) // 大写表示第2位{return 2;}else // 数字表示第0位{return 0;}
}int dp[2][10][70]; // 当前状态为S且最后一个字符是 ch 的方案数
int last[10];      // 状态为S时 所有的字符方案数之和
void solve()
{int n;cin >> n;string s;cin >> s;s = " " + s;//初始化部分int S = 0;int now;int ch; // 当前填入的字符编号if (s[1] == '?'){for (ch = 0; ch <= 61; ch++) // 当前填入ch{now = S | bit(pos(ch)); // 填入s[i]后,当前的二进制状态dp[1][now][ch] = 1;}}else{now = S | bit(pos(my_hash(s[1]))); // 填入s[i]后,当前的二进制状态ch = my_hash(s[1]);dp[1][now][ch] = 1; // 加上全部的if (s[1] >= 'a' && s[1] <= 'z')//如果是小写字母,还可以是大写字母{now = S | bit(pos(my_hash(s[1]) + 26)); // 填入s[i]后,当前的二进制状态ch = my_hash(s[1]) + 26;                // 填大写字母dp[1][now][ch] = 1;                     // 加上全部的}}for (int i = 2; i <= n; i++){for (int S = 0; S < 8; S++)//{int sum = 0;for (int ch = 0; ch <= 61; ch++){dp[0][S][ch] = dp[1][S][ch]; // 滚动数组dp[1][S][ch] = 0;            // 进行初始化sum = add(sum, dp[0][S][ch]);//表示上一层状态为S的所有字符的方案数}last[S] = sum; // 表示上一层状态为S的所有字符的方案数}for (int S = 0; S < 8; S++) // 枚举上一层的状态{int now;//表示填入字符后的状态int ch; // 当前填入的字符编号if (s[i] == '?'){for (ch = 0; ch <= 61; ch++) // 当前填入ch{now = S | bit(pos(ch));                             // 填入s[i]后,当前的二进制状态dp[1][now][ch] = add(dp[1][now][ch], last[S]);      // 加上全部的dp[1][now][ch] = sub(dp[1][now][ch], dp[0][S][ch]); // 相邻不能相同，减去}}else{now = S | bit(pos(my_hash(s[i]))); // 填入s[i]后,当前的二进制状态ch = my_hash(s[i]);dp[1][now][ch] = add(dp[1][now][ch], last[S]);      // 加上全部的dp[1][now][ch] = sub(dp[1][now][ch], dp[0][S][ch]); // 相邻不能相同，减去if (s[i] >= 'a' && s[i] <= 'z') // 填入大写的{now = S | bit(pos(my_hash(s[i]) + 26)); // 填入s[i]后,当前的二进制状态ch = my_hash(s[i]) + 26;dp[1][now][ch] = add(dp[1][now][ch], last[S]);      // 加上全部的dp[1][now][ch] = sub(dp[1][now][ch], dp[0][S][ch]); // 相邻不能相同，减去}}}}int ans = 0;for (int ch = 0; ch <= 61; ch++){ans = add(ans, dp[1][7][ch]);}cout << ans << endl;
}
signed main()
{ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t = 1;// cin >> t;while (t--){solve();}return 0;
}