A A｜B

题目大意

给定两个正整数 $a,x$ ，统计满足以下条件的 $b$ 的个数：

$\quad$ 1. $1 \leq b \leq x$
$\quad$ 2. $a|b = a + b$

分析

$a|b = a + b$ 说明 $a$ 与 $b$ 的二进制表示中 $1$ 的位置互斥.

这里~~很***道地~~用了数位 dp（说好的小白呢？

代码实现

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

typedef long long ll;

const int M = (int)1e6;
const int N = (int)1e5;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const ll mod = (ll)1e9 + 7;

int a, x;
int f[35];
int num[35];

int dfs(int pos, bool limit)
{
    if(pos == -1) return 1;
    if(!limit && ~f[pos]) return f[pos];
    int up = (limit ? num[pos] : 1);
    int res = 0;
    for(int i = 0; i <= up; ++i)
    {
        if(i == 0 || i == 1 && !(a>>pos&1))
        {
            res += dfs(pos - 1, limit && (i == up));
        }
    }
    if(!limit) f[pos] = res;
    return res;
}

int dfs(int n)
{
    int pos = 0;
    while(n)
    {
        num[pos++] = n % 2;
        n /= 2;
    }
    return dfs(pos - 1, 1);
}

void work()
{
    memset(f, -1, sizeof(f));
    scanf("%d %d", &a, &x);
    printf("%d\n", dfs(x) - 1);
}

int main()
{
//    freopen("input.txt", "r", stdin);
    int T; scanf("%d", &T);
    while(T--) work();
//    work();
    return 0;
}

B A + B

题目大意

将数字以及加号用字符矩阵的形式进行表示，对应关系如下：

图片说明

以字符形式给出一个运算式，请你计算结果，同时也请你将结果按照字符的形式输出

分析

直接模拟噢！

代码实现

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

typedef long long ll;

const int M = (int)1e3;
const int N = (int)1e5;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const ll mod = (ll)1e9 + 7;

string s[5];
map<string, int> mp;
map<int, string> remp;

void init()
{
    string t;

    t = "####.##.##.####";
    assert(t.size() == 15);
    mp[t] = 0;

    t = "..#..#..#..#..#";
    assert(t.size() == 15);
    mp[t] = 1;

    t = "###..#####..###";
    assert(t.size() == 15);
    mp[t] = 2;

    t = "###..####..####";
    assert(t.size() == 15);
    mp[t] = 3;

    t = "#.##.####..#..#";
    assert(t.size() == 15);
    mp[t] = 4;

    t = "####..###..####";
    assert(t.size() == 15);
    mp[t] = 5;

    t = "####..####.####";
    assert(t.size() == 15);
    mp[t] = 6;

    t = "####.##.#..#..#";
    assert(t.size() == 15);
    mp[t] = 7;

    t = "####.#####.####";
    assert(t.size() == 15);
    mp[t] = 8;

    t = "####.####..####";
    assert(t.size() == 15);
    mp[t] = 9;

    t = "....#.###.#....";
    assert(t.size() == 15);
    mp[t] = 10;

    for(auto x: mp)
    {
        remp[x.second] = x.first;
    }

//    for(auto x: remp) cout << x.first << " " << x.second << "\n";
}

int cal(int m)
{
    string t = "";
    for(int i = 0; i < 5; ++i) t += s[i].substr(m, 3);
    return mp[t];
}

stack<int> st;

string ans[5];

void drawNum(int n)
{
    for(int i = 0; i < 5; ++i)
    {
        ans[i] += remp[n].substr(3 * i, 3);
    }
}

void draw(int n)
{
    for(int i = 0; i < 5; ++i) ans[i] = "";

    if(n == 0) {drawNum(0); return;}
    while(n)
    {
        st.push(n % 10);
        n /= 10;
    }
    while(!st.empty())
    {
        drawNum(st.top());
        st.pop();
        if(!st.empty())
        {
            for(int i = 0; i < 5; ++i) ans[i] += ".";
        }
    }

    for(int i = 0; i < 5; ++i) cout << ans[i] << "\n";
}

