ZROI 提高组 Day5

小结:暴力 & 优化

  • 心态不能炸,暴力不能丢
  • 对于每一个数据范围都要思考,从算法复杂度猜测入手,直到确定完整算法
  • 对于下一个数据范围,考虑能否对上一个范围的算法做优化(比如 DP 优化)
  • 优化大多数时候建立在基础算法
  • 不能放弃任何一道题,挂也要写个暴力吊着
  • 对于需要建模的题目,构架数学模型(方程)再优化
  • 对于玄学算法题目,做适当猜测结论,暴力验证
  • 刚写完代码后切不能松懈,思考能否再优化

A. 数组计数

给定 ,你需要计算有几个长度为 的数组 满足:

  • 对于所有 ,有
  • 对于所有 ,有

  • 由于方案数可能过多,你只需要输出答案对 取模后的值

输入格式
第一行两个正整数 n,k
输出格式
输出一个非负整数,表示答案对 取模后的值

样例输入

5 2

样例输出

2

限制
对于 30% 的数据,有 .
对于 50% 的数据,有 .
另有 20% 的数据,满足 .
对于 100% 的数据,有 .
时间限制:2s
空间限制:512MB

Subtask1

,直接乱搞……

Subtask2

既然是 的模样,想到 DP

表示长度为 ,总和为 的数列的方案数,

总复杂度 .

Subtask3

大概是给暴搜的人一点福利……

暴搜的时候可以剪枝,考虑到整个序列的增长速度是 级别(1,1,2,4,8,16…),所以长度为 i 的序列,总和肯定 ,所以搜索的时候剪个枝应该是可以拿到分的。

Subtask4

显然在 Subtask2 的基础上前缀和优化一下,因为在 j 自增的时候,k 的范围是逐渐变大的,所以内层循环就不需要了,每次累加即可。

总复杂度 .

#include<cstdio>
using namespace std;
const int N=(int)1e6+2,K=20+2,P=998244353;
int n,k;
int ans,a[K+2];
int f[K][N];
//f[i,j] 长度为 i,总和为 j 时的方案数
int main(){scanf("%d%d",&n,&k);
    f[0][0]=1;
    for(int i=1;i<=k;i++){int mnj=1<<(i-1);//j 的最小值为 2^(i-1)(相当于一个剪枝)
        f[i][mnj]=f[i-1][mnj>>1];// 求和区间的第一个元素
        for(int j=(1<<(i-1))+1;j<=n;j++){if(j%2==0)f[i][j]=(f[i][j-1]+f[i-1][j/2])%P;// 范围扩大,累加
            else f[i][j]=f[i][j-1];// 即 j-1 时的 k 的范围
        }
    }
    printf("%d",f[k][n]);
    return 0;
}

B. 旅行

给定一棵 个点的树,再给定一个长度为 的序列 .

你需要对每个 都求出一条最短的起点为 ,终点为 的路径(可以多次重复经过同一点),使得 都在这条路径上,你只需要输出符合条件的最短的路径上边的数量。

输入格式
第一行两个正整数
接下来 行,每行两个正整数 ,表示一条边
接下来一行有 个正整数,表示
输出格式
输出 m 行,第 i 行一个非负整数,表示题目中对 i 求的最短路径上边的数量

样例输入

4 3
1 2
2 3
2 4
4 3 1

样例输出

2
4
6

限制
对于 20% 的数据,有 1≤n,m≤5
对于 40% 的数据,有 1≤n,m≤10^3
另有 20% 的数据,满足给定的树是一条链,且 1 号点是端点
另有 20% 的数据,满足所有其他点都和 1 号点有边相连
对于 100% 的数据,有 1≤n,m≤10^5,保证 互不相同
时间限制:2s
空间限制:512MB

Subtask1

5 个点,直接暴搜。

Subtask2

考虑 N 方级别的算法:

对于每一个 i,先把 的点在树上找到并建树(相当于将 到根结点的路径上的点都加入到新建的树中)。

于是对于这个新建的树 ,要求走到 的每个叶结点,并在 结点结束。

显然,从根结点到 的路径上的边只用走一次,其他的边则走两次。所以我们只关心 的边数以及根结点到 的距离。

根结点到 的距离即为 的深度,DFS 遍历即可。而对于 的边数,我们可以 构建 ,在构建的过程中统计边数。

具体的构建就是对于每一个 ,不停地向上爬,并标记走过的祖先;遇到已经被标记的祖先就 break. 如此不重不漏,即可 构建 并统计边数。

总复杂度 O(nm).

Subtask3

既然是一条链,则直接统计每个 i 的前缀 max 即为总距离,减去 到 1 结点的距离即可。

但是在判断是否是链的时候,不仅每个点的度为 2, 还要保证 1 结点的度为 1, 否则不是端点(数据的坑)

Subtask4

树的深度为 1, 则每新增一个点,距离 +2;

如果 是 1,那么不用 +2, 但是结果要输出 ans+1(以 1 结尾).

反正 Sbt3 和 Sbt4 都是乱搞……

Subtask5

在 Sbt2 的基础上,将建树的总复杂度降至 O(n) 即可,因为对每个 建树的结果都可以为 所用

总复杂度 O(n).

#include<cstdio>
#include<cstring>
using namespace std;
const int N=(int)1e5,M=(int)1e5;
int n,m,a[M+2];
// 前向星存图
struct qxx{int nex,t;}e[N*2];
int h[N],cnt;
void add_path(int f,int t){e[++cnt]=(qxx){h[f],t};h[f]=cnt;}
// 树结构 - 左儿子右兄弟
struct node{int p,s,b,dp;}t[N+2];
void add_son(int p,int s){t[s].p=p,t[s].b=t[p].s,t[p].s=s;}
//dfs 建树,求深度
bool vis[N+2];
void dfs(int rt,int dp){vis[rt]=true,t[rt].dp=dp;
    for(int i=h[rt];i;i=e[i].nex)
        if(!vis[e[i].t]){add_son(rt,e[i].t);dfs(e[i].t,dp+1);}
}
int main(){scanf("%d%d",&n,&m);
    for(int i=1,a,b;i<n;i++){scanf("%d%d",&a,&b);
        add_path(a,b);add_path(b,a);
    }
    for(int i=1;i<=m;i++)scanf("%d",&a[i]);
    dfs(1,1);// 建树,求深度
    memset(vis,0,sizeof(vis));
    int tot=-1;// 边的数量比点的数量少 1
    for(int i=1;i<=m;i++){// 处理每个 i
        for(int k=a[i];!vis[k]&&k;k=t[k].p)tot++,vis[k]=true;// 加边
        printf("%d\n",tot*2-t[a[i]].dp+1);
    }
    return 0;
}

  转载请注明: Sshwy's Blog ZROI 提高组 Day5

 上一篇
ZROI 提高组 Day4 ZROI 提高组 Day4
A. 天将 n 个数拆成左右两列, 左边表示买, 右边表示卖, 从左向右连边即表示买入和卖出。 考虑第 天是否卖出, 一定是在左边列的前 个中找一个还未配对的最小值和其配对进行买卖获益最大, 如果最小值
2018.10.01
下一篇 
ZROI2018.8.9 玄学数据结构 ZROI2018.8.9 玄学数据结构
数据结构模拟赛题面 A B C A. 黑桃城直接 DFS 遍历树。子树的 DFN 序是连续的,因此转化为区间上维护,线段树即可。 B. 红五月树剖,详细毒瘤的分类讨论 C. 海棠溪Subtask1-3 动态规划,定义 f[i,j] 表示两朵
2018.10.01
  目录