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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

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

void solve() {
    string s;
    cin >> s;
    int n = s.size();
    if (n == 2) {
        cout << "Yes\n";
        return;
    }
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        if (s[i] == '(' or s[i] == ')')
            a[i] = 1;
    }
    int l0 = -1, l1 = -1;
    for (int i = 0; i < n; i++) {
        if (a[i]) {
            if (l0 != -1) {
                if (i - l0 > 2) {
                    cout << "No\n";
                    return;
                }
                l0 = -1;
            }
            if (l1 == -1) {
                l1 = i;
            }
        } else {
            if (l0 == -1) {
                l0 = i;
            }
            if (l1 != -1) {
                if (i - l1 > 2) {
                    cout << "No\n";
                    return;
                }
                l1 = -1;
            }
        }
    }
    if (l0 != -1) {
        if (n - l0 > 2) {
            cout << "No\n";
            return;
        }
    }
    if (l1 != -1) {
        if (n - l1 > 2) {
            cout << "No\n";
            return;
        }
    }
    vector<int> c[2] = {};
    for (int i = 1; i < n; i++) {
        if (a[i] == a[i - 1]) {
            c[a[i]].emplace_back(i);
        }
    }
    if (c[0].size() + c[1].size() > 2) {
        cout << "No\n";
        return;
    }
    cout << "Yes\n";
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

 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

#include <bits/stdc++.h>
using namespace std;
int n;
void solve() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    int x = a + c, y = b + d;
    string s1 = to_string(x);
    int maxn = 0;
    for (auto i : s1) {
        maxn = max(maxn, i - '0');
    }
    for (int i = x; i <= y; i++) {
        string s2 = to_string(i);
        for (auto j : s2) {
            maxn = max(maxn, j - '0');
        }
        if (maxn == 9) {
            cout << 9 << '\n';
            return;
        }
    }
    cout << maxn << '\n';
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

  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
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100

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

using i64 = long long;
struct DSU {
    vector<int> f;

    DSU(int n) : f(n) { iota(f.begin(), f.end(), 0); }

    int find(int x) {
        while (f[x] != x)
            x = f[x] = f[f[x]];
        return x;
    }

    void merge(int x, int y) {
        x = find(x), y = find(y);
        f[y] = x;
    }
};

constexpr int modn = 1e9 + 7;
int p2(i64 b) {
    i64 res = 1;
    i64 a = 2;
    while (b) {
        if (b & 1) {
            (res *= a) %= modn;
        }
        (a *= a) %= modn;
        b >>= 1;
    }
    return res;
}

void solve() {
    int r, c;
    cin >> r >> c;
    vector g(r, vector<char>(c));
    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++)
            cin >> g[i][j];

    DSU dsu(2 * r);
    for (int i = 0, j = c - 1; i <= j; i++, j--) {
        bool ok = false;
        vector<int> c0, c1;
        for (int k = 0; k < r; k++) {
            if (g[k][i] == '1')
                c0.emplace_back(k);
            if (g[k][j] == '1')
                c1.emplace_back(k);
        }
        if (i == j) {
            if (c0.size() > 1)
                ok = true;
        } else {
            if (c0.size() + c1.size() > 2)
                ok = true;
        }
        if (ok == true) {
            cout << "0\n";
            return;
        }
        if (c0.size() == 2) {
            dsu.merge(c0.front(), c0.back() + r);
            dsu.merge(c0.back(), c0.front() + r);
        }
        if (c1.size() == 2) {
            dsu.merge(c1.front(), c1.back() + r);
            dsu.merge(c1.back(), c1.front() + r);
        }
        if (c0.size() == 1 and c1.size() == 1) {
            dsu.merge(c0.front(), c1.front());
            dsu.merge(c0.front() + r, c1.front() + r);
        }
    }
    for (int i = 0; i < r; i++) {
        if (dsu.find(i) == dsu.find(i + r)) {
            cout << "0\n";
            return;
        }
    }
    i64 cnt = 0;
    for (int i = 0; i < 2 * r; i++) {
        if (dsu.find(i) == i)
            cnt++;
    }
    cnt /= 2;
    cout << p2(cnt) << "\n";
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

 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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

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

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    auto check = [&]() -> bool {
        for (int i = 1; i <= n; i++) {
            if (a[i] != i)
                return true;
        }
        return false;
    };
    vector<pair<int, int>> vec;
    while (check()) {
        int l = 1, r = n;
        for (int i = 1; i <= n; i++) {
            if (a[i] == i) {
                l++;
            } else {
                break;
            }
        }
        for (int i = n; i >= 1; i--) {
            if (a[i] == i) {
                r--;
            } else {
                break;
            }
        }
        for (int i = r; i >= l; i--) {
            if (a[i] < a[l]) {
                vec.emplace_back(l, i);
                sort(a.begin() + l, a.begin() + i + 1);
                break;
            }
        }
        r = n;
        for (int i = n; i >= 1; i--) {
            if (a[i] == i) {
                r--;
            } else {
                break;
            }
        }
        for (int i = l; i <= r; i++) {
            if (a[i] > a[r]) {
                vec.emplace_back(i, r);
                sort(a.begin() + i, a.begin() + r + 1);
                break;
            }
        }
    }
    cout << vec.size() << "\n";
    for (auto [x, y] : vec)
        cout << x << " " << y << "\n";
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

  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
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

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

