csust 第五次周赛题解

csust 第五次周赛题解

题目地址：

A 红黑树

最后得到的字符串只有两种情况
1.brbrbrbrbrb s1
2.rbrbrbrbrbr s2
所以我们只要把这两种情况的操作数算出来取较小的

具体怎么算呢
假设 该位为 b 并且 s1为 r cntb++
该位为 r 并且 s1为 b cntr++
操作数就为 max(cntb,cntr);
s2 同理

#include<iostream>
#include<cstdio>
#include<map>
#include<math.h>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=5e3+7;
const int mod=1e9+7;
string s,s1,s2;
int main (){int n,x1=0,x2=0,x3=0,x4=0;cin>>n>>s;int ans1=0,ans2=0;for(int i=0;i<n;i++){if(i%2==1) s1+='b',s2+='r';else s1+='r',s2+='b';}for (int i=0;i<n;i++){if(s[i]=='b'&&s1[i]=='r') x1++;if(s[i]=='r'&&s1[i]=='b') x2++;}for (int i=0;i<n;i++){if(s[i]=='b'&&s2[i]=='r') x3++;if(s[i]=='r'&&s2[i]=='b') x4++;}printf ("%dn",min(max(x1,x2),max(x3,x4)));
}

B厂里吃鸡王 (多源最短路)

题意：
大概就是你降落在任意一个点，求所有的k种装备到你的最短距离。通俗一点就是，你从起点出发，找到离你最近的装备1，然后传送回起点（传送不需要花费），接着找装备2…（菜鸡的我看了半天才懂）

看完这个题 我最原始的思路是 枚举这n个点，每个点跑一次最短路，然后在一件一件装备的取最小值（这样肯定会t）
然后看完lcjdl的题解，和听他解释了好久，我才知道这个怎么写。
我们观察到 装备数量最多就 100 种，那么我们可不可以把每种装备的点看成一个点，然后求这个点到所有1—n 的点的最短路呢。这样最多就是求 100次最短路了。

怎么把装备相同的点看成一个点呢 我们构造一个点（n+1），然后让这个点和所有装备为 i 的点 建立一条长为0的边，对n+1点跑最短路，就能达到想要的结果了，画个图看看应该就知道了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+7;
const int mod=1e9+7;
ll head[maxn],num=0,dis[maxn],ans[maxn],vis[maxn],vec[108][maxn],si[108];struct exam{ll to,w,next;
}e[maxn<<1];
void add(ll u,ll v,ll w){e[num].next=head[u];e[num].to=v;e[num].w=w;head[u]=num++;
}
void SPFA(ll u){queue<ll >que;memset(vis,0,sizeof(vis));for(int i=0;i<maxn;i++) dis[i]=99999999;dis[u]=0;vis[u]=1;que.push(u);while(!pty()){ll now=que.front();que.pop();vis[now]=0;for(int i=head[now];i!=-1;i=e[i].next){if(dis[now]+e[i].w<dis[e[i].to]){dis[e[i].to]=dis[now]+e[i].w;if(!vis[e[i].to]){que.push(e[i].to);vis[e[i].to]=1;}}}}
}
int main (){memset(head,-1,sizeof(head));ll n,m,k,x,u,v;cin>>n>>m>>k;for(int i=1;i<=n;i++){scanf("%lld",&x);vec[x][si[x]++]=i;}for(int i=0;i<m;i++){scanf("%lld%lld",&u,&v);add(u,v,1);add(v,u,1);}for(int i=1;i<=k;i++){head[n+1]=-1;for(int j=0;j<si[i];j++){add(n+1,vec[i][j],0);add(vec[i][j],n+1,0);}SPFA(n+1);for(int i=1;i<=n;i++){ans[i]+=dis[i];}}for(int i=1;i<=n;i++){if(ans[i]>999999) printf ("0 ");else    printf ("%lld ",ans[i]);}
}

C.战域(优先队列)

首先初始值相同 也就是都是0次的时候是有一个初始值的，这里很容易错。然后就把第1次的花费减去第0次的花费放到优先队列里。然后一个一个取出来 更新答案 更新花费（第x+1次减第x次）后放回去就好了，循环m次。

