牛客小白月赛31

A｜B

反思：这个题目分类讨论没有到位，我只是讨论了首位为零的情况，其他位为零的情况没有考虑到。
题目思路：
将题目意思抽象出来，就是求1的所有符合条件1的摆放位置。

代码

#include<bits/stdc++.h>
using namespace std;

int main()
{
#ifdef LOCAL
    freopen("data.in", "r", stdin);
#endif    
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int a, x, ans = 0;
        scanf("%d%d", &a, &x);

        for (int bit = (1 << 30); bit; bit >>= 1) 
        {    
            if (!(x & bit)) continue;
            int cnt = 0;
            for (int i = (bit >> 1); i; i >>= 1) if (!(i & a)) cnt++; //第i位的取值为0，那么0~i-1位的取值的所有可能情况
            ans += (1 << cnt);
            if (bit & a) break; // 第i个位置不能取1，即后面没有需要讨论的情况了，结束取值。
        }
        if ((a | x) == a + x) ans++; //循环中是没有考虑x的，所以将x的取值放进去。
        printf("%d\n", ans - 1); //答案中是大于1，并不存在所有都是0的情况
    }
    return 0;
}

A + B

直接暴力模拟即可

#include<bits/stdc++.h>
using namespace std;

#define _for(i, a, b) for (int i = (a); i < (b); ++i)
const int N = 510, M = 6;
char g[M][N];

int get_num(int x)
{
    if (g[0][x] == '.' && g[0][x + 1] == '.' && g[0][x + 2] == '.') return 10;
    if (g[0][x] == '#' && g[0][x + 1] == '.' && g[0][x + 2] == '#') return 4;
    if (g[0][x] == '.' && g[0][x + 1] == '.' && g[0][x + 2] == '#') return 1;
    if (g[2][x] == '#' && g[2][x + 1] == '.' && g[2][x + 2] == '#')
    {
        if (g[4][x] == '#' && g[4][x + 1] == '#' && g[4][x + 2] == '#') return 0;
        return 7;
    }
    if (g[3][x] == '#' && g[3][x + 1] == '.' && g[3][x + 2] == '.') return 2;
    if (g[1][x] == '.' && g[1][x + 1] == '.' && g[1][x + 2] == '#') return 3;
    if (g[1][x] == '#' && g[1][x + 1] == '.' && g[1][x + 2] == '.') {
        if (g[3][x] == '.') return 5;
        return 6;
    }
    if (g[3][x] == '.') return 9;
    return 8;
}

void put(int x, int l)
{
    char s[5][4] = { "###",
                    "#.#",
                    "#.#",
                    "#.#",
                    "###" };
    if (x)
    {
        switch (x)
        {
        case 1:
            strcpy(s[0], "..#");
            strcpy(s[1], "..#");
            strcpy(s[2], "..#");
            strcpy(s[3], "..#");
            strcpy(s[4], "..#");
            break;
        case 2:
            strcpy(s[0], "###");
            strcpy(s[1], "..#");
            strcpy(s[2], "###");
            strcpy(s[3], "#..");
            strcpy(s[4], "###");
            break;
        case 3:
            strcpy(s[0], "###");
            strcpy(s[1], "..#");
            strcpy(s[2], "###");
            strcpy(s[3], "..#");
            strcpy(s[4], "###");
            break;
        case 4:
            strcpy(s[0], "#.#");
            strcpy(s[1], "#.#");
            strcpy(s[2], "###");
            strcpy(s[3], "..#");
            strcpy(s[4], "..#");
            break;
        case 5:
            strcpy(s[0], "###");
            strcpy(s[1], "#..");
            strcpy(s[2], "###");
            strcpy(s[3], "..#");
            strcpy(s[4], "###");
            break;
        case 6:
            strcpy(s[0], "###");
            strcpy(s[1], "#..");
            strcpy(s[2], "###");
            strcpy(s[3], "#.#");
            strcpy(s[4], "###");
            break;
        case 7:
            strcpy(s[0], "###");
            strcpy(s[1], "#.#");
            strcpy(s[2], "#.#");
            strcpy(s[3], "..#");
            strcpy(s[4], "..#");
            break;
        case 8:
            strcpy(s[0], "###");
            strcpy(s[1], "#.#");
            strcpy(s[2], "###");
            strcpy(s[3], "#.#");
            strcpy(s[4], "###");
            break;
        case 9:
            strcpy(s[0], "###");
            strcpy(s[1], "#.#");
            strcpy(s[2], "###");
            strcpy(s[3], "..#");
            strcpy(s[4], "###");
            break;
        }
    }
    printf("%s", s[l]);
}

void print(int x)
{
    vector<int> v;
    while(x)
    {
        v.push_back(x % 10);
        x /= 10;
    }

    _for(i, 0, 5) for (int j = v.size() - 1; ~j; --j) 
        put(v[j], i), printf("%s", j ? "." : "\n");
}


