2018.6.29 省选模拟赛

*注意:这套题目应版权方要求,不得公示题面。

从这里开始

  • Problem A 小D与电梯
  • Problem B 小D与田野
  • Problem C 小D与函数

Problem A 小D与电梯

题目大意

  假设电梯在0层,容量无限大。给定$n$个人的到达时间和要去的楼层。电梯上下一层楼花费的时间为1,电梯开关门、乘客上下的耗时不计,电梯可以停留在某一层楼。问将所有人送达到目的地,并让电梯回到0层的最少耗时。

  先按到达时间将所有人排序。显然,每次电梯运输的人是一段连续的区间中的人。

  用$f[i]$表示将前$i$个人送到目的地,并且电梯回到0层的最少耗时。

  转移方程显然:$f[i] = \min\left \{ \max(f[j], arrive[i]) + 2 \times max_{j < k \leqslant i}floor[k] \right \}$。

性质1 $f[i]\leqslant f[i + 1]$。

  将阶段$i + 1$的策略去掉第$i + 1$个人,作用于阶段$i$。

  因此,可以二分出一个分界点,使得前一部分取$arrive[i]$,另一部分取$f[j]$。

  对于前一部分,根据后面半个式子随$j$减小而不下降可以知道,取分界点的时候最优。

  对于后一部分,考虑使用一个单调栈维护走的楼层,用线段树维护动态规划的转移。必要时进行修改。

  总时间复杂度$O(n\log n)$。

  考场上很好玩的是,前一部分写错了二分判断条件(多打了个‘=‘),然后mcfx坑爹的subtask评测,小数据的subtask没有过,大数据直接skip掉。喜闻乐见A题爆零。测完后,$n$小于等于5000的数据用$O(n^2)$的动态规划,剩下的部分线段树,然后就AC。内心有句mmp。

