icp备案网站接入信息,企业网站优化定制,上海网站se0优化,阿里巴巴的网站建设与维护Codeforces Round 993 (Div. 4) 只选择对我有价值的题目记录 E. Insane Problem
题目描述
给定五个整数 k k k#xff0c; l 1 l_1 l1#xff0c; r 1 r_1 r1#xff0c; l 2 l_2 l2 和 r 2 r_2 r2#xff0c;Wave 希望你帮助她计算满足以下所有条件的有序对 …Codeforces Round 993 (Div. 4) 只选择对我有价值的题目记录 E. Insane Problem
题目描述
给定五个整数 k k k l 1 l_1 l1 r 1 r_1 r1 l 2 l_2 l2 和 r 2 r_2 r2Wave 希望你帮助她计算满足以下所有条件的有序对 ( x , y ) (x, y) (x,y) 的数量 l 1 ≤ x ≤ r 1 l_1 \leq x \leq r_1 l1≤x≤r1。 l 2 ≤ y ≤ r 2 l_2 \leq y \leq r_2 l2≤y≤r2。存在一个非负整数 n n n使得 y x k n \frac{y}{x} k^n xykn。
输入
第一行包含一个整数 t t t 1 ≤ t ≤ 1 0 4 1 \leq t \leq 10^4 1≤t≤104这里的 t t t 表示测试用例的数量。对于每个测试用例其唯一的一行包含五个整数 k k k l 1 l_1 l1 r 1 r_1 r1 l 2 l_2 l2 和 r 2 r_2 r2 2 ≤ k ≤ 1 0 9 2 \leq k \leq 10^9 2≤k≤109 1 ≤ l 1 ≤ r 1 ≤ 1 0 9 1 \leq l_1 \leq r_1 \leq 10^9 1≤l1≤r1≤109 1 ≤ l 2 ≤ r 2 ≤ 1 0 9 1 \leq l_2 \leq r_2 \leq 10^9 1≤l2≤r2≤109。
输出
对于每个测试用例在新的一行输出匹配的有序对 ( x , y ) (x, y) (x,y) 的数量。
示例
Input输入Output输出52 2 6 2 122 1 1000000000 1 10000000003 5 7 15 631000000000 1 5 6 100000000015 17 78 2596 2091486112199999998761197
注意事项
在第三个测试用例中匹配的有序对如下 ( 5 , 15 ) (5, 15) (5,15) ( 5 , 45 ) (5, 45) (5,45) ( 6 , 18 ) (6, 18) (6,18) ( 6 , 54 ) (6, 54) (6,54) ( 7 , 21 ) (7, 21) (7,21) ( 7 , 63 ) (7, 63) (7,63) 在第四个测试用例中唯一有效的有序对是 ( 1 , 1000000000 ) (1, 1000000000) (1,1000000000)。
思路 枚举加计数问题通常只需要枚举其中一个然后另一个是可以通过计算得到的。由于x和y的范围告诉我们了所以 k n k^n kn的范围我们也能知晓上界为 r r 2 / l 1 rr_2 / l_1 rr2/l1下取整下界为 l ( l 2 r 1 − 1 ) / r 1 l (l_2 r_1 - 1) / r_1 l(l2r1−1)/r1向上取整。现在我们只需要调整一下方程为 y k n x \frac{y}{k^n} x knyx每枚举一个可行的 k n k^n kn后我们用y的最小值和最大值即可求出在这个可行的 k n k^n kn下x的范围通过计算即可得到个数。至于为啥要将方程调整成除法形式而不是更好计算的形式自己思考一下就能明白用乘法的话得到的y值不是一个接一个的中间有很多空隙导致不能直接通过计算得到个数用除法可以解决这样的问题。 #include bits/stdc.h
#define int long long
#define endl \nusing namespace std;void solve(){int k,l1,r1,l2,r2;cinkl1r1l2r2;int l (l2r1-1)/r1;//下界int r r2/l1; //上界int base 1;int ans 0;// coutl rendl;while(basel) base*k; //先找到范围内最小的k^nwhile(baser){int ll (l2base-1) / base;int rr r2 / base;ll max(l1,ll);rr min(r1,rr);if(llrr) ans rr-ll1;base*k;}coutansendl;
}signed main(){int T; cinT; while(T--)solve();return 0;
}
评述 这道题比较有参考价值自己太笨了第一时间竟然无从下手 ----------------------------------------
F. Easy Demon Problem
题目描述
对于任意网格Robot 将其美感定义为网格中元素的总和。
Robot 给出了一个长度为 n n n 的数组 a a a 和一个长度为 m m m 的数组 b b b 。你构造了一个 n n n 乘 m m m 的网格 M M M 使得所有 1 ≤ i ≤ n 1 \leq i \leq n 1≤i≤n 和 1 ≤ j ≤ m 1 \leq j \leq m 1≤j≤m 都是 M i , j a i ⋅ b j M_{i,j}a_i\cdot b_j Mi,jai⋅bj 。
然后Robot 会给出 q q q 个查询每个查询都包含一个整数 x x x 。对于每个查询请判断是否可以***精确地执行一次下面的操作从而使 M M M 具有 x x x 的美感
选择整数 r r r 和 c c c 使得 1 ≤ r ≤ n 1 \leq r \leq n 1≤r≤n 和 1 ≤ c ≤ m 1 \leq c \leq m 1≤c≤m 都是整数。设 M i , j M_{i,j} Mi,j 为 0 0 0 所有有序对 ( i , j ) (i,j) (i,j) 都是 i r ir ir j c jc jc 或都是 i r ir ir 。
请注意查询是不持久的也就是说在查询过程中您不会将任何元素设置为 0 0 0 --您只需要输出是否可以找到 r r r 和 c c c 如果执行了上述操作网格的美观度将为 x x x 。此外请注意即使原始网格的美观度已经是 x x x 您也必须对每个查询执行上述操作。
输入
第一行包含三个整数 n n n 、 m m m 和 q q q ( 1 ≤ n , m ≤ 2 ⋅ 1 0 5 , 1 ≤ q ≤ 5 ⋅ 1 0 4 1 \leq n,m \leq 2\cdot 10^5, 1 \leq q \leq 5\cdot 10^4 1≤n,m≤2⋅105,1≤q≤5⋅104 )–分别是 a a a 的长度、 b b b 的长度和查询次数。
第二行包含 n n n 个整数 a 1 , a 2 , … , a n a_1, a_2, \ldots, a_n a1,a2,…,an ( 0 ≤ ∣ a i ∣ ≤ n 0 \leq |a_i| \leq n 0≤∣ai∣≤n )。
第三行包含 m m m 个整数 b 1 , b 2 , … , b m b_1, b_2, \ldots, b_m b1,b2,…,bm ( 0 ≤ ∣ b i ∣ ≤ m 0 \leq |b_i| \leq m 0≤∣bi∣≤m )。
下面的 q q q 行中各包含一个整数 x x x ( 1 ≤ ∣ x ∣ ≤ 2 ⋅ 1 0 5 1 \leq |x| \leq 2\cdot 10^5 1≤∣x∣≤2⋅105 )即通过将一行和一列中的所有元素都设置为 0 0 0 所获得的网格美感。
输出
对于每个测试用例如果有办法执行上述操作从而使美景为 x x x 则输出 “YES”不带引号否则输出 “NO”不带引号。
您可以在任何情况下输出 YES 和 “NO”例如字符串 “yES”、yes 和 Yes 将被视为肯定回答。
样例1 3 3 6 -2 3 -3 -2 2 -1 -1 1 -2 2 -3 3 输出 NO YES NO NO YES NO 思路 评述 一道不错的题就是题目有点难读其中提前预处理出所有情况再来处理询问的方式可以很有效的降低时间复杂度也是这种题的经典做法。 #include bits/stdc.husing namespace std;using ll long long;
using ld long double;
using pii pairint, int;
using pll pairll, ll;#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3fLLconst int N 2e5 5;bool visA[2 * N 5];
bool visB[2 * N 5];bool ans[2 * N 5];
void solve()
{int n, m, q;cin n m q;std::vectorll a(n);ll sumA 0;for (int i 0; i n; i){cin a[i];sumA a[i];}std::vectorll b(m);ll sumB 0;for (int i 0; i m; i){cin b[i];sumB b[i];}for (int i 0; i n; i){ll d sumA - a[i];if (abs(d) N)visA[d N] 1;}for (int i 0; i m; i){ll d sumB - b[i];if (abs(d) N)visB[d N] 1;}for (int i 1; i N; i){for (int j 1; j * i N; j){ans[N i * j] | visA[N i] visB[N j];ans[N i * j] | visA[N - i] visB[N - j];ans[N - i * j] | visA[N i] visB[N - j];ans[N - i * j] | visA[N - i] visB[N j];}}while (q--){int x;cin x;x N;if (ans[x])cout YES\n;elsecout NO\n;}
}int main()
{ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);// freopen(test.in, r, stdin);// freopen(test.out, w, stdout);int _ 1;// std::cin _;while (_--){solve();}return 0;
}
