常 州 集 训 D a y 6

Posted on By 吴洲桐 常 州 集 训 D a y 6无评论

常州集训Day6

上午

今天讲了图的基本概念，存储与遍历，还有DFS树。

图的基本概念

详情见wcz的blog

图的存储

邻接矩阵

通过存储关系来表示图

#include 
using namespace std;
int n,m,x,y,arr[101][101];
int main()
{
    cin >> n >> m;
    for(int i=1;i> x >> y;
        arr[x][y]=1;
        arr[y][x]=1;
    }
    return 0;
}

边集数组

直接存边，可用于Kruskal与Bellman-ford算法。

邻接表

一般使用vector或者链式前向星实现

#include 
using namespace std;
vector a[100001];
int n,m; 
int main()
{
    cin >> n >> m;
    for(int i=0;i> x >> y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    return 0;
}

链式前向星

链表方式的邻接表

#include 
using namespace std;
int n,m;
int head[100],to[100],next[100],w[100],ind=0;
void add(int a,int b,int c)
{
    to[ind]=b;
    w[ind]=c;
    next[ind]=head[a];
    head[a]=ind;
    ind++;
}
int main()
{
    memset(head,-1,sizeof head);
    cin >> n >> m;
    for(int i=0;i> x >> y >> c;
        add(x,y,c);
        add(y,x,c);
    }
    for(int i=1;i<=n;i++)
    {
        printf("%d:",i);
        for(int j=head[i];j!=-1;j=next[j])
        {
            printf("%d ",to[j]);
        }
        printf("\n");
    }
    return 0;
}

图的遍历

深度优先搜索与广度优先搜索

使用邻接矩阵

#include 
using namespace std;
int n,m,x,y,c,vis[101],arr[101][101];
void dfs(int i)
{
    printf("%d ",i);
    for(int j=0;j n >> m;
    for(int i=1;i> x >> y;
        arr[x][y]=1;
        arr[y][x]=1;
    }
    vis[0]=1;
    dfs(0);
    cout << endl;
    memset(vis,0,sizeof vis);
    vis[0]=1;
    bfs();
    return 0;
}

使用邻接表

#include 
using namespace std;
vector a[100001];
int n,m,vis[100001]; 
void dfs(int i)
{
    cout << i << endl;
    for(int j=0;j<a[i].size();j++)
    {
        if(vis[a[i][j]]==0)
        {
            vis[a[i][j]]=1;
            dfs(a[i][j]);
        }
    } 
} 
int que[100001],f=0,r=0;
void bfs()
{
    while(f!=r)
    {
        cout << que[f] < n >> m;
    for(int i=0;i> x >> y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    vis[1]=1;
    dfs(1);
    cout << endl
    memset(vis,0,sizeof vis);
    que[r++]=1,vis[1]=1;
    bfs();
    return 0;
}

DFS树

可以用来检查包含关系

括号结构性质：

对于任意顶点对(u, v), 考虑区间[d[u],f[u]]和[d[v],f[v]], 以下三个性质恰有一个成立：

  • 完全分离；
  • u的区间完全包含在v的区间内, 则在dfs树上u是v的后代；
  • v的区间完全包含在u的区间内, 则在dfs树上v是u的后代；

定理1(嵌套区间定理):

在DFS森林中v是u的后代，当且仅当d[u]<d[v]<f[v]<f[u],即区间包含关系。

使用邻接矩阵

#include 
using namespace std;
int n,e,a[1001][1001],vis[1001];
int st[1001],ed[1001],t=0;
void dfs(int i)
{
    t++;st[i]=t;
    for(int j=1;j<=n;j++)
    {
        if(a[i][j]  1&&!vis[j])
        {
            vis[j]=1;
            dfs(j);
        }
    }
    t++;ed[i]=t;
}
int main()
{
    cin >> n >> e;
    for(int i=1;i> x >> y;
        a[x][y]=1;
    }
    dfs(1);
    for(int i=1;i<=n;i++) cout << st[i] << " " << ed[i] << endl;
    return 0;
}

使用邻接表

#include 
using namespace std;
int n,e,vis[1001];
int st[1001],ed[1001],t=0;
vector a[1001]; 
void dfs(int i)
{
    t++;st[i]=t;
    for(int j=0;j> n >> e;
    for(int i=1;i> x >> y;
        a[x].push_back(y);
    }
    dfs(1);
    for(int i=1;i<=n;i++) cout << st[i] << " " << ed[i] << endl;
    return 0;
}

下午

打比赛

第一题 根据三角形的三边关系：三角形任意两边之和大于第三边。所以就可以写出以下代码：

时间复杂度O(n)

#include 
using namespace std;
int n,a[1001],maxn=0,num=0;
int main()
{
    freopen("triangle.in","r",stdin);
    freopen("triangle.out","w",stdout);
    cin >> n;
    for(int i=1;i>a[i];
    sort(a+1,a+1+n);
    for(int i=n-2;i>=1;i--)
    {
        if(a[i]+a[i+1]>a[i+2]) num=a[i]+a[i+1]+a[i+2];
        maxn=max(maxn,num);
    }
    cout << maxn;
    return 0;
}

第二题 使用空间换时间与前缀和算法进行优化

#include 
using namespace std;
int n,a[200011],b[200011],maxn=-1;
struct node
{
    int l,r;
}c[400100];
int main()
{
    freopen("seq.in","r",stdin);
    freopen("seq.out","w",stdout);
    cin >> n;
    for(int i=1;i> a[i];
    for(int i=1;i<=n;i++) b[i]=b[i-1]+a[i];
    //存储
    for(int i=1;i<=n;i++)
    {
        if(b[i] == 0) c[b[i]+200000].l=0;//前缀和数组中0的第一个位置为数组开始位置的上一个
        else if(c[b[i]+200000].l==0) c[b[i]+200000].l=i;
        c[b[i]+200000].r=i;
    }
    for(int i=-200000;i<=200000;i++)
    {
        maxn=max(maxn,c[i+200000].r-c[i+200000].l);
    }
    if(maxn == 0) cout << -1; //需要特判
    else cout << maxn;
    return 0;
}

第三题 电池-贪心/数学法

打炸了 30分

第四题 搜索剪枝

使用BFS 60分

训练日志

发表回复