第11周总结

本周ac了大约32道题，包括作业和周六的牛客竞赛。

在做题中发现自己经常犯一些小错误，比如数组开小了或者越界、打错变量名（尤其是在多重for循环中，有时会顺手打重复的变量），还有就是在使用上一题代码中的并查集模板时忘记修改，这导致我浪费了很多时间在一道题上找错误。

还有就是有很多题可能是思路错了或者代码某处有错误，就是过不去，对于这些题还是得找时间细看题解，在之后ac了他。

P2661 [NOIP2015 提高组] 信息传递 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

对于这道题，我在看了题解后知道这题要找出最小环，最小环的边数就是最少的传递次数，学到了两个求最小环边数的方法。

方法1：另开一个数组z来记下每个点到根节点的边数，将其全部初始化为0，在合并时更新点到根节点的距离（进行路径压缩）。如果无法合并（a,b根节点相同），就更新最小环的边数ans=min(ans,z[a]+z[b]+1)。

方法2：不开数组，定义一个全局变量i2，在每次合并时初始化为0，find函数（不进行路径压缩）在找根节点时使i2自增，如果不能合并（根节点相同），就更新最小环的边数ans=min(ans,i2+1)。

#include
#define q 1000004
using namespace std;
int ans=q,i2;bool flag;
int set1[q],qq[q];
struct A{
int z,y,s;
friend bool operator<(A a,A b)   //可能是在做题时没把用不到的删掉
{return a.s>n;
for(int i=1;i<=n;i++)
set1[i]=i;
for(int i=1;i<=n;i++)
{cin>>x;flag=0;
merge(i,x);
if(flag)ans=min(ans,i2+1);
}
cout<

1024-食物链_2021秋季算法入门班第五章习题：优先队列、并查集(重现赛) (nowcoder.com)

这个题上周看过题解，学到了两种方法。这次竞赛正好检验了一下理解的怎么样。在整体思路上没错，只在判断是否为假话时漏了一种情况（还是自己做的题太少了）。

方法1：POJ-1182 食物链_飘过的小牛的博客-CSDN博客_poj 食物链

方法2：POJ - 1182： 食物链 （并查集）_Jerry233的博客-CSDN博客_poj1182

我用的是方法2：代码如下

#include 
#define q 170000
using namespace std;
int set1[q],ans;bool flag;
mapa;
int find(int x)
{int t=x,y;
    while(t!=set1[t])
    t=set1[t];
while(x!=set1[x])
{y=set1[x];
set1[x]=t;
x=y;
}
return t;
}
void merge(int a1,int b1)
{int fa=find(a1);
int fb=find(b1);
if(fa!=fb){
set1[fb]=fa;

}}
int main()
{int n,m,x1,x2,x3;
cin>>n>>m;
for(int i=1;i<=n*3;i++)
    set1[i]=i;
for(int i=0;i>x1>>x2>>x3;
    if(x1==1){
    if(x2>0&&x2<=n&&x3>0&&x3<=n){
if(find(x2)==find(x3+n)||find(x2+n)==find(x3)){ans++;continue;}
        merge(x2,x3);
        merge(x2+n,x3+n);
        merge(x2+2*n,x3+2*n);
        }
        else ans++;
    }
else {
    if(x2>0&&x2<=n&&x3>0&&x3<=n&&x2!=x3){
if(find(x2)==find(x3)||find(x2+n)==find(x3)){ans++;continue;}
     merge(x2,x3+n);
        merge(x2+n,x3+2*n);
        merge(x2+2*n,x3);
}
        else ans++;
}
}

cout<

 这两种方法/思路都可以解决类似“敌人的敌人是朋友”这种题型，对于“敌人的敌人可能也是敌人”的题不行，比如这题：P1955 [NOI2015] 程序自动分析 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

目前还没做出来。 

  P6121 [USACO16OPEN]Closing the Farm G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

P3144 [USACO16OPEN]Closing the Farm S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这个题有两个，一个数据范围小，一个数据范围大。

还有个相似的题：P1197 [JSOI2008]星球大战 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

前两个题：在做数据范围小的题的思路：记下删点的顺序，倒着加点，加一次点就循环n次找有几个连通块。但在数据范围大时肯定超时，结果也确实是这样的。在看了题解后，知道了另一种在删点题中快速知道有几个连通块。方法：定义一个变量ans1，表示当前有几个连通块，初始化为0，在加点时使ans1++，如果后面枚举与该点有边相连的点时可以与其他点合并，就让ans1减1，枚举完后，ans1的值就是当前连通块的个数。

第三题：与前面两个题的区别是该题可能不会删掉所有点，所以要记下那些点没删，在倒序加边之前还要将没被删的边加上，处理方法与上面一样。

第三题代码：

#include
#define q 2000004
using namespace std;
long long b[q],head[q],c[q];bool bbb[q];
long long set1[q],ans,ans1;
struct A{
long long v,to;
}bb[q];
long long find(long long a1)
{long long b=a1,t;
while(b!=set1[b])
   {b=set1[b];}
while(b!=a1)
{t=a1;
a1=set1[a1];
set1[t]=b;
}
return b;
}
long long merge(long long a1,long long b)
{
long long fa=find(a1);
long long fb=find(b);
if(fa!=fb){
set1[fb]=fa;return 1;
}return 0;
}
void add(long long a,long long b)
{bb[ans].v=b;
bb[ans].to=head[a];
    head[a]=ans++;
}

int main()
{std::ios::sync_with_stdio(false);
long long n,m,xx,yy;
memset(head,-1,sizeof(head));
memset(bbb,1,sizeof(bbb));
cin>>n>>m;
for(long long i=1;i<=n;i++)
    set1[i]=i;
for(long long i=0;i>xx>>yy;add(xx,yy);add(yy,xx);}
    long long k;cin>>k;
for(long long i=1;i<=k;i++)
   { cin>>b[i];bbb[b[i]]=0;}
   ans1=n-k;
    for(long long i=1;i<=n;i++)
    {if(bbb[i]){
    for(long long i1=head[i];i1!=-1;i1=bb[i1].to)
    {if(!bbb[bb[i1].v])continue;
     ans1-=merge(i,bb[i1].v);
    }}
    }
c[k+1]=ans1;
for(long long i=k;i>0;i--)
{bbb[b[i]]=1;ans1++;
    for(long long i1=head[b[i]];i1!=-1;i1=bb[i1].to)
    {if(!bbb[bb[i1].v])continue;
     ans1-=merge(b[i],bb[i1].v);
    }
c[i]=ans1;
}
for(long long i=1;i<=k+1;i++)
cout< 


1005-[JSOI2007]建筑抢修_2021秋季算法入门班第五章习题：优先队列、并查集(重现赛) (nowcoder.com)
 
这个题本以为只需要将所有输入进入优先队列，报废时间小的优先，然后循环直到优先队列为空，判断当前时间加上修复时间是否大于报废时间，是的话就选择修它，否则跳过进入下一循环。虽然测试用例通过了，但没ac。
 
之后在下午忽然想到不对的原因： 在优先队列首部的数据虽然报废时间短，需要尽快修，但万一修的时间很长，而后面的数据万一有报废时间长，但修复时间更短呢。这种情况下放弃修前面那个，选择修后面那个（一定会修好，因为第二个的修复时间更短），那总的修复时间就更短了，但修的数量不变。然后就是各种想代码来实现这个思路。在竞赛结束后搜了一下，才发现这是这是提高+/省选-的难度。这难度的题的思路果然与这个难度之下的题的思路不一般。代码：
 
#include 
#define qq 1000000
using namespace std;
struct A
{long long t1,t2;
friend bool operator<(A a1,A a2){return a1.t2q;
int main()
{long long n,ans=0,t=0;
cin>>n;
for(int i=0;i>a[i].t1>>a[i].t2;
}
sort(a,a+n);
for(int i=0;ia[i].t2){
    if(a[i].t1