Educational Codeforces Round 51

A. Vasya And Password
题意:给你N个字符串,要你将所有的字符串变化为包含大写字母、小写字母、数字的字符串
题解:模拟。。我写的好复杂。。。

#include <bits/stdc++.h>

const int MAXN = 1000;

using namespace std;

int T,low,upe,dig,ze;
char s[MAXN];

inline void solve(){
    int len = strlen(s);
    if(dig >= low && low > upe){//dig > low > upe
        for(int i = 0;i < len;i++){
            if('0' <= s[i] && s[i] <= '9') {
                s[i] = 'A';
                return;
            }
        }
    }
    if(dig >= upe && upe > low){//dig > upe > low
        for(int i = 0;i < len;i++){
            if('0' <= s[i] && s[i] <= '9') {
                s[i] = 'a';
                return;
            }
        }
    }
    
    if(upe >= dig && dig > low){//upe > dig > low
        for(int i = 0;i < len;i++){
            if('A' <= s[i] && s[i] <= 'Z') {
                s[i] = 'a';
                return;
            }
        }
    }
    
    if(upe >= low && low > dig){//upe > low > dig
        for(int i = 0;i < len;i++){
            if('A' <= s[i] && s[i] <= 'Z') {
                s[i] = '1';
                return;
            }
        }
    }
    if(low >= dig && dig > upe){//low > dig > upe
        for(int i = 0;i < len;i++){
            if('a' <= s[i] && s[i] <= 'z') {
                s[i] = 'A';
                return;
            }
        }
    }
    
    if(low >= upe && upe > dig){//low > upe > dig
        for(int i = 0;i < len;i++){
            if('a' <= s[i] && s[i] <= 'z') {
                s[i] = '1';
                return;
            }
        }
    }
}

inline void solve_1()
{
    int len =  strlen(s);
    if(dig){
        for(int i = 0;i < len;i++){
            if('0' <= s[i] && s[i] <= '9'){
                if(!low){
                    s[i] = 'a';
                    low++;
                    continue;
                }
                if(!upe){
                    s[i] = 'A';
                    upe++;
                    continue;
                }
            }
        }
        return;
    }
    
    if(low){
        for(int i = 0;i < len;i++){
            if('a' <= s[i] && s[i] <= 'z'){
                if(!dig){
                    s[i] = '1';
                    dig++;
                    continue;
                }
                if(!upe){
                    s[i] = 'A';
                    upe++;
                    continue;
                }
            }
        }
        return;
    }
        
    if(upe){
        for(int i = 0;i < len;i++){
            if('A' <= s[i] && s[i] <= 'Z'){
                if(!dig){
                    s[i] = '1';
                    dig++;
                    continue;
                }
                if(!low){
                    s[i] = 'a';
                    low++;
                    continue;
                }
            }
        }
    }    
}

int main(){
    cin>>T;
    while(T--)
    {
        scanf("%s",s);
        int len = strlen(s);dig = low = upe = ze = 0;
        for(int i = 0;i < len;i++)
        {
            if('0' <= s[i] && s[i] <= '9') dig++;
            if('a' <= s[i] && s[i] <= 'z') low++;
            if('A' <= s[i] && s[i] <= 'Z') upe++;            
        }
        if(!dig) ze++;if(!low) ze++;if(!upe) ze++;
        if(ze == 1) solve();
        if(ze == 2) solve_1();
        printf("%s\n",s);
    }
}

B. Relatively Prime Pairs
题意:要求你输出L~R中尽量多的互质的数对
题解:任何一对连续的自然数都是互质的

#include <bits/stdc++.h>

using namespace std;

long long L,R;

int main()
{
    cin>>L>>R;
    printf("YES\n");
    for(long long i = L;i < R;i += 2){
        printf("%lld %lld\n",i,i+1);
    } 
    return 0;
}

C. Vasya and Multisets
题意:给你一个集合,然后将集合中的数分成两个集合,是的两个集合中间【好数】的数量相同,如果一个数在一个集合中只出现了一次,那么我们认为这个数是好数
题解:如果一个数只出现了一次,那么这么数一定会成为某一个集合的好数,而如果一个数如果出现了两次,那么这个数一定不会使某一个集合中的好数数量多于另外一个集合。如果一个数出现了超过三次,则可能产生一个好数或者是不产生。于是我们统计出现了一次的和三次及以上次数的数,然后对出现次数为1的数分奇偶讨论就好了

#include <bits/stdc++.h>
#define pb push_back

using namespace std;

int n,suma,sumb;
int sum[105];

bool t[105],flag;

vector<int>num[105];

