ABC-278解题报告

发表于 更新于 分类于

比赛传送门

D. All Assign Point Add

题意：给你一个数组 aa，需要支持：全局赋值、单点加、单点查询。

做法一

维护最近一次全局赋值操作及每个位置在该操作后的增加量，当进行赋值操作时清空所有增加量。增加量可以用数组维护，但 STL 实现起来更简单。

By tute7627

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
int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  ll res=0,buf=0;
  bool judge = true;
    ll n;cin>>n;
    vector<ll>a(n);
    map<ll,ll>mp;
    ll last=0;
    rep(i,0,n){
        ll a;cin>>a;
        mp[i+1]+=a;
    }
    ll q;cin>>q;
    while(q--){
        ll t;cin>>t;
        if(t==1){
            ll x;cin>>x;
            last=x;
            mp.clear();
        }
        if(t==2){
            ll i,x;cin>>i>>x;
            mp[i]+=x;
        }
        if(t==3){
            ll i;cin>>i;
            cout<<mp[i]+last<<endl;
        }
    }
  return 0;
}

做法二（赛时做法）

维护最后一次赋值操作的位置（即是第几次操作），单点增加时，若之前的修改在最后一次赋值之前，则将之前的结果删掉，改为赋值的量加这次的修改。询问时比较最后一次单点加和和最后一次赋值操作哪个在后，若赋值在后，则为赋值的结果，否则为维护的结果。