Code

  1 #include <algorithm>
  2 #include <iostream>
  3 #include <cassert>
  4 #include <cstdlib>
  5 #include <cstdio>
  6 #ifndef WIN32
  7 #define Auto "%lld"
  8 #else
  9 #define Auto "%I64d"
 10 #endif
 11 using namespace std;
 12 typedef bool boolean;
 13 #define pii pair<int, int>
 14 #define fi first
 15 #define sc second
 16 #define ll long long
 17
 18 const signed ll llf = (signed ll) (~0ull >> 1);
 19 const int N = 1e6 + 5;
 20
 21 typedef class SegTreeNode {
 22     public:
 23         ll val, lazy;
 24         SegTreeNode *l, *r;
 25
 26         SegTreeNode():val(0), lazy(0), l(NULL), r(NULL) {    }
 27
 28         void pushUp() {
 29             val = min(l->val, r->val);
 30         }
 31
 32         void pushDown() {
 33             l->val += lazy, r->val += lazy;
 34             l->lazy += lazy, r->lazy += lazy;
 35             lazy= 0;
 36         }
 37 }SegTreeNode;
 38
 39 SegTreeNode pool[4 * N];
 40 SegTreeNode *top = pool;
 41
 42 SegTreeNode* newnode() {
 43     return top++;
 44 }
 45
 46 typedef class SegTree {
 47     public:
 48         int n;
 49         SegTreeNode* rt;
 50
 51         SegTree() {    }
 52         SegTree(int n):n(n) {
 53             build(rt, 1, n);
 54         }
 55
 56         void build(SegTreeNode* &p, int l, int r) {
 57             p = newnode();
 58             if (l == r)    return ;
 59             int mid = (l + r) >> 1;
 60             build(p->l, l, mid);
 61             build(p->r, mid + 1, r);
 62         }
 63
 64         void update(SegTreeNode *p, int l, int r, int ql, int qr, ll val) {
 65             if (l == ql && r == qr) {
 66                 p->val += val, p->lazy += val;
 67                 return ;
 68             }
 69             if (p->lazy)    p->pushDown();
 70             int mid = (l + r) >> 1;
 71             if (qr <= mid)
 72                 update(p->l, l, mid, ql, qr, val);
 73             else if (ql > mid)
 74                 update(p->r, mid + 1, r, ql, qr, val);
 75             else {
 76                 update(p->l, l, mid, ql, mid, val);
 77                 update(p->r, mid + 1, r, mid + 1, qr, val);
 78             }
 79             p->pushUp();
 80         }
 81
 82         ll query(SegTreeNode *p , int l, int r, int ql, int qr) {
 83             if (l == ql && r == qr)
 84                 return p->val;
 85             if (p->lazy)    p->pushDown();
 86             int mid = (l + r) >> 1;
 87             if (qr <= mid)
 88                 return query(p->l, l, mid, ql, qr);
 89             if (ql > mid)
 90                 return query(p->r, mid + 1, r, ql, qr);
 91             ll a, b;
 92             a = query(p->l, l, mid, ql, mid);
 93             b = query(p->r, mid + 1, r, mid + 1, qr);
 94             return (a < b) ? (a) : (b);
 95         }
 96
 97         void update(int l, int r, ll val) {
 98             //            cerr << "[" << l << ", " << r << "] added " << val << endl;
 99             update(rt, 1, n, l, r, val);
100         }
101
102         ll query(int l, int r) {
103             return query(rt, 1, n, l, r);
104         }
105 }SegTree;
106
107 int n, tp = -1;
108 ll f[N];
109 pii ps[N];
110 SegTree st;
111 pii pst[N];
112
113 inline void init() {
114     scanf("%d", &n);
115     for (int i = 1; i <= n; i++)
116         scanf("%d%d", &ps[i].fi, &ps[i].sc);
117 }
118
119 inline void solve() {
120     ps[0].fi = ps[0].sc = 0;
121     sort(ps + 1, ps + n + 1);
122     f[0] = 0, st = SegTree(n + 1);
123     for (int i = 1, l, r, di, mid; i <= n; i++) {
124         l = 0, r = i - 1;
125         while (l <= r) {
126             mid = (l + r) >> 1;
127             if (f[mid] <= ps[i].fi)
128                 l = mid + 1;
129             else
130                 r = mid - 1;
131         }
132         di = l - 1;
133         while (~tp && pst[tp].fi < ps[i].sc) {
134             st.update((tp) ? (pst[tp - 1].sc + 1) : (1), pst[tp].sc, (ps[i].sc - pst[tp].fi) * 2ll);
135             tp--;
136         }
137         pst[++tp] = pii(ps[i].sc, i);
138         st.update(i, i, ps[i].sc * 2ll);
139         l = 0, r = tp;
140         while (l <= r) {
141             mid = (l + r) >> 1;
142             if (pst[mid].sc > di)
143                 r = mid - 1;
144             else
145                 l = mid + 1;
146         }
147         f[i] = ps[i].fi + pst[r + 1].fi * 2ll;
148 //        cerr << "A " << f[i] << " " << pst[r + 1].fi << " " << pst[r + 1].sc << endl;
149         //        cerr <<"mid: " << di << " f: " << f[i] << " " << pst[r + 1].fi << endl;
150         if (di < i - 1) {
151             ll cmp = st.query(di + 2, i);
152             f[i] = min(f[i], cmp);
153         }
154         st.update(i + 1, i + 1, f[i]);
155 //        cerr << f[i] << endl;
156     }
157     printf(Auto, f[n]);
158 }
159
160 int main() {
161     init();
162     solve();
163     return 0;
164 }

Problem A

Problem B 小D与田野

