离散化加差分求解
题目Covered Points Count
You are given n
segments on a coordinate line; each endpoint of every segment has integer coordinates. Some segments can degenerate to points. Segments can intersect with each other, be nested in each other or even coincide.
Your task is the following: for every k∈[1..n], calculate the number of points with integer coordinates such that the number of segments that cover these points equals k. A segment with endpoints li and ri covers point x if and only if li≤x≤ri.
Input
...
差分
题目题目:
输入一个长度为n的整数序列。接下来输入m个操作,每个操作包含三个整数l, r, c,表示将序列中[l, r]之间的每个数加上c。请你输出进行完所有操作后的序列。
输入格式
第一行包含两个整数n和m。第二行包含n个整数,表示整数序列。接下来m行,每行包含三个整数l,r,c,表示一个操作。
输出格式
共一行,包含n个整数,表示最终序列。
思路对一个区间内的数加C,如果暴力加,会浪费很多时间,我们可以开一个新数组用于差分操作,数组下标就代表数轴上的每一个数,每次给定一个区间,把以区间左端点未下标的数组值加上C,而以(区间右端点+1)为下标的数组值减去C,进行m次操作后,再求一次前缀和并加上原来数组的值就是进行区间操作后的数组,参考下图:
Code123456789101112131415161718192021222324#include<stdio.h>#include<iostream>#include<algorithm>using namespace std;int a[100],b[100]; //例题,开的很小,你可以开大int ...
二进制补码
这道题看百度上的题解把我看蒙了,想了半天没想通,直到我看见在计算机中负数是用补码来表示的,我才恍然大悟,咋把这个给忘了(抓狂)
题目蒜头君有一个 int\text{int}int 的整数,输出它的 323232 位二进制补码。
输入格式
一个整型整数。
输出格式
输出一行,即该整数的补码表示。
输出时每行末尾的多余空格,不影响答案正确性
样例输入:
7
样例输出
00000000000000000000000000000111
分析:做这道题就是明白一点:计算机中负数用补码来表示,因为整数补码是本身,所以这道题其实就是输出一个数在计算机中的二进制形式,超级简单了
code#include<iostream>
#include<stdio.h>
using namespace std;
int map1[110][110],map2[110][110];
int main()
{
int n;
cin>>n;
for(int i=31;i>=0;i--){
cout<<((n>>i) ...
进制转换模板
题目描述请你编一程序实现两种不同进制之间的数据转换。
输入格式
共三行,第一行是一个正整数,表示需要转换的数的进制n(2≤n≤16)n(2≤n≤16)n(2≤n≤16),第二行是一个n进制数,若n>10n>10n>10则用大写字母A−FA-FA−F表示数码10−1510-1510−15,并且该nnn进制数对应的十进制的值不超过100000000010000000001000000000,第三行也是一个正整数,表示转换之后的数的进制m(2≤m≤16)m(2≤m≤16)m(2≤m≤16)。
输出格式
一个正整数,表示转换之后的mmm进制数。
输入输出样例
输入 #1
16
FF
2
输出 #1
11111111
代码:#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string>
#include<math.h>
#include<vector>
using namespace std;
int change(ch ...
markdown语法
文章链接
总结如下标题在想要设置为标题的文字前面加#来表示一个#是一级标题,二个#是二级标题,以此类推。支持六级标题。
注:标准语法一般在#后跟个空格再写文字
字体
加粗
要加粗的文字左右分别用两个*号包起来
斜体
要倾斜的文字左右分别用一个*号包起来
斜体加粗
要倾斜和加粗的文字左右分别用三个*号包起来
删除线
要加删除线的文字左右分别用两个~~号包起来
引用在引用的文字前加>即可。引用也可以嵌套,如加两个>>三个>>>n个…貌似可以一直加下去,但没神马卵用
效果如下:
这是引用的内容
这是引用的内容
这是引用的内容
分割线三个或者三个以上的 - 或者 * 都可以。
实例:
---
----
***
*****
图片语法:
![图片alt](图片地址 ''图片title'')
图片alt就是显示在图片下面的文字,相当于对图片内容的解释。
图片title是图片的标题,当鼠标移到图片上时显示的内容。title可加可不加
上传本地图片直接点击导航栏的图片标志,选择图片即可markdown格式追求 ...
Sakura Theme美化
https://www.jianshu.com/p/e378b320c184超级详细的一个网址
容斥原理
今天学习了容斥原理,感觉智商又一次遭到了蹂躏(eoe),百度了CSDN上面的讲解,感觉讲的都不是很详细(或许真的是我笨吧,哎~),还是结合题目来讲吧,上题:
I - Co-prime
Given a number N, you are asked to count the number of integers between A and B inclusive which are relatively prime to N.Two integers are said to be co-prime or relatively prime if they have no common positive divisors other than 1 or, equivalently, if their greatest common divisor is 1. The number 1 is relatively prime to every integer.
Input
The first line on input contains T (0 < T <= 100) the ...
快读快写
应用一些题目需要读取的数据量十分庞大,很可能读取数据次数高达几十万次,而这时用cin或者scanf时间上就有了一些差距(scanf比cin要快),当输入数据更加庞大,scanf时间上也有些乏力,毕竟有些题目就是考你会不会快读快写,C语言输入输出字符时是要比数字输出的快的,我们可以利用这一点来把数字转化成字符来输出
下面的inline是内联函数的意思,小伙伴可以看 https://blog.csdn.net/hyqsong/article/details/51857833 了解一下
快读代码inline int read(){
int x=1,y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') x=-1; ch=getchar(); //这里的循环是为了避免输入数字之前的空格造成影响
}
while(ch>='0'&&ch<=' ...
查并集
查并集也是一种比较常用的算法,有必要掌握下面文章转载于CSDN上的一篇博客,我觉得写的很详细,就把它贴出来吧地址:https://blog.csdn.net/Hacker_ZhiDian/article/details/60965556
基础
对于今天要总结的算法,我想先通过一道题目来看一下:
假设现在我有一个任务交给你:要求你查看 id 为 x 和 id 为 y 的两个人是不是朋友,在一开始我会在第一行中输入 3 个数字 n、m 、k。n 是代表总人数。接下来 m 行,每一行我会输入两个数字: Xi 、 Yi, 代表 id 为 Xi 和 id 为 Yi 的两个人是朋友(注意:朋友的朋友也是朋友), 接下来 k 行,每一行我也会输入两个数字: a 和 b ,代表我要你查询 id 为 a 和 id 为 b 的两个人是不是朋友, 如果这两个人是朋友,那么在一行中输出“yes”否则在一行中输出“no”。 数据约束:0 < n, m, k < 10000, 所有人的 id 都是正整数,并且 id 不会超过 n
样例输入:
7 5 4
1 3
2 4
3 4
1 4
5 6
1 ...
快速幂详解
原理先举个例子,比如说算3^6^,你要怎么算,用6个6相乘对不对,那要是3^1000^呢?1000个3相乘,复杂度为O(N),现在我们这样算,6的二进制是110,所以6=1(2^2^)+1(2^1^)+0(2^0^),那么3^6^就变成了3^( 1(2^2^)+1(2^1^)+0(2^0^) )=3^(1(2^2^)) 3^(1(2^1^))^ 3^(0*(2^0^))^,这其实就是快速幂的原理,看起来麻烦了对吗?OK,先不看复杂度,先看用代码如何实现,我们可以用一个数来充当3^(1*(2^2^))^、3^(1*(2^1^))^、3^(0*(2^0^))^,在下面的代码中y就是这个变量,不是每一次都要算的,比如3^(0*(2^0^))^=1,乘不乘都一样,那怎么判断呢?我们每次取二进制数的最后一位,要么是0要么是1,如果是0,就不用不用乘,否则就乘,先看代码:12345678910int p(int a,int b){ int t,y; //定义两个变量,t起到类乘的作用,而y则就是每一次要乘的数 t=1; y=a; //注意一定要初始化 while (b!=0 ...