By IgorI

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
void solve()
{
    int n;
    cin >> n;
    vll a(n);
    cin >> a;
    int q;
    cin >> q;
    ll lst_mass = -2, val = 0;
    vll lst(n, -1);
    for (int i = 0; i < q; i++)
    {
        int t;
        cin >> t;
        if (t == 1)
        {
            int x;
            cin >> x;
            lst_mass = i;
            val = x;
        }
        if (t == 2)
        {
            int j, x;
            cin >> j >> x;
            j--;
            ll cur = 0;
            if (lst_mass > lst[j])
                cur = val;
            else
                cur = a[j];
            cur += x;
            lst[j] = i;
            a[j] = cur;
        }
        if (t == 3)
        {
            int j;
            cin >> j;
            j--;
            if (lst_mass > lst[j])
                cout << val << "\n";
            else
                cout << a[j] << "\n";
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int t = 1;
    #ifdef tests
    cin >> t;
    #endif // tests
    while (t--)
    {
        solve();
    }
}

做法三

单点加、区间赋值、单点查询完全可以用线段树实现，大幅降低思维难度。

By maspy

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
void solve() {
  using Lazy = Lazy_CntSum_Affine<ll>;
  LL(N);
  VEC(ll, A, N);
  LazySegTree<Lazy> seg(N, [&](int i) -> pi { return {1, A[i]}; });
  LL(Q);
  FOR(Q) {
    LL(t);
    if (t == 1) {
      LL(x);
      seg.apply(0, N, {0, x});
    }
    if (t == 2) {
      LL(i, x);
      --i;
      seg.apply(i, i + 1, {1, x});
    }
    if (t == 3) {
      LL(i);
      --i;
      print(seg.get(i).se);
    }
  }
}

signed main() {
  cout << fixed << setprecision(15);

  ll T = 1;
  // LL(T);
  FOR(T) solve();

  return 0;
}

做法四（错误）

By daisybunny

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
#include<bits/stdc++.h>
using namespace std;
long long n,q;
long long ba;
long long m[200005],i[200005],x[200005];
long long a[200005];
vector<pair<long long,long long> > v[200005];
long long lo=-1;
int main()
{
    cin>>n;
    for(long long t=0;t<n;t++)
        cin>>a[t];
    cin>>q;
    for(long long t=0;t<q;t++)
    {
        cin>>m[t];
        if(m[t]==2)
        {
            cin>>i[t]>>x[t];
            i[t]--;
            pair<long long,long long> pr;
            pr.first=t;pr.second=x[t];
            v[i[t]].push_back(pr);
        }
        else if(m[t]==1)
        {
            cin>>x[t];
            lo=t;
        }
        else
        {
            cin>>i[t];
            i[t]--;
            long long c;
            if(lo==-1)
            {
                c=a[i[t]];
            }
            else
            {
                c=x[lo];
            }
            for(long long j=v[i[t]].size()-1;j>=0&&v[i[t]][j].first>lo;j--)
            {
                c+=v[i[t]][j].second;
            }
            cout<<c<<endl;
        }
    }
    return 0;
}

这份代码的思路为，对于单点修改，直接用每个位置一个 vector 存起来，全局赋值也存下来，询问时倒序查找 vector，只考虑在最后一次赋值操作后面的修改。

这份代码虽然 AC，但复杂度是有问题的。只要是在最后一次全局赋值之后的修改，每次询问都会扫一遍，所以复杂度可以被卡成 O(q2)O(q^2)。可以这样构造数据：先在位置 11 单点修改 10510^5 次，然后查询 10510^5 次位置 11。每次查询都会重新处理所有的修改，故无法通过。

如果要将复杂度改正确，可以询问时将这些修改的贡献合并起来，而无需每次扫一遍。

fixed

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
#include<bits/stdc++.h>
using namespace std;
long long n,q;
long long ba;
long long m[200005],i[200005],x[200005];
long long a[200005];
vector<pair<long long,long long> > v[200005];
long long lo=-1;
int main()
{
    cin>>n;
    for(long long t=0;t<n;t++)
        cin>>a[t];
    cin>>q;
    for(long long t=0;t<q;t++)
    {
        cin>>m[t];
        if(m[t]==2)
        {
            cin>>i[t]>>x[t];
            i[t]--;
            pair<long long,long long> pr;
            pr.first=t;pr.second=x[t];
            v[i[t]].push_back(pr);
        }
        else if(m[t]==1)
        {
            cin>>x[t];
            lo=t;
        }
        else
        {
            cin>>i[t];
            i[t]--;
            long long c;
            if(lo==-1)
            {
                c=a[i[t]];
            }
            else
            {
                c=x[lo];
            }
            pair<long long,long long> tmp{0,0};
            while(!v[i[t]].empty()&&v[i[t]].back().first>lo)
            {
                tmp.first=v[i[t]].back().first;
                tmp.second+=v[i[t]].back().second;
                v[i[t]].pop_back();
            }
            if(tmp.second!=0)
            {
                v[i[t]].push_back(tmp);
                c+=v[i[t]].back().second;
            }
            cout<<c<<endl;
        }
    }
    return 0;
}

E. Grid Filling

题意：给你一个 n×mn\times m 的矩阵，值域 [1,k][1,k]，对于每个 x×yx\times y 的子矩阵，求出除去该子矩阵后，剩下部分的颜色个数。

做法一

预处理出 sum[i][j][k]sum[i][j][k] 表示左上角 (1,1)−(i,j)(1,1)-(i,j) 的子矩阵中有多少个 kk，则对于一个子矩阵，可以对于每个 kk 都 O(1)O(1) 计算出子矩阵外有多少个 kk，统计一下即可。总复杂度 O(nmk)O(nmk)。

By Forested

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
int main() {
    i32 h, w, n, sh, sw;
    cin >> h >> w >> n >> sh >> sw;
    Vec<Vec<i32>> a(h, Vec<i32>(w));
    REP(i, h) REP(j, w) {
        cin >> a[i][j];
        --a[i][j];
    }

    Vec<Vec<Vec<i32>>> sum(n, Vec<Vec<i32>>(h + 1, Vec<i32>(w + 1, 0)));
    REP(i, n) {
        REP(j, h) REP(k, w) {
            sum[i][j + 1][k + 1] = sum[i][j][k + 1] + sum[i][j + 1][k] - sum[i][j][k] + (i32) (a[j][k] == i);
        }
    }

    REP(i, h - sh + 1) REP(j, w - sw + 1) {
        i32 cnt = 0;
        REP(k, n) {
            i32 cd = sum[k][i + sh][j + sw] - sum[k][i][j + sw] - sum[k][i + sh][j] + sum[k][i][j];
            if (cd < sum[k][h][w]) {
                ++cnt;
            }
        }
        cout << cnt << " \n"[j == w - sw];
    }
}

做法二

对于每个数 kk，预处理出它所出现的上、下、左、右界。于是对于一个子矩阵，枚举每个 kk，也可以 O(1)O(1) 判断矩阵外是否有 kk：如果上下左右界全部在子矩阵内则没有，否则一定有。正确性显然。复杂度 O(nmk)O(nmk)。

By IgorI

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
void solve()
{
    int n, m, k, h, w;
    cin >> n >> m >> k >> h >> w;
    vvi a(n, vi(m));
    cin >> a;

    vi L(k, INF), R(k, -INF), U(k, INF), D(k, -INF);
    forn(i, n) forn(j, m)
    {
        a[i][j]--;
        L[a[i][j]] = min(L[a[i][j]], i);
        R[a[i][j]] = max(R[a[i][j]], i);
        U[a[i][j]] = min(U[a[i][j]], j);
        D[a[i][j]] = max(D[a[i][j]], j);
    }
    for (int i = 0; i <= n - h; i++)
    {
        for (int j = 0; j <= m - w; j++)
        {
            int x = 0;
            for (int y = 0; y < k; y++)
            {
                if (L[y] < i || R[y] >= i + h || U[y] < j || D[y] >= j + w)
                    x++;
            }
            cout << x << " ";
        }
        cout << "\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int t = 1;
    #ifdef tests
    cin >> t;
    #endif // tests
    while (t--)
    {
        solve();
    }
}

做法三（赛时做法）

对于每一行，从左往右扫，动态维护矩阵外出现颜色的桶。当往右移动一格时，暴力从桶里加入一列，删掉一列即可。复杂度 O(n2m)O(n^2m)。

By tatyam

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
int main(){
    LL(H,W,N,h,w);
    VV(ll,a,H,W);
    each(v,a)each(x,v)x--;
    vec(ll,cnt,N);
    ll kinds=0;
    vv(ll,ans,H-h+1,W-w+1);
    auto add=[&](ll x,ll y){
        if(cnt[a[x][y]]++==0)kinds++;
    };
    auto remove=[&](ll x,ll y){
        if(--cnt[a[x][y]]==0)kinds--;
    };
    rep(H)rep(j,W)add(i,j);
    rep(x,h,H+1){
        rep(i,x-h,x)rep(j,w)remove(i,j);
        ans[x-h][0]=kinds;
        ll y=w;
        while(y<W){
            rep(i,x-h,x)add(i,y-w);
            rep(i,x-h,x)remove(i,y);
            y++;
            ans[x-h][y-w]=kinds;
        }
        rep(i,x-h,x)rep(j,W-w,W)add(i,j);
    }
    each(v,ans)out(v);
}

做法四

与做法三类似，每一行从左往右扫时，可以维护内部每个颜色的出现次数，判断是否等于总出现次数，如果等于则说明外部没有。复杂度 O(n2m)O(n^2m)。

By pengin

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<stdio.h>
int a[302][302];
int count[302];
int cnt[302];
int main()
{
    int H, W, n, h, w;
    scanf("%d %d %d %d %d", &H, &W, &n, &h, &w);
    int i, j, k;
    for (i = 0; i < H; i++)
    {
        for (j = 0; j < W; j++)
        {
            scanf("%d", &a[i][j]);
            a[i][j]--;
        }
    }
    for (i = 0; i < n; i++)
        count[i] = 0;
    for (i = 0; i < H; i++)
        for (j = 0; j < W; j++)
            count[a[i][j]]++;
    int res;
    for (i = 0; i <= H - h; i++)
    {
        for (k = 0; k < n; k++)
            cnt[k] = 0;
        res = 0;
        for (k = 0; k < n; k++)
            if (count[k] > 0)
                res++;
        for (k = i; k < i + h; k++)
        {
            for (j = 0; j < w; j++)
            {
                cnt[a[k][j]]++;
                if (cnt[a[k][j]] == count[a[k][j]])
                    res--;
            }
        }
        printf("%d", res);
        for (j = 0; j < W - w; j++)
        {
            for (k = i; k < i + h; k++)
            {
                if (cnt[a[k][j]] == count[a[k][j]])
                    res++;
                cnt[a[k][j]]--;
            }
            for (k = i; k < i + h; k++)
            {
                cnt[a[k][j + w]]++;
                if (cnt[a[k][j + w]] == count[a[k][j + w]])
                    res--;
            }
            printf(" %d", res);
        }
        printf("\n");
    }
    return 0;
}

做法五

对于每个颜色，同样处理出上下左右界，考虑哪些位置的子矩阵能全部包含它们。最左上角的能包含它们的子矩阵为右下界向左上移 (x,y)(x,y)；最右下角的能包含它们的子矩阵自然为左上界。可以使用修改差分数组，求二维前缀和来维护。复杂度 O(nmk)O(nmk)。

By qwycnjwami

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
template<typename T>
struct Rect {
    Rect(T _t = INF, T _b = -INF, T _l = INF, T _r = -INF) : t(_t), b(_b), l(_l), r(_r) {
    }
    void add(int x, int y) {
        t = min(t, x), b = max(b, x);
        l = min(l, y), r = max(r, y);
    }

    bool empty() {
        return !(t <= b && l <= r);
    }

    T t, b, l, r;

    static const T INF = numeric_limits<T>::max();
};

int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(12);


    int H, W, N, h, w;
    cin >> H >> W >> N >> h >> w;

    vector<vector<int>> A(H, vector<int>(W, 0));
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            cin >> A[i][j];
            --A[i][j];
        }
    }



    vector<Rect<int>> rects(N + 1);
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            rects[A[i][j]].add(i, j);
        }
    }

    int total = 0;
    for (auto& r : rects) {
        if (!r.empty()) {
            ++total;
        }
    }
    print(total);
    vector<vector<int>> acc(H + 2, vector<int>(W + 2, 0));

    for (auto& rect : rects) {
        if (rect.empty()) {
            continue;
        }
        int t = rect.t, b = rect.b, l = rect.l, r = rect.r;
        print(t, b, l, r);
        int minX = max(0, b - (h - 1));
        int maxX = min(t, H - h);
        int minY = max(0, r - (w - 1));
        int maxY = min(l, W - w);
        print(minX, maxX, minY, maxY);
        if (minX <= maxX && minY <= maxY) {
            acc[minX + 1][minY + 1] += 1;
            acc[minX + 1][maxY + 1 + 1] -= 1;
            acc[maxX + 1 + 1][minY + 1] -= 1;
            acc[maxX + 1 + 1][maxY + 1  + 1] += 1;
        }
    }

    for (int i = 1; i <= H; ++i) {
        for (int j = 1; j <= W; ++j) {
            acc[i][j] += acc[i][j - 1] + acc[i - 1][j] - acc[i - 1][j - 1];
        }
    }
    // for (auto& V : acc) {
    //     print(V);
    // }


    for (int i = 0; i + h <= H; ++i) {
        for (int j = 0; j + w <= W; ++j) {
            auto ans = total - acc[i + 1][j + 1];
            write << ans << (j + w == W ? '\n' : ' ');
        }
    }

    return 0;
}

