Codeforces Round #590 (Div. 3) (A,B,C,D（线段树）,E（线段树）)

最近本来是不打算写CF的题解的，但这场是我第一次上蓝的场，就来写写吧。。

题目链接

前三题水题，我15分钟秒了。。

A. Equalize Prices Again

#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=(b);++i) #define mem(a,x) memset(a,x,sizeof(a)) #define pb push_back #define pi pair<int, int> #define mk make_pair using namespace std; typedef long long ll; ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;} const int N=1e2+10; ll a[N]; int main() { int _;cin>>_;while(_--) { int n;scanf("%d",&n); ll sum=0; for(int i=1;i<=n;++i) { scanf("%lld",&a[i]); sum+=a[i]; } ll t=0; ll ans=sum/n; if(sum%n) t=1; printf("%lld\n",ans+t); } }

B2. Social Network (hard version)

数组模拟双向队列，map判重即可

#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=(b);++i) #define mem(a,x) memset(a,x,sizeof(a)) #define pb push_back #define pi pair<int, int> #define mk make_pair using namespace std; typedef long long ll; ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;} map<int,int>mp; const int N=2e5+10,M=1e6+10; int a[N]; int que[M]; int n,k; int main() { scanf("%d%d",&n,&k); int sz=0; for(int i=1;i<=n;++i) { scanf("%d",&a[i]); } int l=1,r=0; for(int i=1;i<=n;++i) { int x=a[i]; if(mp[a[i]]) { continue; } else{ if(sz<k) { que[++r]=x; sz++; mp[x]=1; } else{ mp[que[l]]=0; ++l; que[++r]=x; mp[x]=1; } } } //printf("l:%d r:%d\n",l,r); printf("%d\n",sz); for(int i=r;i>=l;--i) printf("%d ",que[i]); }

C. Pipes

两种情况：（1，2）（3，4，5，6）因为可以旋转

（1，2只能继承上一次流动的方向）。而（3，4，5，6）

如果是在一行往右流向它，只能往下转弯。

如果是在二行往右流向它，只能往上转弯。

如果是从下往下流向它，只能往右转弯（往左可能会陷入死循环）

#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=(b);++i) #define mem(a,x) memset(a,x,sizeof(a)) #define pb push_back #define pi pair<int, int> #define mk make_pair using namespace std; typedef long long ll; ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;} const int N=2e5+10; char s[3][N],s2[N]; int n; int main() { int _;cin>>_;while(_--) { scanf("%d",&n); scanf("%s%s",s[1]+1,s[2]+1); int x=1,y=1; int id=1;//1右 2下，3左，4上 while(1<=x&&x<=2&&1<=y&&y<=n) { //printf("x:%d y:%d\n",x,y); if(s[x][y]=='1'||s[x][y]=='2'){ if(id==1) y++; else if(id==2) x++; else if(id==4) --x; } else { if(id==1) { if(x==1) x++,id=2; else x--,id=4; } else if(id==2) { y++; id=1; } else if(id==4) { y++; id=1; } } } if(x==2&&y==n+1) printf("YES\n"); else printf("NO\n"); } }

D. Distinct Characters Queries

线段树维护区间内不同的数。。用一个整数每一位代表一个字母出现。

然后或运算维护区间内的值即可。。。

判断每一位上是否为1代表这个字母是否出现过。。

