0827

A 多色彩的巧克力
A．cpp /1s /256M
题目描述
奶牛 Bessie 有 N 块巧克力，从左往右排成一行，编号从 0 到 N-1。第 i 块巧克力的颜色是 color[i]。我们定义一个参数MaxLen,它表示：具有相同颜色的连续一段巧克力的最大长度。例如：有 10 块巧克力，颜色分别是: ADDDABBAAB,那么 MaxLen=3,因为有 3 块颜色是 D 的巧克力，而且这 3 块巧克力的位置是连续的。为了使得 MaxLen 最大，Bessie可以交换相邻两块巧克力的位置，但是 Bessie 总共交换的次数不能超过给定的值 swap。那么 MaxLen 的最大值是多少？
输入格式
多组测试数据。
第一行，一个整数 G，表示有 G 组测试数据。1 <= G <=5。
每组测试数据格式如下：
第一行，两个整数 N、swap 。1 <= N <= 50。 1 <= swap <= 2500。
第二行，N 个大写字母，第 i 个字母表示第 i 块巧克力的颜色。
输出格式
共 G 行，每行一个整数。
输入样例
4
7 1
ABCDCBC
7 2
ABCDCBC
9 3
ABBABABBA
9 4
ABBABABBA
输出样例
2
3
4
5
【样例解释】
第二组测试数据：交换后可以变成 ABDCCCB。
第三组测试数据：交换后可以变成 ABBBBAABA。
第四组测试数据：交换后可以变成 AABBBBBAA。

一开始想的是dp，dp[i][j]表示前i个交换j次的最大值。后来发现交换i后面的可能使答案更优，所以放弃了dp，选择了贪心。枚举中心i，考试的时候我还枚举了颜色j，但后来发现，如果中心的颜色和当前色块a[j]的颜色不同时在某些情况下可以得到最优解，但无法得到比中心颜色和当前色块颜色相同的更优解，所以颜色不用枚举，然后用k指针维护当前寻找到的点，l和r表示当前色块的左右端点。

其实考试时巨困，后来去洗了把脸就好了。

附上不优秀的考试代码。