题目大意

  给定一个有向图的邻接矩阵$G$,其中$G_{i, j}$表示从$i$到$j$的有向边的数量。多次询问从$u$到$v$所有长度不超过$k - 1$的路径的代价和除以998244353的余数。定义一条长度为$L$的路径的代价为$L^{T}$。一条路的路径长度定义为它经过有向边的数量。

  题目等价于求出$G + 2^{T}G^{2} + 3^{T}G^{3} + \cdots + (k - 1)^{T}G^{k - 1}$。

  我们知道当$T = 0$的时候,可以用简单的分治水掉。

  然后开始思考$T > 1$的时候。

引理1 若$n, k$均为正整数,则$n^{k}=\sum_{i = 1}^{n}S_{k}^{i}\times i!\times C_{n}^{i}$。其中$S_{k}^{i}表示第二类Stirling数$。

  证明 考虑$n^{k}$的组合意义:把$k$个不同的球放入$n$个不同的盒子中的方案数。

      $S_{k}^{i}$的组合意义是将$k$个不同的球放入$i$个相同的盒子中,并且每个盒子非空的方案数。那么等号右边等价于枚举恰好有多少个不同盒子是非空的,然后将$k$个球放入其中。显然它们是等价的。

  又因为,当$n < k$的时候$S_{n}^{k} = 0$,因此,需要求出的等价于$\sum_{i=1}^{n}\sum_{j = 0}^{T}S_{T}^{j}j! C_{i}^{j}G^{i}=\sum_{j = 0}^{T}S_{T}^{j}j!\sum_{i = 1}^{n} C_{i}^{j}G^{i}$。然后求出当$j = 0, 1, 2, \cdots, T$时,后面的和。继续考虑分治,假设我已经求出了当$1\leqslant i\leqslant mid$的时候的$T + 1$个和。为了求出后面部分的和,考虑使用下面这个结论:

引理2(范德蒙卷积) $C_{n + m} ^ {k} = \sum_{i = 0}^{k}C_{n}^{i}C_{m}^{k - i}$

  证明 这里只介绍组合意义的证明。

  考虑$n + m$个物品中选出$k$个物品,一定从其中$n$个物品中选出了$i$个,然后从另外$m$个物品中选出了$k - i$个物品。式子中枚举了所有可能的$i$,因此等式成立。

  现在假设要求计算的前$r$个的和,中的$r$是偶数。因为如果它是奇数,可以手动补上最后没有被计算的一项。于是有:

$\sum_{i = mid + 1}^{r}C_{i}^{j}G^{i}\\=G^{mid}\sum_{i=1}^{mid}C_{i + mid}^{j}G^{i}\\=G^{mid}\sum_{i=1}^{mid}\sum_{k = 0}^{j}C_{i}^{k}C_{mid}^{j - k}G^{i}\\=G^{mid}\sum_{k = 0}^{j}C_{mid}^{j - k}\left(\sum_{i = 1}^{mid}C_{i}^{k}G^{i} \right )$

  最终式子括号内的是已经计算出来的内容。对于$G^{mid}$可以随着分治一起计算。

  因此总时间复杂度为$O(n^{3}\log K + T^{2}n^{2}\log K)$。感谢Joker提供此做法,完爆标程$O(n^{3}T\log K)$。