int main()
{
    scanf("%d",&n);
    
    int v;
    for(int i = 1;i <= n;i++){
        scanf("%d",&v);
        sum[v]++;
        num[v].pb(i);
    } 
    
    for(int i = 1;i <= 100;i++)
    {
        if(sum[i] == 1) {suma++;continue;}
        if(sum[i] == 2) continue;
        if(sum[i] >= 3) {sumb++;continue;}
    }
    
    if(suma & 1 && !sumb){printf("NO");return 0;}
    
    if(suma & 1){
        suma /= 2;flag = true;
        for(int i = 1;i <= 100;i++){
            if(sum[i] == 1 && suma) {
            t[num[i][0]] = true;
            suma--;    
            }
            if(sum[i] >= 3 && flag){
            t[num[i][0]] = true;
            flag = false;    
            }
        }
    }
    else {
        suma /= 2;
        for(int i = 1;i <= 100;i++){
            if(sum[i] == 1 && suma) {
            t[num[i][0]] = true;
            suma--;    
            }
        }
    }
    printf("YES\n");
    for(int i = 1;i <= n;i++)    if(t[i]) printf("A");else printf("B");
    return 0;
} 

D. Bicolorings
题意:在两行N列的方块上填上A和B字母,而如果A(B)字母四方向联通上还有A(B)字母,则认为所有的这些方块位于同一个区块上,要求你统计一共含有K个区块的方案数是多少
题解:很容易想到状压动规,因为每一列的方案数太固定,而且数量不大.

我们用dp[i][j][k]记录从第一列到第i行含有j个区块最后一列的状态为k的方案数。而我将状态作如下定义。
0 :A 1:B 2:A 3:B
   A   A   B   B
#include <bits/stdc++.h>

const int MOD = 998244353;

using namespace std;

int dp[1005][2005][4],n,m;

int main()
{
    scanf("%d%d",&n,&m);
    
    dp[1][1][0] = 1;dp[1][1][3]= 1;//0 :A 1:B 2:A 3B
    dp[1][2][1] = 1;dp[1][2][2]= 1;//   A   A   B  B
    
    for(int i = 1;i < n;i++)
        for(int j = 1;j <= m;j++)
            for(int k = 0;k <= 3;k++){
                switch(k){
                    case 0: {
                        dp[i+1][j][0] += dp[i][j][k];
                        dp[i+1][j+1][1] += dp[i][j][k];
                        dp[i+1][j+1][2] += dp[i][j][k];
                        dp[i+1][j+1][3] += dp[i][j][k];
                        
                        dp[i+1][j][0] %= MOD;
                        dp[i+1][j+1][1] %= MOD;
                        dp[i+1][j+1][2] %= MOD;
                        dp[i+1][j+1][3] %= MOD;
                        break;
                    }
                    case 1: {
                        dp[i+1][j][1] += dp[i][j][k];
                        dp[i+1][j][0] += dp[i][j][k];
                        dp[i+1][j][3] += dp[i][j][k];
                        dp[i+1][j+2][2] += dp[i][j][k];    
                        
                        dp[i+1][j][1] %= MOD;
                        dp[i+1][j][0] %= MOD;
                        dp[i+1][j][3] %= MOD;
                        dp[i+1][j+2][2] %= MOD;                        
                        break;
                    }
                    case 2: {
                        dp[i+1][j][2] += dp[i][j][k];
                        dp[i+1][j][0] += dp[i][j][k];
                        dp[i+1][j][3] += dp[i][j][k];
                        dp[i+1][j+2][1] += dp[i][j][k];    
                        
                        dp[i+1][j][2] %= MOD;
                        dp[i+1][j][0] %= MOD;
                        dp[i+1][j][3] %= MOD;
                        dp[i+1][j+2][1] %= MOD;                        
                        break;
                    }
                    case 3:    {
                        dp[i+1][j][3] += dp[i][j][k];
                        dp[i+1][j+1][1] += dp[i][j][k];
                        dp[i+1][j+1][2] += dp[i][j][k];
                        dp[i+1][j+1][0] += dp[i][j][k];
                        
                        dp[i+1][j][3] %= MOD;
                        dp[i+1][j+1][1] %= MOD;
                        dp[i+1][j+1][2] %= MOD;
                        dp[i+1][j+1][0] %= MOD;        
                        break;
                    }
                }
            }
            
    long long ans = 0;
    ans += dp[n][m][0];ans += dp[n][m][1];
    ans += dp[n][m][2];ans += dp[n][m][3];
    ans %= MOD;
    printf("%lld\n",ans);
    
    return 0;
} 
Last modification:October 1st, 2018 at 04:46 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment