重庆邮电大学第十九届ACM程序设计大赛（网络赛）回顾

前言

上周末参加校赛网络赛ac五道题，成功进入线下赛。但是近来有些烦躁不知从何学起，遂作此篇回顾赛场心境，也算作补题的记录。

赛场回顾

签到部分

开赛后迅速切掉第一道签到，但第二道签到因为在输入数据时漏掉多组数据的t导致错误，自己没有调试而是卡在那里红温浪费了时间。

D. 海鲜八爪鱼VS小猴7

题目链接：
D. 海鲜八爪鱼VS小猴7
大意：
通过一定次数的区间修改，找最后一次的数组最大值与已有数值进行操作后比较。数据范围：元素个数2e5，元素大小1e9，修改次数2e5，修改大小1e9。
思路1：
可以使用差分数组,记录数组中相邻元素的差值，通过对差值的修改得到最后一次的原数组元素值。相较于朴素算法n^2的时间复杂度，这种方法通过增加一个数组的空间使得时间复杂度优化为O（n）。
ac代码：

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

int a[202020];
int b[202020];

signed main() {
  int n, p, q;
  cin >> n >> p >> q;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= n - 1; i++) {
    b[i] = a[i + 1] - a[i];
  }
  int t;
  cin >> t;
  while (t--) {
    int l, r, v;
    cin >> l >> r >> v;
    if (l == 1) {
      a[1] += v;
      b[r] -= v;
    } else {
      b[l - 1] += v;
      b[r] -= v;
    }
  }

  for (int i = 1; i <= n - 1; i++) {
    a[i + 1] = a[i] + b[i];
  }
  sort(a + 1, a + 1 + n);
  // cout<<a[n]<<endl;
  int ans = max(a[n], p);
  if (ans >= q) {
    cout << "3G win win!" << endl;
  } else
    cout << "3G wanna win win" << endl;
  return 0;
}

注意：
可能爆int ,要使用long long

思路2：
赛后尝试了线段树解决。借助Kevin哥的模板轻松解决。
tr.ADD(1, i, i, a);实现了将值传进树内。
tr.ADD(1, l, r, v);实现了对区间的修改。
int ans = max(tr.Query_max(1, 1, n), p);实现了查询最大值。
ac代码：

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


#define int long long


class XDS {
 private:
  int cnt;
  struct as {
    long long l, r, sum, add, mx, son[2];
  };
  vector<as> e;
#define ls(k) e[k].son[0]


#define rs(k) e[k].son[1]


