ACM---大一第三周周赛(Floyd算法+并查集算法学习周)

Dear 丶 2024-04-24 23:20 101阅读 0赞

> ?write in front?  
> ?个人主页：[认真写博客的夏目浅石.CSDN][.CSDN]  
> ?欢迎各位→点赞? + 收藏⭐️ + 留言?  
> ?系列专栏：[ACM周训练题目合集.CSDN][ACM_.CSDN]  
> ?总结：希望你看完之后，能对你有所帮助，不足请指正！共同学习交流 ?  
> ✉️为什么我们不知疲倦，因为我们都在做自己所热爱的事 ♐

#### 文章目录 ####

*  A - Color the ball
 *  B - Suits
 *  C - 六度分离
 *  D - 无处不在的宗教
 *  E - 农场派对
 *  F - 怪物（简易版）
 *  G - 嫌疑犯
 *  比赛情况：
 *  总结

--------------------

![在这里插入图片描述][f4e0159841ab450d861dde9e8fb5ba0d.gif_pic_center]

## A - Color the ball ##

[杭电—Color the ball][Color the ball]  
![在这里插入图片描述][9075d61ff15143edb21956ac4199fcf6.png]  
解题思路：考察差分数组，基础模板

#include<iostream>
    #include <cstring>
    
    using namespace std;
    
    int arr[100010];
    int n,i;
    
    int main()
    {
        
    	while(scanf("%d", &n), n!=0)
    	{
        
    		memset(arr, 0, sizeof(arr));
    		for(i=1;i<=n;i++)
    		{
        
    			int l,r;
    			cin>>l>>r;
    			arr[l]++;
    			arr[r+1]--;
    		}
    		for(i=1;i<=n;i++)
    		{
        
    			arr[i]+=arr[i-1];
    			if(i!=n)
    			{
        
    			    printf("%d ", arr[i]);
    			}
    			else printf("%d",arr[i]);
    		}
    		cout<<endl;
    	}
    	return 0;
    }

## B - Suits ##

[洛谷—Suits][Suits]  
![在这里插入图片描述][05607e07b08e4c85be9d125ac7c393b9.png]  
解题思路：数学问题，一直分类讨论就可以解了

#include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    
    using namespace std;
    
    int a,b,c,d,e,f;
    typedef long long ll;
    ll m1,m2;
    ll mn=-1;
    
    
    int main() 
    {
        	
    	cin>>a>>b>>c>>d>>e>>f;
    	int max=0;
    	
    	int mn=min(a,d);
        int mx=min(c,d);
    	if(e*mn+f*min(b,min(c,d-mn))>max)
    	{
        
    		max=e*mn+f*min(b,min(c,d-mn));
    	}
    	
    	if(e*min(a,d-min(b,mx))+f*min(b,mx)>max)
    	{
        
    		max=e*min(a,d-min(b,mx))+f*min(b,mx);
    	}
    	
    	if(e*mn>max)
    	{
        
    		max=e*mn;
    	}
    	
    	if(f*min(b,mx)>max)
    	{
        
    		max=f*min(b,mx);
    	}
    	
    	cout<<max;
        return 0;
    }

## C - 六度分离 ##

[杭电—六度分离][Link 1]  
![在这里插入图片描述][c0c6dff101884b98aa05db6436ebb123.png]

#include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    
    using namespace std;
    
    #define inf 0x3f3f3f3f
    
    int g[101][101];
    int n,m,ans;
    
    
    int main()
    {
        
        while(cin>>n>>m)
        {
        
            for(int i=0;i<n;i++)
            {
        
                for(int j=0;j<n;j++)
                {
        
                    if(i==j) g[i][j]=0;
                    else g[i][j]=inf;
                }
            }
            
            while(m--)
            {
        
                int a,b;
                cin>>a>>b;
                g[a][b]=g[b][a]=1;
            }
            
            for(int k=0;k<n;k++)
            {
        
                for(int i=0;i<n;i++)
                {
        
                    for(int j=0;j<n;j++)
                    {
        
                        if(g[i][j]>g[i][k]+g[k][j])
                        {
        
                            g[i][j]=g[i][k]+g[k][j];
                        }
                    }
                }
            }
            //以上全部是模板
            int flag=0;
            for(int i=0;i<n;i++)
            {
        
                for(int j=0;j<n;j++)
                {
        
                    if(g[i][j]>7)
                    {
        
                        puts("No");
                        flag=1;
                        break;
                    }
                }
                if(flag) break;
            }
            if(flag==0)
                puts("Yes");
        }
        
        return 0;
    }