using i64 = long long;

constexpr void debug(auto first, auto... args) {
    std::print(std::cerr, "{}", first);
    ((std::print(std::cerr, " {}", args)), ...);
    std::print(std::cerr, "\n");
}

struct Midder {
    multiset<int> le, gt; // le: 小于等于中位数，gt: 大于等于中位数
    i64 fle = 0, fgt = 0; // 分别记录le和gt中元素的和

    void balance() {
        // 保持平衡：le.size() == gt.size() 或 le.size() + 1 == gt.size()
        while (gt.size() > le.size() + 1) {
            // 从gt移动最小元素到le
            auto it = gt.begin();
            int val = *it;
            le.insert(val);
            fle += val;
            gt.erase(it);
            fgt -= val;
        }

        while (le.size() > gt.size()) {
            // 从le移动最大元素到gt
            auto it = prev(le.end());
            int val = *it;
            gt.insert(val);
            fgt += val;
            le.erase(it);
            fle -= val;
        }
    }

    void insert(int x) {
        if (le.empty() && gt.empty()) {
            gt.insert(x);
            fgt += x;
        } else {
            int mid = *gt.begin(); // 当前中位数
            if (x <= mid) {
                le.insert(x);
                fle += x;
            } else {
                gt.insert(x);
                fgt += x;
            }
        }
        balance();
    }

    void erase(int x) {
        if (le.find(x) != le.end()) {
            le.erase(le.find(x));
            fle -= x;
        } else if (gt.find(x) != gt.end()) {
            gt.erase(gt.find(x));
            fgt -= x;
        }
        balance();
    }

    int query() {
        // 返回中位数
        if (le.size() == gt.size()) {
            // 偶数个元素，返回平均值（注意整数除法可能的问题）
            return (*le.rbegin() + *gt.begin()) / 2;
        } else {
            // 奇数个元素，返回中间值
            return *gt.begin();
        }
    }

    size_t size() const { return le.size() + gt.size(); }
};

void solve() {
    i64 n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i] -= i; // 预处理：a[i] = a[i] - i
    }

    Midder m;
    int ans = 0;

    for (int l = 0, r = 0; r < n; r++) {
        m.insert(a[r]);

        // 计算当前中位数和代价
        while (l <= r) {
            int mid = m.query();
            i64 cost = (i64)mid * m.le.size() - m.fle + m.fgt - (i64)mid * m.gt.size();

            if (cost <= k) {
                break;
            }

            m.erase(a[l]);
            l++;
        }

        ans = max(ans, (int)m.size());
    }

    cout << ans << "\n";
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}