ChenZQ's blog

第五课 动规A 最少末尾0思路首先末尾有 $0$，那么自然是要相乘的数中的因数包含 $2$ 和 $5$。 那么我们就可以预处理出输入矩阵中因数 $2$ 和 $5$ 的个数，然后在以此的基础上进行动态规划。 我们可以分别动态规划最少的 $2$ 和 $5$，然后取最小的就行了，因为一个 $2$ 对应一个 $5$ 才能凑成 $0$，那么最小值自然就是末尾 $0$ 的最小值了。 不过还有 $0$ 的特殊情况没有考虑。 如果一个矩阵有 $0$ ，那么乘积自然为 $0$ ，相当于一个末尾零。所以我们可以特判动态规划的结果，如果不走 $0$ 的路至少有一个末尾 $0$，那么就可以直接找到 $0$ 的位置，然后构造一条路径，如下图： 那么如果不走有 $0$ 的路径，我们就通过 $dp$ 状态回溯输出路径。 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778 ...

77274438eefb2a5029bfe1cf4d76922ded09ee68b835860537b758409c44ee3c447878a449127eb2bba53a8a4c217332866c2581e03541be019b8226b8a8815070cdfc0f3a0e597ba97845cf54209fab4efb1fafb63793eb82ab2e14ced98c5a2b4a9ca146e0fac984d075cc5ff24398761c7ef2dcf31f4d0b9b14982d08b410173c380cc0be3bf3f1c38952a22df3ec72d4eb89347d0d35cf92c43d6a720b66e52b3cc5e9036b99226c5b86de5823ebc267e90f38bff3ca8a7c53f130420fbcfdc8c4dfb26a6df50888e153d18a904b7acc06d7daf3c5c7c86769351adbff5ac1dd02c6f768090a8b9568278a404cb3b1d4b5c20e1bf2bb5 ...

dc2d2011ab63ccdd5ca21e70fc10417b01972298a0dbee1c02f97e06170d8a4d715704c4342003bb0234c0e8c8066b6b98434ce49ee7c627703198a705212f52323ad0e8d8e42c10f0df37de411726dedbc7d1957aa14897080d39326fb1a02adbb5f07ae7c87d123066aa2ff537027efb564f7183260f675487e51ad5cbd7676dfcc9e744cbf365c4db8d450e56f5ccaf189ebf34e31568b5f5889315cc4cb78fc458fe76fe0ede41cb5185db862a2b4d38a9a2b7ec5c669956165098a577138a7abeaf38774c739bc56b0dc29d78e09d8318b912148383ce7e3bc465275adfed9a9e3ba9930062f9c284bb0e63d559517cb4b34da650628 ...

第四课A 点到线段的距离题意在三维中有一个点和一条线段，问你点到线段的最近距离。 思路首先，线段上有一个唯一的点是与另一个点的距离是最小的。 而从这个点往两侧，距离会越大。 那么这条线从左往右的点到另外一个点的距离在坐标轴上就是条抛物线。 二分不能算出这种规律，我们要用三分。 三分就是使用两个类似 $mid$ 的东西，分别在区间的 $\frac {1}{3}$ 和 $\frac {2}{3}$ 处如果发现第一个指针的距离大于第二个指针的，我们就把第一个舍去，也就是抛弃 $\frac {1}{3}$ 的区间，如果第二个大于第一个同理。 这样就可以慢慢接近最近的那个点了。 三维距离可以用勾股定理算出来。 代码12345678910111213141516171819202122232425262728293031323334#include<bits/stdc++.h>using namespace std;struct node{ double x,y,z;};node a,b,p;const double eps=1e-6;double get(do ...

fd150dedd6e41107f6aa0e0af5a794d8f5c2ec396cdd424604b10b20c2edaf9ee580c97cdbb3f47feb3613720cc2635ea91f1ecdd98aa1ea72fd006314a4f160b1decc58229c3dd07c1a58400fc8d82e096c305e87694be738786e8dbfdb5211721699f131c299d62039595b738d8e5dc4b083806874443769be053096bcc9a5e921ce880f91a083f66433dd774d2b2f96035a0e71d6ce8b2ce5850a22912b4b935febfd4791301d8e1b88f03917be3a1ad0a3e455ccf110ae892ded2a53a952d279eec9cd82b7351f618846e9074815ec642405cb220c1d50c88d7263755404ceae06c8e6f1c92a1308cddbce023da8f86e854f9ffc7b173 ...

