一.补题

第一次选拔赛

D题 类斐波那契数列

起初的想法是用三个数组来实现，一个放入全部整数n，另一个实现类斐波那契数列Fn，最后一个实现Gn，发现无法通过所有样例，原因是n的范围太大，运算后long long也装不下了。 通过打表发现每13个数为一个循环，应用规律可通过本题。

E题 下雨

通过图示可得，不下雨的地方是隔板向x轴的投影，也就是说，与y无关，只与每个隔板的x坐标的起止位置有关，通过一个初始为零的数组来实现，每个隔板的x坐标的起到止填入1，最后遍历数组统计1的个数，即得不会下雨的单位数。

二.暑期集训week1

A-B 数对

题目描述

出题是一件痛苦的事情！

相同的题目看多了也会有审美疲劳，于是我舍弃了大家所熟悉的 A+B Problem，改用 A-B 了哈哈！

好吧，题目是这样的：给出一串数以及一个数字 $CC$，要求计算出所有 $A-B=CA\; -\; B\; =\; C$ 的数对的个数（不同位置的数字一样的数对算不同的数对）。

输入格式

输入共两行。

第一行，两个整数 $N,CN,\; C$。

第二行，$NN$ 个整数，作为要求处理的那串数。

输出格式

一行，表示该串数中包含的满足 $A-B=CA\; -\; B\; =\; C$ 的数对的个数。

样例 #1

样例输入 #1

4 1
1 1 2 3

样例输出 #1

3

提示

对于 $75\mathrm{\%}75\backslash \%$ 的数据，$1\le N\le 20001\; \backslash leq\; N\; \backslash leq\; 2000$。

对于 $100\mathrm{\%}100\backslash \%$ 的数据，$1\le N\le 2\times 10^{5}1\; \backslash leq\; N\; \backslash leq\; 2\; \backslash times\; 10^5$。

保证所有输入数据绝对值小于 $2^{30}2^\{30\}$，且 $C\ge 1C\; \backslash ge\; 1$。

2017/4/29 新添数据两组

过题代码

#include <iostream>
#include<cstring>
#include<string>
#include<string.h>
#include<algorithm>
#include<map>
using namespace std;
long long b[200010];

int main()
{
    long long n,a,i,c=0;
    cin >> n >> a;
    for (i = 0; i < n;i++ )
    {
        cin >> b[i];
    }
    sort(b, b + n);

    for (i = 0; i < n; )
    {
        long long t = a + b[i];
        long long bcf = 1;
        for (long long j = i+1; j < n; j++)
        {
            if (b[j] == b[i]) bcf++;
            else break;
        }
        long long l = 0, r = n - 1, m,tr=0;
        while (l <= r)
        {
            m = (l + r) / 2;
            if(b[m]>=t)
            {
                tr =m; r = m - 1;
            }
            else
            {
                l = m + 1;
            }
        }
        if (b[tr] == t)
        {
            long long tcf = 1;
            for ( long long j = tr+1;  j < n;  j++)
            {
                if (b[j] == b[tr]) tcf++;
                else break;
            }
            c += tcf * bcf;
        }
        i += bcf;
    }
    cout << c;
    return 0;
}

思路为枚举A，B中的一个数、二分查找另一个数，检验两个数是否满足条件。 错误为忽略了数据范围，使用long long后解决。

