Codeforces Round #394 (Div. 2) C. Dasha and Password 贪心+预处理+枚举

My Solution

题意：长度为n的密码必须包含至少一个字母一个数字一个非字母非数字的字符，给出n个长度为m的字符串，每个串取一个字符，要求移动最少的步数使所成的密码为合法的密码。

贪心+预处理+枚举

先贪心的预处理出每个字符串 v[i]的v[i].c表示移动到字母的最少步数，v[i].d表示移动到数字的最少步数，v[i].f表示移动到其它字符的最少步数。

先把.c.d.f都初始化为INF，然后扫一遍字符串，如果不存在相应的请求则值依然是INF。

因为n <= 50 所以显然是n^3的枚举，即枚举每一个.c.d.f要求它们来自不同的3个ijk。这样就不会漏掉什么情况了 Y ^_^ Y。

复杂度 O(n^3)

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 1e2 + 8;
const int INF = 1e9 + 8;

string s[maxn];
struct p{
    int d, c, f;
}v[maxn];

int main()
{
    #ifdef LOCAL
    freopen("c.txt", "r", stdin);
    //freopen("c.out", "w", stdout);
    int T = 4;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    int n, m, i, j, k, cnt;
    cin >> n >> m;
    for(i = 0; i < n; i++){ cin >> s[i];
    }
    //memset(v, -1, sizeof v);
    for(i = 0; i < n; i++){
        v[i].c = v[i].d = v[i].f = INF;
        cnt = 0;
        for(j = 0; j < m; j++){ if(isalpha(s[i][j])) v[i].c = min(v[i].c ,cnt); else if(isdigit(s[i][j])) v[i].d = min(v[i].d, cnt); else v[i].f = min(cnt, v[i].f); cnt++; } cnt = 1; for(j = m - 1; j >= 0; j--){
            if(isalpha(s[i][j])) v[i].c = min(v[i].c ,cnt);
            else if(isdigit(s[i][j])) v[i].d = min(v[i].d, cnt);
            else v[i].f = min(cnt, v[i].f);
            cnt++;
        }
    }
    int ans = INF;
    for(i = 0; i < n; i++){
        if(v[i].c == INF) continue;
        for(j = 0; j < n; j++){
            if(v[j].d == INF || i == j) continue;
            for(k = 0; k < n; k++){
                if(v[k].f == INF || i == k || j == k) continue;
                ans = min(ans, v[i].c + v[j].d + v[k].f);
            }
        }
    }

    cout << ans << endl;


    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx