2022“杭电杯”中国大学生算法设计超级联赛（3）题解

1003 Cyber Language

QAQ 签到题~

1009 Package

wa了十发 ，栓Q

#include

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c>'9') { if (c == '-') f = -1; c = getchar(); }
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}

struct qwq {
    int l, r;
    int id;
    bool operator<(const qwq& b) const {
        return r == b.r ? l < b.l : r < b.r;
    }
};

void solve() {
    int k, n;
    //cin >> n >> k;
    n = read(); k = read();
    set<qwq> pq;
    vector<qwq> vq(n + 1);
    vector<pii> st;
    for (int i = 1; i <= n; i++) {
        //cin >> vq[i].l >> vq[i].r;
        vq[i].l = read(); vq[i].r = read();
        st.push_back({ vq[i].l, -i });
        st.push_back({ vq[i].r, i });
        vq[i].id = i;
    }
    sort(st.begin(), st.end());
    int ans = 0;
    for (auto it : st) {
        if (it.second < 0) pq.insert(vq[-it.second]);
        else if (vq[it.second].l != -1) {
            ans++;
            pq.erase(vq[it.second]);
            vq[it.second].l = -1;
            for (int i = 1; i < k && !pq.empty(); i++) {
                auto id = pq.begin()->id;
                vq[id].l = -1;
                pq.erase(pq.begin());
            }
        }
    }
    printf("%d\n", ans);
}

int main() {
    //ios::sync_with_stdio(false);
    //cin.tie(0); cout.tie(0);
    int T = 1;
    //cin >> T;
    T = read();
    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

1002 Boss Rush

状压dp

用 $dp[i].first$ 来记录攻击力
用 $dp[i].second$ 来记录时间

二分时间 判断dp过程中的取到的最大值是否能够到达 h

#include

using namespace std;

typedef long long ll;

ll read() {
    ll x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c>'9') { if (c == '-') f = -1; c = getchar(); }
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}

struct SK {
    int t, len;
    vector<ll> atk;
};
typedef pair<ll, int> pll;

bool check(vector<SK>& v, int mxt, ll h) {
    vector<pll> dp(1 << v.size());
    ll r = 0;
    for (int i = 1; i < (1 << v.size()); i++) {
        for (int j = 0; j < v.size(); j++) {
            if (i & (1 << j)) {
                pll x = dp[i ^ (1 << j)];
                int p = min(v[j].len,( mxt - x.second + 1));
                if (p < 0) continue;
                x.first += v[j].atk[p];
                x.second += v[j].t;
                if (x.first > dp[i].first) dp[i] = x;
                r = max(r, x.first);
                if (p == v[j].len) break;
            }
        }
    }
    return r >= h;
}

void solve() {
    int n; ll h;
    n = read();
    h = read();

   // cout << h << endl;
    vector<SK> v(n);
    for (int i = 0; i < n; i++) {
        v[i].t = read();
        v[i].len = read();
        v[i].atk.resize(v[i].len + 1);
        ll x;
        for (int j = 1; j <= v[i].len; j++) {
            x = read();
            v[i].atk[j] = v[i].atk[j - 1] + x;
        }
    }
    int l = 0, r = 2e6;
    int ans = -1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(v, mid, h)) {
            r = mid - 1;
            ans = mid;
        }
        else {
            l = mid + 1;
        }
    }
    printf("%d\n", ans);
}

int main() {
  //  ios::sync_with_stdio(false);
  //  cin.tie(0); cout.tie(0);
    int T = 1;
    T = read();
    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

1012 Two Permutations

计数dp

用 $dp[i][j].a$ 来表示前面用了多少个a序列 用 $dp[i][j].b$ 来表示前面用了多少个b数组，用 $dp[i][j].val$ 来表示构成这种方法会有几种方式
开一个动态 $map$ 来存储答案
再把 $map$ 的值赋值到 $dp$ 上面去

#include

using namespace std;

#define int long long
typedef long long ll;
typedef pair<int, int> pii;
int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c>'9') { if (c == '-') f = -1; c = getchar(); }
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}

const int mod = 998244353;
const int N = 3e5 + 10;

int a[N], b[N];
int c[N * 2];

struct node {
    int a, b;
    int val;
};

vector<node> dp[N * 2];

void solve() {
   
    int n = read();
    //cin >> n;
    for (int i = 1; i <= n; i++) a[i] = read();
    for (int i = 1; i <= n; i++) b[i] = read();
    for (int i = 1; i <= 2*n; i++) {
        c[i] = read();
    }
    for (int i = 0; i <= 2 * n; i++) dp[i].clear();
    dp[0].push_back({ 0,0,1 });
    for (int i = 1; i <= 2 * n; i++) {
        map<pair<int, int>, int> mp;
        for (int j = 0; j < dp[i - 1].size(); j++) {
            if (a[dp[i - 1][j].a + 1] == c[i]) {
                mp[{dp[i - 1][j].a+1, dp[i - 1][j].b}] += dp[i - 1][j].val;
                mp[{dp[i - 1][j].a+1, dp[i - 1][j].b }] %= mod;
            }
            if (b[dp[i - 1][j].b + 1] == c[i]) {
                mp[{dp[i - 1][j].a, dp[i - 1][j].b+1}] += dp[i - 1][j].val;
                mp[{dp[i - 1][j].a, dp[i - 1][j].b + 1}] %= mod;
            }
        }
        for (auto it : mp) dp[i].push_back({ it.first.first, it.first.second, it.second });
    }
    ll ans = 0;
    for (auto it : dp[2 * n]) ans = (ans + it.val) % mod;
    printf("%lld\n", ans);
}