void work()
{
    for(int i = 0; i < 5; ++i) cin >> s[i];
    int ans = 0, len = s[0].size(), x = 0, f = 0;
    for(int i = 0; i < len; i += 4)
    {
        f = cal(i);
        if(f <= 9) x = x * 10 + f;
        else if(f == 10)
        {
            ans += x;
            x = 0;
        }
    }
    ans += x;

    draw(ans);
}

int main()
{
//    freopen("input.txt", "r", stdin);
    init();
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int T; cin >> T;
    for(int ca = 1; ca <= T; ++ca)
    {
        work();
        if(ca < T) cout << "\n";
    }
//    work();
    return 0;
}

C 图像存储

题目大意

数字图像是一个由“0”和“1”这两个元素组成的矩阵，除去边角上的元素，每个元素都有上下左右相邻的四个元素。再一个数字图像中，元素“0”代表空白，只有元素“1”所在的位置才有一个黑点。由此，一副黑白的图像得以显现。

为了能在更少的空间里存储更多的图像，一个可行的办法就是每种相同的黑块只保留一个，其他的地方只保留位置，这样便实现了压缩。查看时，只需将保留的黑块拓印到其它的位置，这样就实现了图像的复原。

可见，该技术的关键就是对不同的黑块进行记录。我们把由若干个相邻的“1”构成的区域定义为黑块，规定一个孤立的“1”也是一个黑块，黑块中“1”的个数为黑块的大小，通过上下左右平移可以实现重合并且等大的黑块为同一种黑块。现在你的任务是分别算出一个图像中黑块的个数和种数。

分析

BFS + 哈希

代码实现

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

typedef long long ll;
typedef unsigned long long ull;

const int M = (int)1e3;
const int N = (int)1e5;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const ll mod = (ll)1e9 + 7;

int n, m;
char s[M + 5][M + 5];
int vis[M + 5][M + 5];


struct node
{
    int x, y;
    node(int _x = 0, int _y = 0): x(_x), y(_y){}
};

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

struct node2
{
    int n, m; ull h;
    node2(int _n, int _m, ull _h): n(_n), m(_m), h(_h){}

    bool operator< (const node2& b)const
    {
        if(n != b.n) return n < b.n;
        if(m != b.m) return m < b.m;
        return h < b.h;
    }

    bool operator== (const node2& b)const
    {
        return n == b.n && m == b.m && h == b.h;
    }
};

vector<node2> Hash;

void bfs(int x, int y)
{
    queue<node> q;
    int xmin = x, ymin = y, xmax = x, ymax = y;
    node u, v;
    vis[x][y] = 1;
    q.push(node(x, y));
    while(!q.empty())
    {
        u = q.front(); q.pop();
        xmin = min(xmin, u.x); ymin = min(ymin, u.y);
        xmax = max(xmax, u.x); ymax = max(ymax, u.y);
        for(int i = 0; i < 4; ++i)
        {
            v = u;
            v.x += dx[i], v.y += dy[i];
            if(v.x < 0 || v.x >= n || v.y < 0 || v.y >= m) continue;
            if(vis[v.x][v.y] == 0 && s[v.x][v.y] == '1')
            {
                vis[v.x][v.y] = 1;
                q.push(node(v.x, v.y));
            }
        }
    }

    ull h = 0;
    for(int i = xmin; i <= xmax; ++i)
    {
        for(int j = ymin; j <= ymax; ++j)
        {
            if(vis[i][j] == 1)
            {
                vis[i][j] = 2;
                h = h * 1331 + 1;
            }
            else h = h * 1331;
        }
    }

    Hash.push_back(node2(xmax - xmin + 1, ymax - ymin + 1, h));
}

void work()
{
    Hash.clear();
    for(int i = 0; i < n; ++i)
    {
        scanf("%s", s[i]);
        for(int j = 0; j < m; ++j)
        {
            vis[i][j] = 0;
        }
    }
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < m; ++j)
        {
            if(vis[i][j] || s[i][j] == '0') continue;
            bfs(i, j);
        }
    }

    printf("%d ", Hash.size());
    sort(Hash.begin(), Hash.end());
    Hash.erase(unique(Hash.begin(), Hash.end()), Hash.end());
    printf("%d\n", Hash.size());
}

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    while(~scanf("%d %d", &n, &m) && (n + m)) work();
//    int T; scanf("%d", &T);
//    while(T--) work();
//    work();
    return 0;
}

