牛客练习赛42题解

柔情只为你懂 2021-12-23 14:09 262阅读 0赞

# 吐槽 #

写题写的感觉自己仿佛是个傻子

# 题解 #

## A 字符串 ##

### 题目描述 ###

> 给定两个等长的由小写字母构成的串 A,B，其中 $ |A|=|B|=n $
> 
> 现在你需要求出一个子区间 \$\[l,r\]\$
> 
> 使得$ LCP(A\[l,r\],B\[l,r\])×LCS(A\[l,r\],B\[l,r\])+LCP(A\[l,r\],B\[l,r\])+LCS(A\[l,r\],B\[l,r\])$ 最大，并输出这个值。
> 
> \$LCP(S,T)\$表示S和T的最长公共前缀，\$LCS(S,T)\$表示S和T的最长公共后缀。

### 题解 ###

考虑贪心，因为区间的左右端点可以任意选取，直接处理出premax和sufmax，然后贪心即可

**注意LCP和LCS重合的情况**

### 代码 ###

#include <cstdio> #include <algorithm> #include <cstring> #define int long long #define ull unsigned long long using namespace std; const int base=131; const int MAXN = 200010; ull hasha[MAXN],hashb[MAXN],pows[MAXN]; char a[MAXN],b[MAXN]; int n,maxpre[MAXN],maxsuf[MAXN],pre[MAXN],suf[MAXN]; ull hashax(int l,int r){ return hasha[r]-hasha[l-1]*pows[r-l+1]; } ull hashbx(int l,int r){ return hashb[r]-hashb[l-1]*pows[r-l+1]; } void get_hasha(void){ for(int i=1;i<=n;i++) hasha[i]=hasha[i-1]*base+a[i]; } void get_hashb(void){ for(int i=1;i<=n;i++) hashb[i]=hashb[i-1]*base+b[i]; } int ans=0; signed main(){ int ans=0; scanf("%s",a+1); scanf("%s",b+1); n=strlen(a+1); pows[0]=1; for(int i=1;i<=n;i++) pows[i]=pows[i-1]*base; get_hasha(); get_hashb(); int last=1; for(int i=1;i<=n;i++){ if(hashax(last,i)==hashbx(last,i)){ pre[i]=i-last+1; int len=i-last+1; ans=max(ans,len*len+len+len); } else{ if(a[i]==b[i]){ pre[i]=1; last=i; int len=1; ans=max(ans,len*len+len+len); } else{ pre[i]=0; last=i+1; } } } last=n; for(int i=n;i>=1;i--){ if(hashax(i,last)==hashbx(i,last)){ suf[i]=last-i+1; int len=last-i+1; ans=max(ans,len*len+len+len); } else{ if(a[i]==b[i]){ suf[i]=1; last=i; int len=1; ans=max(ans,len*len+len+len); } else{ suf[i]=0; last=i-1; } } } for(int i=1;i<=n;i++) maxpre[i]=max(maxpre[i-1],pre[i]); for(int i=n;i>=1;i--) maxsuf[i]=max(maxsuf[i+1],suf[i]); for(int i=1;i<=n;i++) ans=max(ans,maxpre[i]*maxsuf[i]+maxpre[i]+maxsuf[i]); printf("%lld\n",ans); return 0; }

## B SHTMYCBDFTT ##

### 题目描述 ###

> 注意本题有模数
> 
> 给定一个 长度为 n 的序列 $\{ a \} $，求：  
> \\\[ max\_\{1\\le i\\le j \\le n\}\\\{(a\_i ⊕ a\_\{i+1\}⊕a\_\{i+2\}⊕\\dots⊕a\_j)+(a\_i+a\_\{i+1\}+a\_\{i+2\}+\\dots+a\_j)\\\} \\\]  
> 考虑一个结论，选上一个新的数，得到的答案绝对不会更劣，所以选上全部即可

### 代码 ###

#include <cstdio> #include <cstring> #include <algorithm> #define int long long using namespace std; const int MOD = 100000007; int xorx=0,sumx=0,n; signed main(){ scanf("%lld",&n); for(int i=1;i<=n;i++){ int x; scanf("%lld",&x); xorx^=x; sumx+=x; } printf("%lld",(xorx%MOD+sumx%MOD)%MOD); return 0; }

## C 出题的诀窍 ##

### 题目描述 ###

> 给定m个长为n的序列a1,a2,…,ama1,a2,…,am。  
> 小Z想问你：  
> \$∑\_\{i\_1=1\}^n∑\_\{i\_2=1\}^n\\dots∑\_\{i\_m=1\}^nSUM(a\_\{1,i\_1\},a\_\{2,i\_2\},…,a\_\{m,i\_m\}) mod(1000000007)\$  
> 其中SUM(一个序列)SUM(一个序列)表示这个序列中所有不同的数的和，相当于先sort,unique再求和。

