jxz收拾东西(easy version)

题意

对于一个序列，他的贡献是序列中连续相同数字块的最小数量(例如1112221113的贡献是4，即1213)，求一个序列中所有子序列(所有)的贡献和。

做法

暴力枚举每一个子区间，然后在每一个区间里算当前子区间的贡献。

时间复杂度:O(n³)

关键代码

for(i = 1; i <= n; i ++)  //枚举子区间的左端点
{
    for(j = i; j <= n; j ++)  //枚举子区间的右端点
    {
        ans++;  //区间基本贡献(每一个区间最小贡献为1)
        for(k = i; k < j; k ++)  //计算区间贡献
        {
            if(a[k] != a[k+1]) ans ++; //如果区间相邻两数不相等，贡献++
        }
    }
}
printf("%lld\n",ans);

jxz收拾东西(hard version)

题意

对于一个序列，他的贡献是序列中连续相同数字块的最小数量(例如1112221113的贡献是4，即1213)，求一个序列中所有子序列(所有)的贡献和。但是数据范围更大。

做法

序列长度n变成1e5的大小，无法再支持O(n³)的算法。

考虑每相邻的两个不相等的数对所有包含这两个数的子区间的贡献。

如果相邻的两个数不同，那么所有包含这两个数的子区间的贡献+1，即总贡献+包含这两个数的子区间个数。

对于包含第$ii$个数与第$i+1i+1$个数的区间个数，每个区间的左端点在$[1,i][1,i]$之间，右端点在$[i+1,n][i+1,n]$之间，所以包含这个两个数的子区间个数为$i\ast (n-i)i*(n-i)$。

时间复杂度:O(n)

关键代码

long long ans= 1ll * n * (n + 1) / 2;  //区间基本贡献(区间个数)
for(i = 1; i < n; i ++)
{
    if(a[i] != a[i+1]) ans += 1ll * i * (n - i);
}
printf("%lld\n",ans);

jxz的排列

题意

对于给的一个1 ~ n的排列的序列，你有一次翻转区间的操作(左右翻转)，使得这个序列字典序相对于所有可能的翻转操作的结果最小。

字典序: 如同字典一般，越小的数字(符号)越排在前面。对于两个字符串来说，前$kk$个字符相等，则第$k+1k+1$个字符更小的字符串字典序更小。

例如 baaaa 字典序大于 azzzz

做法

我们已经知道了字典序的比较，对于两个1 ~ n排列的序列，当然是越小的越在最前面最好。

所以在第$ii$个位置的数字刚好为$ii$的字典序最小，但是我们只有一次操作，所以我们尽量的让从1开始的第$ii$个位置的数字刚好为$ii$的连续序列越长越好，所以我们只需要找出第一个第$ii$个位置的数字不为$ii$的位置，然后在找到本来是是那个$ii$的数字的位置，将这两个区间翻转。

时间复杂度O(n)

关键代码

for(i = 1; i <= n; i ++)
{
    if(a[i] != i)
    {
        l = i;  //翻转的左端点
        break;
    }
}
for(i = l; i <= n; i ++)
{
    if(a[i] == l)
    {
        r = i;  //翻转的右端点
        break;
    }
}
for(i = 1; i <= l - 1; i ++) printf("%d ",a[i]);
for(i = r; i >= l; i --) printf("%d ",a[i]);
for(i = r + 1; i <= n; i ++) printf("%d ",a[i]);
printf("\n");

jxz的机房

题意

对于两排有编号的电脑，每个电脑有一个编号，最开始每一排电脑都是每相邻的两个电脑连接，现在想将两排电脑连在一块，同时还还要使得任意电脑坏掉之后，这些电脑不会被分成两个部分。连接第一排电脑与第二排的代价是两个电脑编号的绝对值的差，你需要最小化这个代价。

做法

对每一排电脑的排头和排尾分析，如果排头排尾的电脑不与另一排的电脑相连，当坏的电脑的位置在在排头或排尾旁边，那么排头或排尾的电脑将和其他部分会被拆分开，所以排头排尾的电脑必须与另一排电脑相连。

经过枚举讨论，总共有上图7种连接方式。

时间复杂度O(n)

关键代码

long long sumal=1e9,sumbl=1e9,sumar=1e9,sumbr=1e9;
for(i = 1; i <= n; i ++)
{
    if(abs(b[i] - a[1]) < sumal)
    {
        sumal = abs(b[i] - a[1]);
    }
    if(abs(a[i] - b[1]) < sumbl)
    {
        sumbl = abs(a[i] - b[1]);
    }
    if(abs(b[i] - a[n]) < sumar)
    {
        sumar = abs(b[i] - a[n]);
    }
    if(abs(a[i] - b[n]) < sumbr)
    {
        sumbr = abs(a[i] - b[n]);
    }
}
long long ans = 4e9;
if(ans > abs(a[1] - b[1]) + abs(a[n] - b[n]))
{
    ans = abs(a[1] - b[1]) + abs(a[n] - b[n]);
}
if(ans > abs(a[1] - b[n]) + abs(a[n] - b[1]))
{
    ans = abs(a[1] - b[n]) + abs(a[n] - b[1]);
}
if(ans > abs(a[1] - b[1]) + sumar + sumbr)
{
    ans = abs(a[1] - b[1]) + sumar + sumbr;
}
if(ans > abs(a[n] - b[n]) + sumal + sumbl)
{
    ans = abs(a[n] - b[n]) + sumal + sumbl;
}
if(ans > abs(a[n] - b[1]) + sumal + sumbr)
{
    ans = abs(a[n] - b[1]) + sumal + sumbr;
}
if(ans > abs(a[1] - b[n]) + sumbl + sumar)
{
    ans = abs(a[1] - b[n]) + sumbl + sumar;
}
if(ans > sumal + sumbl + sumar + sumbr)
{
    ans = sumal + sumbl + sumar + sumbr;
}
printf("%lld\n",ans);
···