【BZOJ3624】免费道路

这题大意是有n个点, 给你m条边,其中有一些是水泥路,另一些是鹅卵石路。让你取n-1条边,其中要有k条鹅卵石路,使它成为一棵生成树。

因为有两种路,所以肯定要有几条边是一定要取得,那就先将所有水泥路连边,接着再做生成树,则需要加的边肯定是在答案中的。

这时再判断必定要取的鹅卵石路是否大于k,若大于k则无答案。接着只要将剩下的点做生成树即可

NOIP2016普及组No.1

题目描述

输入
输出

输入

输出

下面是我个人的代码


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<cstdio>
 
using namespace std;
int n,i,a[4],b[4],c[4],x=1000000000;
int main()
{
cin>>n;
for (i=1;i<=3;i++)
{
cin>>a[i]>>b[i];
c[i]=n/a[i];
if (n%a[i]!=0) c[i]++;
c[i]*=b[i];
}
for (i=1;i<=3;i++)
if (c[i]<x) x=c[i];
cout<<x;
return 0;
}

首先这道题作为NOIP普及组第一题在历年来已经算是水到爆的了

明明很简单的一题 但是由于粗心大意 居然少拿了一个点

我很伤心 毕竟辜负了YY对我多年的教导 以及YY对我寄予的厚望

可怜YY一把屎一把尿地培养我 还有刘家昌学长给自己的加油鼓劲

我保证以后YY再抢我手机我一定不会马上抢回来 我过十分钟再抢

最后感谢YY 感谢信息组各位大佬 感谢校长 感谢我爸 感谢我妈 感谢CCTV 感谢国家 感谢世界对我的大力支持

树状数组及其应用

最近在学习位运算,正好把树状数组总结下,也算是能正式给 data structure 建个分类。

那么,树状数组到底有什么用呢?诚然,一样没什么卵用的东西我们学它干嘛。

下面举个树状数组的经典应用:区间求和。

假设我们有如下数组(数组元素从 index=1 开始):var a = [X, 1, 2, 3, 4, 5, 6, 7, 8, 9];

我们设定两种操作,modify(index, x) 表示将 a[index] 元素加上 x, query(n, m) 表示求解 a[n] ~ a[m] 之间元素的和。如果不了解树状数组(当然假设更不了解线段树等其他数据结构),你可能会很容易地写下如下代码:


1
2
3
4
5
6
7
8
9
10
11
12
var a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];

function query(n, m) {
  var sum = 0;
  for (var i = n; i <= m; i++)
    sum += a[i];
  return sum;
}

function modify(index, x) {
  a[index] += x;
}

Ok,复杂度为 O(1) 的删改和复杂度为 O(n) 的查询。如果数据量很大,这样反复的查询是相当耗时的。我们退一步想,如果只有 query(n, m) 这个操作,很容易想到用 sum 数组预处理前 n 项的和,然后用 sum[m] - sum[n-1] 获得答案。但是如果要修改 a[index] 的值,因为该项影响所有 index 之后的 sum 数组元素,所以如果这样做复杂度变为 O(1) 的查询和 O(n) 的删改,并没有什么卵用。

但是这个思路是美好的,我们可以用一个sum数组保存一段特定的区间段的值。假设我们有 a[1] ~ a[9] 9个元素,我们根据一个特定的规则:


1
2
3
4
5
6
7
8
9
sum[1] = a[1];
sum[2] = a[1] + a[2];
sum[3] = a[3];
sum[4] = a[1] + a[2] + a[3] + a[4];
sum[5] = a[5];
sum[6] = a[5] + a[6];
sum[7] = a[7];
sum[8] = a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7] + a[8];
sum[9] = a[9];

如果要求 a[1] ~ a[9] 的和,即为 sum[9] + sum[8],如果要求 a[1] ~ a[7] 的和,即为 sum[7] + sum[6] + sum[4] ,如果要改变 a[1] 的值,改变sum数组中和 a[1] 有关的项即可(即 sum[1] sum[2] sum[4] sum[8])。 这就是树状数组!实现了O(logn)的查询和删改。但是如何将a数组和sum数组联系起来?

来观察这个图:


令这棵树的结点编号为C1,C2...Cn。令每个结点的值为这棵树的值的总和,那么容易发现(如上所说):

C1 = A1
C2 = A1 + A2
C3 = A3
C4 = A1 + A2 + A3 + A4
C5 = A5
C6 = A5 + A6
C7 = A7
C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8

这里有一个有趣的性质:设节点编号为x,那么这个节点管辖的区间为 2^k(其中k为x二进制末尾0的个数)个元素。因为这个区间最后一个元素必然为Ax,所以很明显:Cn = A(n – 2^k + 1) + ... + An,算这个2^k有一个快捷的办法,定义一个函数如下即可(求解2^k即求二进制码右边第一位1的值):


1
2
3
int lowbit(int x) {
  return x & (-x);
}

当想要查询一个SUM(n)(求a[1]~a[n]的和),可以依据如下算法即可:

令 sum = 0,转第二步;
假如 n <= 0,算法结束,返回 sum 值,否则 sum = sum + Cn,转第三步;
n = n – lowbit(n),转第二步。
可以看出,这个算法就是将这一个个区间的和全部加起来。

那么修改呢,修改一个节点,必须修改其所有祖先,最坏情况下为修改第一个元素,最多有 log(n) 的祖先。所以修改算法如下(给某个结点i加上x):

当i > n时,算法结束,否则转第二步;Ci = Ci + x, i = i + lowbit(i) 转第一步。i = i + lowbit(i) 这个过程实际上也只是一个把末尾1补为0的过程。 对于数组求和来说树状数组简直太快了!

关于这部分的代码,将在下文树状数组的具体三大应用中给出。

关于树状数组,有一点需要注意,为了方便,树状数组的 a 数组基本都是从 index=1 开始的。

NOIP2016普及组T1买铅笔

水题,直接模拟。

代码块示例:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <algorithm>
using namespace std;

int work(int a, int b, int c)
{
  int ans = (c / a) * b;
  if (c % a) ans += b;
  return ans;
}

int main(void)
{
  int n;
  cin << n;
  int x, y, ans = 100000000;
  for (int i = 1;i &lt;= 3; i++) {
  cin >> x >> y;
  ans = min(ans, work(x, y, n));
  }
  cout << ans;
  return 0;
}

全国青少年信息学奥林匹克竞赛系列活动简介

宗旨:旨在向那些在中学阶段学习的青少年普及计算机科学知识;给学校的信息技术教育课程提供动力和新的思路;给那些有才华的学生提供相互交流和学习的机会;通过竞赛和相关的活动培养和选拔优秀计算机人才。

背景:1984年邓小平指出:“计算机的普及要从娃娃做起。”中国计算机学会于1984年创办全国青少年计算机程序设计竞赛(简 称:NOI),当年参加竞赛的有8000多人。这一新的活动形式受到党和政府的关怀,得到社会各界的关注与支持。中央领导王震同志出席了首届竞赛发 奖大会,并对此项活动给予了充分肯定。从此每年一次NOI活动,吸引越来越多的青少年投身其中。十几年来,通过竞赛活动培养和发现了大批计算机爱好者,选拔出了许多优秀的计算机后备人才。当年的许多选手已成为计算机硕士、博士,有的已经走上计算机科研岗位。

http://www.noi.cn/about/summary

继续阅读全国青少年信息学奥林匹克竞赛系列活动简介