2016 计蒜之道 初赛 第一场 题解(待补)A. 青云的服务器密钥B. 青云的机房组网方案（简单）

A. 青云的服务器密钥

对于密钥 S1..Sn，我们需要首先计算其对应的π 数组。对于任意的
$i(2≤i≤n)，pi_i=max{L|S_1...S_L=S_{i-L+1}...S_i, (0 leq L < i)}$
也就是最长的前缀等于后缀的长度。
$sum_{i=2}^{n}pi_i$​ 值越小，易破解程度越高。
现在已知密钥的 S1…Sn 中每个小写字母的字符个数，小明想知道易破解程度最高是多少？

官方题解： 如果只有一种字符，很好得出答案。超过 1 种字符，选取最少的一种字符 k 的一个放到第一个位置，剩下种类的字符依次排列，剩下的 k 放到末尾。比如 kxxxxxyyykk。这样最小答案就是 k 的个数减 1。

#include<bits/stdc++.h>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=Pre[x];p;p=Next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=Next[p])  
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (100000007)
#define pb push_back
#define mp make_pair 
#define fi first
#define se second
#define vi vector<int> 
#define pi pair<int,int>
#define SI(a) ((a).size())
typedef long long ll;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
{
    int x=0,f=1; char ch=getchar();
    while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
    while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
    return x*f;
} 
int T,a[30]; 
int s[100],sz=0;
int main()
{
//  freopen("A.in","r",stdin);
//  freopen(".out","w",stdout);
    cin>>T;
    while(T--) {
        int n=26,sz=0;
        For(i,n) {
            int p=read();
            if(p) s[++sz]=p;
        }
        if (sz==0) puts("0");
        else if (sz==1) cout<<s[1]*(s[1]-1)/2<<endl;
        else {
            sort(s+1,s+1+sz);
            cout<<s[1]-1<<endl;
        }
    }


    return 0;
}

B. 青云的机房组网方案（简单）

青云现在要将 n 个机房连成一个互相连通的网络。工程师小王设计出一个方案：通过在 n 个机房之间铺设 n−1条双向的光纤，将所有的机房连接。可以假设数据在两个机房之间的光纤传输需要 1 单位时间。每个机房 iii 有一个初始值 ai，当两个机房的初始值之间互质时，我们认为这两个机房之间的传输性能是非常重要的。请帮小王计算出所有数值互质的机房对之间的传输时间之和。
对于简单版本：$n leq 500，1≤ai≤50$
​对于中等版本：$n≤10000, 1≤ai≤500$
对于困难版本：$n≤100000，ai≤100000$

最后

以上就是心灵美白猫为你收集整理的2016 计蒜之道 初赛 第一场 题解(待补)A. 青云的服务器密钥B. 青云的机房组网方案（简单）的全部内容，希望文章能够帮你解决2016 计蒜之道 初赛 第一场 题解(待补)A. 青云的服务器密钥B. 青云的机房组网方案（简单）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。