int main(){
    T = read();
    while(T--){
        ans = 0;
        n = read();m = read();
        scanf("%s",a + 1);
        for(int i = 1; i <= n; ++i){//centrol
            memset(col,0,sizeof(col));
            for(int j = 1; j <= n; ++j){//col
                if(col[a[j] - 'A']) continue;
                col[a[j] - 'A'] = 1;
                int k = 1,l = 0,r = 0,al = m,cnt = 0;
                if(a[i] == a[j]) {cnt = 1;l = r = 1;}
                for(; i - k >= 1 && i + k <= n; ++k){
                    if((l == 1 && !r)|| (r == 1 && !l)) l = r = 1; 
                    if(a[j] == a[i - k] && al - (k - l) >= 0){
                        al -= (k - l);
                        l++;
                        cnt++;
                    }
                    if(a[j] == a[i + k] && al - (k - r) >= 0){
                        al -= (k - r);
                        r++;
                        cnt++;
                    } 
                }
                for(;i - k >= 1; ++k)
                    if(a[j] == a[i - k] && al - (k - l) >= 0){
                        al -= (k - l);
                        l++;
                        cnt++;
                    }
                for(;i + k <= n; ++k)
                    if(a[j] == a[i + k] && al - (k - r) >= 0){
                        al -= (k - r);
                        r++;
                        cnt++;
                    } 
                ans = max(ans,cnt);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

C.Mushroom 的区间
C.cpp/1s/256M
【题目描述】
Mushroom 有一行数，初始时全部是 0。现在 Mushroom 有 m 个区间[L,R]，他
希望用以下操作得到新的序列。
从 m 个给定区间中选择一个区间[s,t]，把区间中的数对应元素全部翻转。（0 变
1,1 变 0）
请告诉 Mushroom 他能得到多少区间。（模 10^9+7）
【输入格式】
第一行包含两个整数 n，m。表示 n 个数和 m 个区间。
接下来 m 行是所表示的区间。
【输出格式】
一个整数，表示能得到的区间数。
【样例输入】
3 3
1 1
2 2
3 3
【样例输出】
8
【数据范围】
对于 30%的数据，n,m<=20
对于 60%的数据，n,m<=100
对于 100%的数据，n,m<=100000
【样例解释】
每个位置都可以单个修改，所以有 8 种可能。

开始找了几组，画了一下，后来画了Venn图，加上子集的枚举{0}，{1}，{2}，{3}，{1,2}，{1,3}，{2,3}，{1,2,3}发现只有一段区间被完全覆盖时，即可以用之前的任意区间组成时，当前区间可以忽略。
所以考虑并查集维护，区间左开右闭。

开始时快速幂没开longlong差点见了祖宗。常数也要强转longlong

ll mul(ll a,ll b){
    ll ret = 1;
    while(b){
        if(b & 1) ret = ret * a % mod;
        a = a * a % mod;//!!
        b >>= 1;
    }
    return ret;
}
int Find(int u){
    return (fa[u] == u) ? u : fa[u] = Find(fa[u]);
}
int main(){
    int a,b;
    n = read();m = read();
    for(int i = 0; i <= n; ++i) fa[i] = i;
    while(m--){
        a = read();b = read();
        a -= 1;
        int x = Find(a);int y = Find(b);
        if(x != y){
            fa[x] = y;
            cnt++;
        }
    }
    printf("%lld\n",mul(2LL,(ll)cnt));
    return 0;
}

A
CF 208B
题目大意：
给你n张牌，牌的花色和数字只要有一种一样就能合并。每次只能从最右边开始操作，可以覆盖n-1位置，可以覆盖 n-3位置。
问最后能否将全部牌合并成一堆。

暂时还没有想通。

B
CodeForces 709B
数轴上的越野赛,起点为a，数轴上有n个点,须至少到达n-1个点才算完成比赛。问完成比赛的最小路程。
(1 ≤ n ≤ 100 000,  - 1 000 000 ≤ a ≤ 1 000 000)

水题，排序，要么不到1号点，要么不到n号点。然后在判断先跑左右哪边。

C
CodeForces 361B
题目大意：给出n，输出n的一个排列，使得其中下标i和a[i]的gcd不为1的个数有k个。
(1 ≤ n ≤ 105, 0 ≤ k ≤ n)

原来CF也有水题。
最后k个就令a[i] = i
前面的就奇偶互换。
如：1 2 3 4 5 -> 1 (3 2) (5 4)
1 2 3 4 5 6 -> (2,1) (4,3) (6,5)

D
CF 208C
题目大意：有n个城市，m条双向道路（每条边长度为1），让你添加一个警察局（有一个端点是警察局的边会变成安全边），使得安全边比上所有从1到n的最短路数的最大值。
n (2 ≤ n ≤ 100 )

其实思想不难。n的值极小，怎么应该都能过，结果是没开longlong见祖宗，CF居然报MLE。浪费了1h。
可以先找出从1到n的最短路条数，然后枚举哪个点i成为警察局最优。此处要记录跑最短路到i的入度，和从i跑最短路到n的出度。最后两者相乘*2/1到n的最短路条数.

题解对第22个数据的分析，n = 100 因为假设六个一组形成16个4叉路，剩下四个再形成三叉路，则总最短路条数为2^32*3，大于int范围。

queue <int> q;
void bfs(){
    q.push(1);num[1] = 1;vis[1] = 1;
    while(!q.empty()){
        int u = q.front();q.pop();
        for(int i = head[u]; i != -1; i = e[i].nxt){
            if(!num[e[i].v]){
                dis[e[i].v] = dis[u] + 1;
                num[e[i].v] = num[u];
                q.push(e[i].v);
                a[e[i].v][u] = num[u];
                b[u][e[i].v] = 1;
            }
            else if(dis[e[i].v] == dis[u] + 1){
                num[e[i].v] += num[u];
                a[e[i].v][u] = num[u];
                b[u][e[i].v] = 1;
            }
        }
    }
}
int main(){
    int ab,aa;
    memset(head,-1,sizeof(head));
    scanf("%I64d%I64d",&n,&m);
    for(int i = 1; i <= m; ++i){
        scanf("%d%d",&aa,&ab);
        Adde(aa,ab);Adde(ab,aa);
    }
    bfs();
    double t = num[n],ans = 0;
    for(int i = 1; i <= n; ++i){
        if(a[n][i]) {vis[i] = 1;q.push(i);cntb[i] += 1;}
    }
    while(!q.empty()){
        int u = q.front();q.pop();
        for(int i = 1; i <= n; ++i){
            if(a[u][i]){
                cntb[i] += cntb[u];
                if(!vis[i]){
                    vis[i] = 1;
                    q.push(i);
                }
            }
        }
    }
    for(int i = 1; i <= n; ++i){
        if(b[1][i]) {q.push(i);cnta[i] += 1;}
    }
    while(!q.empty()){
        int u = q.front();q.pop();
        for(int i = 1; i <= n; ++i){
            if(b[u][i] && vis[i]){
                if(vis[i] == 1){
                    vis[i] = 2;
                    q.push(i);
                }
                cnta[i] += cnta[u];
            }
        }
    }
    ans = max(cnta[n] / t,cntb[1] / t);
    for(int i = 2; i < n; ++i)  ans = max(ans,(double)2 * (cnta[i] * cntb[i]) / t);
    printf("%.10lf\n",ans);
    return 0;
}

CodeForces 708A Letters Cyclic Shift
从仅由小写字母组成的字符串s中挑选出一个非空子串，将该子串中的每个字母均替换成前一个字母,如'b'换成'a','c'换成'b',以此类推,特别的,'a'要换成'z'，问经过一次转换之后,字典序最小的字符串s为多少

水题，但是没有想到全是a的情况。
从头开始，遇到第一个不是a的字符开始变小，变到第一个a为止。
有一个陷阱是，如果字符串为全a，要把最后一个a变为z。

CF 709D
给出 a00 a01 a10 a11四个数，构造一个01序列。a00表示子序列为“00”数量。其余3个同理。若无合法的序列输出Impossible。

这题在学字符串时就做过，但没有AC，主要是因为此题太坑，特判太多，一定考虑最小值的特例以及最大值在计算过程或结果是否会溢出。
其实思路简单，就是先通过a00,a11计算出0,1的个数，要注意a00为0时，0的个数可能为1.
然后将0放在前面，1放在中间，0又放在最后，前两个构造a01,后两个构造a10，注意微调。

ll check(ll a){
    if(!a) return 0;
    ll t = sqrt(2 * a);
    for(int i = -5; i <= 5; ++i)
        if((t + i) > 0 && (t + i) * (t + i - 1) == 2 * a) return t + i;
    return -1;
}
int main()
{
    scanf("%I64d%I64d%I64d%I64d",&a,&b,&c,&d);
    n = check(a);m = check(d);
    if(n == -1 || m == -1)  {printf("Impossible\n");return 0;}
    if(!n && !m){
        if(!b && !c) {putchar('0');return 0;}
        if(b == 1 && !c) {printf("01");return 0;}
        if(!b && c == 1) {printf("10");return 0;}
        else {printf("Impossible\n");return 0;}
    }
    if(n == 0){
        if((b + c) && m && (b + c) != m) {printf("Impossible\n");return 0;}
        else if(b + c == 0 && m) {for(int i = 1; i <= m; ++i) putchar('1');return 0;}
        for(int i = 1; i <= c; ++i) putchar('1');
        putchar('0');
        for(int i = 1; i <= b; ++i) putchar('1');
    }
    else if(m == 0){
        if((b + c) && n && (b + c) != n) {printf("Impossible\n");return 0;}
        else if(b + c == 0 && n) {for(int i = 1; i <= n; ++i) putchar('0');return 0;}
        for(int i = 1; i <= b; ++i) putchar('0');
        putchar('1');
        for(int i = 1; i <= c; ++i) putchar('0');
    }
    else{
        if((b + c) != n * m)    {printf("Impossible\n");return 0;}
        for(int i = 1; i <= b / m; ++i) putchar('0');
        for(int i = 1; i <= m - b % m; ++i) putchar('1');
        if(n > b / m) putchar('0');
        for(int i = 1; i <= b % m; ++i) putchar('1');
        for(int i = 1; i <= n - b / m - 1; ++i) putchar('0');
    }
    return 0;
}