情况

时间：2024年7月7日22:35
image.png

思路

A - Array Divisibility

题意

给出数组长度，找这样一个数组：下标为K的倍数，它们的和是K的倍数。

思路

直接12345678·····

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void solve()
{
    int n;
    cin >> n;
    vector<int> a(n, 0);
    for (int i = 0; i < n;i++){
        a[i]=i+1;
    }

    for (int i = 0; i < n;i++){
        cout <<a[i]<<" ";
    }
    cout << endl;
}

B

题意

给出操作之前的网格和操作之后的网格，能使用任意次数如下操作：

  1. 在网格中选取任何具有长度和宽度的子矩形
  2. 子矩形有四个角。取所选子矩形的任意一对对角线相对的角，并向它们的值相加1再模3
  3. 对于未选择的一对角，在它们的值中加上2模3

请你判断能否完成。

思路

对于能完成该变化的矩阵每一列的和和每一行的和，在变化前后的差的绝对值模3都为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
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 501;
int cha[N];
int cha2[N];
void solve()
{
    int n, m;
    cin >> n >> m;
    memset(cha, 0, sizeof(cha));
    memset(cha2, 0, sizeof(cha2));

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            char c;
            cin >> c;
            cha[j] += c-'0';
            cha2[i] += c - '0';
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; ++j)
        {
            char x;
            cin >> x;
            cha[j] -= x-'0';
            cha2[i] -= x - '0';
        }
    }
    for (int j = 0; j < m; ++j)
    {
        if (abs(cha[j]) % 3 != 0)
        {
            cout << "NO" << endl;
            return;
        }
    }
    for (int i = 0; i < n; ++i)
    {
        if (abs(cha2[i]) % 3 != 0)
        {
            cout << "NO" << endl;
            return;
        }
    }
    cout << "YES" << endl;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

问题

刚开始少考虑对于每一行的和，没想到WA on test2了

C

题意

三个数组，总和都一样，要找三个区间，每个区间都对应一个数组上的区间，不能有交集。让这三个区间上元素和的值都大于等于 一个区间的和/3，向上取整。

思路

学习高手写法！参考jiangly
那很简单啊，只有一个排列吧，一个排列然后摊。 —–jiangly
从头开始，找到能大于sum/3向上取整最小区间，如果剩下的第三个不可以，那这个区间划分就不行。执行6种情况的每一个区间划分（从头开始找最小，不是全部）。
代码细节比较多：用array，用next_permutation，用cout条件输出，用array存放l,r值

代码

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
#include <bits/stdc++.h>
#include <array>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 100000;
void solve()
{
    int n;
    cin >> n;
array<vector<int>, 3> a;
LL tot = 0;
for (int i = 0; i < 3;i++){
    a[i].resize(n);//给vector设大小
}
for (int j = 0; j < 3; j++)
    for (int i = 0; i < n; i++){
        cin >> a[j][i];
        if(j==0){tot+=a[j][i];}
    }
    array<int, 3> perm{0,1,2};//代表a,b,c三个数组
do{
    array<int, 3> l{}, r{};
    int cur = 0;
    bool ok = true;
    for (int i = 0; i < 3;i++){
        l[perm[i]] = cur + 1; // 记录perm[i]的l边界
        LL sum = 0;
        while(sum<(tot+2)/3 && cur<n){
            sum+=(a[perm[i]][cur++]);
        }
        if(sum<(tot+2)/3){
            ok = false;
            break;//没戏了
        }
        r[perm[i]] = cur;//记录perm[i]的r边界
    }
    if(ok){
        for (int i = 0; i < 3;i++){
            cout << l[i]<<' '<<r[i]<<" \n"[i==2];//方括号内为1时，相当于输出换行，否则输出空格
        }
        return;
        }
}while(next_permutation(perm.begin(),perm.end()));
cout << "-1\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

问题

开LL!开LL!还有，以后用C++20吧···
刚开始想的是前缀和+双指针，以为比赛时候能做出来。结果补题时候发现这个双指针太慢了····，本质上还是暴力。
TLE on test 3 了，不出所料。
后来发现我这种做法需要根据数组和当前值来变化长度。
先找到前两个区间满足条件的最小区间，之后剩下的区间就直接判断就可以了。
丑陋的写法：

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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
#define int LL
const int N = 100000;

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1, 0);
    vector<int> b(n + 1, 0);
    vector<int> c(n + 1, 0);
    int sum = 0;
    for (int j = 1; j <= n; j++)
    {
        int aa;
        cin >> aa;
        sum += aa;
        a[j] = aa + a[j - 1];
    }
   int target = (2 + sum) / 3;
    for (int j = 1; j <= n; j++)

    {
        int bb;

        cin >> bb;
        b[j] = bb + b[j - 1];
    }
    for (int j = 1; j <= n; j++)
    {
        int cc;
        cin >> cc;
        c[j] += cc + c[j - 1];
    }
    int l = 1, r = 1;
    // 1 to l, l+1 to r, r+1 to n
