#P4534. 第1题-指数退避
-
1000ms
Tried: 5
Accepted: 2
Difficulty: 5
所属公司 :
华为
时间 :2025年12月17日-非AI方向(通软&嵌软&测试&算法&数据科学)
-
算法标签>哈希表
第1题-指数退避
解题思路
-
先用哈希表统计数组每个值出现次数
freq[v](数组已排序但不影响,用哈希更快)。 -
对每个询问:
-
若
(x=0):(0^K=0)((K>=1)),所以只可能是(a=y)总数=峰值=freq[y] -
若
(x=1):(1^K=1),所以只可能是(a=y+1)总数=峰值=freq[y+1] -
若
(x>=2):(x^K)严格递增,只需枚举(K=1,2,3......),不断乘 (x) 得到幂p:- 若
p + y > maxA则停止(maxA为数组最大值) - 累加
freq[p+y],并更新峰值 - 下一次令
p *= x,注意用“乘前判断”避免溢出:若p > (maxA - y) / x则下一次会超界,直接停
- 若
-
相关算法:哈希表计数、幂次枚举(指数增长)、溢出/上界剪枝。
复杂度分析
-
预处理建表:时间 (O(n)),空间 (O(n))(按不同值计数)。
-
每次询问:
- (x∈0,1) 为 (O(1))
- (x≥2) 枚举次数约为 (⌊logx(maxA−y)⌋+1),最坏在 (x=2) 时约 34 次(因为 (a[i]≤1010))
-
总体时间:(O(n+mlogmaxA)),本题约 (O(n+34m)),可通过。
-
总体空间:(O(n))
代码实现
Python
import sys
# 功能函数:返回每个询问的(总数, 峰值)
def solve(a, queries):
freq = {}
for v in a:
freq[v] = freq.get(v, 0) + 1
maxA = a[-1]
ans = []
for x, y in queries:
# x=0: 0^K=0(K>=1),只可能等于y
if x == 0:
c = freq.get(y, 0)
ans.append((c, c))
continue
# x=1: 1^K=1
if x == 1:
c = freq.get(y + 1, 0)
ans.append((c, c))
continue
# x>=2:枚举幂 p=x^K
total = 0
peak = 0
limit = maxA - y # 需要 p <= limit
if limit < 0:
ans.append((0, 0))
continue
p = x # K=1
while p <= limit:
v = p + y
c = freq.get(v, 0)
if c:
total += c
if c > peak:
peak = c
# 乘前判断,避免溢出/无意义循环
if p > limit // x:
break
p *= x
ans.append((total, peak))
return ans
def main():
input = sys.stdin.readline
n, m = map(int, input().split())
a = list(map(int, input().split()))
queries = [tuple(map(int, input().split())) for _ in range(m)]
res = solve(a, queries)
sys.stdout.write("\n".join(f"{t} {p}" for t, p in res))
if __name__ == "__main__":
main()
Java
import java.io.*;
import java.util.*;
public class Main {
// 功能函数:处理所有询问,返回二维数组 ans[i][0]=总数, ans[i][1]=峰值
static long[][] solve(long[] a, int[] xs, int[] ys) {
HashMap<Long, Integer> freq = new HashMap<>(a.length * 2);
for (long v : a) freq.put(v, freq.getOrDefault(v, 0) + 1);
long maxA = a[a.length - 1];
int m = xs.length;
long[][] ans = new long[m][2];
for (int i = 0; i < m; i++) {
int x = xs[i];
long y = ys[i];
if (x == 0) { // 0^K=0
int c = freq.getOrDefault(y, 0);
ans[i][0] = c;
ans[i][1] = c;
continue;
}
if (x == 1) { // 1^K=1
int c = freq.getOrDefault(y + 1, 0);
ans[i][0] = c;
ans[i][1] = c;
continue;
}
long limit = maxA - y; // 需要 p<=limit
if (limit < 0) {
ans[i][0] = 0;
ans[i][1] = 0;
continue;
}
long total = 0;
int peak = 0;
long p = x; // K=1
while (p <= limit) {
long v = p + y;
Integer c = freq.get(v);
if (c != null) {
total += c;
if (c > peak) peak = c;
}
// 乘前判断,避免溢出/越界
if (p > limit / x) break;
p *= x;
}
ans[i][0] = total;
ans[i][1] = peak;
}
return ans;
}
public static void main(String[] args) throws Exception {
FastScanner fs = new FastScanner(new BufferedInputStream(System.in));
int n = fs.nextInt();
int m = fs.nextInt();
long[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = fs.nextLong();
int[] xs = new int[m];
int[] ys = new int[m];
for (int i = 0; i < m; i++) {
xs[i] = fs.nextInt();
ys[i] = fs.nextInt();
}
long[][] ans = solve(a, xs, ys);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < m; i++) {
sb.append(ans[i][0]).append(' ').append(ans[i][1]).append('\n');
}
System.out.print(sb.toString());
}
// 简洁输入
static class FastScanner {
private final InputStream in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0, len = 0;
FastScanner(InputStream is) { in = is; }
private int read() throws IOException {
if (ptr >= len) {
len = in.read(buffer);
ptr = 0;
if (len <= 0) return -1;
}
return buffer[ptr++];
}
long nextLong() throws IOException {
int c;
do c = read(); while (c <= ' ' && c != -1);
long sign = 1;
if (c == '-') { sign = -1; c = read(); }
long x = 0;
while (c > ' ') {
x = x * 10 + (c - '0');
c = read();
}
return x * sign;
}
int nextInt() throws IOException { return (int) nextLong(); }
}
}
C++
#include <bits/stdc++.h>
using namespace std;
// 功能函数:处理所有询问,返回(总数, 峰值)
static vector<pair<long long,int>> solve(const vector<long long>& a,
const vector<int>& xs,
const vector<int>& ys) {
unordered_map<long long,int> freq;
freq.reserve(a.size() * 2);
for (auto v : a) freq[v]++;
long long maxA = a.back();
int m = (int)xs.size();
vector<pair<long long,int>> ans(m);
for (int i = 0; i < m; i++) {
int x = xs[i];
long long y = ys[i];
if (x == 0) { // 0^K=0
int c = freq.count(y) ? freq[y] : 0;
ans[i] = {c, c};
continue;
}
if (x == 1) { // 1^K=1
long long v = y + 1;
int c = freq.count(v) ? freq[v] : 0;
ans[i] = {c, c};
continue;
}
long long limit = maxA - y; // 需要 p<=limit
if (limit < 0) {
ans[i] = {0, 0};
continue;
}
long long total = 0;
int peak = 0;
long long p = x; // K=1
while (p <= limit) {
long long v = p + y;
auto it = freq.find(v);
if (it != freq.end()) {
total += it->second;
peak = max(peak, it->second);
}
// 乘前判断,避免溢出/越界
if (p > limit / x) break;
p *= x;
}
ans[i] = {total, peak};
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<long long> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
vector<int> xs(m), ys(m);
for (int i = 0; i < m; i++) cin >> xs[i] >> ys[i];
auto ans = solve(a, xs, ys);
for (auto &p : ans) {
cout << p.first << ' ' << p.second << "\n";
}
return 0;
}
题目内容
服务器常用指数退避策略来避免网络拥塞,每次访问失败后,会大间隔间隔成倍后再访问,下次重试的间隔在最大间隔内随机化。小华作为测试人员模拟了一些输入,服务器后台可看到n个访问时间点,第i个为a[i](其中a[i]值可能重复)。现在他想知道对于一个数对(x[j],y[j]),满足a[i]=(x[j])K+y[j]的访问一共有多少个,峰值是多少?
注:K看可取任意正整数,峰值指K取某一整数时满足a[i]=(x[j])K+y[j]的数量的最大访问个数。
输入描述
第1行两个整数n,m,用空格隔开。表示有n个数,m次询问(1<=n<=100000,1<=m<=200000)。
第2行有n个数,用空格隔开,第i个数为a[i](1<=i<=n,1<=a[i]<=1000000000),从小到大排序。
从第3行到第m+2行,每行两个整数,用空格隔开,表示给定一个整数数对(x[j],y[j])(0<=x[i],y[j]<=10000000)
输出描述
m行,每行两个数,第j行回答询问对于(x[j],y[j]),可满足a[i]=(x[j])K+y[j](K取任意正整数)的数量一共有多少个,峰值为多少,用空格隔开。
样例1
输入
4 2
45 78 90 429981774
12 78
9 42561285
输出
2 1
1 1
说明
对于第一组询问,要满足a[1]=12K+78,当K取1.8时121+78=90=a[3],此时刻有1个访问。
128+78=429981774=a[4],此时刻有1个访问。因此一共2个,峰值为1。
对于第二组询问,要满足a[i]=9K+42561285,当K取9时99+42561285=429981774=a[4]。因此一共1个,峰值为1。
样例2
输入
11 3
2 3 4 5 5 6 7 7 9 16 17
2 0
2 1
0 7
输出
3 1
5 2
2 2
说明
对于第一组询问要满足a[1]=2K+0,当K取1,2,4时:
21+0=2=a[1],此时刻有1个访问
22+0=4=a[3],此时刻有1个访问
24+0=16=a[10],此时刻有1个访问
因此一共3个,蜂值为1。
对于第二组询问,要满足a[1]=2K+1的a[1],当K取1,2,3,4时:
21+1=3=a[2],此时刻有1个访问
22+1=5=a[4]=2[5],此时剪有2个访问
23+1=9=[9],此时充有1个访问
24+1=17=a[11],此时完有1个访问
因此一共5个,峰值为2
对于第三组询问要满足a(1)=0K+7的a抑,值只能为7。a[7]=a[8]=7,有两个数满足因此一共2个,峰值为2