### 题解 ###

正向不好考虑，可以反向考虑，思考每个值对答案产生贡献的次数，等价于求这个数至少被选中一次的方案数，转化一下就是求总方案数-一次都不选中的方案数，假设一个值\$V\$，在第一行出现\$x\_1\$次，在第二行出现\$x\_2\$次，在第n行出现\$x\_n\$次

则它的贡献次数就是\$time=m^n-(m-x\_1)(m-x\_2)\\dots(m-x\_n)\$

然后没了

### 代码 ###

#include <cstdio> #include <cstring> #include <algorithm> #include <vector> #define int long long using namespace std; const int MOD = 1000000007; int a[2010][2010],n,m,barrel[2010],ans=0; vector<pair<int,int> > Vec; int pow(int a,int b){ int ans=1; while(b){ if(b&1) ans=(ans*a)%MOD; a=(a*a)%MOD; b>>=1; } return ans; } int inv[4000]; signed main(){ scanf("%lld %lld",&n,&m); for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) scanf("%lld",&a[i][j]),Vec.push_back(make_pair(a[i][j],i)); int t; for(int i=1;i<=n;i++) inv[i]=pow(i,MOD-2); int nm=pow(n,m); sort(Vec.begin(),Vec.end()); for(int i=0;i<Vec.size();i=t){ int midt=nm; t=i; for(;t<Vec.size()&&Vec[i].first==Vec[t].first;t++){ midt=(midt*inv[n-barrel[Vec[t].second]])%MOD; barrel[Vec[t].second]++; midt=(midt*(n-barrel[Vec[t].second]))%MOD; } for(int j=i;j<t;j++) barrel[Vec[j].second]=0; ans=(ans+Vec[i].first*(nm-midt+MOD)%MOD)%MOD; } printf("%lld\n",ans); return 0; }

## D 序列上问题 ##

### 题目描述 ###

> 请你求出一个 1 ~ N 的排列，使得它正好有 K 个逆序对。  
> 由于存在很多种这样的排列，所以要求出字典序最大的排列。
> 
> 因为排列可能很长，所以你只用输出类似于将这个排列放到 N+1 进制下的值，即 \$∑\_\{i=1\}^Np\[i\]∗(N+1)^i \\ mod 1000000007(10^9+7)\$ ，其中 p 是你求出的排列。

### 题解 ###

题目保证有解，所以考虑最后的序列形态

第n大的如果放到第一位，会产生n-1个逆序对，同理，同时为满足字典序最大，前面的一定是一段n~n-x的连续序列，之后为满足剩下的逆序对数，第k+1大的数一定会被放到n-x的后面，然后是两端递增的序列1 ~ k，k+2 ~ n-x-1，然后x可以二分求出，k+1大的数可以直接算出，剩下的使用等比数列求和即可得出结果

### 代码 ###

#include <cstdio> #include <algorithm> #include <cstring> #define int long long using namespace std; const int MOD = 1000000007; int n,k,ans; int pow(int a,int b){ int ans=1; while(b){ if(b&1) ans=(ans*a)%MOD; a=(a*a)%MOD; b>>=1; } return ans; } int solve(int start,int l,int r){ if(l>r) return 0; int base=pow(n+1,start); int invn=pow(n,MOD-2),mid=pow(n+1,r-l+1); int val_1=mid*r%MOD; int val_2=((mid-1)*invn+l-1)%MOD; int ans=base*(val_1-val_2+MOD)%MOD*invn%MOD; return ans; } signed main(){ scanf("%lld %lld",&n,&k); int l=0,r=n,midans=0; while(l<=r){ int mid=(l+r)>>1; if((2*n-mid-1)*mid<=k*2) midans=mid,l=mid+1; else r=mid-1; } // printf("%lld\n",midans); k-=(2*n-midans-1)*midans/2;//(n~(n-mid)) // ans=(ans+solve(1,n-midans+1,n))%MOD; // printf("%lld ",solve(1,n-midans+1,n)); ans=(ans+(pow(n+1,midans)-1)*(n+1)-solve(1,0,midans-1)+MOD)%MOD; ans=(ans+solve(midans+1,k+1,k+1))%MOD; // printf("%lld ",solve(midans+1,k+1,k+1)); //x=k+1 ans=(ans+solve(midans+2,1,k))%MOD; // printf("%lld ",solve(midans+2,1,k)); //1~x-1,x+1~n-mid-1 ans=(ans+solve(midans+2+k,k+2,n-midans))%MOD; // printf("%lld ",solve(midans+2+k,k+2,n-midans)); printf("%lld\n",(ans+MOD)%MOD); return 0; }

转载于:https://www.cnblogs.com/dreagonm/p/10543648.html