while(r<n){
    int sum1 = a[l],sum2 =b[r]-b[l],sum3 = c[n] - c[r];
    if(sum1<target){
        l++;
        if(l>r)
            r++;
        continue;
    }
    if(sum2<target){
        r++;
        continue;
    }
    if (sum3 >= target)
    {
        printf("%d %d %d %d %d %d\n", 1, l, l + 1, r, r + 1, n);
        return;
    }
    else
        break;
    }
    l = 1, r = 1;
    while (r < n)
    {
        int sum1 = b[l], sum2 = a[r] - a[l], sum3 = c[n] - c[r];
        if (sum1 < target)
        {
            l++;
            if (l > r)
                r++;
            continue;
        }
        if (sum2 < target)
        {
            r++;
            continue;
        }
        if (sum3 >= target)
        {
            printf("%d %d %d %d %d %d\n", l + 1, r, 1, l, r + 1, n);
            return;
        }
        else
            break;
    }
    l = 1, r = 1;
    while (r < n)
    {
        int sum1 = c[l], sum2 = b[r] - b[l], sum3 = a[n] - a[r];
        if (sum1 < target)
        {
            l++;
            if (l > r)
                r++;
            continue;
        }
        if (sum2 < target)
        {
            r++;
            continue;
        }
        if (sum3 >= target)
        {
            printf("%d %d %d %d %d %d\n", r + 1, n, l + 1, r, 1, l);
            return;
        }
        else
            break;
    }
    l = 1, r = 1;
    while (r < n)
    {
        int sum1 = c[l], sum2 = a[r] - a[l], sum3 = b[n] - b[r];
        if (sum1 < target)
        {
            l++;
            if (l > r)
                r++;
            continue;
        }
        if (sum2 < target)
        {
            r++;
            continue;
        }
        if (sum3 >= target)
        {
            printf("%d %d %d %d %d %d\n", l + 1, r, r + 1, n, 1, l);
            return;
        }
        else
            break;
    }
    l = 1, r = 1;
    while (r < n)
    {
        int sum1 = a[l], sum2 = c[r] - c[l ], sum3 = b[n] - b[r];
        if (sum1 < target)
        {
            l++;
            if (l > r)
                r++;
            continue;
        }
        if (sum2 < target)
        {
            r++;
            continue;
        }
        if (sum3 >= target)
        {
            printf("%d %d %d %d %d %d\n", 1, l, r + 1, n, l + 1, r);
            return;
        }
        else
            break;
    }
    l = 1, r = 1;
    while (r < n)
    {
        int sum1 = b[l], sum2 =c[r] - c[l], sum3 = a[n] - a[r];
        if (sum1 < target)
        {
            l++;
            if (l > r)
                r++;
            continue;
        }
        if (sum2 < target)
        {
            r++;
            continue;
        }
        if (sum3 >= target)
        {
            printf("%d %d %d %d %d %d\n", r + 1, n, 1, l, l + 1, r);
            return;
        }else
            break;
    }
 printf("-1\n");
    return;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}