Codeforces Round #590 (Div. 3)

Codeforces Round #590 (Div. 3) A. Equalize Prices Again 题意：求平均值并且向上取整

#include<bits/stdc++.h> #define mset(a,b) memset(a,b,sizeof(a)) using namespace std; #define LL long long const int N=2e5+5; const int mod=1e9+7; int n,m; int a[N]; int main(){ int t; cin>>t; while(t--){ cin>>n; int ans=0; for(int i=1;i<=n;i++) scanf("%d",a+i),ans+=a[i]; printf("%d\n",(ans+n-1)/n); } return 0; }

B：Social Network (hard version) 题意：有一个手机，能接受朋友的消息，按顺序有n条朋友的消息，但是同一时刻只能存在k个朋友的消息，如果>k个，则最找的那个消息丢失。 分析：直接模拟就行，但是由于朋友的id很大，所以要离散化，据说用unorder_map超时，建议看看相关文章，如何优雅的卡掉unorder_map。

#include<bits/stdc++.h> #define mset(a,b) memset(a,b,sizeof(a)) using namespace std; #define LL long long const int N=4e5+5; const int mod=1e9+7; int n,m,k; int a[N],b[N]; bool vis[N]; map<int,int>mp; int main(){ cin>>n>>k; int x=0; for(int i=1;i<=n;i++){ scanf("%d",a+i); if(mp.find(a[i])==mp.end()) mp[a[i]]=++x; } int len=0,la=0; for(int i=1;i<=n;i++){ int x=mp[a[i]]; if(vis[x]) continue; if(len==k) vis[mp[b[la-len+1]]]=false,len--; len++; b[++la]=a[i]; vis[x]=true; } printf("%d\n",len); for(int i=la;i>=la-len+1;i--) printf("%d ",b[i]); return 0; }

C:Pipes 题意：水管流水，起点(1,0)，终点(2,n+1)，有6总类型的水管，编号1,2,3,4,5,6,可以旋转，则{1,2}一样，{3,4,5,6}一样。问水流能不能留到终点。 分析：模拟一下发现水流方向唯一，直接模拟可行，赛中一直在写假dp,还写崩了，多亏群友提醒了一句

#include<bits/stdc++.h> #define mset(a,b) memset(a,b,sizeof(a)) using namespace std; #define LL long long const int N=2e5+5; const int mod=1e9+7; int n,m,k; char a[3][N]; int main(){ int t; cin>>t; while(t--){ scanf("%d",&n); scanf("%s%s",a[1]+1,a[2]+1); for(int i=1;i<=2;i++) for(int j=1;j<=n;j++) if(a[i][j]<='2') a[i][j]=1; else a[i][j]=2; int x=1,y=1,z=(a[1][1]==1)?2:1; while(x>0&&x<=2&&y>=1&&y<=n){ if(z==2){ y++; } else if(z==0){ x--; } else if(z==1){ x++; } if(a[x][y]==2) if(z==2) z=(x==2)?0:1; else z=2; // printf("%d %d %d\n",x,y,z); } if(x==2&&y==(n+1))puts("YES"); else puts("NO"); } return 0; }

D. Distinct Characters Queries 题意：有一个字符串 s, 有两种操作: 1 pos c，将s[pos]修改为c ， 2 l r,查询l,r不同字符的数量。 分析：很容易想到两种写法。 写法1：维护26种字母1—i的数量，单点修改，区间查询。如果一个区间的数量>0则ans++. 写法2：26个set，每个set[i]存的是字符为i的坐标，修改直接find->erase->insert，然后用lower_bound()查找>=l的第一个位置，如果<=r，则ans++.

该题引申出另外一个题：给你n个数字a1,a2,…an,(1<=ai<=n)；有Q组查询，每次查询[l,r]不同数的个数。题目链接：https://ac.nowcoder.com/acm/contest/139/J?&headNav=www

#include<bits/stdc++.h> #define mset(a,b) memset(a,b,sizeof(a)) using namespace std; #define LL long long const int N=1e5+5; const int mod=1e9+7; int n,m,k; char a[N]; int c[27][N]; void upd(int x,int v,int *val){ for(int i=x;i<=n;i+=(i&-i)) val[i]+=v; } int sum(int x,int *val){ int ans=0; for(int i=x;i;i-=i&-i) ans+=val[i]; return ans; } int main(){ scanf("%s",a+1); n=strlen(a+1); for(int i=1;i<=n;i++) upd(i,1,c[a[i]-'a']); int q; scanf("%d",&q); while(q--){ int op; scanf("%d",&op); if(op==1){ int id;char ch; scanf("%d %c",&id,&ch); upd(id,-1,c[a[id]-'a']); upd(id,1,c[ch-'a']); a[id]=ch; } else { int l,r; scanf("%d%d",&l,&r); int ans=0; for(int i=0;i<26;i++){ int x=sum(r,c[i])-sum(l-1,c[i]); if(x) ans++; } printf("%d\n",ans); } } return 0; }

