题目链接:uva 10909 - Lucky Number
题目大意:定义Lucky Number, 给定一个数n,输出有两个差值最小Lucky Number,x和y,要求x+y=n。
解题思路:根据Lucky Number定义,用树状数组预处理出所有的Lucky Number,然后对于每个n,用二分找到最接近n/2的Lucky Number,然后去枚举。
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define lowbit(x) ((x)&(-x))
const int maxn = 2000000;
int N, fenw[maxn+5], vis[maxn+5], num[maxn+5];
void add (int x, int v) {
while (x <= maxn) {
fenw[x] += v;
x += lowbit(x);
}
}
int find (int k) {
int c = 0, p = 0;
for (int i = 20; i >= 0; i--) {
p += (1<<i);
if (p > maxn || c + fenw[p] >= k)
p -= (1<<i);
else
c += fenw[p];
}
return p + 1;
}
int init (int n) {
memset(fenw, 0, sizeof(fenw));
for (int i = 1; i <= maxn; i += 2)
add(i, 1);
n /= 2;
for (int i = 2; i <= n; i++) {
int l = find(i);
if (n < l)
break;
for (int j = l; j <= n; j += l)
vis[j] = find(j);
for (int j = l; j <= n; j += l)
add(vis[j], -1);
n -= n / l;
}
memset(vis, 0, sizeof(vis));
for (int i = 1; i <= n; i++) {
num[i] = find(i);
vis[num[i]] = 1;
}
return n;
}
void solve (int n) {
if ((n&1) == 0) {
int k = upper_bound(num + 1, num + 1 + N, n / 2) - num - 1;
while (k >= 1) {
if (vis[n - num[k]]) {
printf("%d is the sum of %d and %d.\n", n, num[k], n - num[k]);
return;
}
k--;
}
}
printf("%d is not the sum of two luckies!\n", n);
}
int main () {
N = init(maxn);
int n;
while (~scanf("%d", &n)) {
solve(n);
}
return 0;
}
分享到:
相关推荐
判断输入字符串是否为镜像或回文串。 来源于UVaOJ - 401. 水题。
开源项目-codingsince1985-UVa#uva-online-judge-solutions-in-golang.zip,两年来每天都在解决一个uva在线裁判问题,算起来…
使用:数组、哈希表、链表、二分搜索、动态规划、堆栈、堆、reedy、排序、树 DFS、BFS、图、二分搜索树、递归、记忆、队列、映射等。 我目前的统计 # 问题 解决方案 从 标签、笔记 1 Uva-ACM-ICPC 大批 2 Uva-ACM-...
UVA-11059 Maximum Product(动态规划-最大乘积子数组)Given a sequence of integers S = {S1, S2,
uva705 Slash Maze 的代码,在UVaOJ上通过
PDF试题
uva532 Dungeon Master的源代码,并且AC了
Algorithm-UVA-Solutions-in-Python.zip,python 3中各种uva(acm)问题的解决方案。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
这是UVA133 TheDoleQueue救济金发放问题,经典的算法问题。初学算法的人要对这种算法非常熟悉并且能熟练运用。