社区讨论
关于CF C的过样例代码,WA on #3求调
学术版参与者 2已保存回复 5
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 5 条
- 当前快照
- 1 份
- 快照标识符
- @lo37n2ab
- 此快照首次捕获于
- 2023/10/24 02:07 2 年前
- 此快照最后确认于
- 2023/10/24 02:07 2 年前
CPP
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#define FOR(i,m,n) for(int i=m;i<=n;i++)
#define ll long long
#define mp(a,b) make_pair(a,b)
using namespace std;
int T,n,k,tl=0;
int a[17];
bool b[200007];
string s1,s2;
ll ans=0;
set<char>s;
map<char,int>mp;
void check(int sum){
// cout<<"<";
set<int>ss;
FOR(i,1,sum)ss.insert(a[i]);
FOR(i,0,n-1)b[i]=0;
FOR(i,0,n-1)if(s1[i]==s2[i]||ss.find(mp[s1[i]])!=ss.end())b[i]=1;
// cout<<"!!!!!!!";
// FOR(i,0,2)cout<<b[i]<<" ";
// cout<<"!!!!!!!";
int l;
ll res=0;
FOR(i,0,n-1){
if(i==0)l=i;
else if(b[i]==1&&b[i-1]==0)l=i;
if(i==n-1&&b[n]==1)res+=(i-l+1)*(i-l+2)/2;//,printf("{%d,%d,%d}",i,l,(i-l+1)*(i-l+2)/2);
else if(b[i]==1&&b[i+1]==0)res+=(i-l+1)*(i-l+2)/2;//,printf("{%d,%d,%d}",i,l,(i-l+1)*(i-l+2)/2);;
}
ans=max(ans,res);
// cout<<">";
}
void dfs(int loc,int sum){
if(loc==tl+1){
check(sum);
return;
}
dfs(loc+1,sum);
a[sum+1]=loc;
if(sum<k)dfs(loc+1,sum+1);
}
int main(){
cin>>T;
while(T--){
s.clear();mp.clear();ans=0;tl=0;
cin>>n>>k>>s1>>s2;
FOR(i,0,n-1){
char sr=s1[i];
if(s.find(sr)==s.end())s.insert(sr),mp[sr]=++tl;
}
dfs(1,0);
cout<<ans<<endl;
}
return 0;
}
回复
共 5 条回复,欢迎继续交流。
正在加载回复...