直接暴力枚举全排列,再判断即可。
bool check(){
for (LL i = 1; i < n; i ++){
LL cnt = 0;
for (LL j = 0; j < m; j ++)
if (S[seq[i]][j] != S[seq[i + 1]][j])
++ cnt;
if (cnt > 1)
return false;
}
return true;
}
void DFS(LL depth){
if (depth > n){
if (check()){
cout << "Yes";
exit(0);
}
return ;
}
for (LL i = 1; i <= n; i ++){
if (!vis[i]){
vis[i] = 1;
seq[depth] = i;
DFS(depth + 1);
vis[i] = 0;
}
}
return ;
}
先将 与 升序排列,从后往前遍历 数组,对于 ,用 lower_bound
处理出 中不大于 的最后一个元素 ,若 则答案就为 。(因为从后往前遍历 数组一定从大到小, 也是为满足条件的元素中最大的)。
sort(A + 1, A + 1 + n);
sort(B + 1, B + 1 + m);
for (LL i = n; i >= 1; i --){
if (A[i] + D < B[1])
continue;
LL pt = lower_bound(B + 1, B + 1 + m, A[i] + D + 1) - B;
if (pt == 1)
continue;
LL x = B[pt - 1];
if (x < A[i] - D)
continue;
cout << A[i] + x;
return 0;
}
用 set
存图,方便插入删除。第 个集合中含有 表示 到 有一条边。
将每个点的入度存入数组 中。
初始答案 设为 。
对于操作 1:在第 个集合中插入 ,在第 个集合中插入 ,若 , 减一,点 同理,然后将 与 都加一。
对于操作 2:遍历集合 ,将 减一,并在集合 中删除元素 ,若减一后 , 加一。最后清空集合 , 赋值 , 如果原 , 加一。
LL opt, u, v, Ans = n;
for (LL i = 1; i <= Q; i ++){
cin >> opt >> u;
if (opt == 1){
cin >> v;
G[u].insert(v);
G[v].insert(u);
if (!degree[v])
-- Ans;
if (!degree[u])
-- Ans;
degree[v] ++;
degree[u] ++;
}
else{
for (auto v : G[u]){
G[v].erase(u);
degree[v] --;
if (!degree[v])
++ Ans;
}
G[u] = set<LL>();
if (degree[u])
++ Ans;
degree[u] = 0;
}
cout << Ans <<"\n";
}