【题解】牛客小白月赛31

A｜B

假设 A=100100010，则满足 A+B=A|B 条件的B，在 A 中为1的位置必定为0，也就是 B=0xx0xxx0x，其中的 x 可为 0 或 1，因此只要数一下 A 裡面有几个位元是 0，算出 2 的次方就可以得到答案。

但是题目又规定 B <=X ，所以我们要将 X 分段处理，假设 X=1001000100，先找出最左边第一个出现的 1 为 1000000000，分出第一段数字 xxxxxxxxx，(不含上面的数)
也就是 0 ~ 111111111 (1000000000-1)，再用这一段去找有几个位置在 A 中是 0。接下来再找出第二个出现的 1 为 1000000，而第二段数字为 1000xxxxxx，也就是 1000000000 ~ 1000111111 (1001000000-1)，数字的最前面固定是 1000，一样找出后面的位置有几个在 A 中是 0。
要注意的是，如果这个位置在 X 和在 A 中同时为 1，则后面就不会再有答案。因为这个做法只能处理到 X-1，所以 X 要另外处理。
最后，因为题目要求要正整数，但这个做***包含 0，所以答案要再减一。

#include <bits/stdc++.h>

using namespace std;
int A[32];
int a, x, t;
int ans, c, bit, bit2;

int main() {
    for (int i = 0; i < 31; ++i)
        A[i] = pow(2, i);
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &a, &x);
        for (bit = (1 << 30), ans = 0; bit; bit >>= 1) {
            if ((bit & x) == 0) continue;
            for (bit2 = (bit >> 1), c = 0; bit2; bit2 >>= 1)
                if ((bit2 & a) == 0) c++;
            ans += A[c];
            if (bit & a) break;
        }
        if ((a | x) == (a + x)) ans++;
        printf("%d\n", ans - 1);
    }
    return 0;
}

A+B

按照题意模拟即可

#include <iostream>
#include <map>

using namespace std;

int n;
string a[5];
map<string, int> mp;
string num[11] = {"####.##.##.####",
                  "..#..#..#..#..#",
                  "###..#####..###",
                  "###..####..####",
                  "#.##.####..#..#",
                  "####..###..####",
                  "####..####.####",
                  "####.##.#..#..#",
                  "####.#####.####",
                  "####.####..####",
                  "....#.###.#...."};

signed main() {
//    freopen("in", "r", stdin), freopen("out", "w", stdout);
    mp["####.##.##.####"] = 0;
    mp["..#..#..#..#..#"] = 1;
    mp["###..#####..###"] = 2;
    mp["###..####..####"] = 3;
    mp["#.##.####..#..#"] = 4;
    mp["####..###..####"] = 5;
    mp["####..####.####"] = 6;
    mp["####.##.#..#..#"] = 7;
    mp["####.#####.####"] = 8;
    mp["####.####..####"] = 9;
    mp["....#.###.#...."] = 10;
    int Test;
    cin >> Test;
    for (int Case = 1; Case <= Test; Case++) {
        string s;
        getline(cin, s);
        for (auto &i : a) {
            getline(cin, i);
            n = i.size();
        }
        int ans = 0;
        int sum = 0;
        for (int j = 0; j < n; j += 4) {
            string sub = "";
            for (int i = 0; i < 5; i++)sub += a[i].substr(j, 3);
            int tmp = mp[sub];
            if (tmp == 10)ans += sum, sum = 0;
            else sum = sum * 10 + tmp;
        }
        ans += sum;
        string res[5] = {"", "", "", "", ""};
        if (ans == 0) {
            for (int i = 0, j = 0; i < 5; i++, j += 3) {
                res[i] = num[0].substr(j, 3) + res[i];
            }
        } else {
            while (ans) {
                for (int i = 0, j = 0; i < 5; i++, j += 3) {
                    res[i] = num[ans % 10].substr(j, 3) + res[i];
                }
                ans /= 10;
                if (ans) {
                    for (int i = 0; i < 5; i++)res[i] = "." + res[i];
                }
            }
        }
        for (int i = 0; i < 5; i++)cout << res[i] << endl;
        if (Case < Test)cout << endl;
    }
    return 0;
}

图像存储

先求出联通块的数量，然后再对联通块判重即可

#include <bits/stdc++.h>

using namespace std;
int mp[300][300], mv[4][2] = {{1,  0},
                              {-1, 0},
                              {0,  1},
                              {0,  -1}};
