NC13248. 合并字符串的价值
描述
输入描述
第一行一个整数T(T ≤ 500)。 接下来2T行，每行一个字符串，每两行代表一对字符串a和b（|a|,|b|<=100,000；∑(|a|+|b|)<=500,000），字符串的字符集为{A,C,G,T}。
输出描述
对于每组数据输出一行，一个整数表示价值最大的c的价值。
示例1
输入:
2 ACGT ACGT AACCGGTT ACACAGAT
输出:
4 7
C++14(g++5.4) 解法, 执行用时: 113ms, 内存消耗: 4300K, 提交时间: 2019-08-16 18:28:21
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 100005
#define ls(x) x<<1
#define rs(x) (x<<1)|1
char s[maxn], t[maxn];
int n, m, mx[4*maxn], tag[4*maxn];
int a[maxn], tot[4],num[4], pos[4][maxn],nw[4];
int get(char ch){
if(ch == 'A') return 0;
else if(ch == 'C') return 1;
else if(ch == 'G') return 2;
else return 3;
}
void pushup(int rt){
mx[rt] = max(mx[ls(rt)],mx[rs(rt)])+tag[rt];
}
void build(int rt,int l,int r){
tag[rt] = 0;
if(l == r){
mx[rt] = a[l];
return;
}
int mid = (l + r) >> 1;
build(ls(rt),l,mid);
build(rs(rt),mid+1,r);
pushup(rt);
}
void update(int rt,int l,int r,int L,int R,int v){
if(L <= l && r <= R){
mx[rt] += v;
tag[rt] += v;
return;
}
int mid = (l + r) >> 1;
if(L <= mid) update(ls(rt),l,mid,L,R,v);
if(R > mid) update(rs(rt),mid+1,r,L,R,v);
pushup(rt);
}
int main(){
int T;
cin>>T;
while(T--){
memset(tot,0,sizeof(tot));
memset(num,0,sizeof(num));
scanf("%s%s",s+1,t+1);
n = strlen(s+1), m = strlen(t+1);
for(int i = 1;i <= n;i++) tot[get(s[i])]++;
for(int i = 1;i <= m;i++) tot[get(t[i])]++;
for(int c, i = 0;i <= n;i++){
if(i) c = get(s[i]), pos[c][++num[c]] = i;
for(int j =a[i] = 0;j < 4;j++) a[i] += min(num[j],tot[j] - num[j]);
}
build(1,0,n);
memset(nw,0,sizeof(nw));
int ans = 0;
for(int i = 1;i <= m;i++){
ans = max(ans,mx[1]);
int c = get(t[i]);
nw[c]++;
int p = tot[c]/2 - nw[c] + 1;
if(p > 0) update(1,0,n,0,p<=num[c]?pos[c][p]-1:n,1);
p = (tot[c]+1)/2-nw[c]+1;
if(p <= num[c]) update(1,0,n,p>0?pos[c][p]:0,n,-1);
}
printf("%d\n",max(ans,mx[1]));
}
return 0;
}
C++(g++ 7.5.0) 解法, 执行用时: 112ms, 内存消耗: 3696K, 提交时间: 2023-07-09 20:35:48
#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
const int M=2e6;
const int mod=998244353;
const int INF=0x3f3f3f3f;
int T,n,m;
int cnt[4],idx[505];
int pos[4][N+5],num[4],a[N+5];
int cur[4],tree[M+5],lazy[M+5];
char s[N+5],t[N+5];
void build(int x,int l,int r){
lazy[x]=0;
if(l==r){
tree[x]=a[l];
return;
}
int mid=(l+r)/2;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
tree[x]=max(tree[x<<1],tree[x<<1|1]);
}
void pushdown(int x){
int z=lazy[x];
if(!z)return;
lazy[x<<1]+=z;
lazy[x<<1|1]+=z;
tree[x<<1]+=z;
tree[x<<1|1]+=z;
lazy[x]=0;
}
void update(int x,int l,int r,int L,int R,int val){
if(L<=l && r<=R){
tree[x]+=val;
lazy[x]+=val;
return;
}
pushdown(x);
int mid=(l+r)/2;
if(L<=mid)update(x<<1,l,mid,L,R,val);
if(R>mid)update(x<<1|1,mid+1,r,L,R,val);
tree[x]=max(tree[x<<1],tree[x<<1|1]);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
idx['A']=0,idx['C']=1;
idx['G']=2,idx['T']=3;
cin>>T;
while(T--){
cin>>(s+1)>>(t+1);
n=strlen(s+1),m=strlen(t+1);
for(int i=1;i<=n;i++)cnt[idx[s[i]]]++;
for(int i=1;i<=m;i++)cnt[idx[t[i]]]++;
for(int i=1;i<=n;i++){
int c=idx[s[i]];
pos[c][++num[c]]=i;
for(int j=0;j<4;j++)
a[i]+=min(num[j],cnt[j]-num[j]);
}
build(1,0,n);
int ans=tree[1];
for(int i=1;i<=m;i++){
int c=idx[t[i]];
cur[c]++;
int x=cnt[c]/2-cur[c]+1;
if(x>0)
update(1,0,n,0,x<=num[c]?pos[c][x]-1:n,1);
x=(cnt[c]+1)/2-cur[c]+1;
if(x<=num[c])
update(1,0,n,x>0?pos[c][x]:0,n,-1);
ans=max(ans,tree[1]);
}
cout<<ans<<"\n";
memset(cnt,0,sizeof(cnt));
memset(num,0,sizeof(num));
memset(cur,0,sizeof(cur));
for(int i=1;i<=n;i++)a[i]=0;
}
return 0;
}
C++(clang++ 11.0.1) 解法, 执行用时: 578ms, 内存消耗: 3836K, 提交时间: 2023-01-15 19:00:29
#include<bits/stdc++.h>
using namespace std;
char str[2][110000];
int n[2],sum[2][4][110000],ans;
int change(char ch)
{
if(ch=='A')
return 0;
if(ch=='T')
return 1;
if(ch=='G')
return 2;
if(ch=='C')
return 3;
return -1;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%s%s",str[0],str[1]);
int i,j,s,p,q;
for(i=0;i<2;i++)
{
n[i]=strlen(str[i]);
memset(sum[i][0],0,sizeof(sum[i][0]));
for(j=0;j<n[i];j++)
{
for(s=0;s<4;s++)
sum[i][s][j+1]=sum[i][s][j];
sum[i][change(str[i][j])][j+1]++;
}
}
int ch;
ans=0;
for(i=0;i<=n[0];i++)
{
int jmin,jmax;
if(i==0)
{
jmin=0;
jmax=n[1];
}
else
{
jmin=max(0,ch-200);
jmax=min(n[1],ch+200);
}
int awp=0;
for(j=jmin;j<=jmax;j++)
{
int now=0;
for(s=0;s<4;s++)
now+=min(sum[0][s][i]+sum[1][s][j],sum[0][s][n[0]]-sum[0][s][i]+sum[1][s][n[1]]-sum[1][s][j]);
if(awp<now)
{
awp=now;
ch=j;
}
}
if(ans<awp)
ans=awp;
}
printf("%d\n",ans);
}
return 0;
}