int main()
{
#ifdef LOCAL
    freopen("data.in", "r", stdin);
#endif
    int T;
    scanf("%d", &T);

    _for(kase, 0, T)
    {
        if (kase) puts("");
        memset(g, 0, sizeof g);
        _for(i, 0, 5) scanf("%s", g[i]);
        int n = strlen(g[0]), t = 0;
        int sum = 0, ans = 0;

        while(t < n)
        {
            switch (get_num(t))
            {
            case 0:
                sum = sum * 10;
                break;
            case 1:
                sum = sum * 10 + 1;
                break;
            case 2:
                sum = sum * 10 + 2;
                break;
            case 3:
                sum = sum * 10 + 3;
                break;
            case 4:
                sum = sum * 10 + 4;
                break;
            case 5:
                sum = sum * 10 + 5;
                break;
            case 6:
                sum = sum * 10 + 6;
                break;
            case 7:
                sum = sum * 10 + 7;
                break;
            case 8:
                sum = sum * 10 + 8;
                break;
            case 9:
                sum = sum * 10 + 9;
                break;
                default:
                    ans += sum;
                    sum = 0;
                    break;
            }
            t += 4;
        }
        ans += sum;
        print(ans);
    }

    return 0;
}

图像存储

这个题目非常简单，直接bfs加判重即可。

#include<bits/stdc++.h>
using namespace std;

#define _for(i, a, b) for(int i = (a); i < (b); ++i)
typedef pair<int, int> PII;
typedef vector<PII> CELL;
set<CELL> shapes;
const int N = 10100;
int g[N][N], n, m, dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};

void bfs(PII pos)
{
    CELL cell;
    cell.push_back(pos);
    queue<PII> q;
    q.push(pos);
    int min_x = pos.first, min_y = pos.second;

    while(!q.empty())
    {
        PII t = q.front();
        q.pop();

        _for (i, 0, 4)
        {
            int x = t.first + dx[i], y = t.second + dy[i];
            if (0 <= x && x < n && 0 <= y && y < m && g[x][y])
            {
                g[x][y] = 0;
                q.push({ x, y });
                cell.push_back({ x, y });
                min_x = min(x, min_x);
                min_y = min(y, min_y);
            }
        }
    }

    int sz = cell.size();
    _for(i, 0, sz) cell[i].first -= min_x, cell[i].second -= min_y;
    if (!shapes.count(cell)) shapes.insert(cell);
}

int main()
{
#ifdef LOCAL
    freopen("data.in", "r", stdin);
#endif
    while (scanf("%d%d", &n, &m) == 2 && n && m)
    {
        shapes.clear();
        _for(i, 0, n) _for(j, 0, m) scanf("%1d", &g[i][j]);

        int cnt = 0;
        _for (i, 0, n) _for (j, 0, m) if (g[i][j]) bfs({ i, j }), cnt++;

        printf("%d %d\n", cnt, shapes.size());
    }
    return 0;
}

坐标计数

这个题目我打表验算发现所有的点都可以在有限次变成(0, 0)， 所以答案直接是区域中的所有点数。

#include <bits/stdc++.h>

typedef long long LL;
using namespace std;

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        LL x1, y1, x2, y2;
        scanf("%lld%lld%lld%lld", &x1, &y1, &x2, &y2);
        printf("%lld\n", (x2 - x1 + 1) * (y2 - y1 + 1));
    }
    return 0;
}

解方程

所以这个题就是求 a * b 的约数个数。

模板题

#include<iostream>
#include<unordered_map>
using namespace std;

unordered_map<int, int> primes;
typedef long long LL;
int n;

int main() {
#ifdef LOCAL
    freopen("data.in", "r", stdin);
#endif
    int T;
    scanf("%d", &T);
    while (T--) {
        primes.clear();
        LL a, b;
        scanf("%lld%lld", &a, &b);
        LL x = a * b;

        for (int i = 2; i <= x / i; ++i)
            while (x % i == 0) {
                x /= i;
                primes[i]++;
            }
        if (x > 1) primes[x]++;

        LL res = 1;
        for (auto i : primes) res = res * (i.second + 1);
        cout << res << endl;
    }

    return 0;
}

消减整数

定义： 函数s(n)为计算前n项和。

我们根据题意写表达式的时候可以发现：
第一次 ： n - f(k) = m
第二次 ： m + [ n - f(k) ] = 2m
第三次： 当 2m + n >= f(k + 1)时 =》 2m + [ n - f(k) ] - (k + 1) = w
以此类推：
第x次时： xm - a(k + 1) = 0
我们需要得到x，那么只要取m 和 (k + 1）的最大公约数再除以m便得到了x
x = lcm(m, k + 1) / m
因为：lcm(a, b) = a * b / gcd(a, b)
所以得到 ：x = (k + 1) / gcd(m, k + 1)

代码

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

inline LL S(int n)
{
    return 1LL * n * (n + 1) >> 1;
}

int cal(int n)
{ // 取最右边符合条件的数值。
    int l = 1, r = n;
    while (l < r)
    {
        int m = l + r + 1 >> 1;
        if (S(m) <= n) l = m;
        else r = m - 1;
    }
    return l;

}
int main()
{
#ifdef LOCAL
    freopen("data.in", "r", stdin);
#endif
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int n;
        scanf("%d", &n);
        int k = cal(n);
        int m = n - S(k++);
        if (!m) puts("1");
        else printf("%d\n", k / gcd(m, k));
    }
    return 0;
}