#include<iostream>
#include<cstdio>
#include<map>
#include<math.h>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=1e6+7;
const int mod=1e9+7;struct node{int a,b,c,d,y;bool operator >(node a) const  {  return d > a.d; }
}s1,s2;int main (){priority_queue<node, vector<node>, greater<node> >que;struct node s1,s2;int n,m,t=0;ll ans=0;scanf("%d%d",&n,&m);for(int i=0;i<n;i++){scanf("%d%d%d",&s1.a,&s1.b,&s1.c);s1.y=1;s1.d=s1.a+s1.b;// printf ("***");que.push(s1);ans+=s1.c;}while(t<m){s2&#p();que.pop();ans+=s2.d;s2.d=2*s2.a*s2.y+s2.a+s2.b;s2.y++;que.push(s2);t++;}printf ("%lldn",ans);
}

D 摆蔬菜2（二分）

先了解一下那啥 n包蔬菜的组合有 (2^n)-1;
然后我们就对重量排个序
从头开始 对每一包蔬菜找最大的合法区间 区间长度len
所以 答案就是 ans+=(2^len)-1;
这样当然是不太对的 因为我们算了很多重复的。所以每次加的时候 还要减去前面算过的。
举个例子 :
6 7
2 4 5 5 10 11
对 2 找合法区间 就是 [2 4 5 5] ans+=2^4-1;
对 4 找合法区间 就是 [4 5 5 10 11] ans+=2^5-1,但是[4,5,5]上一次已经算过了 所以ans -=2^3-1;
这时候 已经到达最右端了 直接 break .(可以想想为什么)
ps:注意减法取模（比赛的时候我就没注意，还好最后几十秒发现了，很刺激） 找合法区间记得二分 了解一下lower_bound

补充 一下 这题我其实想复杂了，听了大佬们的建议，可以简化操作：
同样是枚举每一个点 找最大合法区间，不同点在于计算：
对于 [2 4 5 5] 我们可以一定把2包括在子区间内 这样就变成了算 [4 5 5] 的可以为空的子集 也就是 2^(4-1);
所以答案就是 ans+=2^(len-1) 是不会重复的

代码:

#include<iostream>
#include<cstdio>
#include<map>
#include<math.h>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=1e6+7;
const int mod=1e9+7;
int a[MAXN];
long long poww(long long a,long long b){//快速幂long long ans=1;while(b>0){if(b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans;
}
int main (){ll n,k,ans=0,rr=0;scanf("%lld%lld",&n,&k);for(int i=1;i<=n;i++){scanf("%lld",&a[i]);}sort(a+1,a+n+1);for(int i=1;i<=n;i++){int l=i,r=n,mid;while(l<r){mid=(l+r)/2;if(a[mid]<=a[i]+k) l=mid+1;else r=mid;}if(l==n&&a[i]+k>=a[n]){ans=(ans+(poww(2,l-i+1)-1-poww(2,rr-i+1)+1+mod)%mod)%mod;break;}ans=(ans+(poww(2,l-i)-1-poww(2,rr-i+1)+1+mod)%mod)%mod;rr=l-1;}printf ("%lldn",ans);return 0;
}

E 摆蔬菜1

听学长说是 单调队列 （我貌似还不会）
我是用 rmq+二分 写的

和上题类似 对每个点向右找最大合法区间 （应该是有单调性的）然后利用前缀和更新答案就好了
难点就在于怎么二分吧 我就先不放代码了

代码：

#include<iostream>
#include<cstdio>
#include<map>
#include<math.h>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=5e5+20;
ll a[MAXN],dpma[MAXN][32],dpmi[MAXN][32],pre[MAXN];
ll qa(int l, int r){int k=log((r-l+1)*1.0)/log(2.0);return max(dpma[l][k],dpma[r-(1<<k)+1][k]);
}
ll qi(int l,int r){int k=log((r-l+1)*1.0)/log(2.0);return min(dpmi[l][k], dpmi[r - (1 << k) + 1][k]);
}
int main (){ll n,k,ans=0;scanf("%lld%lld",&n,&k);for(int i=1;i<=n;i++){scanf("%lld",&a[i]);dpma[i][0]=a[i],dpmi[i][0]=a[i];pre[i]=pre[i-1]+a[i];}for(int j=1;(1<<j)<=n;j++){for(int i=1;i+(1<<j)-1<=n;i++){dpma[i][j]=max(dpma[i][j-1],dpma[i+(1<<(j-1))][j-1]);dpmi[i][j]=min(dpmi[i][j-1],dpmi[i+(1<<(j-1))][j-1]);}}for(int i=1;i<=n;i++){int l=i,r=n,mid;while(l<r-1){mid=(l+r)/2;if(qa(i,mid)-qi(i,mid)<=k){l=mid;}else r=mid-1;}if(qa(i,l+1)-qi(i,l+1)<=k&&l+1<=n) ans=max(pre[l+1]-pre[i-1],ans);ans=max(pre[l]-pre[i-1],ans);}printf ("%lldn",ans);return 0;
}