低价网站建设怎么样,做网站 广州,省建设厅网站6,做百度网站排A.Counting Passes(暴力)
题意#xff1a;
给定 n n n个学生的分数#xff0c;以及及格分 x x x #xff0c;问多少人及格了。
分析#xff1a;
暴力枚举#xff0c;依次判断每个学生的分数即可。
代码#xff1a;
#include bits/stdc.h
using namespace s…A.Counting Passes(暴力)
题意
给定 n n n个学生的分数以及及格分 x x x 问多少人及格了。
分析
暴力枚举依次判断每个学生的分数即可。
代码
#include bits/stdc.h
using namespace std;
int main(){int n, l;cin n l;int ans 0;while (n--) {int x;cin x;ans (x l);}cout ans endl;return 0;
}B.Minimize Abs 1数学
题意
回答 n n n 个问题每个问题给定 a , l , r a,l,r a,l,r问函数 f ( x ) ∣ x − a ∣ f(x)|x−a| f(x)∣x−a∣在 [ l , r ] [l,r] [l,r]的最小值。
分析
全定义域下最小值显然在 x a xa xa 取得。绝对值函数图像是 V V V 型。 现在定义域限定在 [ l , r ] [l,r] [l,r]则分 a ≤ l , a ≥ r , l a r a \le l,a \ge r,l \lt a \lt r a≤l,a≥r,lar 三种情况分别讨论极值即可。即分别在 x l , x r , x a xl,xr,xa xl,xr,xa取得最小值。
代码
#include bits/stdc.h
using namespace std;
int main(){int n, l, r;cin n l r;while (n--) {int a;cin a;if (a l)cout l ;else if (a r)cout r ;elsecout a ;}return 0;
}C.Minimize Abs 2数学
题意
给定整数 d d d问函数 f ( x , y ) ∣ x 2 y 2 − d ∣ f(x,y)|x^2y^2−d| f(x,y)∣x2y2−d∣的最小值。
分析
枚举 x x x的取值范围是 [ 1 , 2 e 6 ] [1,2e6] [1,2e6]然后得 y 2 a b s ( d − x ∗ x ) y^2abs(d−x∗x) y2abs(d−x∗x)分别取 y 1 ⌊ y ⌋ , y 2 ⌈ y ⌉ y_1\lfloor\sqrt{y}\rfloor,y_2\lceil\sqrt{y}\rceil y1⌊y ⌋,y2⌈y ⌉由于会有一正一负的情况 ( x 2 ( y 1 ) 2 ≤ d , x 2 ( y 2 ) 2 ≥ d ) (x^2(y_1)^2 \le d,x^2(y_2)^2 \ge d) (x2(y1)2≤d,x2(y2)2≥d)取 m i n ( f ( x , y 1 ) , f ( x , y 2 ) ) min(f(x,y1),f(x,y2)) min(f(x,y1),f(x,y2))对所有 x x x 取最小值即可。
代码
#include bits/stdc.h
using namespace std;
typedef long long LL;
int main(){LL d;cin d;int up 2e6;LL ans 1e18;for (int i 0; i up; i){LL x 1ll * i * i;LL y abs(d - x);LL y1 floor(sqrt(y)), y2 ceil(sqrt(y));ans min({ans, abs(x y1 * y1 - d), abs(x y2 * y2 - d)});}cout ans endl;return 0;
}
D.Counting Ls思维,枚举
题意
给定一个包含o或者x的二维矩阵。问所有满足下述条件的三元组下标数量。
该三元组上的字符在矩阵中的位置各不相同但是都是o。该三元组中其中两个字符在同一行其中两个字符在同一列。
分析
如果二维矩阵的一个位置的字符为o时该字符可以作为中间点产生的贡献为 ( r o w [ i ] − 1 ) ∗ ( c o l [ j ] − 1 ) (row[i]-1)*(col[j]-1) (row[i]−1)∗(col[j]−1)其中 r o w [ i ] row[i] row[i]表示该行o的个数 c o l [ i ] col[i] col[i]表示该列 o 的个数。累计这些答案计数即可。
代码
#include bits/stdc.h
using namespace std;
typedef long long LL;string s[2005];
int row[2005], col[2005];int main(){int n;cin n;for (int i 0; i n; i) {cin s[i];for (int j 0; j n; j) {if (s[i][j] o) {row[i];col[j];}}}LL ans 0;for (int i 0; i n; i)for (int j 0; j n; j) {if (s[i][j] o) {ans 1ll * (row[i] - 1) * (col[j] - 1);}}cout ans endl;return 0;
}E.Mex and Update(思维,数据结构)
题意
给定一个数组 a a a进行如下操作。每次操作令 a i x a_ix aix。然后输出 m e x ( a ) mex(a) mex(a)。 m e x ( a ) mex(a) mex(a)表示数组 a a a未出现的最小非负整数。
分析
考虑如何求出一个数组的 m e x mex mex我们可以用一个 m a p map map表示数字 i i i的出现次数那每次求 m e x mex mex可以从小到大遍历该数组找到第一个出现次数为 0 0 0的下标即是答案。
但这复杂度可能会高达 O ( n ) O(n) O(n)考虑更快速的方法我们可以用 s e t set set储存 m a p map map中值为 0 0 0(未出现的数)下标这样 s e t set set中的最小值就是答案。
当 a i x a_ix aix时相当于把原来的 a i a_i ai删掉即 m p [ a i ] mp[a_i] mp[ai]−−然后把 x x x加进来即 m p [ x ] mp[x] mp[x]如果 m p [ a i ] mp[a_i] mp[ai]变为 0 0 0则说明 a i a_i ai没有出现将其插入到 s e t set set中。同时 m p [ x ] mp[x] mp[x]变为 1 1 1说明 x x x出现了从 s e t set set中删去。
这样就可以动态维护 m e x mex mex值此时的每次操作的时间复杂度为 O ( l o g n ) O(logn) O(logn)
hint: 包含 n n n个数的数组可能的 m e x mex mex为 0 ∼ n 0 \sim n 0∼n s e t set set可以通过 b e g i n ( ) begin() begin()方法取出头部元素的迭代器然后通过解地址符*取出对应的值。
代码
#include bits/stdc.h
using namespace std;
typedef long long LL;
int a[200005];
mapint, int mp;
setint mex;
int main(){int n, q;cin n q;for (int i 1; i n; i){cin a[i];mp[a[i]];}for (int i 0; i n; i){if (mp[i] 0){mex.insert(i);}}while (q--){int i, x;cin i x;if (mp[a[i]] 1){mex.insert(a[i]);}mp[a[i]]--;if (mp[x] 0){mex.erase(x);}mp[x];a[i] x;cout *mex.begin() endl;}
}F.Minimize Bounding Square(二分,前缀和)
题意
二维平面上 n n n个点可进行最多 k k k 次操作每次操作将一个点上下左右移动一格。点可以重叠。问进行若干次操作后能将所有点覆盖的正方形的边长的最小值。
分析 x x x和 y y y两个维度相互独立我们可以分别考虑每个维度。
考虑一维情况下如果我们固定覆盖的线段长度会发现比较好做。注意到如果边长越大我们需要的移动次数越少可行的可能性就越高相反边长越小需要移动的次数越多可行的可能性就越低。
这里有一个单调性因此我们可以二分最终的边长。问题转化为给定数轴上 n n n个点可以在数轴上放置一个区间要求所有点到达区间内的最小移动距离若该区间是一个点则是一个经典问题取中位数即可。
此题中不难发现最优选法区间的左端点或者右端点一定是其中某个点可以枚举所有情况然后利用二分与前缀和去优化计算距离
代码
#include bits/stdc.h
using namespace std;
typedef long long LL;
int n;
LL k;
const int maxn 2e5 5;
LL x[maxn], y[maxn], sx[maxn], sy[maxn];
LL calc(LL *p, LL *s, int mid){LL res 1e18;for (int i 1; i n; i){LL v 1ll * i * p[i] - s[i];int R p[i] mid;int l 1, r n;while (l r){int mid l r 1;if (p[mid] R)r mid;elsel mid 1;}if (p[r] R)v s[n] - s[r - 1] - 1ll * (n - r 1) * R;res min(res, v);}for (int i n; i; i--){LL v s[n] - s[i - 1] - 1ll * (n - i 1) * p[i];int L p[i] - mid;int l 1, r n;while (l r){int mid l r 1 1;if (p[mid] L)l mid;elser mid - 1;}if (p[r] L)v 1ll * r * L - s[r];res min(res, v);}return res;
}
LL check(LL value){LL v1 calc(x, sx, value), v2 calc(y, sy, value);return v1 v2 k;//v1v2k时返回1否则返回0
}
int main(){cin n k;for (int i 1; i n; i){cin x[i] y[i];}sort(x 1, x 1 n);sort(y 1, y 1 n);for (int i 1; i n; i){sx[i] sx[i - 1] x[i];sy[i] sy[i - 1] y[i];}LL l 0, r 1e9;while (l r) {int mid l r 1;if (check(mid))r mid;elsel mid 1;}cout r endl;return 0;
}学习交流
以下学习交流QQ群群号 546235402大家可以加群一起交流做题思路分享做题技巧欢迎大家的加入。
