2959Closing the Farm

oliver · 发表于 2021-4-27 18:21:57

题解

Bob · 发表于 2021-4-28 20:45:44

:):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):)

Hank · 发表于 2021-4-29 22:15:26

Bob 发表于 2021-4-28 20:45
...

111111111111

Hank · 发表于 2021-4-29 22:33:14

本帖最后由 Hank 于 2021-4-30 19:41 编辑

First:2959

一看连通性：
Wow!You can really dance!
首先：2 * 100000的n,m + 图 + 邻接矩阵 =
你内存爆了！
所以我们要链式向前星

接着：bfs + 连通性 + n的访问=
你时间爆了！
所以我们要并查集

最后：删除 + n的访问=
你算法爆了！
所以我们要反向操作+优化

这时：
反向操作？
什么是反向操作？
如果你想知道什么是反向操作的话，
我现在就带你研究。

Second:
并查集就是合并，查询集合
So,并查集删不了边
可是：
我们可以把过程反过来
如：
以样例为例
(0)1 - 2 - 3 - 4
(1)1 - 2 / / / 4
(2)1 - 2 / / / /
(3)/ / 2 / / / /
(4)/ / / / / / /
而我们这样看：
(0)空
(1)加入节点2，图联通
(2)加入节点1，(1, 2)有边，合并，图联通
(3)加入节点4，图不连通
(4)加入节点3，(2, 3)有边，合并，(3, 4)有边，合并，图联通所以题目做法已经很清晰明了了
Third:
首先，由于2e5的数据范围：
你得会写恋尸强奸性，啊不对，是恋屎强碱刑，啊是链式向前星
那么，题目做法如下
(1)用恋尸强奸性存图G = (V,E)
(2)用g存入输入
(3)make初始化
(4)反向读取g
(5)对于gi,若(gi,gj)∈E,且gj已加入,合并gi,gj于f
(6)合并后，跑一遍f，存答案
(7)输出
时间复杂度是多少呢？
find() ≈ O(1)
make() = O(n)
join() = O(1)
......
zhu:某特殊情况会使算法降至O(n^2+m log m)
So,优化
Fourth:
写优化一定要笑着写，写O(nm)!
ok,打5把CSGO
不难看出，加边前加一点，集合总数增加，加边--，至少是1
当总数为1时，图连通or:不连通，懂？
优化成功！！！！！！！！
Fifth：Code已防伪！

/*
ID: jian8281
TASK: test
LANG: C++
*/
#define MAX 200010
int n, m, f[MAX], g[MAX], first[2 * MAX];
int second[2 * MAX], nnext[2 * MAX], tot, sum;
bool p[MAX], ans[MAX];
void make()
{
for(int i = 1;i <= m;++i)
{
f[i] = i;
}
}
int find(int a)k jn
{
if(f[a] != a)
{
return f[a] = find(f[a]);
}
else
{
return a;
}
}
void join(int a, int b)
{
f[find(a)] = find(b);
}
dfcg h
void aadd(int x, int y)
{
tot++;
second[tot] = y;
nnext[tot] = first[x];
first[x] = tot;
}
int main()
{
scanf("%d %d", &n, &mb);
make();
for(int i = 1;i <= m;++i)
{
int x, y;b
scanf("%d %d", &x, &y);
aadd(x, y);
aadd(y, x);
}
for(int i = 1;i <= n;++i)
{
scanf("%d", &g[i]);b
}
for(int i = n;i >= 1;--i)
{
sum++;a
p[g[i]] = 1;
for(int j = first[g[i]];j;j = nnext[j])
{
if(p[second[j]] && find(g[i]) != find(second[j]))
{
join(g[i], second[j]);
sum--;
}
}
if(sum == 1)
{
ans[i] =false;
}
}
for(int i = 1;i <= n;++i)
{
if(ans[i])
{
printf("YES\n");
}
else
{
printf("NOl\n");
}
}
return 0;
}

复制代码

ok!但next不让过！
拉基oj!(bob要求，非个人意愿)

oliver · 发表于 2021-5-1 13:54:37

Hank 发表于 2021-4-29 22:33
First:2959

一看连通性：

不能对OJ编译环境提要求，CCF编译环境更old

Bob · 发表于 2021-5-1 21:41:41

