CCF202104-4 校门外的树(100分)【打表】

2024-04-08 16:32
文章标签 100 打表 门外 ccf202104

本文主要是介绍CCF202104-4 校门外的树(100分)【打表】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

试题编号: 202104-4
试题名称: 校门外的树
时间限制: 1.0s
内存限制: 512.0MB
问题描述:

问题描述

X 校最近打算美化一下校园环境。前段时间因为修地铁,X 校大门外种的行道树全部都被移走了。现在 X 校打算重新再种一些树,为校园增添一抹绿意。

X 校大门外的道路是东西走向的,我们可以将其看成一条数轴。在这条数轴上有n个障碍物,例如电线杆之类的。虽然障碍物会影响树的生长,但是障碍物不一定能被随便移走,所以 X 校规定在障碍物的位置上不能种树。n个障碍物的坐标都是整数;如果规定向东为正方向,则 n障碍物的坐标按照从西到东的顺序分别为a1,a2,…,an。X 校打算在[a1,an]之间种一些树,使得这些树看起来比较美观。

X 校希望,在一定范围内,树应该是等间隔的。更具体地说,如果把[a1,an)划分成一些区间[ap1,ap2),…,[apm-1,apm), (1=p1<p2<···<pm=n),那么每个区间[api,api+1)内需要至少种一棵树,且该区间内种的树的坐标连同区间端点api,api+1应该构成一个等差数列。不同区间的公差,也就是树的间隔可以不相同。

例如,如果障碍物位于0,2,6这三处,那么我们可以选择在[0,2)和[2,6)分别种树,也可以选择在[0,6)等间隔种树。如果是分别在[0,2)和[2,6)种树,由于每个区间内至少要种一棵树,坐标1上必须种树;而[2,6)上的树可以按照1的间隔种下,也可以按照2的间隔种下。下图表示了这两种美观的种树方案,其中橙色的圆表示障碍物,绿色的圆表示需要在这个位置种树,箭头上的数字表示种下这棵树时对应的间隔为多少。
在这里插入图片描述

对区间[0,2)和[2,6)分别以1和2的间隔种树是美观的
在这里插入图片描述

对区间[0,2)和[2,6)分别以1的间隔种树也是美观的

而如果选择在[0,6)区间等间隔种树,我们只能以3的间隔种树,因为无论是选择间隔1或者间隔2,都需要在坐标2上种树,而这个位置已经有障碍物了。下图分别表示了间隔为3,2,1时的种树情况,红色箭头表示不能在这里种树。
在这里插入图片描述

对区间[0,6)以3的间隔种树是美观的
在这里插入图片描述

对区间[0,6)以2的间隔种树是不美观的
在这里插入图片描述

对区间[0,6)以1的间隔种树也是不美观的

一般地,给定一个区间[al,ar),对于树的坐标的集合 T(al,ar)(TZ),归纳定义T在[al,ar)上是美观的:

1.如果T≠Ø,T∩{al,al+1,…,ar}=Ø,并且存在一个公差d≥1,使得T∪{al,ar}中的元素按照从小到大的顺序排序后,可以构成一个公差为d的等差数列(显然,这个等差数列的首项为al,末项为ar),则T在[al,ar)上是美观的;
2.如果T∩{al,al+1,…,ar}=Ø,并且存在一个下标m(l<m<r),使得T∩(al,am)在[al,am)是美观的,且T∩(am,ar)在[am,ar)上是美观的,则T在[al,ar)上是美观的。

根据这一定义,空集在任意区间上都不是美观的;另外,如果存在下标i使得ai∈T ,那么T一定不是美观的。

我们称两种种树的方案是本质不同的,当且仅当两种方案中,种树的坐标集合不同。请帮助 X 校对[a1,an)求出所有本质不同的美观的种树方案。当然,由于方案可能很多,你只需要输出总方案数对109+7取模的结果。

输入格式

输入的第一行包含一个正整数n,表示障碍物的数量。

输入的第二行包括n个非负整数a1,…,an,表示每个障碍物的坐标。

保证对i=1,2,…,n-1,ai<ai+1。

输出格式

输出一个非负整数,表示本质不同的美观的种树方案的数量对109+7取模的结果。

样例输入

3
0 2 6

样例输出

3

样例说明

这组样例即为题面描述中提到的那组。

样例输入

11
0 10 20 30 40 50 60 70 80 90 100

样例输出

256507

样例输入

333
33 44 67 210 528 762 873 984 1234 1466 1739 2859 3421 4061 4598 5172 5201 5220 5261 5322 5389 5559 6670 7070 7898 8079 8129 8192 8616 8641 8806 9559 9585 9750 10263 10627 10674 10692 10903 11649 11885 12179 12307 12743 13173 13352 13389 13496 13611 15292 15321 16018 16327 16415 16959 16972 17499 17617 17786 18476 18966 19239 19498 19875 20312 20392 21603 21620 21730 21967 21972 21999 22015 22590 22775 23709 23839 24165 24408 24595 25160 25479 25812 26482 27328 28101 28297 28305 28342 28557 28986 29110 29401 29765 30292 30493 30739 31027 31201 31218 31414 32089 32759 32770 32777 32815 32877 32890 33297 33457 33603 33757 33866 34498 34525 34659 34679 34861 34870 34997 35311 35846 36411 36457 36738 36902 37940 38228 40156 40320 40705 40737 40803 41066 41443 41460 41954 41968 42040 42062 42099 43281 43320 43527 43537 43587 43729 44750 44822 45655 45769 46109 46525 47060 47128 47999 48635 48887 48981 49366 49424 49524 50546 50580 50689 51332 51861 51943 52097 52702 53009 53067 53397 53526 53901 54280 54399 54801 55535 55592 55740 55843 56110 56428 56552 56682 56848 57179 57688 57797 57847 57959 58330 58831 59553 59699 59884 59939 61233 61636 61732 61908 62145 62549 62649 62740 62912 62971 63053 64312 64322 64412 64816 64845 64873 64923 64976 65023 65166 65496 66065 66491 66803 66941 67081 68331 68336 68360 68476 69179 69719 69758 69948 70072 70544 70598 70990 71014 71454 71687 71743 71958 72282 72384 72456 72985 73327 74325 75046 75097 76647 77062 77088 77431 77553 77673 77753 78217 78518 78564 79565 79588 79686 80275 80939 81052 81348 81386 81440 81589 81610 81793 82408 82801 82836 83239 83466 83610 83867 83943 84441 84467 85248 85305 85554 85565 85758 86251 86603 86743 87323 87565 87824 87833 88265 88309 89178 89509 89618 89699 89708 90331 90359 90878 90902 91449 92284 92374 92549 92609 93609 94345 94934 95140 95475 95733 95985 95995 96270 96641 96807 97003 97632 98160 98677 98853 98943 99037 99055 99075 99185 99395 99592

样例输出

7094396

评测用例规模与约定

对于10%的数据,保证n=2;

对于30%的数据,保证n≤10;

对于60%的数据,保证n≤100,ai≤1000;

对于100%的数据,保证2≤n≤1000,0≤ai≤100,000,且至少存在一种美观的种树方案。

问题链接:CCF202104-4 校门外的树
问题简述:(略)
问题分析:打表预处理。
程序说明:(略)
参考链接:(略)
题记:(略)

100分的C++语言程序如下:

/* CCF202104-4 校门外的树 */#include <bits/stdc++.h>//#define DEBUGusing namespace std;const int MOD = 1e9 + 7;
const int N = 1000 + 1;
const int AI = 100000 + 1;int n, a[N];
long long f[N];
bool flag[AI];int main()
{vector<int> v[AI];for (int i = 1; i < AI; i++)for (int j = 2 * i; j < AI; j += i)v[j].push_back(i);#ifdef DEBUGfor (int i = 1; i <= 20; i++) {printf("Case #%d: ", i);for (int j = 0; j < (int)v[i].size(); j++)printf("%d ", v[i][j]);printf("\n");}
#endifscanf("%d", &n);for (int i = 1; i <= n; i++) scanf("%d", &a[i]);f[1] = 1;for (int i = 2; i <= n; i++) {memset(flag, false, sizeof flag);for (int j = i - 1; j >= 1; j--) {int d = a[i] - a[j], cnt = 0;for (int k:v[d])if (!flag[k]) cnt++, flag[k] = true;flag[d] = true;f[i] = (f[i] + f[j] * cnt) % MOD;}}printf("%lld\n", f[n]);return 0;
}

AC的C++语言程序如下:

这篇关于CCF202104-4 校门外的树(100分)【打表】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/886090

相关文章

uva 568 Just the Facts(n!打表递推)

