目录

前缀和

P8649 [蓝桥杯 2017 省 B] k 倍区间

并查集（知识点）

P8654 [蓝桥杯 2017 国 C] 合根植物

P8604 [蓝桥杯 2013 国 C] 危险系数 

找规律（哈密顿路径）：

P8623 [蓝桥杯 2015 省 B] 移动距离 

---

前缀和

P8649 [蓝桥杯 2017 省 B] k 倍区间

代码一：大佬详解：点击跳转

#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>

using namespace std;

const int N=2e5+10;
int n,k;
int a[N];
long long int p[N];//前缀和数组，注意，p需要开long long 

int main()
{
    cin>>n>>k;
    map<int,int> mcnt;
    mcnt[0]=1;
    //相当于在所有前缀和中预先加入一个和为0的前缀和 
    //这样能够正确计算出那些直接是k的倍数的子序列数 
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        p[i]=p[i-1]+a[i];
        mcnt[p[i]%k]++;//由同余定理可知 
    }
    
    long long int ans=0;
    for(auto i:mcnt)
    {
        if(i.second>1)
        {
            long long int s=i.second;
            ans+=(s*(s-1))>>1;//s*(s-1)/2 
        }
    }
    cout<<ans<<endl;
    return 0;
}

代码2：

#include<iostream>
#include<map>

using namespace std;

const int N=2e5+10;
int a[N],pre[N];

int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
        
    map<int,int> mp;
    for(int i=1;i<=n;i++)
    {
        pre[i]=(pre[i-1]+a[i])%k;
        mp[pre[i]]++;
    }
    
    int ans=0;
    for(auto i:mp)
    {
        if(i.first==0)
            ans+=i.second*(i.second+1)/2;
        else
            ans+=i.second*(i.second-1)/2;
    }
    cout<<ans<<endl;
    return 0;
 } 

并查集（知识点）

P8654 [蓝桥杯 2017 国 C] 合根植物

该题主要是要求连通块，可用并查集或者bfs

使用并查集方法：思路是通过find函数将合并的根指向同一根节点，最后遍历根节点数即可得出合根植物的种类

#include<iostream>

using namespace std;

const  int N=1e6+10;
int p[N];

int find(int a)
{
    if(p[a]!=a)
    {
        p[a]=find(p[a]);
    }
    return p[a];
}
int main()
{
    int m,n,k;
    cin>>m>>n;
    cin>>k;
    for(int i=1;i<=n*m;i++)//并查集初始化 
        p[i]=i;
        
    for(int i=1;i<=k;i++)
    {
        int x,y;
        cin>>x>>y;
        int px=find(x),py=find(y);//寻找根节点 
        if(px!=py)
            p[px]=py;//通过指向同一根节点实现合并 
    }
    int ans=0;
    for(int i=1;i<=n*m;i++)
        if(find(i)==i)
            ans++;
    cout<<ans<<endl;
    return 0;
}

P8604 [蓝桥杯 2013 国 C] 危险系数 

使用并查集判断连通块，即判断两个点是否连通 

思路：先判断是否连通，不连通输出-1，连通就求关键点个数：将该点和其相连的边删除后u,v两个点是否连通

#include<iostream>

using namespace std;

const int N=2e5+10;

int n,m;//点个数、边个数 
int u,v;
int x[N],y[N];//存储边 
int p[N]; 

int find(int a)
{
    if(p[a]!=a)
        p[a]=find(p[a]);
    return p[a];
}
bool check(int b)//遍历所有点，通过建立一个没有该点（和其边）的集合进行判断 
{
    for(int i=1;i<=n;i++)
        p[i]=i;
    for(int i=1;i<=m;i++)
    {
        if(x[i]==b||y[i]==b)//将遍历的点和边删除
            continue;
        int px=find(x[i]),py=find(y[i]);
        if(px!=py)
            p[px]=py;
     } 
    return find(u)!=find(v);
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x[i]>>y[i];
     }
     cin>>u>>v;//读入询问的两点 
     for(int i=1;i<=n;i++)
        p[i]=i;//并查集初始化
    for(int i=1;i<=m;i++)
    {
        int px=find(x[i]),py=find(y[i]);
        if(px!=py)
            p[px]=py;
     } 
    if(find(u)!=find(v))//当两个点不连通时 
    {
        cout<<"-1"<<endl;
        return 0;
    }
    
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(i!=u&&i!=v)//不能是要查的点 
        {
            if(check(i))
                ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

找规律（哈密顿路径）：

P8623 [蓝桥杯 2015 省 B] 移动距离 

哈密顿路径：实现方法：横坐标的绝对值和纵坐标的绝对值之和
人话：求n，m对应的行列数，并将其对应的行、列相减，并将其绝对值相加即可得出结果
设定最上面为第一行，
可先从简单的行位置求起：通过位置发现规律求：x1=m/w+1（疑惑点：当m=12时x1=3，不对了）
再在确定行的前提下，通过位置关系的规律求列：
先假设不是蛇形排列时的列数，当为偶数时再进行修改（蛇形排列的位置与不是的位置是相对位置的）

#include<cmath>

using namespace std;

int w,n,m;

int main()
{
    cin>>w>>m>>n;
    int x1,y1,x2,y2;
    x1=m/w+1;//行
    x2=n/w+1;
    
    y1=m%w;//列，假设不为蛇形排列时
    y2=n%w;
    //注意：6是特殊位置，要进行特判
    if(y1==0)
        y1=w;
    if(y2==0)
        y2=w;
        
    if(x1%2==0)//当是偶数行时，要进行变化（蛇形排列）
        y1=w-y1+1;
    if(x2%2==0)
        y2=w-y2+1; 
    cout<<abs(x1-x2)+abs(y1-y2)<<endl;//相减的绝对值 
    return 0;
}