signed main() {
    //ios::sync_with_stdio(false);
    //cin.tie(0); cout.tie(0);
    int T = 1;
    //cin >> T;
    T = read();
    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

1011 Taxi

kd树

(队友写的 bushi很懂

#include

using namespace std;

#define int long long

const int INF = 1e9+7;
const int N = 5e5+7;


namespace KD_Tree {
    struct Dot {
        int d[2], mn[2], mx[2], l, r, sz, sum, val;
        Dot() { l = r = 0; }
        Dot(int x, int y, int c) {
            d[0] = x;
            d[1] = y;
            val = c;
            l = r = sz = sum = 0;
        }
        int& operator[](int x) { return d[x]; }
    };
    int D, dcnt = 0, pt[N];
    Dot T[N];
    Dot p[N];
    bool operator<(Dot a, Dot b) { return a[D] < b[D]; }
    inline void umax(int& a, int b) {
        if (a < b) a = b;
    }
    inline void umin(int& a, int b) {
        if (a > b) a = b;
    }
    inline bool cmp(int x, int y) { return T[x][D] < T[y][D]; }
    inline void up(int x) {
        T[x].sz = T[T[x].l].sz + T[T[x].r].sz + 1;
        T[x].sum = max(T[T[x].l].sum, max(T[T[x].r].sum, T[x].val));
        T[x].mn[0] = T[x].mx[0] = T[x][0];
        T[x].mn[1] = T[x].mx[1] = T[x][1];
        if (T[x].l) {
            umax(T[x].mx[0], T[T[x].l].mx[0]);
            umin(T[x].mn[0], T[T[x].l].mn[0]);
            umax(T[x].mx[1], T[T[x].l].mx[1]);
            umin(T[x].mn[1], T[T[x].l].mn[1]);
        }
        if (T[x].r) {
            umax(T[x].mx[0], T[T[x].r].mx[0]);
            umin(T[x].mn[0], T[T[x].r].mn[0]);
            umax(T[x].mx[1], T[T[x].r].mx[1]);
            umin(T[x].mn[1], T[T[x].r].mn[1]);
        } 
    }
    // 离线建树时，只加点，不构树，最后build
    inline void AddDot(int x, int y, int c) {
        ++dcnt;
        pt[dcnt] = dcnt;
        p[dcnt][0] = x;
        p[dcnt][1] = y;
        p[dcnt].val = c;
    }
    // 曼哈顿距离估价函数
    inline int dist(int p1, int px, int py) {
        int dis = 0;
        if (px > T[p1].mn[0]) dis += abs(T[p1].mn[0] - px);
        if (px < T[p1].mx[0]) dis += abs(px - T[p1].mx[0]);
        if (py > T[p1].mn[1]) dis += abs(T[p1].mn[1] - py);
        if (py < T[p1].mx[1]) dis += abs(py - T[p1].mx[1]);
        return min(dis, T[p1].sum);
    }

    int ans = 0;
    inline void ask(int x, int px, int py) {
        int dl, dr, d0 = min(T[x].val, abs(T[x][0] - px) + abs(T[x][1] - py));
        if (d0 > ans) ans = d0;
        dl = T[x].l ? dist(T[x].l, px, py) : 0;
        dr = T[x].r ? dist(T[x].r, px, py) : 0;
        if (dl > dr) {
            if (dl > ans) ask(T[x].l, px, py);
            if (dr > ans) ask(T[x].r, px, py);
        } else {
            if (dr > ans) ask(T[x].r, px, py);
            if (dl > ans) ask(T[x].l, px, py);
        } 
    }

    int QueryMax(int x, int px, int py) {
        ans = 0;
        ask(x, px, py);
        return ans;
    }

    // 建树
    int build(int l, int r, int now) {
        int mid = (l + r) >> 1;
        D = now;
        nth_element(p + l, p + mid, p + r + 1);
        T[mid] = p[mid];
        for (int i = 0; i < 2; i++) T[mid].mn[i] = T[mid].mx[i] = T[mid][i];
        if (l < mid) T[mid].l = build(l, mid - 1, now ^ 1);
        if (r > mid) T[mid].r = build(mid + 1, r, now ^ 1);
        up(mid);
        return  mid;
    }
}


void solve() {
    KD_Tree::dcnt = 0;
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        KD_Tree::AddDot(x, y, w);
    }
    int root = KD_Tree::build(1, n, 0);
    while (q--) {
        int x, y;
        cin >> x >> y;
        cout << KD_Tree::QueryMax(root, x, y) << '\n';
    }
}
#undef int
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
   
    //freopen("1011.out", "w", stdout);
    //freopen("1011.in", "r", stdin);
    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
123
124
125
126
127
128
129
130
131
132
133