 public:
  XDS(int m = 2020202, int l = 1, int r = 1e9) {
    cnt = 1;
    e = vector<as>(m);
    e[1].l = l, e[1].r = r;
  }
  void up(int k) {
    e[k].sum = e[ls(k)].sum + e[rs(k)].sum;
    e[k].mx = max(e[ls(k)].mx, e[rs(k)].mx);
  }
  void down(int k) {
    if (e[k].add) {
      if (ls(k)) {
        e[ls(k)].add += e[k].add;
        e[ls(k)].sum += e[k].add * (e[ls(k)].r - e[ls(k)].l + 1);
        e[ls(k)].mx += e[k].add;
      }
      if (rs(k)) {
        e[rs(k)].add += e[k].add;
        e[rs(k)].sum += e[k].add * (e[rs(k)].r - e[rs(k)].l + 1);
        e[rs(k)].mx += e[k].add;
      }
      e[k].add = 0;
    }
  }
  void ADD(int k, int l, int r, int v) {
    // cout<<k<<" "<<l<<" "<<r<<" "<<v<<endl;
    if (e[k].l == l && e[k].r == r) {
      e[k].add += v;
      e[k].sum += v * (e[k].r - e[k].l + 1);
      e[k].mx += v;
      return;
    }
    down(k);
    int mid = e[k].l + e[k].r >> 1;
    if (r <= mid) {
      if (!ls(k)) ls(k) = ++cnt, e[ls(k)].l = e[k].l, e[ls(k)].r = mid;
      ADD(ls(k), l, r, v);
    } else if (l > mid) {
      if (!rs(k)) rs(k) = ++cnt, e[rs(k)].l = mid + 1, e[rs(k)].r = e[k].r;
      ADD(rs(k), l, r, v);
    } else {
      if (!ls(k)) ls(k) = ++cnt, e[ls(k)].l = e[k].l, e[ls(k)].r = mid;
      if (!rs(k)) rs(k) = ++cnt, e[rs(k)].l = mid + 1, e[rs(k)].r = e[k].r;
      ADD(ls(k), l, mid, v);
      ADD(rs(k), mid + 1, r, v);
    }
    up(k);
  }
  long long Query(int k, int l, int r) {
    if (!k) return 0;
    if (e[k].l == l && e[k].r == r) return e[k].sum;
    down(k);
    int mid = e[k].l + e[k].r >> 1;
    if (r <= mid) {
      if (ls(k))
        return Query(ls(k), l, r);
      else
        return 0;
    } else if (l > mid) {
      if (rs(k))
        return Query(rs(k), l, r);
      else
        return 0;
    } else
      return Query(ls(k), l, mid) + Query(rs(k), mid + 1, r);
  }
  long long Query_max(int k, int l, int r) {
    if (!k) return 0;
    if (e[k].l == l && e[k].r == r) return e[k].mx;
    down(k);
    int mid = e[k].l + e[k].r >> 1;
    if (r <= mid) {
      if (ls(k))
        return Query_max(ls(k), l, r);
      else
        return 0;
    } else if (l > mid) {
      if (rs(k))
        return Query_max(rs(k), l, r);
      else
        return 0;
    } else
      return max(Query_max(ls(k), l, mid), Query_max(rs(k), mid + 1, r));
  }
};
signed main() {
  
  int n, p, q;
  cin >> n >> p >> q;
  XDS tr(2020202);
  for (int i = 1; i <= n; i++) {
    int a;
    cin >> a;
    tr.ADD(1, i, i, a);
  }
  int t;
  cin >> t;
  for (int i = 1; i <= t; i++) {
    int l, r, v;
    cin >> l >> r >> v;
    tr.ADD(1, l, r, v);
  }
  int ans = max(tr.Query_max(1, 1, n), p);
  if (ans >= q)
    cout << "3G win win!" << endl;
  else
    cout << "3G wanna win win" << endl;

  return 0;
}

E. 数字华容道

题目链接：
E. 数字华容道
大意：
判断n*m的数字华容道是否有解。
思路：
观察可知华容道是否有解与其逆序对数奇偶性有关。0的移动左右不改变除0外数字的逆序对数。上下移动如果列数是奇数则奇偶性不变，列数是偶数则奇偶性改变。再通过看0的位置与最下面一行的差值判断需要上下移动的次数。最后总结结论：m为奇数，逆序对为偶数有解；m为偶数，逆序对与移动次数奇偶性一致有解。求逆序对可以通过归并排序或者使用树状数组，此处采用的是归并排序。
ac代码：

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
#include <bits/stdc++.h>
using namespace std;
int a[1010][1010];
int one[1010101];
int tem[1010101];
int cnt = 0;


void merge(int l, int r) {
    int mid = (l + r) / 2;
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (one[i] <= one[j]) {
            tem[k++] = one[i++];
        } else {
            cnt += mid - i + 1;
            tem[k++] = one[j++];
        }
    }
    while (i <= mid) {
        tem[k++] = one[i++];
    }
    while (j <= r) {
        tem[k++] = one[j++];
    }
    for (int q = l; q <= r; q++) {
        one[q] = tem[q];
    }
}


void mergesort(int l, int r) {
    int mid = (l + r) / 2;
    if (l >= r) return;
    mergesort(l, mid);
    mergesort(mid + 1, r);
    merge(l, r);
}

