2019 Multi-University Training Contest 5
补题链接：2019 Multi-University Training Contest 5
罚时爆炸 自闭场
题意：
给定一个整数 $C$ 和 $N$ 组 $a_i,b_i$，求 $∑_{i=1}^N|a_i\cdot x + b_i| = C$ 的所有解，如果有无穷多个解就输出 -1.
思路 分类讨论
分类讨论去绝对值。根据 $b_i / a_i$ 排序，可得各段区间：$[-b_0/a_0, ∞), [-b_1/a_1, -b_0/a_0), [-b_2/a_2, -b_1/a_1), … ,[-b_n/a_n, -b_{n-1}/a_{n-1}), [∞, -b_n/a_n)$ 设 $suma = \sum_{i=1}^Na_i, sumb = \sum_{i=1}^Nb_i$，依次让 $a_ix+b_i$ 变成 $-a_ix-b_i$，也就是 $suma - 2a_i, sumb-2b_i$，求出 $x_i = \frac{c - sumb}{suma}$ 并判断是否在区间内。无穷解的情况：$suma = 0, sumb = c$。
感谢杭电没有卡 $double$。
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 #include <cstdio> #include <iostream> #include <cmath> #include <vector> #include <algorithm> using namespace std ;const int maxn = 1e5 + 10 ;typedef long long ll;struct Coefficient { ll a, b; } co[maxn]; int cmp (Coefficient c1, Coefficient c2) return c1.b * 1.0 / c1.a < c2.b * 1.0 / c2.a; } vector <Coefficient> ans;ll gcd (ll a, ll b) { return b == 0 ? a: gcd(b, a % b); } int main () int T; cin >> T; while (T--) { ans.clear(); int n; ll c; scanf ("%d%lld" , &n, &c); ll suma = 0 , sumb = 0 ; for (int i = 1 ; i <= n; ++i) { scanf ("%lld%lld" , &co[i].a, &co[i].b); suma += co[i].a; sumb += co[i].b; } sort(co + 1 , co + n + 1 , cmp); Coefficient t; t.a = suma, t.b = sumb; if ((c - sumb) * 1.0 / suma >= -co[1 ].b * 1.0 / co[1 ].a) { t.b = c - t.b; ans.push_back(t); } int flag = 1 ; for (int i = 1 ; i <= n; ++i) { suma -= co[i].a * 2 ; sumb -= co[i].b * 2 ; t.a = suma; t.b = sumb; if (!suma) { if (sumb == c) { flag = 0 ; break ; } } if (i < n) { if ((c - sumb) * 1.0 / suma >= -co[i + 1 ].b * 1.0 / co[i + 1 ].a && (c - sumb) * 1.0 / suma < -co[i].b * 1.0 / co[i].a) { t.b = c - t.b; ans.push_back(t); } } else { if ((c - sumb) * 1.0 / suma < -co[i].b * 1.0 / co[i].a) { t.b = c - t.b; ans.push_back(t); } } } if (!flag) printf ("-1\n" ); else { sort(ans.begin(), ans.end(), cmp); printf ("%d" , ans.size()); for (int i = 0 ; i < ans.size(); ++i) { if (ans[i].b * 1.0 / ans[i].a < 0 ) printf (" -" ); else printf (" " ); ll g = gcd(abs (ans[i].b), abs (ans[i].a)); if (ans[i].b == 0 ) printf ("0/1" ); else printf ("%lld/%lld" , abs (ans[i].b) / g, abs (ans[i].a) / g); } printf ("\n" ); } } return 0 ; }
题意：
定义排列 $p_1, p_2, … , p_n$ 的 “difference sequence” 为 $p_2-p_1, p_3-p_2,…,p_n-p_{n-1}$。现在给定 $N$ 和 $K$，求长度为 $N$ 的所有排列中 “difference sequence” 的字典序第 $K$ 小的排列。
题解： 暴力 STL 全排列
题目给定 $K$ 的范围不超过 $10^4$，而 $8! = 40320 > K$，因此可以预处理 $N <= 8$ 的情况，当 $N > 8$ 时暴力求 $a[1] = n$ 的全排列。
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 #include <bits/stdc++.h> using namespace std ;const int maxn = 1e5 + 10 ;struct P { int num[10 ]; string str; } ans[10 ][maxn]; int cmp (P p1, P p2) return p1.str < p2.str; } int main () int a[10 ] = {0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 }; for (int i = 2 ; i <= 8 ; ++i) { int cnt = 1 ; do { for (int j = 1 ; j <= i; ++j) { ans[i][cnt].num[j] = a[j]; if (j < i) ans[i][cnt].str += a[j + 1 ] - a[j] + 'A' ; } ++cnt; } while (next_permutation(a + 1 , a + 1 + i)); sort(ans[i] + 1 , ans[i] + cnt, cmp); } int T; cin >> T; while (T--) { int n, k; scanf ("%d%d" , &n, &k); if (n <= 8 ) { for (int j = 1 ; j <= n; ++j) { printf ("%d" , ans[n][k].num[j]); printf ("%s" , j == n? "\n" : " " ); } } else { int a[30 ]; a[1 ] = n; for (int i = 2 ; i <= n; ++i) { a[i] = i - 1 ; } for (int i = 0 ; i < k - 1 ; ++i) { next_permutation(a + 1 , a + 1 + n); } for (int i = 1 ; i <= n; ++i) { printf ("%d" , a[i]); printf ("%s" , i == n? "\n" : " " ); } } } return 0 ; }
1006 string matching (HDU 6629) 题意
给定字符串 $s[0…len - 1]$，对于每个 $i > 0$，用下图的程序求 $s[i…len - 1]$ 与 $s[0…len - 1]$ 的最长公共前缀的长度时，字符比较的操作进行了几次？
题解 扩展KMP/Z函数
签到题，扩展KMP (Z函数) 的裸题，cin 被卡了，改成 scanf 就过了。
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 #include <bits/stdc++.h> using namespace std ;typedef long long ll;char s[1000010 ];vector <int > z_function () int n = strlen (s); vector <int > z (n) for (int i = 1 , l = 0 , r = 0 ; i < n; ++i) { if (i <= r) z[i] = min(r - i + 1 , z[i - l]); while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i]; if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1 ; } return z; } int main () int T; scanf ("%d" ,&T); while (T--) { scanf ("%s" , s); vector <int > v = z_function(); ll ans = 0 ; int len = v.size(); for (int i = 1 ; i < len; ++i) { if (i == len - 1 ) { ans += 1 ; break ; } if (v[i] + i >= len) ans += v[i]; else ans += v[i] + 1 ; } printf ("%lld\n" , ans); } }
$solved by ch$
题意
给定三个正整数 $N, x, y$，求 $1 \sim N$ 的全排列中满足下列条件的个数。
$p_1 = x$
$p_N = y$
对于所有 $1 \le i < N, |p_i - p_{i + 1}|\le 2$
题解 DP/动态规划
特殊情况有点多，WA 了好几次。
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 #include <bits/stdc++.h> using namespace std ;typedef long long ll;const ll mod = 998244353 ;const int maxn = 1e5 + 10 ;ll dp[maxn] = {1 , 1 , 2 , 3 , 4 }; int main () for (int i = 5 ; i < maxn; ++i) { dp[i] = (dp[i - 1 ] + dp[i - 3 ]) % mod; } int T; cin >> T; while (T--) { ll n, x, y; scanf ("%lld%lld%lld" , &n, &x, &y); if (y - x == 1 && n > 3 && x == 1 ) printf ("1\n" ); else if (y - x == 1 && n > 3 && y == n) printf ("1\n" ); else if (y - x == 1 && n > 3 ) printf ("0\n" ); else if (n <= 4 ) printf ("%lld\n" , dp[y - x - 1 ]); else if (y - x == 2 ) printf ("1\n" ); else if (x == 1 && y == n) printf ("%lld\n" , dp[y - x - 1 ]); else if (x == 1 || y == n) printf ("%lld\n" , dp[y - x - 2 ]); else printf ("%lld\n" , dp[y - x - 3 ]); } return 0 ; }
