【ICM Technex 2018 and Codeforces Round #463 (Div. 1 + Div. 2, combined) B】Recursive Queries
and Codeforces 2018 div round Queries recursive
2023-09-14 09:03:45 时间
【链接】 我是链接,点我呀:)
【题意】
【题解】
写个记忆化搜索。 接近O(n)的复杂度吧【代码】
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
int g[N+10];
int pre[N+10][20];
int f(int x){
int temp = 1;
while (x){
if (x%10!=0)
temp*=(x%10);
x/=10;
}
return temp;
}
int dfs(int x){
if (g[x]!=0) return g[x];
if (x<10){
return g[x] = x;
}else{
return g[x] = dfs(f(x));
}
}
int main(){
#ifdef LOCAL_DEFINE
freopen("rush_in.txt", "r", stdin);
#endif
ios::sync_with_stdio(0),cin.tie(0);
for (int i = 1;i <= N;i++)
if (g[i]==0) dfs(i);
for (int i = 1;i <= N;i++){
for (int j = 1;j <= 9;j++)
pre[i][j] = pre[i-1][j];
if (g[i]<=9) pre[i][g[i]]++;
}
int q;
cin >> q;
while (q--){
int l,r,x;
cin >> l >> r >> x;
cout<<pre[r][x]-pre[l-1][x]<<endl;
}
return 0;
}
相关文章
- 学习日志之synthesis and optimization(4)——banding and sharing
- A. The Fair Nut and Elevator (Codeforces Round #526 (Div. 2))
- ORA-01875: time zone minute must be between -59 and 59 ORACLE 报错 故障修复 远程处理
- ORA-02205: only SELECT and ALTER privileges are valid for sequences ORACLE 报错 故障修复 远程处理
- ORA-24082: propagation may still be happening for the schedule for QUEUE string and DESTINATION string ORACLE 报错 故障修复 远程处理
- ORA-32413: allow concurrent refresh of materialized view and truncate ORACLE 报错 故障修复 远程处理
- ORA-39361: Source time zone is string and target time zone is string. ORACLE 报错 故障修复 远程处理
- Revitalizing Your Database with SAE and MySQL(saemysql)
- Mastering Multicolumn Queries in MySQL: Tips and Tricks(mysql多列查询)
- Mastering the Art of Linux and Deleting Files Like a Pro(linuxand删除)
- Optimizing Data Storage and Retrieval with DSM MySQL(dsmmysql)
- Exploring the Power and Potential of Your Linux Box: A Comprehensive Guide(linuxbox)
- MySQL中AND的使用方法及含义解析(mysql中and的含义)
- Mysql中强大的AND运算符的使用方法探究(mysql中and的使用)
- MySQL中的AND和OR使用逻辑运算符优化查询语句(mysql中and与or)
- Oracle中使用除了And的其他查询关键字(oracle中除了and)
- and的区别Oracle数据库中的OR与AND的差异(oracle中or和)