广州电商小程序开发,北京seo专业团队,怎样打死网站,石家庄住房和建设局网站正题 题目大意
一个序列AAA可以每次选择一段区间(Ai1)%4(i∈[l..r])(A_{i}1)\%4(i\in [l..r])(Ai1)%4(i∈[l..r])。求最少次数使其变成BBB序列。 解题思路
先计算出每个数字最少加多少可以变成目标数字记录入aaa数组。
然后若不考虑一个数要取模多次的话答案就是 ∑i1nmax…正题 题目大意
一个序列AAA可以每次选择一段区间(Ai1)%4(i∈[l..r])(A_{i}1)\%4(i\in [l..r])(Ai1)%4(i∈[l..r])。求最少次数使其变成BBB序列。 解题思路
先计算出每个数字最少加多少可以变成目标数字记录入aaa数组。
然后若不考虑一个数要取模多次的话答案就是 ∑i1nmax{ai−ai−1,0}(a00)\sum_{i1}^n \max\{a_i-a_{i-1},0\}(a_{0}0)i1∑nmax{ai−ai−1,0}(a00)
但是这道题变成了每个柱子的高度是4kiai(k∈N)4k_{i}a_{i}(k\in \mathbb{N})4kiai(k∈N) 那么我们考虑若一段区间[l..r][l..r][l..r]的kkk要加1会更优那么有 al−al−14lt;ar1−ara_{l}-a_{l-1}4lt;a_{r1}-a_{r}al−al−14ar1−ar 那么答案就可以减去(ar1−ar)−(al−al−14)(a_{r1}-a_{r})-(a_{l}-a_{l-1}4)(ar1−ar)−(al−al−14) 那么我们枚举rrr开个桶来计算lll codecodecode
#includecstdio
#includealgorithm
#includecstring
using namespace std;
const int N101000;
int T,n,a[N],ans2147483647,t[5];
int main()
{scanf(%d,T);while(T--){scanf(%d,n);for(int i1;in;i)scanf(%d,a[i]);memset(t,0,sizeof(t));ans0;for(int i1;in;i){int val;scanf(%d,val);a[i](val-a[i]4)%4;ansmax(a[i]-a[i-1],0);}for(int i2;in;i){int ca[i]-a[i-1];if(c0){if(t[1]c1) t[1]--,t[c],ans-c-1;else if(t[2]c2) t[2]--,t[c],ans-c-2; }else t[c4];}printf(%d\n,ans);}
}
