题目大意&链接:
给一个长为n(n<=100 000)的只包含‘a’~‘h’8个字符的字符串s。两个位置i,j(i!=j)存在一条边,当且仅当|i-j|==1或s[i]==s[j]。求这个无向图的直径,以及直径数量。
题解:
命题1:任意位置之间距离不会大于15。
证明:对于任意两个位置i,j之间,其所经过每种字符不会超过2个(因为相同字符会连边),所以i,j经过节点至多为16,也就意味着边数至多为15。
然后我们对于每个节点,需要计算出其与其他节点距离,当然为了不重复,只需考虑pos小于当前节点的位置。此时我们分为两种情况:
1.|i-j|<=15;
2.|i-j|>15。
对于第一种我们是取|i-j|与i先到达一种字母,j也到达这种字母距离和取较小值。所以我们设
$F[i][c]$表示i节点到达c这种字母的最小距离。即i到j的距离为:$min(|i-j|,F[i][c]+1+F[j][c])$。
命题2:i与j到达的同一种字母的位置如果相同,一定不是最优解。
证明:假设到达同一个位置,那么只可能是通过这个位置的左右两个节点。那么,对于到达左右这两个节点如果其路径之间不存在相同的字母,那么其距离和|i-j|相同,如果存在相同字母,则一定比当前方式短。综上所述,到达同一位置一定不是最短路。
对于第二种,我们由命题1可知,其距离不会大于15。我们再来看一个命题:
命题3:设$dis[c1][c2]$表示c1字母到达c2字母的最小距离,那么我们有,若$s[i]==c1$,则$dis[c1][c2]<=F[i][c2]<=dis[c1][c2]+1$。
证明:这个……显然吧?
我们此时考虑对于第二种情况下的j,|i-j|一定不是最短的,所以一定是从$F[i][c]+1+F[j][c]$中选取最小值,那么由命题3可知,我们并不需要其确切位置,仅需知道$F[i][c]$与$dis[ci][c]$之间的关系,然后我们可以用一个二进制数$mark[j]$来表示其与$dis[cj][c]$之间的关系,然后我们把关系相同(即mark[j]相同)的j统计其数量,然后再求一下此时i与某一种mark之间的最短路即可。
代码:
1 #include2 #include 3 #include 4 using namespace std; 5 const int N=100100; 6 int n,f[N][16],dis[20][20]; 7 char s[N]; 8 int q[N],d[N]; 9 int mark[N];10 int c[N][1<<8];11 inline void bfs(int c){12 int l=0,r=0;13 for(int i=1;i<=n;i++)if(s[i]-'a'==c){14 q[r++]=i,d[i]=0;15 }else d[i]=-1;16 bool vis[16]={ 0};17 vis[c]=true;18 while(l 1&&d[now-1]==-1) q[r++]=now-1,d[now-1]=d[now]+1;29 if(now dis[s[i]-'a'][j]) mark[i]|=1< ans) ans=now,cnt=1; 58 }59 int t=i-16;60 if(t>=1) c[s[t]-'a'][mark[t]]++;61 for(int j=0;j<8;j++) for(int k=0;k<256;k++)62 if(c[j][k]){63 int now=0x7fffffff;64 for(int l=0;l<8;l++){65 now=min(now,dis[j][l]+1+f[i][l]+((k&(1< >l));66 //printf("%d\n",(k&(1< >l);67 }68 if(now==ans) cnt+=c[j][k];69 if(now>ans) ans=now,cnt=c[j][k];70 }71 }72 printf("%d %lld\n",ans,cnt);73 }