D 坐标计数

题目大意

定义一个坐标变换，坐标 $(x,y)$ 变换后变为 $(x \oplus y, |x-y|)$ 。

给定一片矩形区域，计算区域内有多少个整数点在经过有限次变换后变为 $(0,0)$ 。

分析

手玩一下发现所有点都可以经过有限次变换后变为 $(0,0)$ .

那么用容斥原理计算一下矩形面积即可.

代码实现

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

typedef long long ll;

const int M = (int)1e6;
const int N = (int)1e5;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const ll mod = (ll)1e9 + 7;

ll cal(int x, int y)
{
    return 1ll * x * y;
}

void work()
{
    int x1, y1, x2, y2; scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
    ll ans = cal(x2, y2) - cal(x2, y1 - 1) - cal(x1 - 1, y2) + cal(x1 - 1, y1 - 1);
    printf("%lld\n", ans);
}

int main()
{
//    freopen("input.txt", "r", stdin);
    int T; scanf("%d", &T);
    while(T--) work();
//    work();
    return 0;
}

E 解方程

题目大意

给出两个正整数 $a,b$ ，计算满足方程 $ax+by=xy$ 的正整数 $(x, y)$ 的组数。

分析

从 $ax+by=xy$ 开始推

把 $by$ 移项到等式右边得 $ax = (x - b)y$ .

即 $y = \frac{ax}{x - b} = a + \frac{ab}{x - b}$ .

要保证 $y$ 为整数，只需让 $x - b | ab$ .

因此答案即为 $ab$ 的约数个数.

记 $ab$ 唯一分解为 $p_1^{c_1}p_2^{c_2}\cdots p_k^{c_k}$ ，则 $ab$ 的约数个数为 $\prod_{i=1}^k{c_i+1}$ .

代码实现

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

typedef long long ll;

const int M = (int)1e6;
const int N = (int)1e5;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const ll mod = (ll)1e9 + 7;

bool is_prime[M + 5];
int prime[M + 5], cnt;

void init()
{
    memset(is_prime, 1, sizeof(is_prime));
    is_prime[0] = is_prime[1] = 0;
    for(int i = 2; i <= M; ++i)
    {
        if(is_prime[i])
        {
            prime[++cnt] = i;
        }
        for(int j = 1; j <= cnt && i * prime[j] <= M; ++j)
        {
            is_prime[i * prime[j]] = 0;
            if(i % prime[j] == 0)
            {
                break;
            }
        }
    }
}

unordered_map<ll, int> mp;

void divide(ll n)
{
    mp.clear();
    for(int i = 1; i <= cnt && 1ll * prime[i] * prime[i] <= n; ++i)
    {
        if(n % prime[i] == 0)
        {
            int c = 0;
            while(n % prime[i] == 0)
            {
                n /= prime[i];
                ++c;
            }
            mp[prime[i]] = c;
        }
    }
    if(n != 1) mp[n] = 1;
}

void work()
{
    int a, b; scanf("%d %d", &a, &b);
    divide(1ll * a * b);
    int ans = 1;
    for(auto x: mp) ans *= x.second + 1;
    printf("%d\n", ans);
}

int main()
{
    init();
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    int T; scanf("%d", &T);
    while(T--) work();
//    work();
    return 0;
}

F 消减整数

题目大意

给你一个数字 $N$ 依序减掉 $1,2,3,\cdots$ 直到不够减。如果刚好减到 $0$ 就结束，否则就加上 $N$ 继续从 $1$ 开始减，直到减到 $0$ 为止。

请给出一个数字，计算对于该数字一共重复了几次这个过程。

分析

对于一次过程，可以用二分快速求出本次总共减去多少.

接着对答案加了个记忆化就艹过去了！

之后再来更正解吧~

代码实现

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

typedef long long ll;

const int M = (int)1e3;
const int N = (int)1e5;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const ll mod = (ll)1e9 + 7;

unordered_map<int, int> mp;

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

