10624 - Super Number
2024-10-13 21:05:04
题意:给出n到m的范围,求出一个数在前i位数组成的数字能被i整除。假设存在输出这个数,假设不存在。输出-1.
思路:回溯,每次放第i位,然后推断是否符合题意。这题踩着时间过去的2.6s(看了下别人的题解。能够降低取模次数来节省时间)。
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm> using namespace std; const int MAXN = 35; int arr[MAXN];
int n, m, flag; int mod(int d) {
int sum = 0;
for (int i = 0; i < d; i++) {
sum = (sum * 10 + arr[i]) % d;
}
return sum;
} int dfs(int cur) {
if (cur == m)
return true;
for (int i = 0; i <= 9; i++) {
arr[cur] = i;
if (cur < n - 1 || (cur >= n - 1 && !mod(cur + 1))) {
if (dfs(cur + 1))
return true;
}
}
return false;
} int main() {
int cas, t = 1;
scanf("%d", &cas);
while (cas--) {
scanf("%d%d", &n, &m);
flag = 0;
for (int i = 1; i <= 9; i++) {
arr[0] = i;
if (dfs(1)) {
flag = 1;
break;
}
}
printf("Case %d: ", t++);
if (flag) {
for (int i = 0; i < m; i++)
printf("%d", arr[i]);
printf("\n");
}
else
printf("-1\n");
}
return 0;
}
版权声明:本文博客原创文章,博客,未经同意,不得转载。
最新文章
- window.onload、DOMContentLoaded和$(document).ready()
- (转载)AppScan使用分享
- UI设计实战篇——利用Bootstrap框架制作查询页面的界面
- 【转】velocity 显示List和Map方法
- hdu Wooden Sticks
- JS中的className含义
- [转]Javascript 严格模式详解
- usb.ids
- 纯JavaScript实现HTML5 Canvas六种特效滤镜
- 上传Android或Java库到Maven central repository(转载)
- Bitmap 格式
- Javaweb分页功能简单实现
- Oracle实战笔记(第二天)
- 在阿里云上搭建 Spark 实验平台
- c语言:第二次作业,循环结构
- python——字符串格式化
- 在Eclipse中使用Maven jetty的debug模式
- 从源码编译InfluxDB
- [转]ssh和SSH服务(包含隧道内容)
- 训练 の Bessie的体重问题
热门文章
- a标签的背景图在ie8下不显示的问题
- cocos2d-x 3.1.1 学习笔记[2]Sprite 精灵
- Java EE (9) -- JDBC &; JTA
- HDU ACM 2845 Beans-&;gt;动态规划
- cocos2d-x 3.0游戏实例学习笔记 《跑酷》第一步--- 开始界面
- lucas定理解决大组合数取模
- Linux学习记录--命名管道通信
- 第1周 SQL Server 如何执行一个查询
- android 4.0 中出错 java.lang.UnsupportedOperationException
- VMware装ubuntu 进不去图形界面, 卡在Installing VMware Tools