牛客小白月赛31题解（5/10）

牛客小白月赛31部分题解（5/10）

A.A|B

待补。。。

B.A+B

B.A+B
大模拟，难得写。。。

C.图像存储

C.图像存储
待补。。。

1、BFS搜索连通分量

2、变换坐标

3、去重

D.坐标计数

题意为统计一个区域内满足条件的点的个数，通过打表可以看出每个点都满足条件，所以只需要输出区域内所有点的个数即可（推了半天，打个表发现天呐。。。

代码：

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int t;
    cin >> t;
    
    while(t--)
    {
        long long x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        
        cout << (x2 - x1 + 1) * (y2 - y1 + 1) << endl;
    }
    return 0;
}

E.解方程

待补。。。

F.消减整数

分析：设n减到x时不够减

第一次：n减到x时不够减，剩余t，则t < x

第二次：n+t减到x时不够减, 剩余2t-x, 则2t-x<x

第i次：n+it减到x时不够减，剩余it-(i-1)x，则it-(i-1)x<x

由此可得，当且仅当最后(i*t)是x的倍数时，能够减完x，并n减到0

代码：

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int t;
    cin >> t;
    
    while(t--)
    {
        int i, n, x = 0;
        cin >> n;
        while(n >= x) n -= x, x++;
        for(i = 1; ; i++)
            if(i*n % x == 0)
                break;
        cout << i << endl;
    }
    return 0;
}

G.简单题的逆袭

题意：给定x,y，找出满足方程 $x^k le y $的最大的k

分情况讨论：

1、当x或者y等于0，或者x=1的时候，无论k多大，都不可能大于y，所以k不存在，输出-1；

2、当x>y且y!=0的时候，很明显，只有当k = 0的时候，才能满足题意，输出0；

3、当x == y的时候，只有当k = 1时，才能满足题意，输出1；

4、前面条件都不满足的一般情况，由于x和y的数据范围非常大，可能会爆，转而可以想出：假设k已经最大了，移项可得：(1 leq y / x^k),问题转化为求最大的k+1使得(1/k leq y / x^{k+1}),由于k为正整数（int除法中1/k == 0），问题进一步转化为y除以多少个x等于0，答案即为个数减1；

代码：

#include <iostream>
#include <algorithm>

using namespace std;

int t;
long long x, y;

int main()
{
    cin >> t;
    
    while(t--)
    {
        cin >> x >> y;
        if(!x || !y || x == 1) cout << -1 << endl;
        else if(x > y) cout << 0 << endl;
        else if(x == y) cout << 1 << endl;
        else
        {
            int i;
            for(i = 0; y; i++) y = y / x;
            cout << i - 1 << endl;
        }
    }
    return 0;
}

H.对称之美

我们可以预处理除每个字符串的字母a~z的个数，然后比较对称位置字符串的字符组成，如果有相同的字符个数都不为0则循环继续，若循环正常结束，说明存在，输出“Yes”, 否则说明不存在，退出循环输出“No”。

代码：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int t, n;
int a[30], b[30];
char s[110][55];

int main()
{
    cin >> t;
    
    while(t--)
    {
        cin >> n;
        for(int i = 0; i < n; i++) scanf("%s", s[i]);
        
        bool flag = true;
        for(int i = 0, j = n-1; i < j; i++, j--)
        {
            memset(a, 0, sizeof a);
            memset(b, 0, sizeof b);
            for(int k = 0; k < strlen(s[i]); k++) a[s[i][k] - 'a']++;
            for(int k = 0; k < strlen(s[j]); k++) b[s[j][k] - 'a']++;
            int c;
            for(c = 0; c < 26; c++) if(a[c] && b[c]) break;
            if(c == 26)
            {
                flag = false;
                break;
            }
        }
        if(flag) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

I.非对称之美

对输入字符串进行对称检查，如果初始都不对称，那个最长非回文子串就是其自己，输出长度

当整个字符串是回文串的时候，去掉最后一个字符，检查长度为len-1的子串的对称性，此时有两种个情况：

1、不是是回文串，输出len-1即可

2、是回文串，自己通过简单模拟推一下可以发现，如果该len-1的子串也是回文的，那个这个字符串的所有字符都相同，不存在非回文子串，输出0。

#include <iostream>
#include <string>

using namespace std;

int main()
{
    string s;
    cin >> s;
    
    bool flag1 = true, flag2 = true;
    for(int i = 0, j = s.length() - 1; i <= j; i++, j--)
        if(s[i] != s[j])
        {
            flag1 = false;
            break;
        }
    for(int i = 0, j = s.length() - 2; i <= j; i++, j--)
        if(s[i] != s[j])
        {
            flag2 = false;
            break;
        }
    
    if(!flag1) cout << s.length() << endl;
    else if(!flag2) cout << s.length() - 1 << endl;
    else cout << 0 << endl;
    
    return 0;
}

J.排列算式

待补。。。