What is the problem D. New Year Concert in Codeforces Round 769 (Div. 2) about?
- 内容介绍
- 文章标签
- 相关推荐
本文共计1319个文字，预计阅读时间需要6分钟。
题目解析：阅读以下内容，理解题目大意。给你一个只包含正整数的数组（a），你可以任意修改其中的元素为任意正整数。问你对（a）的每个前缀和数组（（a_1，a_1+a_2，a_1+a_2+a_3…））进行修改后，最少需要修改多少个元素。
面向题解做题题面看这里题目大意
给你一个只含正整数的数组 \(a\)，你可以任意修改其中的元素为任意正整数，问你对于 \(a\) 的每个前缀数组\((a_1,a_1a_2,a_1a_2a_3\dots)\)，至少需要修改多少个元素，才能满足：该前缀数组中不存在任何一个子区间 \(a_l,a_{l+1}\dots a_{r-1},a_r\)，满足 \(\gcd(a_l,a_{l+1}\dots a_{r-1},a_r)=r-l+1\)，即每个子区间的区间 \(\gcd\) 都不等于区间长度。
\((1\leq n\leq 2e5,~1\leq a_i\leq1e9)\)
题目分析首先考虑最暴力的算法，从左到右，对于每个位置 \(i\)，我们对他前面的每一个位置 \(j(1\leq j\leq i)\) 都判断一下，看下 \(a_j\) 到 \(a_i\) 的区间 \(\gcd\) 是否等于区间长度，如果每个都不等，则不需要修改；否则，至少要修改一个数，修改谁呢？修改为啥呢？设我们要修改的数为 \(a_k\)，注意到可以修改为任意正整数，显然我们只需要将其修改成一个特别大的质数，就可以在保证 \([1,i]\) 区间合法性的同时，让处在后面的区间 \([k+1,n]\) 中的每个位置 \(i'\) 只需判断 \([k+1,i']\) 即可，所以为了保证修改次数为最小，\(k\) 一定要取最大值，因此 \(k=i\)，只需修改 \(a_i\) 即可。
本文共计1319个文字，预计阅读时间需要6分钟。
题目解析：阅读以下内容，理解题目大意。给你一个只包含正整数的数组（a），你可以任意修改其中的元素为任意正整数。问你对（a）的每个前缀和数组（（a_1，a_1+a_2，a_1+a_2+a_3…））进行修改后，最少需要修改多少个元素。
面向题解做题题面看这里题目大意
给你一个只含正整数的数组 \(a\)，你可以任意修改其中的元素为任意正整数，问你对于 \(a\) 的每个前缀数组\((a_1,a_1a_2,a_1a_2a_3\dots)\)，至少需要修改多少个元素，才能满足：该前缀数组中不存在任何一个子区间 \(a_l,a_{l+1}\dots a_{r-1},a_r\)，满足 \(\gcd(a_l,a_{l+1}\dots a_{r-1},a_r)=r-l+1\)，即每个子区间的区间 \(\gcd\) 都不等于区间长度。
\((1\leq n\leq 2e5,~1\leq a_i\leq1e9)\)
题目分析首先考虑最暴力的算法，从左到右，对于每个位置 \(i\)，我们对他前面的每一个位置 \(j(1\leq j\leq i)\) 都判断一下，看下 \(a_j\) 到 \(a_i\) 的区间 \(\gcd\) 是否等于区间长度，如果每个都不等，则不需要修改；否则，至少要修改一个数，修改谁呢？修改为啥呢？设我们要修改的数为 \(a_k\)，注意到可以修改为任意正整数，显然我们只需要将其修改成一个特别大的质数，就可以在保证 \([1,i]\) 区间合法性的同时，让处在后面的区间 \([k+1,n]\) 中的每个位置 \(i'\) 只需判断 \([k+1,i']\) 即可，所以为了保证修改次数为最小，\(k\) 一定要取最大值，因此 \(k=i\)，只需修改 \(a_i\) 即可。