int n, m, cnt;

set<vector<pair<int, int> > > S1;

void Bfs(int x, int y) {
    queue<pair<int, int> > Q;
    vector<pair<int, int> > v;
    Q.push({x, y});
    v.push_back({x, y});
    int mx = x, my = y;
    mp[x][y] = 0;
    while (Q.size()) {
        pair<int, int> top = Q.front();
        Q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = top.first + mv[i][0];
            int ny = top.second + mv[i][1];
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && mp[nx][ny]) {
                mp[nx][ny] = 0;
                Q.push({nx, ny});
                v.push_back({nx, ny});
                mx = min(mx, nx), my = min(my, ny);
            }
        }
    }
    for (int i = 0; i < v.size(); i++) {
        v[i].first -= x;
        v[i].second -= y;
    }
    S1.insert(v);
}

int main() {
    //freopen("in", "r", stdin);
    while (cin >> n >> m) {
        if (!n && !m) break;
        cnt = 0, S1.clear();
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                scanf("%1d", &mp[i][j]);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (mp[i][j]) cnt++, Bfs(i, j);
            }
        }
        cout << cnt << ' ' << S1.size() << endl;
    }
    return 0;
}

坐标计数

所有的坐标都会在有限次数内变成(0,0)，所以只要统计区域内坐标个数即可。

#include <bits/stdc++.h>

#define ll long long
using namespace std;

int t;
ll x_1, y_1;
ll x_2, y_2;

int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%lld%lld%lld%lld", &x_1, &y_1, &x_2, &y_2);
        printf("%lld\n", (x_2 - x_1 + 1) * (y_2 - y_1 + 1));
    }
    return 0;
}

解方程

答案即为求的因子个数

#include <bits/stdc++.h>

#define MaxN 1000000
using namespace std;
bool m[MaxN];
long long p[78500];
int ps;

void genp() {
    int i, j, k, q = int(sqrt(MaxN));
    p[0] = 2;
    for (i = 3; i < q; i += 2) {
        if (!m[i]) for (k = 2 * i, j = i * i; j < MaxN; j += k) m[j] = true;
    }
    for (ps = 1, i = 3; i < MaxN; i += 2)
        if (!m[i]) p[ps++] = i;
}

int main() {
    genp();
    long long k1, k2, kk;
    int cnt, i, t, ans;
    cin >> t;
    while (t--) {
        cin >> k1 >> k2;
        kk = k1 * k2;
        if (kk == 1) cout << 1 << endl;
        else {
            ans = 1;
            for (i = 0; i < ps && kk != 1; ++i) {
                for (cnt = 1; kk % p[i] == 0; ++cnt) kk /= p[i];
                ans *= cnt;
            }
            if (kk != 1) ans *= 2;
            cout << ans << endl;
        }
    }
    return 0;
}

消减整数

直接模拟会超时。

假设第一次不够减时，是想要减K而只剩下M。则第二次就会剩下，第三次剩下，直到剩下的数量大于等于K时减去K，减去K后剩下的又不足K，又要重头开始减。

所以题目就转化为：每次加M，大于等于K时就减掉K，问多少次以后归零。

稍加观察可以发现，归零的时候加的数值总和为K的倍数，而能够加的有只有M的倍数，所以题目是在问：最快加了多少次以后变为M，K的公倍数，就是求最小公倍数。

#include <bits/stdc++.h>

#define ll long long
using namespace std;

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int cal(int n) {
    int l = 1, r = n, ans = l;
    while (l <= r) {
        ll mid = (l + r) >> 1;
        if ((1 + mid) * mid / 2 <= n) ans = mid, l = mid + 1;
        else r = mid - 1;
    }
    return ans;
}

int main() {
//    freopen("in", "r", stdin);
    int t, n;
    cin >> t;
    while (t--) {
        scanf("%d", &n);
        int k = cal(n);
        int m = n - (1LL + k) * k / 2;
//        cout << n << ' ' << k << ' ' << m << ' ';
        if (m == 0) puts("1");
        else printf("%d\n", (k+1) / gcd(m, (k+1)));
    }
    return 0;
}

简单题的逆袭

注意long long overflow，大多数人都WA在这里了

考虑x=0

考虑x=1

考虑y=0

#include <iostream>

using namespace std;

typedef long long ll;