f410a65fd59156f33db67808447b7c2b0eba874dd2ee5249580e45391e1d972ea6f1b412b3b8cef421f8ddc8013e4b220286604b840ad9ac13fea325d56015457de7db8698b45af39d14b920904f654660f01f3ea1cc6eecb0ee15519a4d313f01ee055958c556ccdc0aeee4718b646b9f9512650bb43dfdc08ae78a08a3fb0032a4b0aaf301dac417c7ac4bd10bdc17996b71d2c445eb20c900dde87512cd30995d107576336ed45879ab325f65595f024731d8f42bedb393d8dc8c84a14b8ff80b3f7311ecef36447d446606981a32479f9eb2cb051d455b2c0a48d33e4579117377103633e38972bec96a87008aa21470f725f7c26af7b ...

带权并查集简介带权并查集是一种在维护 $f$ 数组的同时维护一个新数组，代表当前点到根的距离和。 A 两个团伙题意告诉你两个操作： 表示 x y不是同一个团伙 问你 x y是否是一个团伙 解法如果两人不是同一团伙，就合并，并且连一条权值为 $1$ 的边，更新点到根的和。 查询就看点到根的距离是否能被 $2$ 整除，能就说明是同一个团伙，否则不是。 代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include <bits/stdc++.h>using namespace std;const int N = 1000010;int f[N],sum[N];int n,m;int t;int find(int x){ if(x==f[x]) return x; int root=find(f[x]); sum[x]^=sum[f[x]]; return f[x]=root;}int main(){ scanf(" ...

周赛好题难题总结517周赛26期 div1晚间场第一场C题 吃饼干题目描述小海狸共有 $m$ 块饼干，编号从 $1$ 到 $m$。第 $i$ 块饼干需要 $a_i$ 分钟时间烘培，不需要一定连续 $a_i$ 分钟烘培一块饼干。 小海狸还有一份 $n$ 分钟的计划表，$d_i$ 表示第 $i$ 分钟小海狸能吃掉的饼干，$0$ 表示不能吃，吃饼干要花掉一分钟。 问吃掉饼干的最小分钟数，不能吃完输出 $-1$。 思路可以二分最小分钟数，然后从二分的分钟数从后往前枚举，可以定义一个变量表示当前的剩余时间，每次看还有没有时间能做完饼干并且当前能吃，就吃掉。最后看能不能吃 $m$ 块饼干。 代码12345678910111213141516171819202122232425262728293031323334#include <bits/stdc++.h>using namespace std;int n,m;int a[100010],b[100010];bool flag[100010];bool check(int mi){ int x=mi-1; for(int i ...

第七课倍增算法学习笔记A静态区间最小值查询题意有给你一个数组，给你两个下标，问你区间最小值。 解法我们可以设状态 $dp_{i,j}$ 表示 $i$ 位置往后 $2^j-1$ 个位置的最小值是多少。 而考虑到用二进制不能完全覆盖，假设要求出 $x$ 和 $y$ 之间的最小值，用二进制无法完全覆盖，则设 $k$ 为 $2^k < y - x + 1$ 满足要求的最大值，则区间最小值为 $min(dp_{x,k},dp_{y-(1<<k)+1,k})$，其实第二个就是在补充第一个为覆盖完整的区间。 而预处理出这样的一个 $dp$ 数组，我们可以将第二个下标为 $0$ 的先预处理，然后从第二个下标为 $1$ 的开始，而可以得出转移方程 $dp_{i,j}=min(dp_{i,j-1},dp_{i+(1<<(j-1)),j-1})$，因为是二进制，所以 $j-1$ 的这两段刚刚好平分 $i$ 到 $i+2^j$ 这段区间。 而得出 $k$，我们可以求出第 $i$ 个位置需要二的几次方才能够到（要小于）,可以利用递推思想，$f_i = f_{i& ...

第一课 STL入门A-统计数字1.题目内容、给定 $n$ 个数字，统计出现次数最多的。如果有多个数字出现次数都是最多的，从小到大输出。 2.问题思路可以用一个 map 统计出现过的数字，先用一个迭代器遍历一遍，找出最大值，然后再遍历一遍找出出现次数等于最大值的数。 3.考点map 的用法 map 的访问方式：map[idx]。 定义方式： map<数据类型,数据类型>。 迭代器：map<数据类型,数据类型>::iterator it=mp.begin()。 访问:it->first 指向 map 的第一个数据类型，it->second 指向第二个。 4.代码1234567891011121314151617181920212223242526#include<bits/stdc++.h>using namespace std;map<int,int> mp;int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;i++) { ...