Code

  1 #include <iostream>
  2 #include <cstdlib>
  3 #include <cstdio>
  4 using namespace std;
  5 typedef bool boolean;
  6
  7 const int N = 73, M = 998244353;
  8 int n, k, q, T;
  9
 10 void exgcd(int a, int b, int& x, int& y) {
 11     if (!b)
 12         x = 1, y = 0;
 13     else {
 14         exgcd(b, a % b, y, x);
 15         y -= (a / b) * x;
 16     }
 17 }
 18
 19 int inv(int a, int n) {
 20     int x, y;
 21     exgcd(a, n, x, y);
 22     return (x < 0) ? (x + n) : (x);
 23 }
 24
 25 typedef class Matrix {
 26     public:
 27         int ar[N][N];
 28
 29         Matrix operator * (Matrix b) {
 30             Matrix rt;
 31             for (int i = 1; i <= n; i++)
 32                 for (int j = 1; j <= n; j++) {
 33                     rt[i][j] = 0;
 34                     for (int k = 1; k <= n; k++)
 35                         rt[i][j] = (rt[i][j] + ar[i][k] * 1ll * b[k][j]) % M;
 36                 }
 37             return rt;
 38         }
 39
 40         Matrix operator + (Matrix b) {
 41             Matrix rt;
 42             for (int i = 1; i <= n; i++)
 43                 for (int j = 1; j <= n; j++)
 44                     rt[i][j] = (ar[i][j] + b[i][j]) % M;
 45             return rt;
 46         }
 47
 48         Matrix operator * (int b) {
 49             Matrix rt;
 50             for (int i = 1; i <= n; i++)
 51                 for (int j = 1; j <= n; j++)
 52                     rt[i][j] = (ar[i][j] * 1ll * b) % M;
 53            return rt;
 54         }
 55
 56         int* operator [] (int pos) {
 57             return ar[pos];
 58         }
 59
 60         void debugOut() {
 61             for (int i = 1; i <= n; i++, cerr << endl)
 62                 for (int j = 1; j <= n; j++)
 63                     cerr << ar[i][j] << " ";
 64         }
 65 }Matrix;
 66
 67 Matrix g;
 68
 69 inline void init() {
 70     scanf("%d%d%d%d", &n, &k, &q, &T);
 71     for (int i = 1; i <= n; i++)
 72         for (int j = 1; j <= n; j++)
 73             scanf("%d", g[i] + j);
 74 }
 75
 76 Matrix pa;
 77 Matrix ms[22][6];
 78 Matrix* dividing(int dep, int n) {
 79     Matrix *rt = ms[dep];
 80     if (n == 1) {
 81         pa = g, rt[0] = rt[1] = g;
 82         for (int i = 2; i <= T; i++)
 83             rt[i] = g * 0;
 84         return rt;
 85     }
 86     int mid = n >> 1;
 87     dividing(dep + 1, mid);
 88     Matrix *ar = ms[dep + 1];
 89     rt[0] = ar[0] * pa + ar[0];
 90     int Cs[T + 1], C = 1;
 91     Cs[0] = 1;
 92     for (int i = 1; i <= T; i++)
 93         Cs[i] = (Cs[i - 1] * 1ll * (mid + 1 - i) % M) * 1ll * inv(i, M) % M;
 94     for (int k = 1; k <= T; k++) {
 95         rt[k] = g * 0;
 96         for (int j = 0; j <= k; j++)
 97             rt[k] = rt[k] + ar[j] * Cs[k - j];
 98         rt[k] = rt[k] * pa + ar[k];
 99     }
100     pa = pa * pa;
101     if (n & 1) {
102         pa = pa * g;
103         rt[0] = rt[0] + pa;
104         for (int i = 1; i <= T; i++) {
105             C = (C * 1ll * (n + 1 - i) % M) * 1ll * inv(i, M) % M;
106             rt[i] = rt[i] + pa * C;
107         }
108     }
109     return rt;
110 }
111
112 const int S[6][6] = {{1}, {0, 1}, {0, 1, 2}, {0, 1, 6, 6}, {0, 1, 14, 36, 24}, {0, 1, 30, 150, 240, 120}};
113 Matrix res;
114
115 inline void solve() {
116     Matrix* rts = dividing(0, k - 1);
117     int u, v;
118     res = g * 0;
119     for (int i = 0; i <= T; i++)
120         res = res + rts[i] * S[T][i];
121     while (q--) {
122         scanf("%d%d", &u, &v);
123         printf("%d\n", res[u][v] + (u == v && T == 0));
124     }
125 }
126
127 int main() {
128     init();
129     solve();
130     return 0;
131 }

Problem B

Problem C 小D与函数

