成都网站建设的定位,松江品牌网站建设,如何有效提高网站排名,成都住建局官网报名被挤爆黑幕【传送门#xff1a;BZOJ3555】 简要题意#xff1a; 给出n个字符串长度为m#xff0c;给出字符串的字符种数#xff0c;求出相似的字符串个数 相似字符串的定义为#xff1a;相同位置上两个字符串有且只有一个字符不相同时#xff0c;两个字符串相似 题解#xff1a; 乱…【传送门BZOJ3555】 简要题意 给出n个字符串长度为m给出字符串的字符种数求出相似的字符串个数 相似字符串的定义为相同位置上两个字符串有且只有一个字符不相同时两个字符串相似 题解 乱搞搞因为题目描述中说明会给出字符种数就把各种字符按照出现的顺序编一下号然后我就想成是字符种数1进制来做先处理一下前缀和后缀和然后枚举i表示第i位不同那么我们就先忽略第i位的字符然后保存左边的字符串和右边的字符串用字符种数1进制来表示然后按照左边的大小排序左边相同时按照右边的大小排序然后就判断左右都相等的字符串的个数 注意假设当前我们得到了有x个字符串是相等的时候那么相似的个数为x*(x-1)/2 题目20s19s跑过去RP 参考代码 #includecstdio
#includecstring
#includecstdlib
#includealgorithm
#includecmath
using namespace std;
typedef long long LL;
char st[210];
LL l[31000][210];
LL r[31000][210];
struct node
{LL l,r;
}cnt[31000];
LL cc[210];
int cmp(const void *xx,const void *yy)
{node n1*(node *)xx;node n2*(node *)yy;if(n1.ln2.l) return -1;if(n1.ln2.l) return 1;if(n1.rn2.r) return -1;if(n1.rn2.r) return 1;return 0;
}
int main()
{int n,m,d;scanf(%d%d%d,n,m,d);memset(cc,0,sizeof(cc));int len0;for(int i1;in;i){scanf(%s,st1);for(int j1;jm;j) if(cc[st[j]]0) cc[st[j]]len;l[i][0]0;r[i][m1]0;for(int j1;jm;j) l[i][j]l[i][j-1]*(d1)cc[st[j]];for(int jm;j1;j--) r[i][j]r[i][j1]*(d1)cc[st[j]];}int ans0;for(int i1;im;i){for(int j1;jn;j) cnt[j].ll[j][i-1],cnt[j].rr[j][i1];qsort(cnt1,n,sizeof(node),cmp);int dd1;for(int j2;jn;j){if(cnt[j].lcnt[j-1].lcnt[j].rcnt[j-1].r) dd;else{ansdd*(dd-1)/2;dd1;}}ansdd*(dd-1)/2;}printf(%d\n,ans);return 0;
} 转载于:https://www.cnblogs.com/Never-mind/p/7878869.html