[COCI 2011/2012 #5] EKO / 砍树

题目描述

伐木工人 Mirko 需要砍 $MM$ 米长的木材。对 Mirko 来说这是很简单的工作，因为他有一个漂亮的新伐木机，可以如野火一般砍伐森林。不过，Mirko 只被允许砍伐一排树。

Mirko 的伐木机工作流程如下：Mirko 设置一个高度参数 $HH$（米），伐木机升起一个巨大的锯片到高度 $HH$，并锯掉所有树比 $HH$ 高的部分（当然，树木不高于 $HH$ 米的部分保持不变）。Mirko 就得到树木被锯下的部分。例如，如果一排树的高度分别为 $20,15,1020,15,10$ 和 $1717$，Mirko 把锯片升到 $1515$ 米的高度，切割后树木剩下的高度将是 $15,15,1015,15,10$ 和 $1515$，而 Mirko 将从第 $11$ 棵树得到 $55$ 米，从第 $44$ 棵树得到 $22$ 米，共得到 $77$ 米木材。

Mirko 非常关注生态保护，所以他不会砍掉过多的木材。这也是他尽可能高地设定伐木机锯片的原因。请帮助 Mirko 找到伐木机锯片的最大的整数高度 $HH$，使得他能得到的木材至少为 $MM$ 米。换句话说，如果再升高 $11$ 米，他将得不到 $MM$ 米木材。

输入格式

第 $11$ 行 $22$ 个整数 $NN$ 和 $MM$，$NN$ 表示树木的数量，$MM$ 表示需要的木材总长度。

第 $22$ 行 $NN$ 个整数表示每棵树的高度。

输出格式

$11$ 个整数，表示锯片的最高高度。

样例 #1

样例输入 #1

4 7
20 15 10 17

样例输出 #1

15

样例 #2

样例输入 #2

5 20
4 42 40 26 46

样例输出 #2

36

提示

对于 $100\mathrm{\%}100\backslash \%$ 的测试数据，$1\le N\le 10^{6}1\backslash le\; N\backslash le10^6$，$1\le M\le 2\times 10^{9}1\backslash le\; M\backslash le2\backslash times10^9$，树的高度 ，所有树的高度总和 $>M>M$。

过题代码:

#include <iostream>
#include<cstring>
#include<string>
#include<string.h>
#include<algorithm>
#include<map>
using namespace std;
long long a[1000010];
int main()
{
    long long n,m,i;
    long long l=0, r =0,t,z;
    cin >> n>>m;
    for ( i = 0; i < n; i++)
    {
        cin >> a[i];
        if (a[i] > r)  r = a[i];
    }    
    while (l <= r)
    {
        z = 0;
        t = (l + r) >> 1;
        for ( i = 0; i < n; i++)
        {
            if(a[i]>t)
            z += a[i] - t;
        }
        if (z < m)
        {
            r = t - 1;
        }
        else 
            l = t + 1;
    }
    cout << l-1;
    return 0;
}

出现第二个二分解题的思想，即直接二分答案然后检验答案的合法性。设l为可能的最小答案，r为可能的最大答案，不断缩小区间得到最优解。

出现最小的最大值之类的字眼即可考虑使用二分答案的思想

烦恼的高考志愿

题目背景

计算机竞赛小组的神牛 V 神终于结束了高考，然而作为班长的他还不能闲下来，班主任老 t 给了他一个艰巨的任务：帮同学找出最合理的大学填报方案。可是 v 神太忙了，身后还有一群小姑娘等着和他约会，于是他想到了同为计算机竞赛小组的你，请你帮他完成这个艰巨的任务。

题目描述

现有 $m(m\le 100000)m(m\backslash le100000)$ 所学校，每所学校预计分数线是 $a_i(a_i\le 10^6)a\_i(a\_i\backslash le10^6)$。有 $n(n\le 100000)n(n\backslash le100000)$ 位学生，估分分别为 $b_i(b_i\le 10^6)b\_i(b\_i\backslash le10^6)$。

根据 $nn$ 位学生的估分情况，分别给每位学生推荐一所学校，要求学校的预计分数线和学生的估分相差最小（可高可低，毕竟是估分嘛），这个最小值为不满意度。求所有学生不满意度和的最小值。

输入格式

第一行读入两个整数 $m,nm,n$。$mm$ 表示学校数，$nn$ 表示学生数。

第二行共有 $mm$ 个数，表示 $mm$ 个学校的预计录取分数。第三行有 $nn$ 个数，表示 $nn$ 个学生的估分成绩。

输出格式

输出一行，为最小的不满度之和。

样例 #1

样例输入 #1

4 3
513 598 567 689
500 600 550

样例输出 #1

32

提示

数据范围：

对于 $30\mathrm{\%}30\backslash \%$ 的数据，$1\le n,m\le 10001\backslash leq\; n,m\backslash leq1000$，估分和录取线 $\le 10000\backslash leq10000$；

对于 $100\mathrm{\%}100\backslash \%$ 的数据，$1\le n,m\le 1000001\backslash leq\; n,m\backslash leq100000$，估分和录取线 $\le 1000000\backslash leq\; 1000000$。

过题代码：

#include <iostream>
#include<cstring>
#include<string>
#include<string.h>
#include<algorithm>
#include<map>
using namespace std;
long long a[100010], b;//录取线，估分
int main()
{
    long long i, m, n, z=0;
    cin >> m >> n;
    for ( i = 0; i < m; i++)	
        cin >> a[i];
    sort(a, a + m);
    for (i = 0; i < n; i++)
    {
        cin >> b;
        long long tar;
        tar = lower_bound(a, a + m, b) - a;
        if(tar==m)
        {
            z += b-a[m-1];
        }
        else
        {
            if (!tar)
                z += a[0] - b;
            else
                z += min(abs(a[tar] - b),abs(a[tar - 1] - b));
        }
    }
    cout << z;
    return 0;
}

使用了直接二分答案的思想，使用了STL容器的lower_bound( ),即二分查找给定范围大于等于目标值的数的地址，减去起始位置地址即得下标