蓝桥杯——练习（3.8）_小蓝有 t 组询问,每次给定两个数字 l, r 你需要计算出区间中所有

蓝桥杯——练习（3.8）

算法训练 二进制数数

题目链接：http://lx.lanqiao.cn/problem.page?gpid=T536

资源限制

时间限制：1.0s 内存限制：256.0MB

问题描述

给定L,R。统计[L,R]区间内的所有数在二进制下包含的“1”的个数之和。
　　如5的二进制为101，包含2个“1”。

输入格式

第一行包含2个数L,R

输出格式

一个数S，表示[L,R]区间内的所有数在二进制下包含的“1”的个数之和。

样例输入

2 3

样例输出

3

数据规模和约定

L<=R<=100000;

解题思路

用s统计满足要求的个数，枚举从L到R的数据，用number暂时存放当时的值，对number的值进行处理，x存放number对2的余数，当x为1的时候，让s++，最后的s便是统计的数目。

代码

#include<iostream>
using namespace std;

int s=0;
int main()
{
	int L,R;
	cin>>L>>R;
	for(int i=L;i<=R;i++)
	{
		int number=i;
		while(number)
		{
			int x=number%2;
			number/=2;
			if(x==1)
			s++;
		}
	}
	cout<<s<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

视频学习——深度优先搜索练习

视频链接：https://www.bilibili.com/video/BV1jE411g76D?p=14

学习心得

• 深度优先（DFS，Depth-First Search）算法是最常见的搜索方法之一。

• 它从某个状态开始，不断地转移状态，直到无法继续，然后返回前一步的状态，继续换一种状态，如此不断重复，知道发现问题的解。

• 深度优先搜索顺序(不一定是字典顺序)，可以通过复杂度类 RNC 中的随机并行算法来计算。

题目练习 算法训练 安慰奶牛

题目链接：http://lx.lanqiao.cn/problem.page?gpid=T16

资源限制

时间限制：1.0s 内存限制：256.0MB

问题描述

Farmer John变得非常懒，他不想再继续维护供奶牛之间供通行的道路。道路被用来连接N个牧场，牧场被连续地编号为1到N。每一个牧场都是一个奶牛的家。FJ计划除去P条道路中尽可能多的道路，但是还要保持牧场之间 的连通性。你首先要决定那些道路是需要保留的N-1条道路。第j条双向道路连接了牧场Sj和Ej(1 <= Sj <= N; 1 <= Ej <= N; Sj!= Ej)，而且走完它需要Lj的时间。没有两个牧场是被一条以上的道路所连接。奶牛们非常伤心，因为她们的交通系统被削减了。你需要到每一个奶牛的住处去安慰她们。每次你到达第i个牧场的时候(即使你已经到过)，你必须花去Ci的时间和奶牛交谈。你每个晚上都会在同一个牧场(这是供你选择的)过夜，直到奶牛们都从悲伤中缓过神来。在早上 起来和晚上回去睡觉的时候，你都需要和在你睡觉的牧场的奶牛交谈一次。这样你才能完成你的 交谈任务。假设Farmer John采纳了你的建议，请计算出使所有奶牛都被安慰的最少时间。

输入格式

第1行包含两个整数N和P。

接下来N行，每行包含一个整数Ci。

接下来P行，每行包含三个整数Sj, Ej和Lj。

输出格式

输出一个整数, 所需要的总时间(包含和在你所在的牧场的奶牛的两次谈话时间)。

样例输入

5 6
10
10
20
6
30
1 2 5
2 3 5
2 4 12
3 4 17
2 5 15
3 5 6

样例输出

176

数据规模与约定

5 <= N <= 10000，N-1 <= P <= 100000，0 <= Lj <= 1000，1 <= Ci <= 1,000。

代码

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=100005; 
long long a[N];
long long total,mi;
int b[N];
int n,p;
const long long inf=0x3f3f3f3f;
struct P
{
	int s;
	int e;
	long long d;
};
P node[N];
bool cmp(P a,P b)
{
	return a.d<b.d;
}
int find(int x)
{
	return x==b[x]?b[x]:b[x]=find(b[x]);
}
void merge(int x,int y)
{
	int i=find(x);
	int j=find(y);
	if(i==j)return ;
	b[j]=i;
}
void Kruskal()
{
	int i;
	int a1,a2;
	for(i=1;i<=p;i++)
	{
		a1=find(node[i].s);
		a2=find(node[i].e);
		if(a1==a2)continue;
		total+=node[i].d;
		merge(node[i].s,node[i].e);
	}
}
int main()
{
	total=0;
	mi=inf;
	int i;
	cin>>n>>p;
	for(i=0;i<=n;i++)
	{
		b[i]=i;
	}
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
		mi=min(mi,a[i]);
	}
	P t;
	long long l;
	for(i=1;i<=p;i++)
	{
		cin>>node[i].s>>node[i].e>>l;
		node[i].d=l*2+a[node[i].s]+a[node[i].e];
	}
	sort(node+1,node+1+p,cmp);
	Kruskal();
	total+=mi;
	cout<<total<<endl;
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73