T1：
20分：状压DP或Dfs O(2^n)暴力
60分：发现答案为1e5级别，做0/1背包即可
100分：分析过程，由于要求最小的非幸运数，那么由于数的组成是连续的
那么模拟过程发现，能够延伸所能组成的数的集合的单位数为：1,2,4,11,22,44
进一步拓展发现第i个数为Pre[i - 1] + 1，因此若a[i] > Pre[i - 1] + 1，那么答案则为
Pre[i - 1] + 1，时间复杂度O(nlogn)（sort排序）
代码如下：
1 #include <bits/stdc++.h>
2 using namespace std;
3 #define I long long
4 #define C char
5 #define B bool
6 #define V void
7 #define D double
8 #define LL long long
9 #define UI unsigned int
10 #define UL unsigned long long
11 #define P pair<I,I>
12 #define MP make_pair
13 #define a first
14 #define b second
15 #define lowbit(x) (x & -x)
16 #define debug cout << "It's Ok Here !" << endl;
17 #define FP(x) freopen (#x,"r",stdin)
18 #define FC(x) freopen (#x,"w",stdout)
19 const I N = 1e5 + 3;
20 I n,a[N],Pre[N];
21 inline I read () {
22 I x(0),y(1); C z(getchar());
23 while (!isdigit(z)) { if (z == '-') y = -1; z = getchar(); }
24 while ( isdigit(z)) x = x * 10 + (z ^ 48), z = getchar();
25 return x * y;
26 }
27 inline V Max (I &a,I b) { a = a > b ? a : b; }
28 inline V Min (I &a,I b) { a = a < b ? a : b; }
29 inline I max (I a,I b) { return a > b ? a : b; }
30 inline I min (I a,I b) { return a < b ? a : b; }
31 inline V swap (I &a,I &b) { a ^= b, b ^= a, a ^= b; }
32 inline I abs (I a) { return a >= 0 ? a : -a; }
33 inline P operator + (const P &a,const P &b) {
34 return MP (a.a + b.a,a.b + b.b);
35 }
36 inline P operator - (const P &a,const P &b) {
37 return MP (a.a - b.a,a.b - b.b);
38 }
39
40 signed main () {
41 FP (math.in), FC (math.out);
42 n = read ();
43 for (I i(1);i <= n; ++ i)
44 a[i] = read ();
45 sort (a + 1,a + n + 1);
46 for (I i(1);i <= n; ++ i)
47 Pre[i] = Pre[i - 1] + a[i];
48 for (I i(1);i <= n; ++ i)
49 if (a[i] > Pre[i - 1] + 1)
50 printf ("%lld\n",Pre[i - 1] + 1), exit (0);
51 printf ("%lld\n",Pre[n] + 1), exit (0);
52 }
View Code
T2：
矩阵乘法，重新定义矩阵乘法为C[i][j] = $\prod$A[i][k]^B[k][j]，于是直接调配矩阵系数即可
需要注意的是，由于将幂乘转化为指数相加，那么在指数矩阵取模时需要根据费马定理对(mod - 1)取模
代码如下：
1 %:pragma GCC optimize (2)
2 #include <bits/stdc++.h>
3 using namespace std;
4 #define I long long
5 #define C char
6 #define B bool
7 #define V void
8 #define D double
9 #define LL long long
10 #define UI unsigned int
11 #define UL unsigned long long
12 #define P pair<I,I>
13 #define MP make_pair
14 #define a first
15 #define b second
16 #define lowbit(x) (x & -x)
17 #define debug cout << "It's Ok Here !" << endl;
18 #define FP(x) freopen (#x,"r",stdin)
19 #define FC(x) freopen (#x,"w",stdout)
20 const I N = 200, mod = 998244353;
21 I n,t,F[N],G[N][N];
22 inline I read () {
23 I x(0),y(1); C z(getchar());
24 while (!isdigit(z)) { if (z == '-') y = -1; z = getchar(); }
25 while ( isdigit(z)) x = x * 10 + (z ^ 48), z = getchar();
26 return x * y;
27 }
28 inline V Max (I &a,I b) { a = a > b ? a : b; }
29 inline V Min (I &a,I b) { a = a < b ? a : b; }
30 inline I max (I a,I b) { return a > b ? a : b; }
31 inline I min (I a,I b) { return a < b ? a : b; }
32 inline V swap (I &a,I &b) { a ^= b, b ^= a, a ^= b; }
33 inline I abs (I a) { return a >= 0 ? a : -a; }
34 inline P operator + (const P &a,const P &b) {
35 return MP (a.a + b.a,a.b + b.b);
36 }
37 inline P operator - (const P &a,const P &b) {
38 return MP (a.a - b.a,a.b - b.b);
39 }
40 inline I fp (I a,I b) {
41 if (a == 0 || a == 1) return a;
42 I ans (1);
43 for (; b ;b >>= 1, a = a * a % mod)
44 if (b & 1) ans = ans * a % mod;
45 return ans;
46 }
47 inline V Matrix_mul () {
48 I X[N];
49 fill (X,X + t,1);
50 for (I k(0);k < t; ++ k)
51 for (I j(0);j < t; ++ j)
52 X[j] = X[j] * fp (F[k],G[k][j]) % mod;
53 memcpy (F,X,sizeof F);
54 }
55 inline V Matrix_self () {
56 I X[N][N];
57 memset (X,0,sizeof X);
58 for (I i(0);i < t; ++ i)
59 for (I k(0);k < t; ++ k) if (G[i][k])
60 for (I j(0);j < t; ++ j) if (G[k][j])
61 (X[i][j] += G[i][k] * G[k][j] % (mod - 1)) %= (mod - 1);
62 memcpy (G,X,sizeof X);
63 }
64 signed main () {
65 FP (seq.in), FC (seq.out);
66 n = read (), t = read ();
67 for (I i(0);i < t; ++ i)
68 G[i][0] = read ();
69 for (I i(0);i < t; ++ i)
70 F[t - i - 1] = read ();
71 for (I i(0);i + 1 < t; ++ i)
72 G[i][i + 1] = 1;
73 if (n <= t) printf ("%lld\n",F[t - n]), exit (0);
74 I x (n - t);
75 for (; x ;x >>= 1, Matrix_self ())
76 if (x & 1) Matrix_mul ();
77 printf ("%lld\n",F[0]);
78 }
View Code
T3：
全源最短路，考虑在最短路过程中记录每个白点连向最短路的连边，最终在每个白点所有连边集合中取最小值即可
代码如下：
1 #include <bits/stdc++.h>
2 using namespace std;
3 #define I long long
4 #define C char
5 #define B bool
6 #define V void
7 #define LL long long
8 #define UI unsigned int
9 #define UL unsigned long long
10 #define P pair<I,I>
11 #define MP make_pair
12 #define a first
13 #define b second
14 #define lowbit(x) (x & -x)
15 #define debug cout << "It's Ok Here !" << endl;
16 #define FP(x) freopen (#x,"r",stdin)
17 #define FC(x) freopen (#x,"w",stdout)
18 const I N = 1e5 + 3;
19 B typ[N];
20 I n,m,d[N],pre[N],ans;
21 I tot,head[N],to[N << 2],nxt[N << 2],wgt[N << 2];
22 vector <I> rec[N];
23 inline I read () {
24 I x(0),y(1); C z(getchar());
25 while (!isdigit(z)) { if (z == '-') y = -1; z = getchar(); }
26 while ( isdigit(z)) x = x * 10 + (z ^ 48), z = getchar();
27 return x * y;
28 }
29 inline V Max (I &a,I b) { a = a > b ? a : b; }
30 inline V Min (I &a,I b) { a = a < b ? a : b; }
31 inline I max (I a,I b) { return a > b ? a : b; }
32 inline I min (I a,I b) { return a < b ? a : b; }
33 inline V swap (I &a,I &b) { a ^= b, b ^= a, a ^= b; }
34 inline I abs (I a) { return a >= 0 ? a : -a; }
35 inline P operator + (const P &a,const P &b) {
36 return MP (a.a + b.a,a.b + b.b);
37 }
38 inline P operator - (const P &a,const P &b) {
39 return MP (a.a - b.a,a.b - b.b);
40 }
41 inline V found (I z,I y,I x) {
42 to[++tot] = y, nxt[tot] = head[x], wgt[tot] = z, head[x] = tot;
43 to[++tot] = x, nxt[tot] = head[y], wgt[tot] = z, head[y] = tot;
44 }
45 inline V Dijkstra () {
46 priority_queue <P> q; B vis[N];
47 memset (vis,0,sizeof vis), memset (d,0x3f,sizeof d);
48 for (I i(1);i <= n; ++ i) if (typ[i])
49 q.push (MP (0,i)), d[i] = 0;
50 while (!q.empty ()) {
51 I x (q.top ().b); q.pop ();
52 if (vis[x]) continue; vis[x] = 1;
53 for (I i(head[x]),y(to[i]),z(wgt[i]); i ;i = nxt[i],y = to[i],z = wgt[i]) {
54 if (d[x] + z == d[y]) rec[y].push_back (z);
55 if (d[x] + z < d[y]) d[y] = d[x] + z, q.push (MP (-d[y],y)), rec[y].clear (), rec[y].push_back (z);
56 }
57 }
58 }
59 signed main () {
60 FP (minimum.in), FC (minimum.out);
61 n = read (), m = read ();
62 for (I i(1);i <= n; ++ i)
63 typ[i] = read ();
64 for (I i(1);i <= m; ++ i)
65 found (read (),read (),read ());
66 Dijkstra ();
67 for (I i(1);i <= n; ++ i) if (!typ[i]) {
68 if (rec[i].empty ()) puts ("impossible"), exit (0);
69 I MI (INT_MAX); for (auto x : rec[i]) Min (MI,x);
70 ans += MI;
71 }
72 printf ("%lld\n",ans);
73 }
View Code
T4：
状压DP，是状态划分类型，考虑定义f[i]表示只考虑i集合中所有元素的拓扑序方案数
那么对于(1 << j & i == 0)f[i | 1 << j] += f[i] * (1 << cnt)，其中j为非i集合中的点，cnt为
i集合中连向j点的边数，其意义为考虑将j点作为新集合的拓扑序最后一个，那么i集合对新集合
的贡献即为f[i] * (1 << cnt)，即任意删边
代码如下：
1 #include <bits/stdc++.h>
2 using namespace std;
3 #define I long long
4 #define C char
5 #define B bool
6 #define V void
7 #define D double
8 #define LL long long
9 #define UI unsigned int
10 #define UL unsigned long long
11 #define P pair<I,I>
12 #define MP make_pair
13 #define a first
14 #define b second
15 #define lowbit(x) (x & -x)
16 #define debug cout << "It's Ok Here !" << endl;
17 #define FP(x) freopen (#x,"r",stdin)
18 #define FC(x) freopen (#x,"w",stdout)
19 const I N = 22, mod = 998244353;
20 I n,m,ans,f[1 << N],s[N];
21 I tot,head[N],to[N*N],nxt[N*N];
22 inline I read () {
23 I x(0),y(1); C z(getchar());
24 while (!isdigit(z)) { if (z == '-') y = -1; z = getchar(); }
25 while ( isdigit(z)) x = x * 10 + (z ^ 48), z = getchar();
26 return x * y;
27 }
28 inline V Max (I &a,I b) { a = a > b ? a : b; }
29 inline V Min (I &a,I b) { a = a < b ? a : b; }
30 inline I max (I a,I b) { return a > b ? a : b; }
31 inline I min (I a,I b) { return a < b ? a : b; }
32 inline V swap (I &a,I &b) { a ^= b, b ^= a, a ^= b; }
33 inline I abs (I a) { return a >= 0 ? a : -a; }
34 inline P operator + (const P &a,const P &b) {
35 return MP (a.a + b.a,a.b + b.b);
36 }
37 inline P operator - (const P &a,const P &b) {
38 return MP (a.a - b.a,a.b - b.b);
39 }
40 inline V found (I y,I x) {
41 to[++tot] = y, nxt[tot] = head[x], head[x] = y, s[y] |= 1 << x;
42 }
43 signed main () {
44 FP (topology.in), FC (topology.out);
45 n = read (), m = read ();
46 for (I i(1);i <= m; ++ i)
47 found (read () - 1, read () - 1);
48 f[0] = 1;
49 for (I i(0);i < 1 << n; ++ i)
50 for (I j(0);j < n; ++ j) if ((1 << j & i) == 0) {
51 I cnt (__builtin_popcount (s[j] & i));
52 (f[i | 1 << j] += f[i] * (1 << cnt) % mod) %= mod;
53 }
54 printf ("%lld\n",f[(1 << n) - 1]);
55 }
View Code