简单题的逆袭

这个题目没想到直接这样做就出来了，当时比赛的时候没有想出来，题目还是看少了啊。
值得注意的是这个题目的特殊值。

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

LL cal(LL x, LL y)
{
    if (x <= 1 || y == 0) return -1;
    LL ans = 0;
    while (y >= x) y /= x, ans++;
    return ans;
}

int main()
{
#ifdef LOCAL
    freopen("data.in", "r", stdin);
#endif
    int T;
    scanf("%d", &T);
    while (T--)
    {
        LL x, y;
        scanf("%lld%lld", &x, &y);
        printf("%lld\n", cal(x, y));
    }

    return 0;
}

对称之美

两边对称判断即可。

#include<bits/stdc++.h>
using namespace std;

const int N = 110;
char s[N][N];
int cunt[30], n;

bool judge(int i)
{
    memset(cunt, 0, sizeof cunt);
    int sz = strlen(s[i]);
    for (int j = 0; j < sz; ++j) cunt[s[i][j] - 'a']++;
    sz = strlen(s[n - i - 1]);

    bool flag = false;
    for (int j = 0; j < sz; ++j) if (cunt[s[n - i - 1][j] - 'a'])  return true;
    return false;
}

int main()
{
#ifdef LOCAL
    freopen("data.in", "r", stdin);
#endif

    int T;
    scanf("%d", &T);
    while (T--)
    {
        memset(s, 0, sizeof s);
        scanf("%d", &n);
        for (int i = 0; i < n; ++i) scanf("%s", s[i]);

        bool ans = true;
        for (int i = 0; i <= n / 2; ++i) if (!judge(i))
        {
            ans = false;
            break;
        }
        if (ans) puts("Yes");
        else puts("No");
    }
    return 0;
}

非对称之美

直接判断是否是回文串，如果不是那么直接返回长度，是的话，那么就是长度减一，因为去掉头或尾他必定不是回文串了（出除开全是相同字符的字符串）。
所以还要特判一下全是相同字符的字符串，输出0。

#include<bits/stdc++.h>
using namespace std;

bool is_Same(string s)
{
    char c = s[0];
    for (const auto& p : s) if (c != p) return false;
    return true;
}

int main()
{
    string s;
    cin >> s;
    if (is_Same(s))
    {
        puts("0");    
        return 0;
    }
    string t = s;
    reverse(t.begin(), t.end());
    cout << s.size() - (t == s) << endl;
    return 0;
}

排列算式

贪心算法
先总和的加起来，如果总和都不符合条件的话输出NO
再处理 -3的情况，依次用一个+3、两个2,一个-1、一个2一个1、三个1中和为0，还存在-3的话输出NO
再处理3的情况，依次用两个-2,一个1、一个-2一个-1、三个-1中和为0，如果3的个数大于1的话输出NO
顺利到这一步了输出YES。
采用了排除法，将NO的情况排除了，剩下的就是YES的情况了，

#include<bits/stdc++.h>
using namespace std;

#define _for(i, a, b) for (int i = (a); i < (b); ++i) 
const int N = 10;
int a[N], n;

bool judge(){
    while (a[0])
    {
        if (a[6]) a[6]--, a[0]--;
        else if (a[5] > 1 && a[2]) a[5] -= 2, a[2]--, a[0]--;
        else if (a[4] && a[5]) a[5] --, a[4]--, a[0]--;
        else if (a[4] > 2) a[4] -= 3, a[0]--;
        else return false;
    }
    while (a[6] > 1)
    {
        if (a[1] > 1 && a[4]) a[1] -= 2, a[4]--, a[6]--;
        else if (a[1] && a[2]) a[1]--, a[2]--, a[6]--;
        else if (a[2] > 2) a[2] -= 3, a[6]--;
        else return false;
    }
    return true;
}

int main()
{
#ifdef LOCAL
    freopen("data.in", "r", stdin);
#endif
    int T;
    scanf("%d", &T);
    while (T--)
    {
        memset(a, 0, sizeof a);
        char s[5];
        scanf("%d", &n);
        int sum = 0;
        _for(i, 0, n)
        {
            scanf("%s", s);
            int x = s[1] - '0';
            if (*s == '-') x = -x;
            sum += x;
            a[x + 3]++;
        }
        if (sum < 0 || sum > 3 || !judge()) puts("No");
        else puts("Yes");
    }
    return 0;
}

总结

这次比赛是我寒假的第一场比赛，也是正式的第一场比赛，比赛还是打少了，没有时间没有分配的过来，首先得要保证每个题都看了一眼，目前的想法是每个题先去看一遍，仔细理解题意，将思路写在纸上，整个看完之后挑选出最适合先做的题目出来做，先把自己能AC题目拿到手。此次比赛数学和推理题较多，代码不怎么长，确实比较好玩。