题目#

牛客小白赛15

题解#

E. 希望#

希望是什么，希望是我们这个时代最珍贵的东西。

直接用一颗线段树维护区间最小值就可以了。

然后在做一个背包。

H.数据结构题#

一个很神奇的思路。

我们将每一个出现x的位置，放进G[x]中，然后查找第一个比r大的位置，和第一个大于定于l的位置，然后这两个位置做差就可以得到x在这段区间中的出现次数了。

代码#

E. 希望#

1
/*---------------------------------
2

3
 @Author:   Dicer
4
 @DateTime: 2019-06-16 11:54:32
5

6
---------------------------------*/
7

8
#include <bits/stdc++.h>
9
using namespace std;
10
typedef long long ll;
11
typedef pair<int, int> pii;
12
inline ll qpow(ll a,ll b,ll mod){ll res=1;while(b){if(b&1)res = (res*a)%mod;a=(a*a)%mod;b>>=1;}return res;}
13
const double eps = 1e-8;
14
const int INF = 0x3f3f3f3f;
15
const int mod = 1e9+7;
16
const int MAXN = 2e5 + 7;
17

18
struct node{
19
    int l, r;
20
    int mid(){return (l+r)>>1;}
21
    int val;
22
}s[MAXN<<1];
23
ll a[MAXN], b[MAXN], dp[MAXN];
24
void build(int l, int r, int x){
25
    s[x].l = l; s[x].r = r; s[x].val = 500;
26
    int mid = (l+r)>>1;
27
    if(l == r)  return;
28
    build(l, mid, x<<1);
29
    build(mid+1, r, x<<1|1);
30
}
31
inline void upd(int l, int r, int x, int v){
32
    // cout << l << ' ' << r << ' ' << s[x].l << ' ' << s[x].r << ' ' << v << endl;
33
    if(s[x].l >= l && s[x].r <= r){
34
        s[x].val = min(s[x].val, v);
35
        return;
36
    }
37
    int mid = s[x].mid();
38
    if(r > mid) upd(l, r, x<<1|1, v);
39
    if(l <= mid) upd(l, r, x<<1, v);
40
}
41
inline void pushdown(int x){
42
    if(s[x].l == s[x].r){
43
        a[s[x].l] = s[x].val;
44
        return;
45
    }
46
    s[x<<1].val = min(s[x<<1].val, s[x].val);
47
    s[x<<1|1].val = min(s[x<<1|1].val, s[x].val);
48
    pushdown(x<<1);
49
    pushdown(x<<1|1);
50
}
51
int main(int argc, char const *argv[])
52
{
53
    #ifndef ONLINE_JUDGE
54
        freopen("in.txt", "r", stdin);
55
        freopen("out.txt", "w", stdout);
56
    #endif
57

58
    int n, k, m;
59
    cin >> n >> k >> m;
60
    for(int i = 1; i <= n; ++i) cin >> b[i];
61
    build(1, n, 1);
62
    int l, r; ll c;
63
    for(int i = 1; i <= m; ++i){
64
        cin >> l >> r >> c;
65
        upd(l, r, 1, c);
66
    }
67
    pushdown(1);
68
    // for(int i = 1; i <= n; ++i) cout << a[i] << ' ';
69
    // cout << endl;
70
    //dp
71
  ll sum = 0;
72
    for(int i = 1; i <= n; ++i){
73
      sum += b[i];
74
      if(b[i] >= 0)  continue;
75
      for(int j = k; j >= a[i]; --j){
76
        dp[j] = max(dp[j], dp[j-a[i]] - b[i]);
77
      }
78
    }
79
    cout << sum+dp[k] << endl;
80
    return 0;
81
}

H.数据结构题#

1
/*---------------------------------
2

3
 @Author:   Dicer
4
 @DateTime: 2019-06-16 01:55:25
5

6
---------------------------------*/
7

8
#include <bits/stdc++.h>
9
using namespace std;
10
typedef long long ll;
11
typedef pair<int, int> pii;
12
inline ll qpow(ll a,ll b,ll mod){ll res=1;while(b){if(b&1)res = (res*a)%mod;a=(a*a)%mod;b>>=1;}return res;}
13
const double eps = 1e-8;
14
const int INF = 0x3f3f3f3f;
15
const int mod = 20180623;
16
const int MAXN = 2e5 + 7;
17

18
int a[MAXN];
19
vector<int> G[MAXN];
20
int main(int argc, char const *argv[])
21
{
22
    #ifndef ONLINE_JUDGE
23
        freopen("in.txt", "r", stdin);
24
        freopen("out.txt", "w", stdout);
25
    #endif
26

27
    int n, m;
28
    cin >> n >> m;
29
    for(int i = 1; i <= n; ++i){
30
        cin >> a[i];
31
        G[a[i]].push_back(i);
32
    }
33
    ll x, a, b, l1, l2, r1, r2;
34
    for(int i = 1; i <= m; ++i){
35
        cin >> l1 >> r1 >> l2 >> r2 >> x;
36
        if(l1 > r1) swap(l1, r1);
37
        if(l2 > r2) swap(l2, r2);
38
        a = upper_bound(G[x].begin(), G[x].end(), r1) - lower_bound(G[x].begin(), G[x].end(), l1);
39
        b = upper_bound(G[x].begin(), G[x].end(), r2) - lower_bound(G[x].begin(), G[x].end(), l2);
40
        cout << a << endl;
41
        cout << b << endl;
42
        cout << (a%mod)*(b%mod)%mod << endl;
43
    }
44
    return 0;
45
}