## D - 无处不在的宗教 ##

[POJ无处不在的宗教][POJ]

![在这里插入图片描述][f715d43bef714aaba14126989c1406c8.png]

//水题，竟然我也能AC....
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    
    using namespace std;
    
    int n,m;
    int p[100010];
    
    
    int find(int x)
    {
        
        return p[x]==x?x:(p[x]=find(p[x]));//算法模板
        
    }
    int s=1;
    int main()
    {
        
        cin>>n>>m;
    again:
        int ans=0;
        for(int i=1;i<=n;i++) p[i]=i;
        
        while(m--)
        {
        
            int i,j;
            cin>>i>>j;
            i=find(i);
            j=find(j);
            if(i!=j)
            {
        
                p[i]=j;//模板
            }
        }
        
        for(int i=1;i<=n;i++)
        {
        
            if(find(i)==i)
            {
        
                ans++;
            }
        }
        printf("Case %d: %d\n",s++,ans);
        
        cin>>n>>m;
        if(n==0&&m==0) return 0;
        else goto again;
        
        return 0;
    }

## E - 农场派对 ##

[\#10075. 「一本通 3.2 练习 1」农场派对][10075. _ 3.2 _ 1]  
![在这里插入图片描述][37b7c93b7c4d464bbde7bae871f3ed3a.png]

#include<iostream>
    #include<algorithm>
    #include<cstring>
    
    using namespace std;
    
    #define inf 0x3f3f3f3f//结论，一个很大的数，适合这个算法的初始化
    
    int n,m,x;
    long long g[1010][1010];
    long long path[1010][1010];
    
    int main()
    {
        
        int max=0;
        cin>>n>>m>>x;
        
        for(int i=1;i<=n;i++)
        {
        
            for(int j=1;j<=n;j++)
            {
        
                if(i==j) g[i][j]=0;
                else g[i][j]=inf;
            }
        }
        
        for(int i=1;i<=m;i++)
        {
        
            int a,b,t;
            cin>>a>>b>>t;
            g[a][b]=t;
        }
    	
        for(int k=1;k<=n;k++)
        {
        
            for(int i=1;i<=n;i++)
            {
        
                for(int j=1;j<=n;j++)
                {
        
                    if(g[i][j]>g[i][k]+g[k][j])
                    {
        
                        g[i][j]=g[i][k]+g[k][j];
                    }
                }
            }
        }
        //以上全部是算法模板
        for(int i=1;i<=n;i++)
        {
        
            if(g[i][x]+g[x][i]>=max)//这里根据题目要求来写就对了，调试了一会儿AC了
            {
        
                max=g[i][x]+g[x][i];
            }
        }
        
        cout<<max<<endl;
        
        return 0;
    }

## F - 怪物（简易版） ##

[A. Monsters (easy version)][A. Monsters _easy version]  
![在这里插入图片描述][9a2eea0f655744c48a6dceea698c8550.png]

#include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    
    using namespace std;
    
    typedef long long ll;
    
    ll t,n,arr[200010],i,j;
    
    
    int main()
    {
        
        cin>>t;
        while(t--)
        {
        
            ll cnt=0;
            cin>>n;
            
            for(i=1;i<=n;i++) cin>>arr[i];
            
            sort(arr+1,arr+n+1);
            
            if(arr[1]!=1)
            {
        
                cnt+=arr[1]-1;
                arr[1]=1;
            }
            
            for(i=2;i<=n;i++)
            {
        
                if(arr[i]-arr[i-1]>=2)
                {
        
                    cnt+=arr[i]-arr[i-1]-1;
                    arr[i]=arr[i-1]+1;
                }
            }
            cout<<cnt<<endl;
        }
        
        return 0;
    }

## G - 嫌疑犯 ##

[The Suspects][]  
![在这里插入图片描述][6a990b4f28cc4b84adb21b2e947b8650.png]

#include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    
    using namespace std;
    
    int n,m,ans,k;
    int p[100010];
    int a[100010];
    
    int find(int x)
    {
        
        return p[x]==x?x:(p[x]=find(p[x]));//并查集的固定模板
    }
    
    inline void he(int i,int j)
    {
        
        int x=find(i);
        int y=find(j);
        if(x<y)//这里意思是：让小的数做根节点，也是为了贴近题目要求
        {
        
            p[y]=x;
        }
        else p[x]=y;
    }
    
    int main()
    {
        
        while(cin>>n>>m&&n||m)
        {
        
            ans=0;
            for(int i=0;i<n;i++) p[i]=i;//初始化
            
            while(m--)
            {
        
                cin>>k;
                cin>>a[0];//合并
                for(int i=1;i<k;i++)
                {
        
                    cin>>a[i];
                    he(a[i],a[i-1]);
                }
            }
            for(int i=0;i<n;i++)
            {
        
                if(find(i)==0)//根据题意来求解。
                {
        
                    ans++;
                }
            }
            cout<<ans<<endl;
        }
        return 0;
    }

## 比赛情况： ##

大一第十（前面有个学长试水~），退步好多这一次，下面做一下这一周比赛的一个总结，以便于后面的学习。  
![在这里插入图片描述][4eed9aaf8361482ca1d113e53c8c7beb.png]  
表述题目难度以及做题时候的感想：  
`A---`临时加上去的，感觉学长们为了照顾那些爆0的同学加的，简单差分模板。

`B---`这个是我第二个做出来的，花费了我巨多时间，哭了，我的思维还是不够敏捷，需要多加练习思维题目，不然这种题目大家都拿到了，我还要花好多时间才能过，真的很难受的

`C---`没时间做，后面自己尝试了一下子，发现只要根据题目逻辑去写是完全套板子的问题，就是多加一点循环和判断的问题。

`D---`这个更加的板子，我一次可AC了，非常模板。

`E---`Floyd算法的板子题目，我第一个AC的这个题目，相对于板子，只需要加一点判断就可以了，简单。

`F---`没时间做，后面自己尝试了一下子，思维题，被我的好哥们讲懂了，我还是不擅长写思维题目，脑子很笨。

`G---`这个比赛的时候写了，but没写完全，就结束了，后面补了一下题，发现这个题目就是并的时候需要注意外，别的就是板子，害，我可能太笨了。

## 总结 ##

> 心态：就是可能看到别人比我聪明，就心里非常难受，比赛的时候落后，心里更是难受，觉得算法好难学啊，好想退缩，但是算法迟早是要学习的，不如顶住压力，好好学，哪怕倒数第一，也要勇往直前，放平心态，`继续加油夏目浅石`。

> 学习方法：一定要学会思考，把每一周的题目自己`独立思考至少30min`后不会了再去看答案`学习人家的思路`，不然效率很低下。还有就是，昨完一定一定要`总结模板`和`总结思路`，`总结题型！！！！！！！！！！！`

> 时间安排：后续要晚上7-10点好好学习算法，到宿舍补一补学校课程，看看网课，学校课程能逃就逃，然后学点有用的。

**虽然很苦难，但是还是要继续坚持下去。**  
![在这里插入图片描述][53dcb703ea4b4e2095186ad7fb30aae9.png]  
**激励一下自己吧，虽然挺难过的**

[.CSDN]: https://blog.csdn.net/congfen214?type=blog
[ACM_.CSDN]: https://blog.csdn.net/congfen214/category_12101464.html?spm=1001.2014.3001.5482
[f4e0159841ab450d861dde9e8fb5ba0d.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/55185df30572419987cb8882a0d62624.gif
[Color the ball]: https://acm.hdu.edu.cn/showproblem.php?pid=1556
[9075d61ff15143edb21956ac4199fcf6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/6a08818104054e5fa554572ad54aaba0.png
[Suits]: https://www.luogu.com.cn/problem/CF1271A
[05607e07b08e4c85be9d125ac7c393b9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/d55dc78fb0d94f62b8ee505234271dea.png
[Link 1]: https://acm.hdu.edu.cn/showproblem.php?pid=1869
[c0c6dff101884b98aa05db6436ebb123.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/f9201cbbb8ff492681dcf627b0d6866c.png
[POJ]: http://poj.org/problem?id=2524
[f715d43bef714aaba14126989c1406c8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/3f2fa7d8497a498e8ce0b1175a3778d6.png
[10075. _ 3.2 _ 1]: https://loj.ac/p/10075
[37b7c93b7c4d464bbde7bae871f3ed3a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/fffce725f1fd4ddd80adcb11024fae2c.png
[A. Monsters _easy version]: https://codeforces.com/problemset/problem/1784/A
[9a2eea0f655744c48a6dceea698c8550.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/17466e119fb547bd884ce0b6d263c16a.png
[The Suspects]: http://poj.org/problem?id=1611
[6a990b4f28cc4b84adb21b2e947b8650.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/eb132c04c3e44288af518c6f2cfa1863.png
[4eed9aaf8361482ca1d113e53c8c7beb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/74cb27fe82ad4e6db938a55973d63078.png
[53dcb703ea4b4e2095186ad7fb30aae9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/bdcdf633517840a8b83e52c0b71f9ecb.png