北京东直门网站建设,seo网站快速整站优化技术,wordpress文章引用格式,建设行政主管部门政务网站D Transitivity
题解:
根据题意可以推出结论: 如果存在连通块,那么这个连通块要满足条件,必然是满连通块.
一共有两种情况
1. 存在一个连通块不是满连通块
设cnt表示连通块的节点个数, num表示连通块边的个数
一个连通块的贡献 cnt*(cnt-1)/2 - num;
那么最终答案 连…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;
vectorint g[N];
int sz[N];//连通块大小
int cnt[N];//边的数量
int vis[N];
void solve()
{int n,m;cin n m;for(int i 1; im; 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; in; i){if(vis[i]){continue;}dfs(dfs,i,-1,i);cnt[i]/2;int val cal(cnt[i],sz[i]);//连通块的贡献if(val ! 0){ansval;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;mapstring, int vis;vectornode 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; in; 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;
}