void work()
{
    int n; scanf("%d", &n);
    if(mp.count(n))
    {
        printf("%d\n", mp[n]);
        return;
    }
    int m = n;
    int p = 0;
    while(1)
    {
        ++p;
        n -= cal(n);
        if(n == 0)
        {
            mp[m] = p;
            printf("%d\n", p);
            return;
        }
        n += m;
    }
}

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    int T; scanf("%d", &T);
    while(T--) work();
//    work();
    return 0;
}

G 简单题的逆袭

题目大意

给定 $x,y$ ，找出满足方程 $x^k \leq y$ 的最大的 $k$ .

分析

一开始尝试分类讨论来着，结果一直 WA 个不停...

于是采用了暴力.

代码实现

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

typedef __int128 ll;

const int M = (int)1e6;
const int N = (int)1e5;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const ll mod = (ll)1e9 + 7;

ll read()
{
    ll x = 0; int f = 1;
    char ch = getchar();
    while(!isdigit(ch))
    {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

void work()
{
    ll x, y;
    x = read(), y = read();
    int k = 0;
    ll t = 1;
    if(t > y)
    {
        printf("-1\n");
        return;
    }
    for(int i = 1; i <= 70; ++i)
    {
        if(t <= y && t * x > y)
        {
            printf("%d\n", i - 1);
            return;
        }
        t *= x;
    }
    printf("-1\n");
}

int main()
{
//    freopen("input.txt", "r", stdin);
    int T; scanf("%d", &T);
    while(T--) work();
//    work();
    return 0;
}

H 对称之美

题目大意

给出 $n$ 个字符串，从第 $1$ 个字符串一直到第 $n$ 个字符串每个串取一个字母来构成一个新字符串，新字符串的第 $i$ 个字母只能从第i行的字符串中选出，这样就得到了一个新的长度为 $n$ 的字符串，请问这个字符串是否有可能为回文字符串？

分析

统计每个串的每个字母的出现情况，然后暴力匹配.

代码实现

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

typedef long long ll;

const int M = (int)1e2;
const int N = (int)1e5;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const ll mod = (ll)1e9 + 7;

int n, cnt[M + 5][26];
char s[M + 5];

void work()
{
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
    {
        scanf("%s", s);
        int m = strlen(s);
        for(int j = 0; j < 26; ++j) cnt[i][j] = 0;
        for(int j = 0; j < m; ++j) cnt[i][s[j] - 'a']++;
    }
    for(int i = 0; i < n / 2; ++i)
    {
        bool f = 0;
        for(int j = 0; j < 26; ++j)
        {
            if(cnt[i][j] && cnt[n - i - 1][j])
            {
                f = 1;
                break;
            }
        }
        if(!f)
        {
            puts("No");
            return;
        }
    }
    puts("Yes");
}

int main()
{
//    freopen("input.txt", "r", stdin);
    int T; scanf("%d", &T);
    while(T--) work();
//    work();
    return 0;
}

I 非对称之美

题目大意

给出一个字符串，求最长非回文子字符串的长度

分析

如果一个串 $s$ 不是回文串，那么答案就是 $|s|$ .

否则如果 $s[0:|s|-2]$ 不是回文串，那么答案就是 $|s|-1$ .

否则不难证明串 $s$ 的所有字符全部相同，答案为 $0$ .

代码实现

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

typedef long long ll;

const int M = (int)1e7;
const int N = (int)1e5;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const ll mod = (ll)1e9 + 7;

int n;
char s[M + 5];

bool check()
{
    for(int i = 0; i < n / 2; ++i)
    {
        if(s[i] != s[n - i - 1]) return 0;
    }
    return 1;
}

void work()
{
    scanf("%s", s);
    n = strlen(s);
    if(check())
    {
        --n;
        if(check()) printf("%d\n", 0);
        else        printf("%d\n", n);
    }
    else printf("%d\n", n);
}

int main()
{
//    freopen("input.txt", "r", stdin);
//    int T; scanf("%d", &T);
//    while(T--) work();
    work();
    return 0;
}

牛客小白月赛31【解题报告】

题目大意

分析

代码实现

题目大意

分析

代码实现

题目大意

分析

代码实现

题目大意

分析

代码实现

题目大意

分析

代码实现

题目大意

分析

代码实现

题目大意

分析

代码实现

题目大意

分析

代码实现

题目大意

分析

代码实现

J 排列算式（待补）

题目大意

分析

代码实现