E:Special Permutations 题意： 定义排列 $pi(n)=[i,1,2,....,i-1,i+1,i+2...,n]$; 例如： $p1(4)=[1,2,3,4]$ $p2(4)=[2,1,3,4]$ $p3(4)=[3,1,2,4]$ $p4(4)=[4,1,2,3]$

定义 $pos(p,val)$ 为 val 在排列 pi 中的位置. 则 $pos(pi,val)=\{\begin{array}{cc}val+1& val<i\\ 1& val=i\\ val& val>i\end{array}$

给你 m 个数字 x1,x2,…,xm(1<=xi<=n)

定义 $f(p)={\sum }_{i=1}^{m-1}|pos(p,x_i)-pos(p,x_{i+1})|$

求 $f(p1)+f(p2)+..f(pn)$

分析： 考虑单个的 $f(pi)$，如果排列 p 是正常的话，很容易计算出来，而 $f(pi)$ 相比正常的有哪些区别呢。考虑单个 $|pos(pj,x_i)-pos(pj,x_{i+1})|$ ，这里很容易得到几种情况，假设 $x_i<x_{i+1}$ 一共有五种情况.

$x_i>j$，和正常的情况一样，答案不变$x_i=j$， 变化量为 $|1-x_{i+1}|-|x_i-x_{i+1}|$$x_i<j<x_{i+1}$，变化量为 $|x_i+1-x_{i+1}|-|x_i-x_{i+1}|$$x_{i+1}=j$，变化量为 $|x_i+1-1|-|x_i-x_{i+1}|$$x_{i+1}<j$，和正常的情况一样，答案不变

很明显，对答案有影响的只有情况2,3,4，并且情况2和4对一个f(pj)有影响，情况3是对给一连续的$x_i<j<x_{i+1}$的 $f(pj)$ +该变量，很容易想到用前缀和或者一些数据结构计算答案。

#include<bits/stdc++.h> #define mset(a,b) memset(a,b,sizeof(a)) using namespace std; #define LL long long #define ma make_pair const int N=2e5+5; const int mod=1e9+7; int n,m,k; int a[N]; LL val[N]; int main(){ cin>>n>>m; for(int i=1;i<=m;i++) scanf("%d",a+i); LL x=0; for(int i=1;i<m;i++) x+=abs(a[i]-a[i+1]); val[1]=x; for(int i=1;i<m;i++){ if(a[i]<a[i+1]){ //1 x=abs(a[i]-a[i+1]); x=abs(1-a[i+1])-x; val[a[i]]+=x; val[a[i]+1]-=x; //2 x=abs(a[i]-a[i+1]); x=abs(a[i]+1-a[i+1])-x; val[a[i]+1]+=x; val[a[i+1]]-=x; //3 x=abs(a[i]-a[i+1]); x=abs(a[i]+1-1)-x; val[a[i+1]]+=x; val[a[i+1]+1]-=x; } else if(a[i]==a[i+1]){ ; } else { swap(a[i],a[i+1]); //1 x=abs(a[i]-a[i+1]); x=abs(1-a[i+1])-x; val[a[i]]+=x; val[a[i]+1]-=x; //2 x=abs(a[i]-a[i+1]); x=abs(a[i]+1-a[i+1])-x; val[a[i]+1]+=x; val[a[i+1]]-=x; //3 x=abs(a[i]-a[i+1]); x=abs(a[i]+1-1)-x; val[a[i+1]]+=x; val[a[i+1]+1]-=x; swap(a[i],a[i+1]); } } for(int i=1;i<=n;i++) val[i]+=val[i-1],printf("%lld ",val[i]); return 0; }

F:Yet Another Substring Reverse SosDP

#include <bits/stdc++.h> const int N=2e6+5; const int M=20; #define LL long long using namespace std; int n,dp[N],a[N]; char s[N]; int main(){ cin>>s+1; for(int i=1;s[i];i++){ int x=0,c=0; for(int j=i;s[j];j++){ int t=1<<(s[j]-'a'); if(x&t)break; x|=t;++c; dp[x]=c; a[x]=c; } } for(int i=0;i<=M;i++) for(int j=0;j<(1<<M);j++) if(j&(1<<i)) dp[j]=max(dp[j],dp[j^(1<<i)]); int ans=0; for(int i=0;i<(1<<M);i++) ans=max(ans,a[i]+dp[i^((1<<M)-1)]);//,printf("%d %d\n",a[i],dp[i^((1<<M)-1)]); cout<<ans; return 0; }