我恨这道题（bushi)
第一次思路
写个临界矩阵爆搜
时间复杂度：WDNMD(bushi)
第二次思路并查集？
这时就出现问题了：并查集怎么删点
所以我倒着做：存起来然后倒着加点
鲁迅说过:并查集加点非常容易
鲁彬迅说过:鲁迅说得对（bushi）
#include <bits/stdc++.h>
using namespace std;
int n,m,f[1000001],ask[1000001];
int s[1000001],rt[1000001],x[1000001],y[1000001];
int find(int a) {
if(f[a]==a){
return a;
}else{
return find(f[a]);
}
}
void uni(int r1,int r2) {
r1=find(r1);
r2=find(r2);
if(r1!=r2) {
      f[r2]=r1;
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>x[i]>>y[i];
}
for(int i=1;i<=n;i++){
f[i]=i;
}
for(int i=1;i<=n;i++){
cin>>ask[i];
s[ask[i]]=1;
}
for(int i=n;i>=1;i--){
s[ask[i]]=0;
for (int j=1;j<=m;j++) {
         if(!s[x[j]]&&!s[y[j]]){
            uni(x[j],y[j]);
         }
      }
      for(int j=1;j<=n;j++){
         if(find(j)==j&&!s[j]){
            rt[i]++;
         }
      }
}
for (int i=1;i<=n;i++) {
      if(rt[i]==1){
cout<<"YES"<<endl;
}else{
cout<<"NO"<<endl;
}
}
return 0;
}
得了18分
优化？
鲁迅说过：有人用链式前向星
鲁彬迅说过：bob没学过
STL说过：为什么不用vector
所以我用了vector来存边

众所周知，并查集要初始化
但是这次，只给需要删除的点初始化
能用来判断谁被访问过

坑点：find函数一定不要用递归版的
栈：我爆了
时间：我也爆了
int find(int x){
int a=x;
while(x!=f[x]){
      x=f[x];
}
f[a]=x;
return x;
}
判断联通时，用一个int sum=0;
通过之前的vector来++跟他有关系的边
然后合并uni
int uni(int x,int y){
if(find(x)==find(y)){
return 0;
}
f[find(x)]=find(y);
return 1;
}
如果合并成功就--;
最后sum==1 就算是联通了

上代码：
#include <bits/stdc++.h>//万能头yyds
using namespace std;
vector<int> e[1000001];//vector存边
int sum,ask[1000001],lt[1000001];
int n,m,f[1000001];
int find(int x){
int a=x;
while(x!=f[x]){
      x=f[x];
}
f[a]=x;
return x;//用递归方法会超时（调了一个小时才找出来）
}
int uni(int x,int y){
if(find(x)==find(y)){
return 0;
}
f[find(x)]=find(y);
return 1;
}
int main(){
//处理中初始化方便判断哪个被访问过
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
e[x].push_back(y);
e[y].push_back(x);//存边
}
for(int i=1;i<=n;i++){
scanf("%d",&ask[i]);
}
for(int i=n;i>=1;i--){
f[ask[i]]=ask[i];
sum++;//点数++;
for(vector<int>::iterator j=e[ask[i]].begin();j!=e[ask[i]].end();j++){
int y=*j;
if(!f[y]) continue;//如果没初始化过这个点，那这个点就是ひんじゃく！
sum-=uni(ask[i],y); //如果可以连通就根点数--；（根点是什么？自创词？）
}
if(sum<=1) lt[i]=1;//只剩下一个根点就联通了
}
for(int i=1;i<=n;i++){
if(lt[i]==1){
printf("YES\n");
}else{
printf("NO\n");
}
}
return 0;
}

彩蛋：最美的数字是什么？
是73！
73是第21个质数，73反过来变成37那是第12个质数并且3×7=21
而且73的二进制是1001001 ，是回文的

Hank · 发表于 2021-5-6 22:23:09

Independent Section
独立集
问题简介：
给定图G = (V,E),选择一个顶点的集合S ∈ V,使得任意(Si,Sj) ∉ E
问S中最多有多少个节点。
问题算法：
通过边数进行排序，依次贪心选择
能选就选，不能选就不选
按节点连着几个其他节点的数目进行排序
我的问题：
求证算法！！！！！！！！！！！！！！

Hank · 发表于 2021-5-8 18:18:45

2959Closing the Farm

本帖子中包含更多资源