int main() {
    int n, m;
    cin >> n >> m;
    int row;
    int times = 0;  


    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            if (a[i][j] != 0) {
                one[++times] = a[i][j];
            } else {
                row = i;
            }
        }
    }

    int d = n - row;  

    
    mergesort(1, times);

    
    if (m % 2 == 1) {
        d = 0;
    }

    
    if ((cnt + d) % 2 == 1) {
        cout << "NO" << endl;
    } else {
        cout << "YES" << endl;
    }

    return 0;
}

B. 1e9+7

题目链接：
B. 1e9+7
大意：
1e9+7除i（i<=p）所得商相同的数字为一类，求每类数字的个数，进行异或操作后输出结果。
思路：
对于每一类，如果可以找到最右端的值关于最左端的值的函数关系式，就能求出每类数字的个数和下一类最左端的值。从而解决了问题。
ac代码：

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

const int big=1e9+7;
signed main() {
  int t;
  cin >> t;
  while (t--) {
    int p;
    cin >> p;
    int x = 2;
    int ans = 1;
    while (big / (int)(big / x) <= p) {
      int y = big / (int)(big/ x);
      ans = ans ^ (y - x + 1);
      // if(x!=y)cout<<x<<" "<<y<<" "<<(big/x)<<" "<<(big/y)<<endl;
      x = y + 1;
    }
    if(x<=p)ans^=(p-x+1);
    cout<<ans<<endl;
  }

  return 0;
}

赛后补题

A. 帽子为什么尖尖的？

题目链接：
A. 帽子为什么尖尖的？
大意：
给定数组长度n(2e5),数组元素大小(1e9),q(2e5)次操作：增或删元素，查询在给定大小内元素之和，
思路：
1.离散化+树状数组
将数组元素大小离散化，再用树状数组单点修改或区间查询。
2.动态开点线段树
不是很会，只知道套模板。
ac代码

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;
#define int long long

class SZSZ{
	private:
    vector<int>tree;
    int N;
    public:
    SZSZ(int n=5e5){//<1e6
        tree=vector<int>(n+114);
        N=n+100;
    }
    #define lowbit(x) (x&(-x))