F. Shiritori

题意：给你 nn 个字符串，两个人轮流拿走字符串，要求拿走的字符串的首必须等于上一次拿走的字符串的尾。第一次可以拿任意字符串。问先手必胜还是后手必胜。

一个显然的状压 DP。定义 f[mask][i]f[mask][i] 表示当前集合为 maskmask，上一次选了字符串 ii；或者 f[mask][c]f[mask][c] 表示当前集合为 maskmask，上一次的末尾字符为 cc，接下来先手必胜还是后手必胜。转移时只能选择剩余的，能匹配的字符串转移。对于第一次操作任意选特殊处理一下即可。可以用循环也可以用记忆化搜索。

循环写法

By maspy

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() {
  LL(N);
  VEC(string, S, N);
  // 残り文字列、直前 -> 先手はかつか？
  vv(bool, DP, 1 << N, N);
  FOR(s, 1 << N) {
    FOR(i, N) {
      vi cand;
      FOR(j, N) {
        if (!(s & 1 << j)) continue;
        if (S[i].back() != S[j][0]) continue;
        cand.eb(j);
      }
      for (auto&& j: cand) {
        int t = s - (1 << j);
        assert(s > t);
        if (DP[t][j] == 0) DP[s][i] = 1;
      }
    }
  }

  FOR(i, N) {
    ll full = (1 << N) - 1;
    ll s = full - (1 << i);
    if (DP[s][i] == 0) return print("First");
  }
  print("Second");
}

signed main() {
  cout << fixed << setprecision(15);

  ll T = 1;
  // LL(T);
  FOR(T) solve();

  return 0;
}

记搜写法

By Forested

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
int main() {
    constexpr i32 S = 26;
    i32 n;
    cin >> n;
    Vec<i32> a(n), b(n);
    REP(i, n) {
        string s;
        cin >> s;
        a[i] = s[0] - 'a';
        b[i] = s.back() - 'a';
    }

    Vec<Vec<i32>> memo(n, Vec<i32>(1 << n, -1));
    const auto dp = [&](const auto &dp, i32 lst, i32 used) -> i32 {
        if (used == (1 << n) - 1) {
            return 1;
        }
        if (memo[lst][used] != -1) {
            return memo[lst][used];
        }
        REP(i, n) {
            if (used & (1 << i)) {
                continue;
            }
            if (used != 0 && b[lst] != a[i]) {
                continue;
            }
            if (dp(dp, i, used ^ (1 << i)) == 1) {
                return memo[lst][used] = 0;
            }
        }
        return memo[lst][used] = 1;
    };
    i32 winner = dp(dp, 0, 0);
    cout << (winner == 0 ? "First\n" : "Second\n");
}