首页 > 代码库 > BZOJ 3704(昊昊的机油之GRST-维护构造贪心解)
BZOJ 3704(昊昊的机油之GRST-维护构造贪心解)
3704: 昊昊的机油之GRST
Time Limit: 10 Sec Memory Limit: 1024 MBSubmit: 47 Solved: 15
[Submit][Status]
Description
昊昊有个好机油,他就是传说中的着力点。现在昊昊获得了一份长度为n的GRST牌(mod 4 意义下),打算作为送给好机油的生日礼物(不是在2月的么)。但是,昊昊深知他的机油是个神犇,作为数字控的他,只会喜欢特定的序列。但是昊昊不怕,他可以使用一次菲亚特(他的机油最喜欢的大招),将一段区间内的数字全部+1,若某个数字为3,则+1后变为0。但昊昊的神力是有限的,问从初始序列a到达最终序列b,最少需要使用多少次菲亚特。
Input
第一行一个正整数n,表示GRST长度。
接下来两行,每行n个值,分别表示ai bi。
Output
仅一个数,即最少需要使用多少次菲亚特。
Sample Input
3
0 2 1
1 0 2
0 2 1
1 0 2
Sample Output
2
HINT
数据规模与约定
样例说明:第一次对区间[1,2] 使用菲亚特。第二次对区间[2,3] 使用菲亚特。N<=10000000 , 0<=ai,bi<=3
Source
每个单位要按的次数%4 是确定的 记为c1.
如果我们只能对[a,n]进行操作,那么每段高度就是确定且单调增的 记为c
将其拆分为d ,则d∈{0,1,2,3}
考虑,序列 ci,ci+3,c[i+2] 。。单调增。。。cn , 此时ans=cn
若改为 ci,ci-1,c[i+2]-4...cn-4 此时ans‘=ans-3 ([c[i+1],n]减少4,但是多了[ci,ci])
先后对多3,多2,多1情况分析,得到维护后的贪心解。
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<functional> #include<iostream> #include<cmath> #include<cctype> #include<ctime> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=pre[x];p;p=next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=next[p]) #define Lson (x<<1) #define Rson ((x<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (4) #define MAXN (10000000+10) long long mul(long long a,long long b){return (a*b)%F;} long long add(long long a,long long b){return (a+b)%F;} long long sub(long long a,long long b){return (a-b+(a-b)/F*F+F)%F;} int sub(int a,int b){return (a-b+(a-b)/F*F+F)%F;} typedef long long ll; int n,a[MAXN],b[MAXN],c[MAXN],d[MAXN],f[MAXN]; //序列a,b 第i格维护的次数c,c的拆分序列d,f为c的高度/4 int decrease(int h) //h:若c序列中 有 p,p+h 则维护成 p,p+h-4 减少的魔法次数为 { int dec_time=0; For(i,n) if (dec_time<f[i]&&d[i]==h) { d[i]-=4;dec_time++; } For(i,n) c[i]=c[i-1]+d[i]; ForD(i,n) f[i]=min(c[i]/4,f[i+1]); return dec_time*h; } int main() { // freopen("bzoj3704.in","r",stdin); // freopen("bzoj3704.out","w",stdout); scanf("%d",&n); For(i,n) scanf("%d",&a[i]); For(i,n) scanf("%d",&b[i]); c[0]=f[0]=d[0]=0; For(i,n) { c[i]=sub(b[i],a[i])+f[i-1]*4; if (c[i-1]>c[i]) c[i]+=4; d[i]=c[i]-c[i-1]; f[i]=c[i]/4; } // For(i,n) cout<<c[i]<<' ';cout<<endl; // For(i,n) cout<<d[i]<<' ';cout<<endl; // For(i,n) cout<<f[i]<<' ';cout<<endl; c[n+1]=f[n+1]=INF; int ans=c[n]; // cout<<ans<<endl; ForD(i,3) { ans-=decrease(i); } cout<<ans<<endl; return 0; }
BZOJ 3704(昊昊的机油之GRST-维护构造贪心解)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。