ll cal(ll ta, ll tb) {
    if (ta <= 1 || tb == 0) return -1;
    ll ans = 0;
    while (tb >= ta) ans++, tb /= ta;
    return ans;
}

int main() {
    long long int a, n;
    int t;
    cin >> t;
    while (t--) {
        scanf("%lld%lld", &a, &n);
        cout << cal(a, n) << endl;
    }

    return 0;
}

对称之美

判断第一个和最后一个有无相同的字母

判断第二个和倒数第二个有无相同的字母

。。。

#include <bits/stdc++.h>

using namespace std;

int n, t;
string s[100];

bool match(string s1, string s2) {
    bool used[26];
    for (int i = 0; i < 26; ++i)
        used[i] = false;
    for (int i = s1.size() - 1; i >= 0; --i)
        used[s1[i] - 'a'] = true;
    for (int i = s2.size() - 1; i >= 0; --i)
        if (used[s2[i] - 'a']) return true;
    return false;
}

int main() {

    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 0; i < n; ++i) cin >> s[i];
        bool yes = true;
        for (int i = 0; i < n / 2; ++i) {
            if (!match(s[i], s[n - 1 - i])) {
                yes = false;
                break;
            }
        }
        if (yes) puts("Yes");
        else puts("No");
    }
    return 0;
}

非对称之美

只有n,n-1,0三种情况

分别判一下即可

#include<bits/stdc++.h>

//#define int long long
const int Maxn = 1000000005;
using namespace std;

signed main() {
    //freopen("in","r",stdin);
    string s;
    cin >> s;
    if (s.size() == 1) {
        cout << "0" << endl;
        return 0;
    }
    if (s.size() == 2) {
        if (s[0] == s[1]) {
            cout << "0" << endl;
        } else {
            cout << 2 << endl;
        }
        return 0;
    }
    int i;
    int flag1 = 0;
    int flag2 = 0;
    for (i = 0; i < s.length() / 2; i++) {
        if (s[i] != s[s.length() - 1 - i]) {
            flag1 = 1;
            break;
        }
    }
    if (flag1 == 1) {
        cout << s.length() << endl;
        return 0;
    }
    int l = s.length() - 1;
    for (i = 0; i < l / 2; i++) {
        if (s[i] != s[l - 1 - i]) {
            flag2 = 1;
            break;
        }
    }
    if (flag2 == 1) {
        cout << s.length() - 1 << endl;
        return 0;
    }
    cout << "0" << endl;
    return 0;
}

排列算式

这个题900次提交里有800次左右都是一个人交的！

贪心(贪婪)(greedy)算法。

分以下三步：

1、就是先考虑(-3)，依次判断能否让(+3)或2×(+2)+(-1)或(+2)+(+1)或3×(+1)把它中和掉(加起来=0)(注意判断顺序！！！)，直到没有(-3)为止；若在中途没有东西能够中和(-3)，则“NO”。

2、然后考虑(+3)，当(+3)的个数大于1时(想想为什么)，依次判断能否让(-3)或2×(-2)+(+1)或(-2)+(-1)或3×(-1)把它中和(注意判断顺序！！！)，直到(+3)个数小于等于1为止；若在中途没有东西能够中和(+3)，则“NO”。

3、若都没有“NO”，则“YES”。

#include <stdio.h>
#include <string.h>

int *num, a[7];

int min(int a, int b) { return (a > b) ? b : a; }

int check() {
    int t = 0;
    for (int i = -3; i <= 3; i++)
        t += num[i] * i;
    if (t > 3 || t < 0)
        return 0;

    t = min(num[3], num[-3]);
    num[3] -= t;
    num[-3] -= t;

    t = min(num[2], num[-1]);
    num[2] -= t;
    num[-1] -= t;
    num[1] += t;

    t = min(num[-3], num[1]);
    num[1] -= t;
    num[-3] -= t;
    num[-2] += t;

    if (num[-3])
        return 0;


    t = min(num[-2], num[1]);
    num[-2] -= t;
    num[1] -= t;
    num[-1] += t;

    t = min(num[3], num[-1]);
    num[-1] -= t;
    num[3] -= t;
    num[2] += t;
    if (num[3] > 1)
        return 0;
    return 1;
}

int main() {
    int n, t, now;
    num = &a[3];
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        memset(a, 0, sizeof(a));
        while (n--) {
            scanf("%d", &now);
            num[now]++;
        }
        printf("%s\n", check() ? "YES" : "NO");
    }
    return 0;
}