Namomo Spring Camp 2022 Div1 每日一题记录 (2022.05.14-2022.05.20)
GCD
题目链接
3 s, 1024 MB
题目描述
给定整数 \(a\) 和 \(m\) , 计算整数 \(x\) 的数量，满足 \(0\le x< m\) 同时 \(gcd(a,m)= gcd(a+x,m)\)
输入格式
第一行一个数字 \(T\)
接下来 \(T\) 行 \(2\) 个整数 \(a,m\)
输出格式
T 行，每行一个数，表示答案
样例输入
1 2 3 4 3 4 9 5 10 42 9999999967
样例输出
数据规模
所有数据保证 \(1\le T\le 50,1\le a< m\le 1e10\)
解题思路
复杂度
代码参考
Show code
题目链接
5 s, 128 MB
题目描述
有两个长度为 \(n\) 的排列 \(A、B\)
其中数的范围均为 \(1 - n\) . 若 \(abs(A[i] - B[j]) \le 4\) , 则 \(A[i]\) 与 \(B[j]\) 间可以连一条边
现要求在边与边不相交的情况下的最大的连边数量
例如样例中：如果 \(a_1\) 和 \(b_2\) 连边 且 \(a_2\) 和 \(b_1\) 连边，则这两条边相交
数据保证 \(A,B\) 都是一个排列
输入格式
第一行一个整数 \(n\)
接下来 \(n\) 行，每行一个数字 \(a_i\)
接下来 \(n\) 行，每行一个数字 \(b_i\)
样例输入
1 2 3 4 5 6 7 8 9 10 11 12 13 6 1 2 3 4 5 6 6 5 4 3 2 1
样例输出
数据范围
\(1 \le n \le 10^5\)
解题思路
树状数组优化 LCS
设 \(f(i,j)\) 表示左边 \([1,i]\) , 右边 \([1,j]\) 范围内的最大值，显然是个 LCS 类型的 DP, 有
\[
f(i,j)=\max\{f(i,j-1),f(i-1,j),f(i-1,j-1)+[|a_i-b_j|\leq 4]\}
\]
然后用树状数组维护前缀最值优化即可
复杂度
\(O(n\log n)\)
代码参考
Show code
Luogu_P3657 view raw 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 #include <bits/stdc++.h> using namespace std;#define _for(i, l, r, vals...) \ for (decltype(l + r) i = (l), i##end = (r), ##vals; i <= i##end; ++i) template <class T >bool chkmin (T &a, T b) return b < a ? a = b, true : false ; } template <class T >bool chkmax (T &a, T b) return a < b ? a = b, true : false ; } const uint32_t OFFSET = 5 ;const uint32_t N = 1e5 + OFFSET, M = 2e5 + OFFSET, K = 21 ;template <size_t N, typename Tp, bool _clear = false >class BIT {protected : Tp tree[N]; constexpr size_t lowbit (ptrdiff_t x) const return x & (-x); } public : BIT () {} void clear () memset (tree, 0 , sizeof (tree)); } void modify (size_t pos, Tp val) for (size_t i = pos; i < N; i += lowbit (i)) tree[i] = max (tree[i], val); } Tp query (size_t pos) const { Tp ret = 0 ; for (size_t i = pos; i; i = (ptrdiff_t )i - lowbit (i)) ret = max (ret, tree[i]); return ret; } }; BIT<N, int > tr; int a[N];int idx_b[N];int f[N];auto solve () -> void int n; cin >> n; _for(i, 1 , n) cin >> a[i]; _for(i, 1 , n, _) { cin >> _; idx_b[_] = i; } _for(i, 1 , n) { _for(j, max (1 , a[i] - 4 ), min (n, a[i] + 4 )) f[j] = tr.query (idx_b[j] - 1 ); _for(j, max (1 , a[i] - 4 ), min (n, a[i] + 4 )) tr.modify (idx_b[j], f[j] + 1 ); } cout << tr.query (n); } int main () ios::sync_with_stdio (false ); cin.tie (nullptr ); cout.tie (nullptr ); solve (); return 0 ; }
序列中位数
题目链接
1 s, 1024 MB
题目描述
给定正整数 \(N\) , 求出 \(1 \sim N - 1\) 中所有与 \(N\) 互质的数构成的序列 的中位数
我们定义：一个长度为 \(K\) 的序列的中位数是序列中第 \(\lfloor\frac{K + 1}{2}\rfloor\) 大的数字。且两个正整数 \(a\) 与 \(b\) 互质当且仅当 \(gcd(a, b) = 1\)
输入格式
第一行一个正整数 \(T\) , 表示数据组数
对于每组数据，一行输入一个正整数 \(N\)
对于所有数据，满足 \(1 \leq T \leq 100\) ,\(2 \leq N \leq 10^{18}\)
输出格式
对于每组测试数据，输出一行一个正整数，表示答案
样例输入
样例输出
解题思路
复杂度
代码参考
Show code
选元素 (数据加强版)
题目链接
1 s, 1024 MB
题目描述
给定一个长度为 \(n\) 的整数序列 \(a_1,a_2,…,a_n\)
请你从中挑选 \(x\) 个元素，要求:
原序列中的每一个长度为 \(k\) 的连续子序列都至少包含一个被选中的元素
满足条件 \(1\) 的前提下，所选 \(x\) 个元素的相加之和应尽可能大。输出最大可能和
输入格式
第一行包含三个整数 \(n,k,x\)
第二行包含 \(n\) 个整数 \(a_1,a_2,…,a_n\)
输出格式
如果无法满足题目要求，则输出 \(−1\)
否则，输出一个整数，表示所选元素的最大可能和
数据范围
所有测试点满足 \(1≤k,x≤n≤2500, 1≤a_i≤10^9\)
输入样例 1
输出样例 1
输入样例 2
输出样例 2
输入样例 3
输出样例 3
解题思路
复杂度
代码参考
Show code
最长上升子序列计数 (Bonus)
题目链接
1 s, 1024 MB
本题是 http://oj.daimayuan.top/problem/326 的加强版，差别仅在于 \(n\) 与 \(a_i\) 的取值
题目描述
求最长上升子序列及其长度的问题已经相当普及，本题希望你求解 最长上升子序列的个数
只要有序元组有一个值不同，就称不同。如 \([1, {\color{green}3},{\color{red}3}, 0, 4]\) 中 \([1, {\color{green}3}, 4], [1,{\color{red}3}, 4]\) 算作两个答案
输入格式
输入包含两行，第一行有一个整数 \(n\) , 表示序列 \(\{a\}\) 的大小
接下来一行包含 \(n\) 个用空格分隔的整数，依次表示 \(a_1, a_2, \cdots, a_n\)
输出格式
输出最长上升子序列的个数
由于这个值可能很大，你只需要输出其模余 \(10^9 + 7\) 的结果
数据规模
-\(1 \le n \le 4 \times 10 ^ 5\) -\(a_i \in [-10 ^ 8, 10 ^ 8]\)
样例 1 输入
样例 1 输出
样例 2 输入
样例 2 输出
解释
共包含:
\([1, 2, 4, 7] \times 3\)
\([1, 2, 3, 4] \times 2\)
解题思路
复杂度
代码参考
Show code
LCM 与 GCD (CF1499D)
题目链接
3 s, 1024 MB
题目描述
给定三个正整数 \(x,y,k\) , 求满足 \(x \times lcm(a,b) - y \times gcd(a,b) = k\) 的数对 \((a,b)\) 的数量，其中 \(lcm(a,b)\) 是 \(a,b\) 的最小公倍数，\(gcd(a,b)\) 是 \(a,b\) 的最大公约数
若 \(a \neq b\) 那么 \((a,b)\) 与 \((b,a)\) 是两个不同的数对
输入格式
第一行一个整数 \(t\) , 表示数据组数.\((1 \leq t \leq 10^3)\)
接下来 \(t\) 行，每行输入三个整数 \(x,y,k\) , 含义如题面所示.\(( 1 \leq x,y,k \leq 10^7 )\)
输出格式
输出 \(t\) 行，每行一个整数，表示满足要求二元对的数量
样例输入
1 2 3 4 5 4 1 1 3 4 2 6 3 3 7 2 7 25
样例输出
解题思路
简单数论
显然有
\[
\alpha (xpq-y)=k
\]
其中 \(p,q\) 互质
然后枚举 \(k\) 的因子之后计算 \(p,q\) 的对数即可
复杂度
\(O(2K+t\sqrt{2k})\) , 其中 \(K=10^7\)
代码参考
Show code
CodeForces_1499D view raw 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;using i64 = int64_t ;#define _for(i, l, r, vals...) \ for (decltype(l + r) i = (l), i##end = (r), ##vals; i <= i##end; ++i) const int N = 2e7 + 5 , P = 1.5e6 + 5 ;bool vis[N];int prime[P], cnt_prime;uint8_t prime_factor_cnt[N];void init_prime (const int &n = N - 1 ) for (int i = 2 ; i <= n; ++i) { if (!vis[i]) { prime[++cnt_prime] = i; prime_factor_cnt[i] = 1 ; } for (int j = 1 ; j <= cnt_prime && i * prime[j] <= n; ++j) { vis[i * prime[j]] = 1 ; prime_factor_cnt[i * prime[j]] = prime_factor_cnt[i]; if (i % prime[j] == 0 ) break ; ++prime_factor_cnt[i * prime[j]]; } } } i64 calc (i64 x, i64 y, i64 k2) { if ((k2 + y) % x) return 0 ; return i64 (1 ) << prime_factor_cnt[(k2 + y) / x]; } auto solve () -> void i64 x, y, k; cin >> x >> y >> k; if (k % gcd (x, y)) { cout << "0\n" ; return ; } i64 ans = 0 ; _for(i, 1 , (int )sqrt (k)) { if (k % i) continue ; ans += calc (x, y, k / i); if (i != k / i) ans += calc (x, y, i); } cout << ans << '\n' ; } int main () ios::sync_with_stdio (false ); cin.tie (nullptr ); cout.tie (nullptr ); init_prime (); int _t ; cin >> _t ; while (_t --) solve (); return 0 ; }
前缀集 (AtCoder abc250e)
题目链接
2 s, 512 MB
题目描述
定义序列 \(a\) 的前缀集 \(S(a, i)\) 为 a[1]..a[i] 这 i 个元素构成的集合
给定两个长为 \(n\) 的序列 \(a, b\)
\(m\) 次询问，每次询问两个位置 i, j
请你判断 \(a\) 的前缀集 \(S(a, i)\) 和 \(b\) 的前缀集 \(S(b, i)\) 是否相同
输入描述
一行一个整数 \(n(n\leq 5\times 10^5)\)
两行，一行 \(n\) 个整数，分别描述 \(a, b(1\leq a_i,b_i\leq 10^9)\)
一行一个整数 \(m(m\leq 5\times 10^5)\)
\(m\) 行，每行两个数 \(i(1\leq i\leq n)\) , \(j(1\leq j \leq n)\) , 表示询问 \(S(a, i)\) 和 \(S(b, j)\)
输出描述
m 行，如果相同输出 Y, 否则输出 N
样例输入
1 2 3 4 5 6 7 8 9 10 11 5 1 2 3 4 5 1 2 2 4 3 7 1 1 2 2 2 3 3 3 4 4 4 5 5 5
样例输出
原题链接
戳我
解题思路
Hash / Set
取 \(S_A(i)=|\{a_1,a_2,...,a_i\}|\) , 那么 \(S(a,i)=S(b,j)\implies S_A(i)=S_B(j)\)
若 \(S_A(i)=S_B(j)\) , 只需事先计算出来 \(a,b\) 去重后当 \(S_A(i)\) 取哪些值时才会相同即可
复杂度
\(O(n+q)\)
代码参考
Show code
AtCoder_abc250e view raw 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 #include <bits/stdc++.h> using namespace std;#define _for(i, l, r, vals...) \ for (decltype(l + r) i = (l), i##end = (r), ##vals; i <= i##end; ++i) #define _run_continue(expressions) \ { \ expressions; \ continue; \ } template <class T >bool chkmin (T &a, T b) return b < a ? a = b, true : false ; } template <class T >bool chkmax (T &a, T b) return a < b ? a = b, true : false ; } const uint32_t OFFSET = 5 ;const uint32_t N = 2e5 + OFFSET, M = 2e5 + OFFSET, K = 21 ;int unq_cnt_a[N], unq_cnt_b[N];vector<int > unq_a, unq_b; set<int > s; #define __init__(x) \ unq_##x.reserve(n); \ _for(i, 1, n, _) { \ cin >> _; \ s.insert(_); \ unq_cnt_##x[i] = s.size(); \ if (unq_cnt_##x[i] > unq_cnt_##x[i - 1]) unq_##x.push_back(_); \ } bool ans[N];auto __ins__ = [](int x) { if (s.count (x)) s.erase (x); else s.insert (x); }; auto solve () -> void int n; cin >> n; __init__(a); s.clear (); __init__(b); s.clear (); _for(i, 1 , min (unq_a.size (), unq_b.size ())) { __ins__(unq_a[i - 1 ]); __ins__(unq_b[i - 1 ]); ans[i] = !s.size (); } int q; cin >> q; _for(i, 1 , q, x, y) { cin >> x >> y; if (unq_cnt_a[x] != unq_cnt_b[y]) _run_continue(cout << "No\n" ); cout << (ans[unq_cnt_a[x]] ? "Yes\n" : "No\n" ); } } int main () ios::sync_with_stdio (false ); cin.tie (nullptr ); cout.tie (nullptr ); solve (); return 0 ; }