    void add(int x,int v){
        x++;
        for(int i=x;i<=N;i+=lowbit(i))tree[i]+=v;
    };
    int que(int x){
        x++;int sum=0;
        for(int i=x;i>0;i-=lowbit(i))sum+=tree[i];
        return sum;
    }
};
signed main() {
    int n,q;
    cin>>n;
    set<int>st;map<int,int>mp;
    vector<int>a(n);
    for(auto &now:a){
        cin>>now;
        st.insert(now);
    }
    cin>>q;
    vector<tuple<int,int,int>>Q(q);
    for(auto &[op,t1,t2]:Q){
        cin>>op;
        if(op==3)cin>>t1>>t2,st.insert(t1),st.insert(t1-1),st.insert(t2);
        else cin>>t1,st.insert(t1);
    }
    int tot=0;
    for(auto now:st)mp[now]=++tot;
    SZSZ tr(tot+10);
    for(auto now:a)tr.add(mp[now],now);
    for(auto [op,t1,t2]:Q){
        if(op==1)tr.add(mp[t1],t1);
        else if(op==2)tr.add(mp[t1],-t1);
        else cout<<tr.que(mp[t2])-tr.que(mp[t1-1])<<endl;
    }
    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
123
124
125
126
127
128
129
130
131
132
133
134
#include <bits/stdc++.h>
using namespace std;
#define int long long


#define int long long


class XDS {
 private:
  int cnt;
  struct as {
    long long l, r, sum, add, mx, son[2];
  };
  vector<as> e;
#define ls(k) e[k].son[0]


#define rs(k) e[k].son[1]


 public:
  XDS(int m = 2020202, int l = 1, int r = 1e9) {
    cnt = 1;
    e = vector<as>(m);
    e[1].l = l, e[1].r = r;
  }
  void up(int k) {
    e[k].sum = e[ls(k)].sum + e[rs(k)].sum;
    e[k].mx = max(e[ls(k)].mx, e[rs(k)].mx);
  }
  void down(int k) {
    if (e[k].add) {
      if (ls(k)) {
        e[ls(k)].add += e[k].add;
        e[ls(k)].sum += e[k].add * (e[ls(k)].r - e[ls(k)].l + 1);
        e[ls(k)].mx += e[k].add;
      }
      if (rs(k)) {
        e[rs(k)].add += e[k].add;
        e[rs(k)].sum += e[k].add * (e[rs(k)].r - e[rs(k)].l + 1);
        e[rs(k)].mx += e[k].add;
      }
      e[k].add = 0;
    }
  }
  void ADD(int k, int l, int r, int v) {
    // cout<<k<<" "<<l<<" "<<r<<" "<<v<<endl;
    if (e[k].l == l && e[k].r == r) {
      e[k].add += v;
      e[k].sum += v * (e[k].r - e[k].l + 1);
      e[k].mx += v;
      return;
    }
    down(k);
    int mid = e[k].l + e[k].r >> 1;
    if (r <= mid) {
      if (!ls(k)) ls(k) = ++cnt, e[ls(k)].l = e[k].l, e[ls(k)].r = mid;
      ADD(ls(k), l, r, v);
    } else if (l > mid) {
      if (!rs(k)) rs(k) = ++cnt, e[rs(k)].l = mid + 1, e[rs(k)].r = e[k].r;
      ADD(rs(k), l, r, v);
    } else {
      if (!ls(k)) ls(k) = ++cnt, e[ls(k)].l = e[k].l, e[ls(k)].r = mid;
      if (!rs(k)) rs(k) = ++cnt, e[rs(k)].l = mid + 1, e[rs(k)].r = e[k].r;
      ADD(ls(k), l, mid, v);
      ADD(rs(k), mid + 1, r, v);
    }
    up(k);
  }
  long long Query(int k, int l, int r) {
    if (!k) return 0;
    if (e[k].l == l && e[k].r == r) return e[k].sum;
    down(k);
    int mid = e[k].l + e[k].r >> 1;
    if (r <= mid) {
      if (ls(k))
        return Query(ls(k), l, r);
      else
        return 0;
    } else if (l > mid) {
      if (rs(k))
        return Query(rs(k), l, r);
      else
        return 0;
    } else
      return Query(ls(k), l, mid) + Query(rs(k), mid + 1, r);
  }
  long long Query_max(int k, int l, int r) {
    if (!k) return 0;
    if (e[k].l == l && e[k].r == r) return e[k].mx;
    down(k);
    int mid = e[k].l + e[k].r >> 1;
    if (r <= mid) {
      if (ls(k))
        return Query_max(ls(k), l, r);
      else
        return 0;
    } else if (l > mid) {
      if (rs(k))
        return Query_max(rs(k), l, r);
      else
        return 0;
    } else
      return max(Query_max(ls(k), l, mid), Query_max(rs(k), mid + 1, r));
  }
};
signed main() {
  XDS tr(2400000);
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    int m;
    cin >> m;
    tr.ADD(1, m, m, m);
  }
  int q;
  cin>>q;
  for(int i=1;i<=q;i++){
    int t1,t2,t3;
    cin>>t1;
    if(t1==1){
        cin>>t2;
        tr.ADD(1,t2,t2,t2);
    }else if(t1==2){
        cin>>t2;
        tr.ADD(1,t2,t2,-t2);
    }else {
        cin>>t2>>t3;
        cout<<tr.Query(1,t2,t3)<<endl;
    }
  }
  return 0;
}

剩下的题目选择了投降……