题意是求n!的末尾第一个不为0的数字。 不用大数,特别的处理。 代码: #include <stdio.h>const int maxn = 10000 + 1;int f[maxn];int main(){#ifdef LOCALfreopen("in.txt", "r", stdin);#endif // LOCALf[0] = 1;for (int i = 1; i <=

uva 10916 Factstone Benchmark(打表)

题意是求 k ! <= 2 ^ n ,的最小k。 由于n比较大,大到 2 ^ 20 次方,所以 2 ^ 2 ^ 20比较难算,所以做一些基础的数学变换。 对不等式两边同时取log2,得: log2(k ! ) <=  log2(2 ^ n)= n,即:log2(1) + log2(2) + log2 (3) + log2(4) + ... + log2(k) <= n ,其中 n 为 2 ^

计蒜客 Half-consecutive Numbers 暴力打表找规律

The numbers 11, 33, 66, 1010, 1515, 2121, 2828, 3636, 4545 and t_i=\frac{1}{2}i(i+1)t​i​​=​2​​1​​i(i+1), are called half-consecutive. For given NN, find the smallest rr which is no smaller than NN

【LeetCode热题100】前缀和

这篇博客共记录了8道前缀和算法相关的题目,分别是:【模版】前缀和、【模版】二维前缀和、寻找数组的中心下标、除自身以外数组的乘积、和为K的子数组、和可被K整除的子数组、连续数组、矩阵区域和。 #include <iostream>#include <vector>using namespace std;int main() {//1. 读取数据int n = 0, q = 0;ci

牛客小白月赛100部分题解

比赛地址:牛客小白月赛100_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ A.ACM中的A题 #include<bits/stdc++.h>using namespace std;#define ll long long#define ull = unsigned long longvoid solve() {ll a,b,c;cin>>a>>b>

牛客小白月赛100(A,B,C,D,E,F三元环计数)

比赛链接 官方讲解 这场比较简单,ABC都很签到,D是个不太裸需要预处理的 B F S BFS BFS 搜索,E是调和级数暴力枚举,F是三元环计数。三元环考的比较少,没见过可能会偏难。 A ACM中的A题 思路: 就是枚举每个边变成原来的两倍,然后看看两短边之和是否大于第三边即可。 不能只给最短边乘 2 2 2,比如 1 4 8 这组数据,也不能只给第二短边乘 2 2 2,比

诺瓦星云校招嵌入式面试题及参考答案(100+面试题、10万字长文)

SPI 通信有哪些内核接口? 在嵌入式系统中,SPI(Serial Peripheral Interface,串行外设接口)通信通常涉及以下内核接口: 时钟控制接口:用于控制 SPI 时钟的频率和相位。通过设置时钟寄存器,可以调整 SPI 通信的速度以适应不同的外设需求。数据发送和接收接口:负责将数据从主机发送到从机以及从从机接收数据到主机。这些接口通常包括数据寄存器,用于存储待发

高精度打表-Factoring Large Numbers

求斐波那契数,不打表的话会超时,打表的话普通的高精度开不出来那么大的数组,不如一个int存8位,特殊处理一下,具体看代码 #include<stdio.h>#include<string.h>#define MAX_SIZE 5005#define LEN 150#define to 100000000/*一个int存8位*/int num[MAX_SIZE][LEN];void

多个线程如何轮流输出1到100

多个线程如何轮流输出1到100的值 这个面试问题主要考察如何让线程同步,首先线程同步必会用到的就是互斥锁,互斥锁保证多个线程对数据的同时操作不会出错。但是线程同步还会用到条件变量condition_variable,condition_variable(条件变量)是 C++11 中提供的一种多线程同步机制,它允许一个或多个线程等待另一个线程发出通知,以便能够有效地进行线程同步。 conditi

【最新华为OD机试E卷-支持在线评测】机器人活动区域(100分)多语言题解-(Python/C/JavaScript/Java/Cpp)

🍭 大家好这里是春秋招笔试突围 ,一枚热爱算法的程序员 ✨ 本系列打算持续跟新华为OD-E/D卷的三语言AC题解 💻 ACM金牌🏅️团队| 多次AK大厂笔试 | 编程一对一辅导 👏 感谢大家的订阅➕ 和 喜欢💗 🍿 最新华为OD机试D卷目录,全、新、准,题目覆盖率达 95% 以上,支持题目在线评测,专栏文章质量平均 94 分 最新华为OD机试目录: https://blog.