开开心心写 - 个人主页动态

2021-08-12 18:47

void ST_create(){ for(int i = 1; i <= n; i++) F[i][0] = a[i]; int k = log2(n); for(int j = 1; j <= k; j++) for(int i = 1; i <= n - (1<<j) + 1; i++) F[i][j] = max(F[i][j-1], F[i+(1<<(j-1))][j-1]); } int ST_query(int l, int r){ int k = ...

0 点赞评论收藏

2021-04-27 23:13

已编辑

西北工业大学 Java

ACM - CQOI - 数三角形 - 数学 - 容斥原理

题目链接 思路：三角形 = 三点不共线求三角形个数 = 选择所有三点的方案（好算）- 三点共线的方案（不好算）三点共线的方案 = 横着共线的方案（好算）+ 竖着共线的方案（好算）+ 斜着共线的方案（不好算）其中，括号里写着好算的都是简单组合数。 那么现在来画图，在一个（n，m）的矩形之中，什么情况下连接主对角线和副对角线，会发生三点共线的情况？如图所示，红色箭头标注的线上就会存在三点共线。（注意，这是副对角线，左下、右上） 结论（1）：在（n，m）矩形之中，主、副对角线存在对称性，所以算一个就好，答案×2结论（2）：（n，m）矩形什么情况下，存在主、副对角线中三点共线情况？gcd(n,m)&...

0 点赞评论收藏

2021-04-16 15:49

西北工业大学 Java

ACM - 每日一题 - 4.9 线段树lazy

题目链接 主要是学习的前几个dalao的代码，整理了一遍自己的格式。注意好 lazy 标记。细节都在代码里。 #include <bits/stdc++.h> using namespace std; #define Lrt (rt << 1) #define Rrt (rt << 1 | 1) #define mid ((l + r) >> 1) const int N = 1e5 + 10; struct Tree{ bool lazy[26]; int w[26]; }tree[N<<2]; struct...

0 点赞评论收藏

2021-04-12 20:24

西北工业大学 Java

ACM - 牛客每日一题 - 4.13 - [HAOI2012]音量调节 - dp

题目链接在这儿：链接说明 题意：中文题 思路：为什么不能用深搜+减脂？尝试了一发，果然TLE了，因为理论上是2^50次方的运算。有一个小小减脂是：后缀和，如果当前的值加后面所有的值不超过当前记录的最大值，就返回。超时代码也贴一下： #include <bits/stdc++.h> using namespace std; const int maxn = 55; int n, k, m; int a[maxn]; int sumafter[maxn]; int flag; void dfs(int step, int sum){ if (sum + sumafter[...

0 点赞评论收藏

2021-03-30 16:00

西北工业大学 Java

ACM - CF - 1498B - Box Fitting - 数据结构+二分

题目链接 题意：n个木条，高度为1，长度都是2的次幂。问给定长度为L的方格，高度为1，最少需要多少个这样的方格可以把所有n个木条放进去？ 思路：每次放可以放的最大的！即，贪心。难点：比较当前格子的剩余量以及剩下木条的可用的最大值时，需要排序。排好了之后，每次放进去的木条应该是最接近剩下长度的。 举例：在样例1中，应该放：8+8，而不是8+4+2+1. vector<int> 可以排序，怎么解决贪心的问题：二分。upper_bound()：在有序数组中，找到用于在指定范围内查找大于目标值的第一个元素。lower_bound()：在有序数组中，找到用于在指定范围内查找不小于（大于等于...

0 点赞评论收藏

2021-03-19 13:15

已编辑

西北工业大学 Java

ACM - Sand Fortress - 二分

题目提交链接牛客提交链接CF提交链接 题意：输入：n和H。求一个数列。数列限制条件：（1）第一个数不超过H。（2）第i个和第i+1个数的差值的绝对值不超过1，且数列长度为无穷大。（3）数列中所有数的和为n输出：这个数列可能有很多情况。输出这个数列长度的最小值。 分析：数列长度最小，数列中所有的数的和一定 => 数列中的数尽可能大。（1） => 初值限制。（2） => 数有无穷多个，理解为结尾一定会出现 k，k-1，k-2，...，2，1 的情况。所以，“尽可能大” => 数列中的最大值尽可能大 => 给定数列中的最大值，判断在给定的限制条件下能得到该数列的最大值...

0 点赞评论收藏

2021-03-17 11:27

西北工业大学 Java

ACM - nowcoder [HNOI2004]打鼹鼠 - dp

题目链接 题意：中文题自己看 分析：（这个题最扯淡的是m的值是1e4，然后最暴力的 m^2 的 dp 能过）非常非常非常类似：最大不上升（下降）子序列。初始 dp[?] = 1然后往前看，如果位置 j 的数比位置 i 的数满足题意的条件，那么 dp 值更新。 本题一样因为机器人的初始位置可控：等价于，我们只需要管过程中的位置和终点位置，起点无所谓。意味着，对于当前 i，我们枚举之前的每一个 j，如果能到，那么就尝试 dp 更新。 能到 = 在给定的时间走到给定的位置。 代码。 #include<bits/stdc++.h> using namespace std; const ...

0 点赞评论收藏

2021-03-16 22:31

西北工业大学 Java

ACM - CF1490D - 递归

题目链接 题意：结合题目的图来看给定一个数组{3，5，2，1，4}.以该数组的最大数值作为根节点，左右依次二分递归，建立一棵二叉树。问，最终，这个数组中所有节点在这棵二叉树的深度。结合图示，答案为：1 0 2 3 1 思路：数据很小，n=100.每次找最大值的过程，可以直接for循环找，数据不大。那么，每次找到最大值之后，对左右两边都递归同样操作，深度增加即可。dfs标准姿势。边界数据就是到了单个叶子节点。 代码： #include <bits/stdc++.h> using namespace std; const int maxn = 150; int T; int a[...

0 点赞评论收藏

2021-03-15 17:45

西北工业大学 Java

ACM - 4743E - 线段树

题目链接 题目理解难度点：（1）每次改动不恢复，修改的状态保持。（2）对于一个给定的堆，堆中有i个石子，允许搬运j次。很容易猜想：要平均分配所有的石子，用数学方法可以证明。当j=2时，7=3+4=5+2=6+1,9+16 < 4+25 < 1+36.所以，类似贪心，而不是DP，初始化就可以把表格直接打好。（3）如何维护。线段树。每次修改第i堆的石子为j，跟搬运次数没有关系，那么就是单点修改，依次pushup修改总方案即可。 剩下的就是线段树模板。代码如下。 #include <bits/stdc++.h> using namespace std; typedef l...

0 点赞评论收藏

2021-03-15 17:53

已编辑

西北工业大学 Java

ACM - 牛客4743C - 三分

题目链接 题意：中文题 思路：三分。对于（a，b），不妨设：A=2a+3b，B=4a+b对于A装备来说，要想越多，那么消耗的b就很快。对于B装备来说，要想越多，那么消耗的a就很快。对于总数来说，A+B，那么一定存在“合理”分配，使得a和b的消耗比较平均。这个“合理”的方案，就是最大值，也就是三分中的极大值。所以，用函数图像思考：在左边，函数递增；在右边，函数递减。函数有极大值。 边界条件：考虑：calc(ml) <= calc(mr)首先注意这里一定带有等号，如果弄成 >= ，也一样 由于 ml 的函数值小，我们要求的是极大值，那么意味着，在[l,ml]的区间内，一定比 mr 的...

0 点赞评论收藏

2021-03-14 17:05

西北工业大学 Java

ACM - CF1059D 二分/三分

题目链接 题意：n个点，给定（Xi，Yi）的坐标，问：找到一个最小半径的圆，既与x轴相切，又包含所有的n个点。 边界条件：当n个点，既有出现在x轴上方的，又有出现在x轴下方的点时，不存在。当n个点，出现了至少两个点在x轴上时，不存在。画画图就能想明白。圆需要与x轴相切，必然与x轴只有1个交点。 二分做法：给定r，判断是否可行。 代码 #include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 20; int n; double x[maxn]; double y[maxn]; int ok(doub...

0 点赞评论收藏

2021-03-14 16:53

西北工业大学 Java

ACM - 晾衣服 - 二分

题目链接 题意：中文题自己看思考：二分标准框架：给定一个答案，用O（n）的时间遍历一遍，判断可行性 边界条件：题中限制了，bcde相互的大小关系，意味着，横着晒更占杆子长度，但是更快所以，对于每一件衣服单独考虑就好。在给定的时间内，如果能竖着晒，就竖着，因为更省杆子长度。如果不行，就横着。最后累加起来看，杆子放不放得下。 小技巧：预处理横着晒和竖着晒的时间。 代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 2e5 + 20; ll a[maxn]; ...

0 点赞评论收藏

2021-03-13 20:50

西北工业大学 Java

ACM - 位数差 - 分治二分

题目链接 官方题解 题意：中文题，自己看 样例解释：10个数0 ~ 9其中，1有9，2有8，9，以此类推，答案是1+2+3+4+4+3+2+1=20 思路分析：（1）为啥不能直接排序？再二分。举个例子。660 70 80 90 100 1106110 100 90 80 70 60这两组数据，按照题意，是不同的两组数据。拿（60，110）举例。在第一组，60和110，贡献1在第二组，110和60，贡献0所以，不能直接排序。注意：1<=i<j<=n.所以i，j的选取是讲顺序的 （2）为啥需要分治？这个简单。因为平方的算法超时。但是分治之后就降级成了nlogn的算法。 （3）...

0 点赞评论收藏

2021-03-13 12:56

西北工业大学 Java

ACM - CF - 1496B - 二分

CF题目链接 题意：给定一n个数的数组，数组元素不重复，给定k次操作。问：k次操作之后，数组中不重复的元素个数是多少。操作定义为：(max{} + mex{}) / 2向上取整。其中：max{}是数组中最大的数，mex{}是数组中第一个未出现的自然数。 样例解释：4 10 1 3 41次操作，mex{} = 2, max{} = 4, 添加3，答案是43 10 1 4 3 00 1 40次操作，答案是33 20 1 2两次操作，mex{}=3, max{}=2, 添加3；mex{}=4,max=3，添加4，答案是53 21 2 3两次操作，mex{}=0, max{}=3, 添加2，变成{1...

0 点赞评论收藏

2021-03-13 12:34

西北工业大学 Java

Black & White 题解

https://ac.nowcoder.com/acm/contest/893/F?&headNav=acm 题目链接在上 题意：给一串n位长度的0，1字符串，允许最多m次修改，即0改成1，1改成0，问：最终最长的连续相同的字符串可以是多少长度？ 样例解读：5 100101长度为5，修改1次，即把1改成0，变成00001，答案是42 101长度为2，修改1次，这就随便了，1改成0，或者0改成1，变成00，或11，答案是2 思路：要求最长，换个思路：告诉你有一段连续相同的字符串长度为x，能否在m次修改里，判断成功与否？可以。前缀和+for循环判断题意再转换：最长 即 x 最大二分。 前...

0 点赞评论收藏

关注他的用户也关注了：