P3372【模板】线段树1
洛谷P3372【模板】线段树1题解。
洛谷P6492 COCI 2010-2011 #6 STEP
洛谷 P6492 COCI 2010-2011 #6 STEP 题解。
20200608递归测试T2地盘划分题解
题目
分析递归分析首先,看到这个题,我们可以先从样例入手分析。看样例,容易发现每次剩下的长方形的宽就是上次长方形的长减宽,长就是上一个长方形的宽。(如果宽比长大,换一下顺序就可以了)
那我们就容易想到这道题可以用递归来解决。每次传入剩下的长方形的长和宽就行了。
直到长和宽有一个是零就可以了。
到这里,我们就可以写出递归的代码了。
递归代码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|| ...
关于各种背包问题
关于背包问题的讲解。
57级返校测试-T3-成绩单
题目:
题目背景今天大家返校参加考试,本来信心满满以为能拿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 ...
2020年3月8日NOIP课程知识整理
一、高精度计算
这一次课程主要讲了高精度加、减、乘。
首先,定义一个高精度的结构体,储存这个数字的长度、和这个数字本身。
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--) ...










