平面设计师参考网站,建设企业网站登录入口,建设银行网上银行登录,音乐网站怎么做文章目录 洛谷P3193 [HNOI2008] GT考试ATC abc339E Smooth SubsequenceATC abc339F Product Equality 洛谷P3193 [HNOI2008] GT考试
题目链接
KMPdp矩阵快速幂
还没有理解得很清楚#xff0c;主要是对KMP理解还不够深刻
#include bits/stdc.husing namespace std;… 文章目录 洛谷P3193 [HNOI2008] GT考试ATC abc339E Smooth SubsequenceATC abc339F Product Equality 洛谷P3193 [HNOI2008] GT考试
题目链接
KMPdp矩阵快速幂
还没有理解得很清楚主要是对KMP理解还不够深刻
#include bits/stdc.husing namespace std;#define int long long
using i64 long long;typedef pairint, int PII;
typedef pairdouble, double PDD;
typedef pairint, PII PIII;
typedef pairPII, PII PIIII;const int N 2010;int n, m, mod;struct Martix
{int a[30][30]; // 在这里修改矩阵的大小Martix() { memset(a, 0, sizeof(a)); }Martix operator*(const Martix B) const // 乘法运算符重载{Martix res;for (int i 0; i m; i )for (int j 0; j m; j )for (int k 0; k m; k )res.a[i][j] (res.a[i][j] a[i][k] * B.a[k][j]) % mod;return res;}
} G;vectorint pi(N);
void get_pi(string s)
{int j 0;for (int i 2; i m; i){while (j s[j 1] ! s[i]) j pi[j];if (s[j 1] s[i]) j ;pi[i] j;}for (int i 0; i m; i){for (char ch 0; ch 9; ch){j i;while (j s[j 1] ! ch) j pi[j];if (s[j 1] ch) j ;G.a[i][j] ;}}
}Martix power(Martix a, int b)
{Martix ans;for (int i 0; i m; i ) ans.a[i][i] 1;while (b){if (b 1) ans ans * a;b 1;a a * a;}return ans;
}void solve()
{cin n m mod;string s; cin s;s s;get_pi(s);G power(G, n);int ans 0;for (int i 1; i m; i ) ans (ans G.a[0][i]) % mod;cout ans \n;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t 1;// cin t;while (t -- ){solve();}
}ATC abc339E Smooth Subsequence
题目链接
线段树优化dp
把以每个数字结尾的最佳答案存进线段树中查询即可
#include bits/stdc.husing namespace std;#define int long long
using i64 long long;typedef pairint, int PII;
typedef pairdouble, double PDD;
typedef pairint, PII PIII;const int N 5e5 10;
const int mod 1e9 7;struct Node
{int l, r, maxx;
} tr[N * 4];void pushup(Node u, Node left, Node right)
{u.maxx max(left.maxx, right.maxx);
}void pushup(int u)
{pushup(tr[u], tr[u 1], tr[u 1 | 1]);
}void build(int u, int l, int r)
{tr[u] {l, r, 0};if (l r) return;int mid l r 1;build(u 1, l, mid), build(u 1 | 1, mid 1, r);
}void modify(int u, int pos, int x)
{if (tr[u].l pos tr[u].r pos){tr[u].maxx x;return;}int mid tr[u].l tr[u].r 1;if (pos mid) modify(u 1, pos, x);else modify(u 1 | 1, pos, x);pushup(u);
}Node query(int u, int l, int r)
{if (tr[u].l l tr[u].r r) return tr[u];int mid tr[u].l tr[u].r 1;if (r mid) return query(u 1, l, r);else if (l mid) return query(u 1 | 1, l, r);else{auto left query(u 1, l, mid);auto right query(u 1 | 1, mid 1, r);Node res {l, r};pushup(res, left, right);return res;}
}void solve()
{int n, d;cin n d;build(1, 1, N);vectorint dp(n 1);for (int i 1; i n; i ){int x;cin x;Node res query(1, x - d, x d);dp[i] max((i64)1, res.maxx 1);modify(1, x, dp[i]);}int ans 0;for (int i 1; i n; i ){ans max(ans, dp[i]);}cout ans \n;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t 1;// cin t;while (t -- ){solve();}
}ATC abc339F Product Equality
题目链接
哈希
这里的一个trick是乘积的个数比较少哈希之后很可能出现一样的关键字此时可以进行双哈希或更多的哈希都没问题取不同的模数减小出现相同关键字的概率
#include bits/stdc.husing namespace std;#define int long long
using i64 long long;typedef pairint, int PII;
typedef pairdouble, double PDD;
typedef pairint, PII PIII;const int N 5e5 10;
const int mod1 954169327;
const int mod2 906097321;void solve()
{int n;cin n;vectorstring a(n);mapint, int mp1, mp2;auto mm [](string s, int mod){int res 0;for (auto t : s){res (res * 10 t - 0) % mod;}return res;};vectorint b1(n), b2(n);for (int i 0; i n; i ){cin a[i];b1[i] mm(a[i], mod1);mp1[b1[i]] ;b2[i] mm(a[i], mod2);mp2[b2[i]] ;}int ans 0;for (int i 0; i n; i ){for (int j 0; j n; j ){ans min(mp1[(b1[i] * b1[j]) % mod1], mp2[(b2[i] * b2[j]) % mod2]);}}cout ans \n;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t 1;// cin t;while (t -- ){solve();}
}