#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=(b);++i) #define mem(a,x) memset(a,x,sizeof(a)) #define pb push_back #define pi pair<int, int> #define mk make_pair using namespace std; typedef long long ll; ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;} const int N=1e5+10; char s[N]; int a[N],n,q; int sum[4*N]; void up(int id,int l,int r,int pos,int val,int ty) { if(l==r){ if(ty==1) { sum[id]=(1<<val); //printf("pos:%d val:%d %d\n",pos,val,(1<<val)); } else sum[id]=0; return ; } int mid=l+r>>1; //printf("mid:%d\n",mid); if(pos<=mid) up(id<<1,l,mid,pos,val,ty); else up(id<<1|1,mid+1,r,pos,val,ty); sum[id]=sum[id<<1]|sum[id<<1|1]; //printf("ls:%d rs:%d id:%d\n",sum[id<<1],sum[id<<1|1],sum[id]); } int qu(int id,int l,int r,int ql,int qr) { if(ql<=l&&r<=qr) { return sum[id]; } int mid=l+r>>1; int ans=0; if(ql<=mid) ans|=qu(id<<1,l,mid,ql,qr); if(qr>mid) ans|=qu(id<<1|1,mid+1,r,ql,qr); return ans; } int cal(int x) { int ans=0; while(x) { if(x&1) ans++; x=x/2; } return ans; } int main() { scanf("%s",s+1); n=strlen(s+1); //printf("n:%d\n",n); scanf("%d",&q); for(int i=1;i<=n;++i){ up(1,1,n,i,s[i]-'a',1); } //printf("**anss:%d\n",cal(sum[1])); while(q--) { int ty; scanf("%d",&ty); if(ty==2){ int l,r;scanf("%d%d",&l,&r); int ans=qu(1,1,n,l,r); printf("%d\n",cal(ans)); } else{ int pos; char c[5]; scanf("%d%s",&pos,c); int val=c[0]-'a'; up(1,1,n,pos,val,2); up(1,1,n,pos,val,1); } } }

E. Special Permutations

这题题目很难懂我感觉。。

有这么一个定义：

pos的定义：

f（p）的定义：

 

让你求

公式绕来绕去的。

其实仔细分析一下：

当n=5的时候。。所有的排列是这样的：

1，2，3，4，5

2，1，3，4，5

3，1，2，4，5

4，1，2，3，5

5，1，2，3，4

那么当数组x中相邻的两项为2，4的时候。我们考虑l=2，r=4对所有的排列产生的贡献：

2开头这个排列加上r-1答案

4开头这个排列加上l答案

（1，l)和（r+1,n）区间的排列产生r-1答案

（l+1 ,r-1）区间的排列产生r-l-1答案

那么差分一下或者线段树维护一下区间和就可以了

#include<bits/stdc++.h> using namespace std; const int N=2e5+10; typedef long long ll; #define ls o<<1 #define rs o<<1|1 ll sum[N*4],lazy[N*4]; int n,m; int a[N]; void push(int id,int l,int r) { if(lazy[id]) { lazy[id<<1]+=lazy[id]; lazy[id<<1|1]+=lazy[id]; int m=l+r>>1; sum[id<<1]+=lazy[id]*(m-l+1); sum[id<<1|1]+=lazy[id]*(r-m); lazy[id]=0; return ; } } void up(int id,int l,int r,int ql,int qr,ll val) { if(ql>qr) return ; if(ql<=l&&r<=qr) { lazy[id]+=val; sum[id]+=val*(r-l+1); return ; } push(id,l,r); int mid=l+r>>1; if(ql<=mid) up(id<<1,l,mid,ql,qr,val); if(qr>mid) up(id<<1|1,mid+1,r,ql,qr,val); sum[id]=sum[id<<1]+sum[id<<1|1]; } ll qu(int id,int l,int r,int pos) { if(l==r) return sum[id]; int mid=l+r>>1; push(id,l,r); if(pos<=mid) return qu(id<<1,l,mid,pos); return qu(id<<1|1,mid+1,r,pos); } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;++i) scanf("%d",&a[i]); for(int i=2;i<=m;++i) { int l=a[i-1]; int r=a[i]; if(l>r) swap(l,r); if(l==r) continue; up(1,1,n,l,l,r-1); up(1,1,n,r,r,l); if(l-1>=1) up(1,1,n,1,l-1,r-l); if(r+1<=n) up(1,1,n,r+1,n,r-l); if(r-l>1) up(1,1,n,l+1,r-1,r-l-1); } for(int i=1;i<=n;++i) printf("%lld ",qu(1,1,n,i)); }