前排感谢@范总、@黄总两位大佬的支持。

1.积木-5

给你 n 堆积木，第 i 堆积木有 a[i] 个，现在你需要处理以下两种操作： 1 X Y ：给第X堆的积木添加 Y 个，即a[X] += Y。 2 L R ：求出区间[L，R]内积木的最大值。

RMQ(Range Minimum/Maximum Query)模板题，使用线段树/ST算法。

2.吃饼干

有 m 块饼干，每天至少吃一块，至多全吃完，问总共有多少种吃法。

依据题意，我们很容易写出递归函数代码

void f(int m)
{
	if (m == 0)cnt++;
	for (int i = 1; i <= m; i++)
	{ 
		f(m - i);
	}
}

但是，本题最大输入为100，必定超时。该怎么办呢？我们观察本题较小数字的结果1——1、2——2、3——4、4——8、5——16。很容易观察得出本题的答案是2^(m-1)。

做到这里，本题的坑还没有结束，2的100次方三十多位，远远超过LLONG_MAX。此时需要使用高精度运算。

关于高精度运算的介绍：【高精度运算】高性能BigInt类 支持负数（内存优化版）

3.tql捕鱼-3

依旧是那个高端的捕鱼设备，tql 又来捕鱼了，这一次，鱼儿们决定在 n 行 n 列的海面中均匀分布，即每个格子中鱼的数量都相等。

tql 依然可以选择一个格子进行撒网，然后把这个格子所在行和所在列的鱼全部捕获，你有幸作为 tql 的小助手，负责清点 tql 每次捕获的鱼的数量。

注意：被捕获后，对应的格子就没有鱼了。

本题的数据量极大，故不可能使用数组记录鱼分布情况。依题意，在选择m行m列的格子后，同一行和同一列的鱼全部被捕，被捕的鱼的数量为2m-1只。在多次捕获后，选定的格子所在的行或列可能已经被捕获过所以没有鱼了，这又要另外统计。

一共有四种可能性：

1.选定的格子之前已经被选过，捕获的鱼的数量为0

2.选定的格子所在行被捕获过，捕获的鱼的数量为m减所在行被选定的格子数

3.选定的格子所在列被捕获过，捕获的鱼的数量为m减所在列被选定的格子数

4.选定的格子所在行和列均未被捕获过，捕获的鱼的数量为2m-1

  
int main()
{
        set<int>sx; set<int>sy;
	int n, m;
	cin >> n >> m;
	int cntx = n, cnty = n;
	while (m--) {
		int x, y;
		cin >> x >> y;
		int tx = sx.count(x);
		int ty = sy.count(y);
		if (tx && ty) {
			cout << 0;//选定的格子之前已经被选过，捕获的鱼的数量为0
		}
		else if (tx && ty == 0) {
			cout << n - sx.size();
		}
		else if (tx == 0 && ty) {
			cout << n - sy.size();
		}
		else{
			cout << 2 * n - 1 - sy.size() -sx.size();//选定的格子所在行和列均未被捕获过，捕获的鱼的数量为2m-1
		}
		sx.insert(x);
		sy.insert(y);
		cout << endl;
	}
}

4.派件问题-2

罗少有 n 件物品需要派送，但是他太懒了，于是他想找若干个小弟来帮忙。

已知每个小弟的服务费由两部分组成：跑腿费 s 元 + t * t 元，其中 t 代表这个小弟携带的物品件数。

请问罗少至少需要花多少钱才能把这 n 件物品派送完。

本题解析请移步《对极值问题的探索》。

5.质数问题

设 f(n) = 比 n 小的最大质数，现在给定两个正整数 L 和 R，求对于区间 [ L，R ] 内的每一个正整数 x，f(x) 之和。

线性筛+差分数组。

首先用线性筛筛出质数，可以得到prime数组（存放所有质数）。依题意易得，从prime[i]+1到prime[i+1]的比n小的最大质数都是prime[i]。我们只需要写双重循环给数组赋值就可以了。

for (int i = 1; i <= prime[0]; i++)
    {
        for (int num=prime[i]+1; num <= prime[i+1]; num++)visit[num] = prime[i];
    }

求区间内的和，需要用到差分数组，相关题目见链接，不再赘述。

直接上代码：

#include<iostream>
#include<string.h>
using namespace std;
typedef long long ll;
const int maxn = 1000035;
int prime[maxn];
ll visit[maxn];
void Prime() {
    for (int i = 2; i <= maxn; i++) {
        if (!visit[i]) {
            prime[++prime[0]] = i;
        }
        for (int j = 1; j <= prime[0] && i * prime[j] <= maxn; j++) {
            visit[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                break;
            }
        }
    }
}

int main()
{
    Prime();
    memset(visit, 0, sizeof(visit));
    for (int i = 1; i <= prime[0]; i++)
    {
        for (int num = prime[i] + 1; num <= prime[i + 1]; num++)visit[num] = prime[i];
    }
    for (int i = 1; i <= 1000007; i++) { visit[i] = visit[i - 1] + visit[i]; }
    int T; 
    cin >> T;
    while (T--)
    {
        int a, b;
        cin >> a >> b;
        cout << visit[b] - visit[a - 1] << endl;
    }
    return 0;
}

6.二进制拼接

将区间[L,R]之间的数字用二进制表示，并拼接成一段新的二进制数串，求这个二进制数串对应的十进制。

对于[L,R]之间数字i的拼接，可以分为两部分[L,i-1]和i来考虑。

设[L,i-1]的十进制为ans，[L,i]的结果就是ans<<k+i(ans的二进制后面接上i的二进制)，k是二进制下i的长度。怎么求k呢？

如何求k？

对于两个数字x,x-1,他们二进制下的位数无非是相同或者差1，当x是2的幂次方的时候，他们就相差1，所以我们就可以利用递推式，去累加位数k，那么这个题就转化成如何判断数字x是否是2的幂次方。

如何判断x是否是2的幂次方?

x&(x-1)是个很神奇的操作，他可以让你的最右边一位的1变成0，如果最后一位1变成0变成0了，说明他只有最左边的1，因此就是2的幂次方。

——Fanxw

#include<iostream>
#include<string.h>
using namespace std;
int main()
{
    int a, b;
    cin >> a >> b;
    int cnt = 0;
    int first = a;
    while (first)//求出第一个数多少位
    {
        cnt++;
        first >>= 1;
    }
    long long ans = a;
    for (int i = a+1; i <= b; i++)//从a+1个数开始算，而不是第a个数
    {
        if ((i & (i - 1)) == 0)cnt++;//i&i-1如果等于0，就说明二进制数位数+1
        ans <<= cnt;
        ans += i;
        ans %= 1000000007;
    }
    cout << ans << endl;
    return 0;
}