Shirakami Ling

洛谷P3372【模板】线段树1题解。

洛谷 P6492 COCI 2010-2011 #6 STEP 题解。

题目 分析递归分析首先，看到这个题，我们可以先从样例入手分析。看样例，容易发现每次剩下的长方形的宽就是上次长方形的长减宽，长就是上一个长方形的宽。（如果宽比长大，换一下顺序就可以了） 那我们就容易想到这道题可以用递归来解决。每次传入剩下的长方形的长和宽就行了。 直到长和宽有一个是零就可以了。 到这里，我们就可以写出递归的代码了。 递归代码1234567891011121314151617181920212223242526272829303132333435363738394041424344#pragma GCC optimize(3)#include<bits/stdc++.h>using namespace std;unsigned int totX,totY;unsigned int RESULT;void clac(unsigned int x,unsigned int y){ if(x<y)//如果长比宽小，那就交换顺序，否则会出现负数 { swap(x,y); } if(x==0|| ...

关于背包问题的讲解。

题目： 题目背景今天大家返校参加考试，本来信心满满以为能拿400分自己再提交一下试试吧！ 题目描述又考试了，这次考试的人数特别多，每个人的学号很特别，是用字符串表示的（不超过 30 位），每次考试结束后，成绩统计是一件很重要的事情。 老师们都很关心学生的成绩，于是他们把学生的成绩按学号排列(字典顺序，学号全为 小写字母，从小到大排列)（不排成绩），并统计各个分数，及分数段的人数，以及满分人员 （满分要奖励 XXX 奖学金的）。 输入格式第一行：一个数 n （n<=130000 人）。 以下 n 行：每行两个信息，分别为学号，分数（1~150 分） 输出格式第一行：各个分数段（空格隔开）（例如 110 1120（见例样，不包括 150 分 的人数）。 第二行：各个分数段的人数（空格隔开，没有则输出 0）。 接下来的 n 行，分别为 n 个学生的学号，成绩，（空格隔开）。 再接下来的一行为满分的人的人数 x（如果没有则为 0）（保证 x 不超过 10000）。 接下来的 x 行为满分人的学号（如果 x 为 0 则为一行No）（按字典序从小到大排序）。 注意：一行若有多个数据， ...

运算符重载是怎么回事呢？运算符相信大家都很熟悉，但是运算符重载是怎么回事呢，下面就让小编带大家一起了解吧。 运算符重载，其实就是重载运算符，大家可能会很惊讶运算符怎么会重载呢？但事实就是这样，小编也感到非常惊讶。 这就是关于运算符重载的事情了，大家有什么想法呢，欢迎在评论区告诉小编一起讨论哦！

Floyd算法使用条件可以求出多源最短路，可以处理负权边的情况，但是不能出现负环。 时间复杂度O（n3） 讲解Floyed算法使用的是动态规划的方法。 只需要使用最简单粗暴的做法，将出发点、结束点、中转点都枚举一遍就可以了。 状态转移方程： 1d[i][j]=min(d[i][k]+d[k][j],d[i][j]) 这样，再写出Floyd算法的核心代码就很容易了。 另外需要注意的是：Floyd算法不能解决带有负权回路（或者叫负权环）的图，因为带有负权回路的图没有最短路。例如下面这个图就不存在1号顶点到3号顶点的最短路径。因为1->2->3->1->2->3->->1->2->3这样路径中，每绕一次1->-2>3这样的环，最短路就会减少1，永远找不到最短路。其实如果一个图中带有负权回路那么这个图则没有最短路。 核心代码1234for(k=1;k<=n;k++) //枚举中转点 for(i=1;i<=n;i++) //枚举起点 for(j=1;j<=n;j+ ...

题目问题描述离散化就是把无限空间（或非常大的空间）中有限的个体映射到有限的空间（较小空间）中去，以此提高算法的时空效率。通俗的说，离散化就是在不改变数据相对大小的条件下，对数据进行相应的缩小。 ####栗子 原始数据： 18 999 91 100000 0000 15 999 91 离散化后： 11 3 4 2 3 离散化有什么用处呢？有时候我们需要根据数值的大小开一个数组，由于数值很多，没办法开那么大的数组（大了会超内存限制的），但是数据的个数有限。 如：有500000个数字，他们的范围是0-2000000000，这样就满足离散化的条件。我们可以把这些数离散化，最小的缩小为1，大小相邻的依次增加1，这样所有的数的范围一定能缩小到1到500000之间，同时不改变相对大小关系。 ####任务 给你n个整数序列a[1],a[2],..,a[n]。请你在不改变相对大小关系的前提下进行离散化。 ####要求 1.离散化后，最小的数值为1。2.原序列中相同的数，离散后还应相同。3.大小相邻的两个数离散后相差为1。4.离散后序列相对位置不变。 ###输入 第一行n 原始数据的个数 。第二行n ...

##莫比乌斯反演相关 ###莫比乌斯函数 $$\mu(n)=\left{\begin{array}{ll}1 & \text { 若 } n=1 \(-1)^{k} & \text { 若 } n \text { 无平方数因数，且 } n=p_{1} p_{2} \ldots \ldots p_{k} \0 & \text { 若 } n \text { 有大于 } 1 \text { 的平方数因数。 }\end{array}\right.$$ 设f(n)、g(n)是两个数论函数，它们的狄利克雷乘积也是一个数论函数，其定义为： $$\begin{aligned}h(n)=& \sum_{d \mid n} f(d) g\left(\frac{n}{d}\right) \& d>0\end{aligned}$$若函数满足：$$f(n)=\sum_{d \mid n} g(d)=\sum_{d \mid n} g\left(\frac{n}{d}\right)$$则有$$g(n)=\sum_{d \mid n} \mu(d) f\left(\f ...

一、高精度计算 这一次课程主要讲了高精度加、减、乘。 首先，定义一个高精度的结构体，储存这个数字的长度、和这个数字本身。 123456789101112131415161718192021222324252627struct gaojing{ int n,z[2333]; gaojing() { n=1; memset(z,0,sizeof(z)); } void init() { scanf("%s",s+1); int l=strlen(s+1); reverse(s+1,s+l+1); n = l; for (int a=1;a<=n;a++) z[a] = s[a]-'0'; } void print() { for (int a=n;a>=1;a--) ...