情况

时间：2024年7月26日22:35

题解

A

题意

鸡两只腿，牛4。一共n腿，最少多少只动物

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void solve()
{
    int t;
    cin >> t;
    int ans = 0;

    if (t % 4 == 0)
    {
        ans = t / 4;
    }
    else
    {
        ans = (t / 4) + 1;
    }

    cout << ans << endl;
}

jiangly先/2，看奇偶，再/2

B

题意

缩一个矩阵。

思路

因为放缩长度内的都相等，所以直接从原矩阵隔着一个长度找一个。

代码

Fool’s v

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void solve()
{
    int n, k;
    cin >> n >> k;
    int rx = n / k;
    int v[n][n];
    int realm[rx][rx];
    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < n ;j++ )
        {
            char c;
            cin >> c;
            v[i][j] = c - '0';
        }
    }
        for(int i = 0 ; i < rx ; i++){
            for(int j = 0 ; j < rx ;j++)
            {
                realm[i][j] = v[i*k][j*k];
                cout << realm[i][j];
            }
            cout << endl;
        }
        return;
}

jiangly

jiangly写的更简单，用string读入每一行就行了。不用开二维。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void solve()
{
    int n, k;
    std::cin >> n >> k;

    std::vector<std::string> s(n);
    for (int i = 0; i < n; i++)
    {
        std::cin >> s[i];
    }
    for (int i = 0; i < n; i += k)
    {
        for (int j = 0; j < n; j += k)
        {
            std::cout << s[i][j];
        }
        std::cout << "\n";
    }
}

C

题意

你得到两个字符串 a 和 b ，长度为 n 。然后，你（被迫违背你的意愿）回答 q 查询。
对于每一个查询，您都将得到一个由 l 和 r 限定的范围。在一个操作中，您可以选择整数 ii （ l≤i≤r ）并设置 ai=x ，其中 x 是您想要的任何字符。输出必须执行的最小操作数，以使
sorted(a[l..r])=sorted(b[l..r]) 。对一个查询执行的操作不会影响其他查询。
对于任意字符串 c ， sorted(c[l..r]) 表示由字符 cl,cl+1,…,cr。 c按字典顺序排序。

思路

前缀和统计字母次数，答案为字母出现次数差绝对值/2。

代码

fool’s v

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
void solve()
{
    int n, q;
    cin >> n >> q;
    string s1, s2;
    cin >> s1 >> s2;

    vector<vector<int>> pref1(n + 1, vector<int>(26, 0));
    vector<vector<int>> pref2(n + 1, vector<int>(26, 0));

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < 26; ++j)
        {
            pref1[i + 1][j] = pref1[i][j];
            pref2[i + 1][j] = pref2[i][j];
        }
        pref1[i + 1][s1[i] - 'a']++;
        pref2[i + 1][s2[i] - 'a']++;
    }

    while (q--)
    {
        int l, r;
        cin >> l >> r;
       

        int count1, count2, ans = 0;
        for (int i = 0; i < 26; ++i)
        {
            count1 = pref1[r][i] - pref1[l-1][i];
            count2 = pref2[r][i] - pref2[l-1][i];
            ans += abs(count1 - count2);
        }

        cout << ans / 2 << endl;
    }
}

jiangly

细节：pre[i + 1] = pre[i];很简洁的写法。相减操作在第一轮遍历就完成。输出max那个和绝对值除以2一样效果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void solve()
    {
        int n, q;
        std::cin >> n >> q;

        std::string a, b;
        std::cin >> a >> b;

        std::vector<std::array<int, 26>> pre(n + 1);
        for (int i = 0; i < n; i++)
        {
            pre[i + 1] = pre[i];
            pre[i + 1][a[i] - 'a']++;
            pre[i + 1][b[i] - 'a']--;
        }

        while (q--)
        {
            int l, r;
            std::cin >> l >> r;
            l--;

            int ans = 0;
            for (int c = 0; c < 26; c++)
            {
                ans += std::max(0, pre[r][c] - pre[l][c]);
            }
            std::cout << ans << "\n";
        }
    }

问题

c题TLE好多次。很奇怪。不过TLE答案确实比较繁琐。

D

题意

给定两个整数 n 和 x ，求正整数的三元组（ a,b,ca,b,c ）的个数，使得 ab+ac+bc≤n和 a+b+c≤x 。a,b,c严格大于0；

思路

遍历a来限制b，遍历范围中的b限制c。这样全都能遍历完。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void solve()
{
    int n, x;
    cin >> n;
    cin >> x;
    int count = 0;
    for (int a = 1; a <= x; a++)
    {
        int bmax = min(x - a, n / a);
        for (int b = 1; b <= bmax; b++)
        {
            int cmax = min(x - a - b, (n - a * b) / (a + b));
            if(cmax > 0)
            count += cmax;
        }
    }
    cout << count << '\n';
}

E

题意

01串，输出所有L.R中0的个数等于1的个数子串的子串数量。（直接翻译容易错是这样的）

思路

0变成-1找，和是0就是满足题意。用前缀和数组记录。

  1. 改写整个序列，把1看作1，0看作-1，这一步是很经典的，有很多题都运用到了这种技巧。
  2. 接下来“区间和为0”转化为“前缀和相等”，也是很经典的的技巧。
  3. 最后改变思考的角度，不从 (l, r) 而从 (x, y) 考虑，统计一个 (x, y) 会被几个 (l, r) 包含，这一步也很经典。
    最后就是写代码的问题了，给我的感觉就是这题很典。

后*前=一个lr的次数贡献。
遍历1-n过程中，是遍历后是定值。加的这个数前值和，表示这个后值下标之前有多少前值累计。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void solve()
{
    string s;
    cin >> s;

    int n = s.size();
    vector<int> pref(n + 1), count(2 * n + 1, 0);

    for (int i = 0; i < n; i++)
    {
        if (s[i] == '1')
            pref[i + 1] = pref[i] + 1;
        else
            pref[i + 1] = pref[i] - 1;
    }

    int ans = 0;
    for (int i = 0; i < n; i++)
    { 

        count[pref[i] + n] += i + 1;
        int dangqian = count[pref[i + 1] + n];//前面
        ans = (ans + dangqian * (n -  i) )% MOD; //n-i是i+1位置的后值
        
    }

    cout << ans << endl;
}

问题

没有modint板子