Java教程

2021“MINIEYE杯”中国大学生算法设计超级联赛 第四场题解

本文主要是介绍2021“MINIEYE杯”中国大学生算法设计超级联赛 第四场题解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

2021“MINIEYE杯”中国大学生算法设计超级联赛   第四场题解

第一题傻瓜题卡了两小时？

6986 Kanade Loves Maze Designing

题意：

给定一棵树，树上每个点的编号从1  - N，然后每个点有一个值。

现在要你从树上每一个点出发，到其他点，然后带入到该函数中求函数值......

有点绕，我们打个比方：

比如现在我们从第 i 个点出发，显然轮到遍历第 j 个点了，函数中 ai,j 代表的就是从i -> j我能拿去不同权值的数量

比如下面这样一棵树

其中：

1 -> 1

2 -> 1

3 -> 4

4 -> 5

5 -> 1

6 -> 4

以上是各个点的权值

那么我们从1 -> 2的ai,j就是1，因为只能拿到1这个种类的数

但是我们从1 -> 4的ai,j就是2，因为我们能拿到1和5这两个数

知道了这个ai,j是怎么回事，下一步就是怎么算？

由于是从一个点出发，我们需要遍历整个图，然后对于一棵树我们可以知道如下性质：

每两点之间的路径有且只有一条(如果不重复经过一条边的话)

那么其实我们从一个节点出发，遍历一遍这个树，就能得到ai,j的值了

具体DFS代码如下：

点击查看代码 
void dfs(int cur,int fa)
{
    if(!cn[c[cur]])
    now[cur] = now[fa] + 1;
    else
    now[cur] = now[fa];
    
    cn[c[cur]] += 1;
    for(int i = head[cur];i;i = a[i].ne)
    {
        int to = a[i].to;
        if(to != fa)
        dfs(to,cur);
    }
    cn[c[cur]] -= 1;
}

简单解释一下：

从cur点出发，如果当前点的权值是第一次遍历得到，那么就相当于是在父亲结点的a i , j基础上+1

否则就是父亲结点的值

然后记录一下这个权值。

后面我们退出当前节点时需要将此权值回溯，也就是 - 1操作~

完整代码：

点击查看代码 
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int MAXN = 2000 + 7;
const int MOD1 = 1e9 + 7;
const int MOD2 = 1e9 + 9;
typedef long long ll;
struct node
{
    int ne,to;
    int w;
}a[MAXN<<2];
int head[MAXN],cnt;
void add(int x,int y,int w = 0)
{
    a[++cnt].ne = head[x];
    head[x] = cnt;
    a[cnt].to = y;
    a[cnt].w = w;
}
ll c[MAXN];
ll pw1[MAXN],pw2[MAXN];
void ini()
{
    pw1[0] = pw2[0] = 1;
    for(int i = 1;i < MAXN;i++)
    {
        pw1[i] = pw1[i - 1]*19560929%MOD1;
        pw2[i] = pw2[i - 1]*19560929%MOD2;
    }
}
ll now[MAXN];
ll cn[MAXN];
void dfs(int cur,int fa)
{
    if(!cn[c[cur]])
    now[cur] = now[fa] + 1;
    else
    now[cur] = now[fa];
    
    cn[c[cur]] += 1;
    for(int i = head[cur];i;i = a[i].ne)
    {
        int to = a[i].to;
        if(to != fa)
        dfs(to,cur);
    }
    cn[c[cur]] -= 1;
}
int main()
{
    int t;
    ini();
//    ll ans = 0;
//    int b[6] = {1,1,2,2,1,2};
//    for(int i = 0;i < 6;i++)
//    {
//        ans = ans + b[i]*pw1[i]%MOD1;
//        ans %= MOD1;
//    }
//    cout<<ans;
//    return 0;
    scanf("%d",&t);
    while(t--)
    {
        for(int i = 1;i <= cnt;i++)
        head[i] = 0;
        cnt = 0;
        
        int n;
        scanf("%d",&n);
        for(int i = 2;i <= n;++i)
        {
            int x;
            scanf("%d",&x);
            add(x,i);
            add(i,x);
        }
        for(int i = 1;i <= n;++i)    scanf("%lld",&c[i]);
        for(int i = 1;i <= n;++i)
        {
            now[i] = 0;
            dfs(i,i);
            ll ans1 = 0,ans2 = 0;
            for(int j = 1;j <= n;++j)
            {
                ans1 = ans1 + now[j]*pw1[j - 1]%MOD1;
                ans1 %= MOD1;
                ans2 = ans2 + now[j]*pw2[j - 1]%MOD2;
                ans2 %= MOD2;
            }
            printf("%lld %lld\n",ans1,ans2);
        }
    }
    return 0;
}

6992 Lawn of the Dead

两场连续的比赛都有从1,1出发到N，M，而且每次都是往右或者往下走的这种题，还是不会，真彩

题意：

给你一个僵尸，开始在(1,1)，只能往右走和往下走，然后有些地方有雷，问你僵尸可以访问的节点数量

思路：

首先我们非常容易得到一个结论，那就是

第一行出现的第一个禁区之后的所有点我们都不能走到

嗯，然后就没有然后了

后面的情况会有些复杂，dalao们觉得简单当我没说QAQ

我们思考一下这样一个问题：

对于一行一段连续的区间，什么情况下我们才能走这段区间的点呢？

看下面的图~

这篇关于2021“MINIEYE杯”中国大学生算法设计超级联赛 第四场题解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航