总述
题目网站:
http://oj.saikr.com/contest/19/problem
题目G
有n
个视频文件, 分别命名1.mp4,2.mp4,...,n.mp4
现在要将他们从小到大按字典序排序,并且删除掉其中的前50
个,现在请你告诉他,按照字典序排序的前50
个分别是谁呢?
Input
一行一个数字n
, 表示存在的视频个数
题目范围保证:50 < n <= 10^9
Output
一共50
行,每行一个字符串,分别为字典序第i
小的视频文件名,注意,这个文件名里需要包含.mp4
.
思路
原题:Leetcode 440. 字典序的第k小数字
按字典序进行DFS深搜,输出即可。
代码
#include <iostream>
#include <algorithm>
#include <unordered_map>
typedef long long LL;
using namespace std;
int n;
int cnt; //记录当前遍历到第几个数字
unordered_map<int, bool> q;
void work()
{
int p;
for (int i = 1; i <= 9; i++)
{
p = n;
int c = 1;
int j;
//先从当前位数开始,每一次不断往后加0输出
//1,10,100,...,1000000
for (j = i; j <= p; j *= 10, c *= 10)
{
if (q[j]) continue; //如果该数已被输出则跳过
q[j] = true; //标记数字,并输出
cnt++;
printf("%d.mp4\n", j);
if (cnt == 50) return;
}
//如果大于n,则进行回溯
if (j > p) j /= 10, c /= 10;
//从给定范围的最大长度开始,假设n = 15000
//则从10000开始, 用c存储这个数,l = 10000
for (int l = j; l > 1; l /= 10, c /= 10)
{
int k = 1;
j = l;
//从10001到20000,有9999个数字可以输出
//因此k < 10000
while (j < n && k < c)
{
j++;
k++;
//如果当前是10的倍数,则需要退一位输出
//10009 - 1001 - 10010
if (j % 10 == 0 && !q[j / 10])
{
printf("%d.mp4\n", j / 10);
cnt++;
if (cnt == 50) return;
}
//判断当前数字是否已输出
if (!q[j])
{
printf("%d.mp4\n", j);
cnt++;
if (cnt == 50) return;
}
}
}
}
}
int main()
{
scanf("%d", &n);
work();
return 0;
}
题目L
对于n个整数,n是一个2^x
的整数,来保证这个线段树是一棵满二叉树。
他现在想问你,每次给一段区间加上一个整数(每次操作对后续有影响),然后依次在线段树中选一个叶子节点,一直走到根节点,将一路经过的节点权值累加,问把每一个叶子节点选择一遍后的全部的总和是多少。
Input
第一行整数n,m
, 表示线段树维护的原序列的长度,询问次数。
第二行 n(1 <= n <= 2^17)个数,表示原序列。
接下来m(1≤m≤100000)行,每行三个数l,r,x
,表示对区间[l,r]
加上x
Output
共 m 行,表示查询的权值和。
样例输入
8 2
1 2 3 4 5 6 7 8
1 3 4
1 8 2
样例输出
720
960
思路
根据代码能看出来,
这是一棵线段树,
按样例: [1,8]
/ \
[1,4] [5,8]
/ \ / \
[1,2] [3,4] [5,6][7,8]
/\ /\ /\ /\
[1][2] [3][4] [5][6][7][8]
我们以1节点为例,选1叶子节点往上走到根节点,会把1的值重复4遍,
把所有叶子节点走完,会发现每个节点会重复走2^dep-1遍,dep是当前树的层数,
那么,我们只需要给当前数列的总值,乘上一个2^dep-1就是答案。
代码:
#include <iostream>
#include <cstdio>
typedef long long LL;
using namespace std;
//n和q为序列的长度和询问个数
//dep为树的高度
//ans为答案
//sum为原序列的总和
LL n, q, dep, ans, sum;
int main()
{
scanf("%lld%lld", &n, &q);
for (int i = 1; i <= n; i++)
{
LL x;
scanf("%lld", &x);
sum += x;
}
//求树的高度
LL x = n;
while (x)
{
x >>= 1;
dep++;
}
ans = sum * ((1 << dep) - 1);
//处理询问
while (q--)
{
LL l, r, x;
ans += (r - l + 1) * x * (1 << dep - 1);
printf("%lld\n", ans);
}
return 0;
}