今天做的一些1600左右的cf题 其中需要特别注意的是一种对subarray处理的方法:遍历右端点
1333C:Eugene and an array|1700|处理子串遍历 一个串如果有子串和为0是不好的。给出一个串,求好的子串个数。 显然我们可以求前缀和,然后二次出现的两点间即为一个和为0的区间。 一个串不能包含一个这样的区间。 但是如何高效遍历之? 对于全部子串这种两个范围的,可以对右端点遍历,即求以i为结尾的所有个数(即i的贡献)。 此时,维护上一个0区间的起点位置即可,从他到i的每个起点对应一个子串。注意0区间不一定是以i为右端点的,但是必然有一个右端点,所以每次发现0区间的右端点,都要更新一次。 实现如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 const int maxn=2e5 +10 ;ll d[maxn]; int main () { std ::ios::sync_with_stdio(false );std ::cin .tie(0 ); int n;cin >>n; ll ans=0 ; ll tmp=0 ; map <ll,ll> ma; d[0 ]=0 ; ma[0 ]=1 ; ll now=-1 ; for (ll i=1 ;i<=n;++i){ cin >>tmp; d[i]=d[i-1 ]+tmp; now=max(now,ma[d[i]]); ans+=(i-now); ma[d[i]]=i+1 ; } cout <<ans<<endl ; }
和上一题类似,原本遍历每个值和判断复杂度爆炸,通过二分变为nlogn,其中check部分经过优化,否则也是n方的而且实现复杂。 我们是对答案二分,所以只要判断这个答案的大小,check中,对数列求一个前缀和,若大于此答案记1,否则-1,如果一个区间比0大,这个区间的中位数将比此答案更大。 同样,我们需要遍历区间,则遍历区间右端点,为了尽量使得此段值大,维护一个最小的值即可(注意保持区间长度至少k)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 const int maxn=2e5 +10 ;int n,m;int in[maxn];int nums[maxn];int db[maxn];int cnt[maxn];int ask (int k) { for (int i=1 ;i<=n;++i){ db[i]=(in[i]>=k ? 1 :0 )*2 -1 +db[i-1 ]; } int now=0 ; for (int i=m;i<=n;++i){ if (db[i]-now>=1 ){ return 1 ; }else { now=min(now,db[i+1 -m]); } } return 0 ; } int main () { std ::ios::sync_with_stdio(false );std ::cin .tie(0 ); cin >>n>>m; int l=inf,r=0 ; for (int i=1 ;i<=n;++i){ cin >>in[i]; l=min(l,in[i]); r=max(r,in[i]); } while (l!=r){ int mid=(l+r+1 )/2 ; int tag=ask(mid); if (tag){ l=mid; }else { r=mid-1 ; } } cout <<l<<endl ; }
1253C:sweets eating|1500|分组前缀和 需要处理的是k个糖,每天最多吃m个,从第1天开始,糖的影响值是天数与其甜度之积。 求最小总影响。(题目要求k遍历1-n) 在纸上模拟,可以发现,随着k增加,每次增加的是与index模m相关的一个子序列的前缀和。 可以推出对应前缀和是序列中前$k+m-(i mod m==0? m:i mod m) \over m$个数的和。 可以实现如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 const int maxn=2e5 +100 ;ll in[maxn]; vector <ll> res[maxn];int main () { std ::ios::sync_with_stdio(false );std ::cin .tie(0 ); ll n,m; cin >>n>>m; for (ll i=1 ;i<=n;++i){ cin >>in[i]; } sort(in+1 ,in+1 +n); for (ll i=1 ;i<=n;++i){ ll tmp; if (res[i%m].size()==0 ){ tmp=0 ; }else tmp=res[i%m][res[i%m].size()-1 ]; res[i%m].push_back(tmp+in[i]); } ll ans=0 ; for (ll i=1 ;i<=n;++i){ ll tmp=(i+m-(i%m==0 ? m:i%m))/m; ans+=res[i%m][tmp-1 ]; cout <<ans<<' ' ; }cout <<endl ; }
1337C:linova and kingdom|1600|greedy 比较水,可以发现,每个点被取到时,子数必然填满,即贡献确定,存图,dfs+回溯,分别求出lv和子树节点数,即可得出lv-sum,对此排序贪心取前k个即可。 注意,由于边是双向边,用disjointSet不方便,而且注意邻接表开2倍边。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 const int maxn=4e5 +10 ;int ver[maxn],head[maxn],nxt[maxn];int d[maxn];int vis[maxn];int tot=0 ;void add (int x,int y) { ver[++tot]=y,nxt[tot]=head[x],head[x]=tot; } int dfs (int x,int v) { vis[x]=1 ; int sum=0 ; for (int i=head[x];i;i=nxt[i]){ int y=ver[i]; if (vis[y]==0 ){ sum+=dfs(y,v+1 ); } } d[x]=v-sum; return sum+1 ; } int main () { int n,k;cin >>n>>k; int x,y; for (int i=1 ;i<n;++i){ cin >>x>>y; add(x,y);add(y,x); } dfs(1 ,0 ); ll ans=0 ; sort(d+1 ,d+1 +n); for (int i=n;i>n-k;--i){ ans+=d[i]; } cout <<ans<<endl ; }
1334C:circle of monsters|1600|水 。。。这题应该900分吧
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 const int maxn=3e5 +10 ;ll a[maxn]; ll b[maxn]; int main () { std ::ios::sync_with_stdio(false );std ::cin .tie(0 ); per(){ int n;cin >>n; for (int i=1 ;i<=n;++i){ cin >>a[i]>>b[i]; } a[0 ]=a[n]; b[0 ]=b[n]; ll ans=0 ; ll start=-1 ; ll now=INF; for (int i=1 ;i<=n;++i){ if (now>min(a[i],b[i-1 ])){ now=min(a[i],b[i-1 ]); start=i; } } ans+=a[start]; for (int i=start+1 ;i<=n;++i){ ans+=max(0l l,a[i]-b[i-1 ]); } for (int i=1 ;i<start;++i){ ans+=max(0l l,a[i]-b[i-1 ]); } cout <<ans<<endl ; } return 0 ; }
1332:K-complete word|1500|字符串 最终的结果是一个重复出现的回文串,所以一些位置是相关联的,分别决定改成哪个即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 const int maxn=2e5 +10 ;char in[maxn];int num[maxn][26 ];int main () { std ::ios::sync_with_stdio(false );std ::cin .tie(0 ); per(){ int n,k;cin >>n>>k; for (int i=1 ;i<=k;++i){ for (int j=0 ;j<26 ;++j){ num[i][j]=0 ; } } cin >>in+1 ; for (int i=1 ;i<=n;++i){ num[(i%k==0 ? k:i%k)][in[i]-'a' ]++; } int div=n/k; ll ans=0 ; if (k%2 ==0 ){ int tmp=k/2 ; for (int j=1 ;j<=tmp;++j){ int cnt=0 ; for (int li=0 ;li<26 ;++li){ cnt=max(cnt,num[j][li]+num[k+1 -j][li]); } ans+=2 *div-cnt; } }else { int tmp=k/2 ; for (int j=1 ;j<=tmp;++j){ int cnt=0 ; for (int li=0 ;li<26 ;++li){ cnt=max(cnt,num[j][li]+num[k+1 -j][li]); } ans+=2 *div-cnt; } int cn=0 ; for (int li=0 ;li<26 ;++li){ cn=max(cn,num[tmp+1 ][li]); } ans+=(div-cn); } cout <<ans<<endl ; } return 0 ; }
1469C:building a fence|1600|dp 两段是确定的,我们从1开始,下一个位置被其前驱限制,也被h限制,取其交集(如果取不出就失败)为取值范围,进而限制下一个。最后一个在第n-1的限制内即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 const int maxn=2e5 +10 ;int h[maxn];int at[maxn];int ad[maxn];int main () { std ::ios::sync_with_stdio(false );std ::cin .tie(0 ); per(){ int n,k;cin >>n>>k; for (int i=1 ;i<=n;++i) cin >>h[i]; at[1 ]=ad[1 ]=h[1 ]+k; at[n]=ad[n]=h[n]+k; int tag=1 ; for (int i=2 ;i<n;++i){ int l=h[i]+k,r=h[i]+2 *k-1 ; int l2=ad[i-1 ]-k+1 ,r2=at[i-1 ]+k-1 ; if (l>r2||l2>r){ tag=0 ; break ; }else { ad[i]=max(l,l2); at[i]=min(r,r2); } } int l2=ad[n-1 ]-k+1 ,r2=at[n-1 ]+k-1 ; if (!(at[n]>=l2&&at[n]<=r2)){ tag=0 ; } if (tag){ cout <<"YES" <<endl ; }else cout <<"NO" <<endl ; } }
1330A:Dreamoon and Ranking Collection|900|水 模拟即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 const int maxn=305 ;int in[maxn];int main () { std ::ios::sync_with_stdio(false );std ::cin .tie(0 ); per(){ memset (in,0 ,sizeof in); int n,x;cin >>n>>x; int tmp;for (int i=1 ;i<=n;++i){ cin >>tmp; in[tmp]=1 ; } int ans=0 ; for (int i=1 ;i<=300 ;++i){ if (in[i]==1 ){ ans++; }else { if (x>0 ){ x--; ans++; }else { break ; } } } cout <<ans<<endl ; } }
1476C:Longest Simple Cycle|1600|dp 从最后一个开始dp,每次考虑,是当前这一根长,还是一个顺时针转90度的欧姆形的长,如果连在一点了必须结算,重新计数,到第一个必须结束。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 const int maxn=1e5 +10 ;ll a[maxn]; ll b[maxn]; ll c[maxn]; int main () { std ::ios::sync_with_stdio(false );std ::cin .tie(0 ); per(){ int n;cin >>n; for (int i=1 ;i<=n;++i)cin >>c[i]; for (int i=1 ;i<=n;++i)cin >>a[i]; for (int i=1 ;i<=n;++i)cin >>b[i]; ll now=c[n]-1 ; ll ans=0 ; for (int i=n-1 ;i>=1 ;--i){ ll tmp=abs (a[i+1 ]-b[i+1 ]); if (tmp==0 ){ ans=max(ans,now+2 ); now=c[i]-1 ; }else { now+=2 ; ans=max(ans,now+tmp); now+=c[i]-1 -tmp; now=max(now,c[i]-1 ); } } cout <<ans<<endl ; } return 0 ; }