【题解】Hello Winter Vacation Round #7
本文最后更新于 206 天前,其中的信息可能已经有所发展或是发生改变。

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

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;
}
文章标题:【题解】Hello Winter Vacation Round #7
文章链接:https://intmain0.com/90/
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。转载请注明出处
评论和私信会在第一时间回复。如果您觉得文章对您有帮助,可以点击文章右下角【分享】一下。您的鼓励是博主的最大动力!
暂无评论

发送评论 编辑评论


|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