/**//* 给出mx,my,w(1<= mx,my<=10^5, 1<= w <= 10^7) 求minimal{x*y},1<=x<=mx,1<=y<=my 使得[1x][1y]这个区域内满足 a*b = rev(a)*rev(b)的点的个数>=w 我能想到的是 先预处理出所有rev(a),从左到右扫描x,加进新的点(即所有满足x*b = rev(x)*rev(b),1<=b<=my) 然后二分y,找出满足w的最小的y 也想到将a*b = rev(a)*rev(b)变形为 a/rev(a) = rev(b)/b,但想不下去了, 不知怎么快速获取所有满足x*b = rev(x)*rev(b)(主要是因为a/rev(a)是浮点数,不知怎么用下标存) 看了别人的,用map<double,int>就可以了 →.→ 看了watashi的,是存分子分母(先用gcd约分一下) ------------------------------OMG
总体算法就是 从左到右扫描x,加入所有满足x*b = rev(x)*rev(b)的点 而满足这个条件的就是满足x/rev(x) = rev(b)/b的,由于之前已经存了mpy[(b,rev(b))] 满足上面式子点的个数就是mpy[(rev(x),x)]了 比较神奇的是,他在枚举x时,要获取满足>=w的y,不是二分y的,是通过微调的 -----------OMG 即若当前的x*y范围内的点>=w, y--; iw -= mpx[(rev(y),y)]; mpy[(y,rev(y))]--; 若<w,再补上去
第一次看到这样微调的,神奇丫~~~~~~~~~ y从my出发 一直保持iw>=w,微调至最接近w但>=w 整个过程,y肯定是递减的~~~ */ #include<iostream> #include<cstring> #include<map> #include<algorithm> #include<stack> #include<queue> #include<cmath> #include<string> #include<cstdlib> #include<vector> #include<cstdio> #include<set> #include<list> #include<numeric> #include<cassert> #include<ctime> #include<bitset>
using namespace std;
const long long INF = 12345678987654321LL; const int MAXN = 100100;
pair<int,int> r[MAXN];//(i, rev(i))
inline int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
inline int rev(int x) { int r = 0; while(x > 0) { r = r*10 + x % 10; x /= 10; } return r; }
pair<int,int> inv(pair<int,int> &p) { return make_pair(p.second, p.first); }
void init() { for (int i = 1 ; i <= 100000; i++) { int t = rev(i); int g = gcd(i,t); r[i] = make_pair(i/g, t/g); } }
int main() { #ifndef ONLINE_JUDGE freopen("in","r",stdin); #endif
init(); for (int mx,my,w; ~scanf("%d%d%d", &mx, &my, &w);) {
map<pair<int,int>, int> mpx, mpy; for (int y = 1; y <= my; y++) { mpy[r[y]]++; }
long long X = -1, Y = -1; long long iw = 0; for (long long x = 1, y = my; x <= mx; x++) {//y是从my出发的 iw += mpy[inv(r[x])]; mpx[r[x]]++; while(iw >= w) { iw -= mpx[inv(r[y])]; mpy[r[y]]--; y--; if(iw < w) { y++; mpy[r[y]]++; iw += mpx[inv(r[y])]; break; } } //一直保持着iw>=w,然后引进新的x时,尝试y-- //整个过程,y肯定是递减的~~~ if(iw>=w && (X == -1 || x*y < X*Y) ) { X = x; Y = y; } } if (X == -1) { puts("-1"); } else { printf("%I64d %I64d\n", X, Y); } } return 0; }
|
|
常用链接
随笔分类
Links
搜索
最新评论
|
|