A. digits2
solved at 00:47(+1)
签到题，将\(n\)输出\(n\)次即可，不知道队友在想什么。。。 ## B. generator 1
upsolved
矩阵快速幂，只是次数非常高
用十进制快速幂就好了，居然没想出来。。。
C. generator 2
upsolved
BSGS,需要改块的大小使得总复杂度更低
E. independent set 1
upsolved
有一张\(n(1<=n<=26)\)个点的图,问每个子图的最大独立集的和是多少
\(2^n\)状压dp, 设\(dp[i]\)表示点状态是\(i\)的最大独立集大小，设\(x\)是\(i\)最低位的\(1\)（这样容易转移），则要么不包含这个\(1\)，那就是\(dp[i-(1<<x)]\),要么包含这个\(1\),那就是\(1+dp[i-(1<<x)-(i\&G[x])]\),其中\(G[x]\)表示\(x\)的邻接点的状压集合，二者取最大值就好了，因为内存限制，\(dp\)数组需要用\(char\)类型
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include <bits/stdc++.h>
using namespace std;
char f[1 << 26];
int g[26], n, m, x, y, ans;
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; ++i) {
scanf("%d%d", &x, &y);
g[x] |= 1 << y;
g[y] |= 1 << x;
}
f[0] = 0;
for(int i = 1; i < (1 << n); ++i) {
int x = __builtin_ffs(i) - 1;
f[i] = max((int)f[i ^ (1 << x)], 1 + f[(i ^ (1 << x)) - (i & g[x])]);
ans += f[i];
}
printf("%d\n", ans);
return 0;
}
|
F. maximum clique 1
upsolved
一张\(n(1<=n<=5000)\)个的图，每个点有点权，点权两两不同，两个点右边当且仅当它们的点权的二进制位有至少两位不同，求最大团并输出一个方案
考虑其补图，显然补图两点有边当且仅当有一个二进制位不同，显然是一张二分图，求最大独立集即可
G. subsequence 1
solved at 01:19
两个数字字符串\(s\), \(t\), 长度不超过\(3000\)，求\(s\)不含前导\(0\)的子串作为数字比\(t\)大的方案数
如果一个没有前导\(0\)的子串比\(t\)长，那肯定比\(t\)大，组合数算出来
接下来考虑子串和\(t\)一样长，设\(dp[i][j]\)表示考虑\(s\)的前\(i\)位，已经选了\(j\)位，并且已经比\(t\)的前\(j\)位大的方案数，\(dp2[i][j]\)表示相等的方案数，转移方程可以很容易地推出来（见代码），\(dp[n][m]\)就是长度相等时的方案数
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
| #include <bits/stdc++.h>
using namespace std;
const int N = 3010, mod = 998244353;
int fac[N], invfac[N], ans, T, n, m;
int qp(int a, int n) {
int res = 1;
while(n) {
if(n & 1)
res = 1LL * res * a % mod;
a = 1LL * a * a % mod;
n >>= 1;
}
return res;
}
void init() {
fac[0] = invfac[0] = 1;
for(int i = 1; i < N; ++i) {
fac[i] = 1LL * fac[i - 1] * i % mod;
invfac[i] = qp(fac[i], mod - 2);
}
}
int C(int n, int m) {
return 1LL * fac[n] * invfac[n - m] % mod * invfac[m] % mod;
}
int dp[N][N], dp2[N][N];
char s[N], t[N];
int main() {
init();
scanf("%d", &T);
while(T--) {
scanf("%d%d%s%s", &n, &m, s + 1, t + 1);
ans = 0;
for(int i = 0; i <= n; ++i) {
for(int j = 0; j <= m; ++j) dp[i][j] = dp2[i][j] = 0;
dp2[i][0] = 1;
}
for(int i = 1; i <= n; ++i) {
if(s[i] == '0') continue;
for(int j = n - i; j >= m; --j) {
ans = (ans + C(n - i, j)) % mod;
}
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % mod;;
if(s[i] > t[j]) {
dp[i][j] = (dp[i][j] + dp2[i - 1][j - 1]) % mod;
}
dp2[i][j] = dp2[i - 1][j];
if(s[i] == t[j])
dp2[i][j] = (dp2[i][j] + dp2[i - 1][j - 1]) % mod;
}
}
ans = (ans + dp[n][m]) % mod;
printf("%d\n", ans);
}
return 0;
}
|
H. subsequence 2
solved at 02:46
长为\(n(1<=n<=10000)\)的字符串，仅有前\(m(2<=m<=10)\)个小写字母组成，然后给你这\(m*(m-1)/2\)个字符串，表示原字符串只含两种字符的子串，比如说\(abc\)会给你\(ab,bc,ac\)这三个子串，请你构造出一种原字符串
一眼望过去就是一个拓扑排序，比赛的时候写了个线段树优化建图。。。其实只要建相邻字母的有向边就行了
I. three points 1
upsolved
队友做的，给你一个矩形区域和一个矩形内三角形的三边长度，让你输出这个三角形的顶点坐标，队友说把最长边的一个顶点设在矩形顶点，另一个顶点放在矩形的边上，看第三个点是否合法就好了