题目大意

  设$F_{k}(n) = \sum_{i = 1}^{n}i^{k}, G_{k}(n) = \sum_{i = 1}^{n}F_{k}(n), H_{k}(n) = \sum_{i = 0}^{n}G(A + i\cdot d)$。给定常数$k,n,A,d,p$,分别求出$F_{k}(n), G_{k}(n), H_{k}(n)$除以$p$的余数,保证$p$是一个质数。

  根据差分分别证得三个函数是关于$n$的$k + 1, k + 2, k + 3$次多项式。

  然后逐差法水过。时间复杂度$O(k^{2}T)$。

Code

 1 #include <iostream>
 2 #include <cstdlib>
 3 #include <cstdio>
 4 using namespace std;
 5 typedef bool boolean;
 6
 7 #define ll long long
 8 const int K = 1015;
 9
10 void exgcd(int a, int b, int& d, int& x, int& y) {
11     if (!b)
12         d = a, x = 1, y = 0;
13     else {
14         exgcd(b, a % b, d, y, x);
15         y -= (a / b) * x;
16     }
17 }
18
19 int inv(int a, int n) {
20     int d, x, y;
21     exgcd(a, n, d, x, y);
22     return (x < 0) ? (x + n) : (x);
23 }
24
25 int qpow(int a, int pos, int p) {
26     int pa = a, rt = 1;
27     for ( ; pos; pos >>= 1, pa = pa * 1ll * pa % p)
28         if (pos & 1)
29             rt = rt * 1ll * pa % p;
30     return rt;
31 }
32
33 int T;
34 int k, n, A, d, p;
35
36 inline void init() {
37     scanf("%d%d%d%d%d", &k, &n, &A, &d, &p);
38 }
39
40 int ds[K][K];
41 int cs[K], ncs[K];
42
43 void getDelta(int *cs, int k) {
44     for (int i = 1; i <= k; i++)
45         for (int j = 0; j <= k - i; j++)
46             ds[i][j] = (ds[i - 1][j + 1] * 1ll - ds[i - 1][j] + p) % p;
47     for (int i = 0; i <= k; i++)
48         cs[i] = ds[i][0];
49 }
50
51 int invs[K];
52
53 void prepare() {
54     for (int i = 1; i <= k + 10; i++)
55         invs[i] = inv(i, p);
56 }
57
58 int G(ll n) {
59     int pn = n % p;
60     int C = ((pn + 2) * 1ll * (pn + 1) / 2) % p, res = C * 1ll * cs[0] % p;
61     for (int i = 1; i <= k; i++) {
62         C = (C * 1ll * ((pn + 1ll - i + p) % p) % p) * invs[i + 2] % p;
63         res = (res + C * 1ll * cs[i]) % p;
64     }
65     return res;
66 }
67
68 inline void solve() {
69     ds[0][0] = 0;
70     for (int i = 1; i <= k; i++)
71         ds[0][i] = qpow(i, k, p);
72     getDelta(cs, k);
73     int C = n + 1, res = C * 1ll * cs[0] % p, ans;
74     for (int i = 1; i <= k; i++) {
75         C = (C * 1ll * (n + 1 - i) % p) * invs[i + 1] % p;
76         res = (res + C * 1ll * cs[i]) % p;
77     }
78     for (int i = 0; i <= k + 8; i++)
79         ds[0][i] = G(A + d * 1ll * i);
80     getDelta(ncs, k + 8);
81     C = n + 1, ans = C * 1ll * ncs[0] % p;
82     for (int i = 1; i <= k + 8; i++) {
83         C = (C * 1ll * (n + 1 - i) % p) * invs[i + 1] % p;
84         ans = (ans + C * 1ll * ncs[i]) % p;
85     }
86     printf("%d %d %d\n", res, G(n), ans);
87 }
88
89 int main() {
90     scanf("%d", &T);
91     while (T--) {
92         init();
93         prepare();
94         solve();
95     }
96     return 0;
97 }

Problem C

原文地址:https://www.cnblogs.com/yyf0309/p/9248156.html

时间: 06-30