codeforces 820 C. Mister B and Boring Game（找规律）

题目链接：http://codeforces.com/contest/820/problem/C

题解：显然a<=b的规律很好找只要

例如a=2,b=5,只要这样排列就行abbbbbbabbbbbbabbbbbb....

然后a>b的规律是

例如a=5,b=2,只要这样的排列就行abcdeeeabfghhhabcdeeeanfghhh.....

当然满足这些条件的话就可以求出大于r-l>T的结果(T=2*(a+b))

显然if(a <= b) ans = a + 1; else ans = 2 * a - b;就按照上面的构造方法。

然后小与一周期的时候就直接暴力判断，这个很好判断详见代码。

#include <iostream>

#include <cstring>

using namespace std;

int a , b , l , r , ans , T;

char s[200];

bool vis[27];

int dfs(char cp) {

    int count = 0;

    for(int i = 0 ; i < a ; i++) s[i] = ('a' + i);

    for(int i = a ; i < a + b ; i++) s[i] = cp;

    memset(vis , false , sizeof(vis));

    for(int i = b ; i < a + b ; i++) vis[s[i] - 'a'] = true;

    int sta = a + b , ed = 0;

    while(sta < 2 * a + b) {

        while(vis[ed]) ed++;

        s[sta] = ed + 'a';

        sta++ , ed++;

    }

    for(int i = 2 * a + b ; i < T ; i++) s[i] = s[i - 1];

    memset(vis , false , sizeof(vis));

    if(l <= r) {

        for(int i = l ; i <= r ; i++) {

            if(!vis[s[i] - 'a']) {

                count++ , vis[s[i] - 'a'] = true;

            }

        }

    }

    else {

        for(int i = 0 ; i <= r ; i++) {

            if(!vis[s[i] - 'a']) {

                count++ , vis[s[i] - 'a'] = true;

            }

        }

        for(int i = l ; i < T ; i++) {

            if(!vis[s[i] - 'a']) {

                count++ , vis[s[i] - 'a'] = true;

            }

        }

    }

    return count;

}

int main() {

    cin >> a >> b >> l >> r;

    l-- , r--;

    if(a <= b) ans = a + 1;

    else ans = 2 * a - b;

    T = 2 * (a + b);

    if(r - l >= T);

    else {

        r %= T , l %= T;

        for(int i = 0 ; i < a ; i++) {

            ans = min(dfs('a' + i) , ans);

        }

    }

    cout << ans << endl;

    return 0;

}

巴特西

codeforces 820 C. Mister B and Boring Game（找规律）

最新文章

热门文章