開啟瘋狂水題解模式，大概會持續好幾次...直到我趕上進度為止。

以下題解包括：

\[1001【HDU-6624】 \\ 1004【HDU-6627】 \\ 1005【HDU-6628】 \\ 1006【HDU-6629】 \\ 1007【HDU-6630】\]

【1001】 數學 HDU-6624 fraction

http://acm.hdu.edu.cn/showproblem.php?pid=6624

找到最小正整數的 \(b\) 滿足 \(a<b\) 且 \(a = bx(mod \ p)\)。

參考：https://blog.csdn.net/Sarah_Wang0220/article/details/98771865

可知：\(0<a<b\)，\(bx=py+a\) ==> \(0<a=bx-py<b\) ==> \(\frac{p}{x} < \frac{b}{y} < \frac{p}{x-1}\)，要求最小的 \(b\)。

迭代法：
\[ \begin{aligned} & \because \frac{p}{x} < \frac{b}{y} < \frac{p}{x-1} \ 且 \ p > x \\ & \therefore \frac{p}{x} > 0 \ \ 取 \ t = \frac{p}{x} \\ & \therefore \frac{p-tx}{x} < \frac{b-ty}{y} < \frac{p-t(x-1)}{x-1} \\ & 取倒數得：\frac{x-1}{p-t(x-1)} < \frac{y}{b-ty} < \frac{x}{p-tx} \\ & 同理，繼續減去左邊的整數部分 \\ & 此時 \ b' = b - ty 不斷減小 \end{aligned} \]

#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <bitset> #include <cctype> #include <cstdio> #include <vector> #include <string> #include <cstdlib> #include <cstring> #include <fstream> #include <iomanip> #include <numeric> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; const double PI = acos(-1.0); const double eps = 1e-6; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7;void solve(ll a, ll b, ll &c, ll &d, ll e, ll f) {ll t = a/b;if(e/f > t) {c = t+1;d = 1;return ;}a = a - t*b;e = e - t*f;solve(f, e, d, c, b, a);c = c + t*d; }int main() {int t;scanf("%d", &t);while(t--) {ll p, x;scanf("%lld%lld", &p, &x);ll b, y;solve(p, x, b, y, p, x-1);printf("%lld/%lld\n", b*x-p*y, b);}return 0; }

【1004】 數學 HDU-6627 equation

http://acm.hdu.edu.cn/showproblem.php?pid=6627

給定 \(n\) 和 \(c\)，輸入 \(n\) 個 \(a_i\) 和 \(b_i\)，計算所有 \(x\) 的解使得：\(\sum^{n}_{i=1} |a_ix+b_i| = c\)。

對于每個絕對值等式找出 \(x\) 的區間，再進行排序枚舉區間，統計解的個數。

#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <bitset> #include <cctype> #include <cstdio> #include <vector> #include <string> #include <cstdlib> #include <cstring> #include <fstream> #include <iomanip> #include <numeric> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; const double PI = acos(-1.0); const double eps = 1e-6; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7;const int maxn = 1e5+5;int n; ll c; ll suma[maxn], sumb[maxn]; // 記錄 系數/常數 前綴和 map<double, int> vis;struct node {ll a, b;double f;bool operator < (const node &q) const {return f > q.f;} }p[maxn], ans[maxn];bool cmp(node x, node y) {return x.f < y.f; }int main() {int t;scanf("%d", &t);suma[0] = sumb[0] = 0; while(t--) {vis.clear();scanf("%d%lld", &n, &c);for(int i = 1; i <= n; i++) {scanf("%lld%lld", &p[i].a, &p[i].b);p[i].f = -1.0*p[i].b/p[i].a; // 每組方程等于 0的解}sort(p+1, p+1+n);for(int i = 1; i <= n; i++) {suma[i] = suma[i-1] + p[i].a;sumb[i] = sumb[i-1] + p[i].b;}int flag = 0;int cnt = 0;for(int i = 0; i <= n; i++) {ll A = suma[n] - 2*suma[i]; // 當前區間解的 系數 前綴和（分母）ll B = sumb[n] - 2*sumb[i]; // 當前區間解的 常數 前綴和ll C = c - B; // 等式常數移到右邊獲取最終常數（分子）if(A == 0) {if(C == 0) { // 無窮解flag = 1; break;}else { // 無解continue;}}else {ll temp = __gcd(abs(C), abs(A));double mark = 1.0 * C / A;if(vis[mark] == 0) { // 去重if((i==n || mark>p[i+1].f) && (i==0 || mark<=p[i].f)) { // 邊界判定ans[cnt].a = C / temp;ans[cnt].b = A / temp;ans[cnt++].f = mark;}}}}if(flag == 1) {printf("-1\n");}else {printf("%d", cnt);sort(ans, ans+cnt, cmp);for(int i = 0; i < cnt; i++) {if(ans[i].a*ans[i].b > 0) {printf(" %lld/%lld", abs(ans[i].a), abs(ans[i].b));}else if(ans[i].a*ans[i].b == 0) {printf(" 0/1");}else {printf(" -%lld/%lld", abs(ans[i].a), abs(ans[i].b));}}printf("\n");}}return 0; }

【1005】 思維 HDU-6628 permutation 1

http://acm.hdu.edu.cn/showproblem.php?pid=6628

\(t\) 組案例，已知序列為：\(p_1p_2...p_n\)，定義差異序列為：\(p_2-p_1,p_3-p_2,...,p_n-p_{n-1}\)。給定 \(n\) 和 \(k\)，求序列 \(1,2,3,...,n\) 中差異序列排名第 K 小的那個，輸出它。（\(2 \leq n \leq 20 \ \ \ 1 \leq k \leq min(10^4,n!)\)）

對于 \(n \leq 8\) 時，直接暴力就行。

對于 \(n > 8\) 時，找到規律：先放下 \(n\) 這個數，后面最小就是 \(1,2,3,...,n-1\)，然后只需要對后 8 位進行排列即可，因為 \(8! > 10^4\)。

#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <bitset> #include <cctype> #include <cstdio> #include <vector> #include <string> #include <cstdlib> #include <cstring> #include <fstream> #include <iomanip> #include <numeric> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; const double PI = acos(-1.0); const double eps = 1e-6; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7;const int maxn = 4e4+500;int a[10] = {1, 2, 3, 4, 5, 6, 7, 8}; int a_8[10] = {1, 2, 3, 4, 5, 6, 7}; int _a_8[10] = {1, 2, 3, 4, 5, 6, 8}; int tot, tot1, tot2, cnt;struct node {int z[10];bool operator < (const node x) const {for(int i = 0; i < 8; i++) {if(z[i] < x.z[i]) {return 1;}else if(z[i] == x.z[i]) {continue;}else {return 0;}}} }temp[maxn], t_8[maxn], _t_8[maxn];struct NODE {int z[10];int x[10]; }res[maxn];bool cmp(NODE nn, NODE mm) {for(int i = 0; i < 8; i++) {if(nn.x[i] < mm.x[i]) {return 1;}else if(nn.x[i] == mm.x[i]) {continue;}else {return 0;}}return 0; }void init() {do {for(int i = 0; i < 8; i++) {temp[tot].z[i] = a[i];}tot++;} while(next_permutation(a, a+8));sort(temp, temp+tot); }void cal(int n) {int aa[10];for(int i = 0; i < n; i++) {aa[i] = i+1;}do {for(int i = 0; i < n; i++) {res[cnt].z[i] = aa[i];}for(int i = 1; i < n; i++) {res[cnt].x[i-1] = res[cnt].z[i] - res[cnt].z[i-1];// cout << res[cnt].x[i-1] << " ";}// cout << endl;cnt++;} while(next_permutation(aa, aa+n));sort(res, res+cnt, cmp); }int main() {tot = tot1 = tot2 = 0;init();int t;scanf("%d", &t);while(t--) {int n, k;scanf("%d%d", &n, &k);if(n <= 8) {cnt = 0;cal(n);for(int i = 0; i < n; i++) {printf("%d%c", res[k-1].z[i], i==n-1?'\n':' ');}}else {printf("%d ", n);for(int i = 1; i < n-8; i++) {printf("%d ", i);}k = k - 1;for(int i = 0; i < 8; i++) {printf("%d%c", temp[k].z[i]+n-9, i==7?'\n':' ');}}}return 0; }

【1006】 擴展KMP HDU-6629 string matching

http://acm.hdu.edu.cn/showproblem.php?pid=6629

給定一個字符串，現要求得它的每一個后綴和原串的公共前綴，問暴力執行這一過程需要多少步。

擴展KMP裸題。

#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <bitset> #include <cctype> #include <cstdio> #include <vector> #include <string> #include <cstdlib> #include <cstring> #include <fstream> #include <iomanip> #include <numeric> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; const double PI = acos(-1.0); const double eps = 1e-6; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7;const int maxn = 1e6+5;char s[maxn]; char T[maxn]; ll nxt[maxn], extend[maxn];void getnxt(char str[]) {int i = 0, j, po;int len = strlen(str);nxt[0] = len;while(str[i] == str[i+1] && i+1 < len) i++; nxt[1] = i;po = 1;for(i = 2; i < len; i++) {if(nxt[i-po]+i < nxt[po]+po) // case1 可以直接得到next[i]的值nxt[i] = nxt[i-po];else { // case2 要繼續匹配才能得到next[i]的值j = nxt[po] + po - i;if(j < 0) // 如果i>po+next[po],則要從頭開始匹配j = 0; while(str[j] == str[j+i] && i+j < len) j++; nxt[i] = j;po = i;}} } void EXKMP(char s1[], char s2[]) {int i = 0, j, po;int l1 = strlen(s1);int l2 = strlen(s2);getnxt(s2);while(s1[i] == s2[i] && i < l2 && i < l1) i++;extend[0] = i;po = 0;for(i = 1; i < l1; i++) {if(nxt[i-po]+i < extend[po]+po) //case1 直接可以得到extend[i]的值extend[i] = nxt[i-po];else { // case2 要繼續匹配才能得到extend[i]的值j = extend[po]+po-i;if(j < 0) // 如果i>extend[po]+po則要從頭開始匹配j = 0;while(s1[j+i]==s2[j] && i+j < l1 && j < l2) j++;extend[i] = j;po = i;}} }int main() {int t;scanf("%d", &t);while(t--) {scanf("%s", s);strcpy(T, s);EXKMP(s, T);int n = strlen(s);ll ans = 0;for(int i = 1; i < n; i++) {ans = ans + extend[i];if(extend[i] != n-i) {ans = ans + 1;}}printf("%lld\n", ans);}return 0; }

【1007】 規律 HDU-6630 permutation 2

http://acm.hdu.edu.cn/showproblem.php?pid=6630

給定 \(n,x,y\)，對于 \(1\) 到 \(n\) 這 \(n\) 個數，滿足：\(p_1 = x, \ p_2 = y, \ |p_i-p_{i-1}| \leq 2 \ (1 \leq i < n)\)。

打表找規律即可。

#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <bitset> #include <cctype> #include <cstdio> #include <vector> #include <string> #include <cstdlib> #include <cstring> #include <fstream> #include <iomanip> #include <numeric> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; const double PI = acos(-1.0); const double eps = 1e-6; const int inf = 0x3f3f3f3f; const int mod = 998244353;const int maxn = 1e5+5;ll a[maxn];int main() {int t;scanf("%d", &t);while(t--) {int n, x, y;scanf("%d%d%d", &n, &x, &y);if(n == 2 || n == 3) {printf("1\n");continue;}a[0] = 0;if(x == 1) {a[1] = 1;a[2] = 1;for(int i = 3; i <= y-x; i++) {if(i == n-x) {a[i] = (a[i-1] + a[i-2] + a[i-3]) % mod;}else {a[i] = (a[i-1] + a[i-3]) % mod;}}}else if(x == n-1) {printf("1\n");continue;}else {a[1] = 0;a[2] = 1;for(int i = 3; i <= y-x; i++) {if(i == n-x) {a[i] = (a[i-1] + a[i-2] + a[i-3]) % mod;}else {a[i] = (a[i-1] + a[i-3]) % mod;}} }printf("%lld\n", a[y-x]);}return 0; }

轉載于:https://www.cnblogs.com/Decray/p/11330796.html

總結

以上是生活随笔為你收集整理的暑假N天乐【比赛篇】 —— 2019杭电暑期多校训练营（第五场）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。