GVKun编程网logo

HDU - 5845 Best Division dp + 字典树（字典树详解）

28

在本文中，我们将带你了解HDU-5845BestDivisiondp+字典树在这篇文章中，我们将为您详细介绍HDU-5845BestDivisiondp+字典树的方方面面，并解答字典树详解常见的疑惑，

在本文中，我们将带你了解HDU - 5845 Best Division dp + 字典树在这篇文章中，我们将为您详细介绍HDU - 5845 Best Division dp + 字典树的方方面面，并解答字典树详解常见的疑惑，同时我们还将给您一些技巧，以帮助您实现更有效的2016"百度之星" - 资格赛（Astar Round1）（hdu5685（线段树、乘法逆元），hdu5686（大数），hdu5687（字典树），hdu5688）、2019 年牛客多校第一场 I 题 Points Division 线段树 + DP、2019HDU 多校第三场 Distribution of books 二分 + DP、@hdu - 6584@ Meteor。

本文目录一览：

HDU - 5845 Best Division dp + 字典树（字典树详解）

HDU - 5845 Best Division dp + 字典树（字典树详解）

HDU - 5845

dp[ i ] 表示分完前 i 段， 最多能分几段。

我们能得到一个n2的dp， 然后用字典树优化掉。

我用了一个multiset去维护删除， 但实际上因为dp值有单调性， 所有维护sz就够了。

换成c++卡内从卡过去的。

//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize(4)
//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
#include<set>
#define LL long long
#define LD long double
#define ull unsigned long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL,LL>
#define PLI pair<LL,int>
#define PII pair<int,int>
#define SZ(x) ((int)x.size())
#define ALL(x) (x).begin(),(x).end()
#define fio ios::sync_with_stdio(false); cin.tie(0);

using namespace std;

const int N = 1e5 + 7;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-8;
const double PI = acos(-1);

template<class T,class S> inline void add(T &a,S b) {a += b; if(a >= mod) a -= mod;}
template<class T,class S> inline void sub(T &a,S b) {a -= b; if(a < 0) a += mod;}
template<class T,class S> inline bool chkmax(T &a,S b) {return a < b ? a = b,true : false;}
template<class T,class S> inline bool chkmin(T &a,S b) {return a > b ? a = b,true : false;}

//mt19937 rng(chrono::steady_clock::Now().time_since_epoch().count());

const int LOG = 28;

int n,up,len;
int a[N];
int dp[N];

void read() {
    int p,q;
    scanf("%d%d%d",&a[1],&p,&q);
    for(int i = 2; i <= n; i++) {
        a[i] = (1LL * a[i - 1] * p + q) % 268435456;
    }
    for(int i = 1; i <= n; i++) {
        a[i] ^= a[i - 1];
    }
}

int trietot,Rt;

struct Trie {
    int ch[2],mx;
} tr[N * LOG];

multiset<int> mulset[N * LOG];

inline int newNode() {
    trietot++;
    tr[trietot].ch[0] = 0;
    tr[trietot].ch[1] = 0;
    tr[trietot].mx = -1;
    mulset[trietot].clear();
    return trietot;
}

void ins(int x,int val) {
    int u = Rt;
    for(int i = LOG - 1; i >= 0; i--) {
        chkmax(tr[u].mx,val);
        int v = tr[u].ch[x >> i & 1];
        if(!v) tr[u].ch[x >> i & 1] = newNode();
        v = tr[u].ch[x >> i & 1];
        u = v;
    }
    mulset[u].insert(val);
    chkmax(tr[u].mx,val);
}

void del(int u,int x,int val,int d) {
    if(d == -1) {
        mulset[u].erase(mulset[u].lower_bound(val));
        if(SZ(mulset[u])) tr[u].mx = *mulset[u].rbegin();
        else tr[u].mx = -1;
        return;
    }
    del(tr[u].ch[x >> d & 1],x,val,d - 1);
    tr[u].mx = max(tr[tr[u].ch[0]].mx,tr[tr[u].ch[1]].mx);
}

int query(int x) {
    int ans = -1;
    bool limit = true;
    bool ban = false;
    int u = Rt;
    for(int i = LOG - 1; i >= 0; i--) {
        if(limit) {
            int sml = x >> i & 1;
            int big = sml ^ 1;
            int smlv = tr[u].ch[sml];
            int bigv = tr[u].ch[big];
            if(!(up >> i & 1)) {
                u = smlv;
            }
            else {
                if(tr[smlv].mx >= tr[bigv].mx) {
                    limit = false;
                    u = smlv;
                }
                else {
                    chkmax(ans,tr[smlv].mx);
                    u = bigv;
                }
            }
        }
        else {
            chkmax(ans,tr[u].mx);
            ban = true;
            break;
        }
    }
    if(!ban) chkmax(ans,tr[u].mx);
    return ans;
}

void init() {
    tr[0].mx = -1;
    trietot = 0;
    Rt = newNode();
}

int main() {
    int T; scanf("%d",&T);
    while(T--) {
        init();
        scanf("%d%d%d",&n,&up,&len);
        read();
        ins(0,0);
        for(int i = 1,j = 0; i <= n; i++) {
            while(j + len < i) {
                if(dp[j] != -1) del(Rt,a[j],dp[j],LOG - 1);
                j++;
            }
            dp[i] = query(a[i]);
            if(dp[i] != -1) {
                dp[i]++;
                ins(a[i],dp[i]);
            }
        }
        if(dp[n] != -1) printf("%d\n",dp[n]);
        else puts("0");
    }
    return 0;
}

/*
*/

2016

2016"百度之星" - 资格赛（Astar Round1）（hdu5685（线段树、乘法逆元），hdu5686（大数），hdu5687（字典树），hdu5688）

Problem A

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5685

解题思路：

可以用线段树求解，但是数据有问题，前期一直re，不晓得哪里错了，看了讨论才知道，数据有问题，后期数据被更正过来。但是

在hdu交时，一直wrong，看别人比赛时的代码都是用乘法逆元做的，还以为自己的做法错了，后来好心人告知，hdu上的数据是比

赛时前期的数据，瞬间吐血。。。

AC代码（线段树）：

#include <iostream>
#include <cstdio>
#include <cstring>
#define lson id<<1
#define rson id<<1|1
using namespace std;

const int MOD = 9973;
const int N = 100005;
char str[N];
int ans = 0;

struct node{
    int l,r,val;
}tree[N<<2];

void build(int id,int l,int r){
    tree[id].l = l;
    tree[id].r = r;
    if(l == r){
        tree[id].val = str[l]-28;
        return ;
    }
    int mid = (l+r)>>1;
    build(lson,l,mid);
    build(rson,mid+1,r);
    tree[id].val = tree[lson].val*tree[rson].val%MOD;
}

int query(int id,int r){
    if(tree[id].l >= l && tree[id].r <= r)
        return tree[id].val;
    int mid = (tree[id].l+tree[id].r)>>1;
    if(r <= mid)
        return query(lson,r);
    if(l > mid)
        return query(rson,r);
    return query(lson,mid)*query(rson,r)%MOD;
}

int main(){
    int n;
    while(~scanf("%d",&n)){
        scanf("%s",str+1);
        int a,b,len = strlen(str+1);
        build(1,1,len);
        while(n--){
            scanf("%d%d",&a,&b);
            if(a < 1 || b > len){
                printf("%d\n",ans);
                continue;
            }//如果以后数据被更正过来，可不要此步。
            ans = query(1,a,b);
            printf("%d\n",ans);
        }
    }
    return 0;
}

AC代码（乘法逆元）：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MOD = 9973;
const int N = 100005;
char str[N];
int inv[MOD+5],no[N];

int main(){
    inv[1] = 1;
    for(int i = 2; i < MOD; ++i)
        inv[i] = inv[MOD%i]*(MOD-MOD/i)%MOD;
    int n;
    while(~scanf("%d",str);
        int len = strlen(str);
        no[0] = 1;
        for(int i = 0; i < len; ++i)
            no[i+1] = no[i]*(str[i]-28)%MOD;
        while(n--){
            int a,b;
            scanf("%d%d",&b);
            printf("%d\n",no[b]*inv[no[a-1]]%MOD);
        }
    }
    return 0;
}

Problem B

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5686

解题思路：

这题hdu数据也有问题，拿比赛时的代码交上去Wrong了，后来才发现这题数据也有问题，n可以等于0.。。。而且等于0时，是输出

一空行。。。

AC代码：

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        BigInteger[] dp = new BigInteger[205];
        dp[1] = BigInteger.ONE; dp[2] = BigInteger.valueOf(2);
        for(int i = 3; i <= 200; ++i)
            dp[i] = dp[i-1].add(dp[i-2]);
        Scanner sca = new Scanner(system.in);
        while(sca.hasNext()){
            int n = sca.nextInt();
            if(n == 0){
                System.out.println();
                continue;
            }
            System.out.println(dp[n]);
        }
    }
}

Problem C

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5687

解题思路：

这题题目不难，但是要注意一些细节，比如原来有hello，要你删除he后，剩下的前缀如果值为0了，也要被删除，这点注意好就行

了。（具体细节看deltrie这个函数）

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

struct node{
    int cnt;
    struct node *next[26];
    node(){
        cnt = 0;
        memset(next,sizeof(next));
    }
};

node *root = NULL;
char op[10],str[35];

void build(char *s){
    node *p = root;
    int l = strlen(s);
    for(int i = 0; i < l; i++){
        if(p->next[s[i]-''a''] == NULL){
            p->next[s[i]-''a''] = new node();
        }
        p = p->next[s[i]-''a''];
        p->cnt++;
    }
}

void del(node *root){
    for(int i = 0; i < 26; ++i){
        if(root->next[i] != NULL)
            delete(root->next[i]);
    }
    delete root;
}

void deltrie(char *s){
    int l = strlen(s);
    node *p = root;
    for(int i = 0; i < l; ++i){
        if(p->next[s[i]-''a''] == NULL)
            return ;
        p = p->next[s[i]-''a''];
    }
    int num = p->cnt;
    node *q;
    p = root;
    for(int i = 0; i < l; ++i){
        q = p->next[s[i]-''a''];
        q->cnt -= num;
        if(q->cnt == 0){
            del(q);
            p->next[s[i]-''a''] = NULL;
            return ;
        }
        p = p->next[s[i]-''a''];
    }
}

bool findtrie(char *s){
    node *p = root;
    int l = strlen(s);
    for(int i = 0; i < l; i++){
        if(p->next[s[i]-''a''] == NULL)
            return false;
        p = p->next[s[i]-''a''];
    }
    return true;
}

int main(){
    int n;
    while(~scanf("%d",&n)){
        root = new node;
        for(int i = 0; i < n; ++i){
            scanf("%s%s",op,str);
            if(op[0] == ''i'')
                build(str);
            else if(op[0] == ''d'')
                deltrie(str);
            else{
                if(findtrie(str))
                    puts("Yes");
                else
                    puts("No");
            }
        }
    }
    return 0;
}

Problem D

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5688

解题思路：

直接用map处理即可。。。

AC代码：

#include <iostream>
#include <cstdio>
#include <string>
#include <map>
#include <algorithm>
using namespace std;

map<string,int> ma;

int main(){
    int n;
    while(~scanf("%d",&n)){
        ma.clear();
        while(n--){
            string name;
            cin>>name;
            sort(name.begin(),name.end());
            printf("%d\n",ma[name]);
            ++ma[name];
        }
    }
    return 0;
}

2019 年牛客多校第一场 I 题 Points Division 线段树 + DP

2019 年牛客多校第一场 I 题 Points Division 线段树 + DP

题目链接

传送门

题意

给你 $n$ 个点，每个点的坐标为 $(x_i,y_i)$，有两个权值 $a_i,b_i$。 现在要你将它分成 $\mathbb {A},\mathbb {B}$ 两部分，使得在满足 “$\mathbb {A}$ 的点不能落在在 $\mathbb {B}$ 的点的右下方” 的条件下 $\sum\limits_{i\in\mathbb {A}} a_i+\sum\limits_{j\in\mathbb {B}} b_j$ 最大。

思路

这篇博客讲得很详细，大家可以看这位大佬的昂～

代码实现如下

#include <set>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;

typedef long long LL;
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pLi;
typedef pair<int, LL> pil;;
typedef pair<int, int> pii;
typedef unsigned long long uLL;

#define lson rt<<1
#define rson rt<<1|1
#define lowbit(x) x&(-x)
#define name2str(name) (#name)
#define bug printf("*********\n")
#define debug(x) cout<<#x"=["<<x<<"]" <<endl
#define FIN freopen("D://Code//in.txt","r",stdin)
#define IO ios::sync_with_stdio(false),cin.tie(0)

const double eps = 1e-8;
const int mod = 1000000007;
const int maxn = 1e5 + 7;
const double pi = acos(-1);
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3fLL;

int n;
vector<int> vec;
struct Point {
    int x, y, a, b;
    bool operator < (const Point& pp) const {
        return x == pp.x ? y > pp.y : x < pp.x;
    }
}point[maxn];

struct node {
    int l, r;
    LL mx, lazy;
}segtree[maxn<<2];

void push_up(int rt) {
    segtree[rt].mx = max(segtree[lson].mx, segtree[rson].mx);
}

void push_down(int rt) {
    LL x = segtree[rt].lazy;
    segtree[rt].lazy = 0;
    segtree[lson].lazy += x;
    segtree[rson].lazy += x;
    segtree[lson].mx += x;
    segtree[rson].mx += x;
}

void build(int rt, int l, int r) {
    segtree[rt].l = l, segtree[rt].r = r;
    segtree[rt].mx = segtree[rt].lazy = 0;
    if(l == r) return;
    int mid = (segtree[rt].l + segtree[rt].r) >> 1;
    build(lson, l, mid);
    build(rson, mid + 1, r);
}

void update1(int rt, int pos, LL val) {
    if(segtree[rt].l == segtree[rt].r) {
        segtree[rt].mx = val;
        return;
    }
    push_down(rt);
    int mid = (segtree[rt].l + segtree[rt].r) >> 1;
    if(pos <= mid) update1(lson, pos, val);
    else update1(rson, pos, val);
    push_up(rt);
}

void update2(int rt, int l, int r, LL val) {
    if(segtree[rt].l == l && segtree[rt].r == r) {
        segtree[rt].mx += val;
        segtree[rt].lazy += val;
        return;
    }
    push_down(rt);
    int mid = (segtree[rt].l + segtree[rt].r) >> 1;
    if(r <= mid) update2(lson, l, r, val);
    else if(l > mid) update2(rson, l, r, val);
    else {
        update2(lson, l, mid, val);
        update2(rson, mid + 1, r, val);
    }
    push_up(rt);
}

LL query(int rt, int l, int r) {
    if(segtree[rt].l == l && segtree[rt].r == r) {
        return segtree[rt].mx;
    }
    push_down(rt);
    int mid = (segtree[rt].l + segtree[rt].r) >> 1;
    if(r <= mid) return query(lson, l, r);
    else if(l > mid) return query(rson, l, r);
    else return max(query(lson, l, mid), query(rson, mid + 1, r));
}

int main() {
#ifndef ONLINE_JUDGE
FIN;
#endif // ONLINE_JUDGE
    while(~scanf("%d", &n)) {
        vec.clear();
        for(int i = 1; i <= n; ++i) {
            scanf("%d%d%d%d", &point[i].x, &point[i].y, &point[i].a, &point[i].b);
            vec.push_back(point[i].y);
        }
        sort(vec.begin(), vec.end());
        vec.erase(unique(vec.begin(), vec.end()), vec.end());
        sort(point + 1, point + n + 1);
        for(int i = 1; i <= n; ++i) {
            point[i].y = lower_bound(vec.begin(), vec.end(), point[i].y) - vec.begin() + 1;
        }
        int sz = vec.size();
        build(1, 0, sz + 1);
        for(int i = 1; i <= n; ++i) {
            LL num = query(1, 0, point[i].y);
            update1(1, point[i].y, num + point[i].b);
            update2(1, 0, point[i].y - 1, point[i].a);
            update2(1, point[i].y + 1, sz + 1, point[i].b);
        }
        printf("%lld\n", segtree[1].mx);
    }
    return 0;
}

2019HDU 多校第三场 Distribution of books 二分 + DP

2019HDU 多校第三场 Distribution of books 二分 + DP

题意：给你一个序列，你可以选择序列的一个前缀，把前缀分成 k 个连续的部分，要求这 k 个部分的区间和的最大值尽量的小，问这个最小的最大值是多少？

思路：首先看到最大值的最小值，容易想到二分。对于每个二分值 mid，我们判断原序列是否可以构成 k 个区间和小于等于 mid 的区间，这个可以用 DP 来做。我们先求出序列的前缀和，这样可以把区间和变成前缀相减的形式。之后，对于当前的前缀和 sum [i], 我们找前缀和大于等于 sum [i] - mid 的状态中 dp 值最大的向自己转移。如果最后存在状态的 dp 值大于等于 k，那么说明二分的 mid 值偏大，要缩小上边界。反之亦然。dp 用离散化 + 线段树优化，总复杂度 O (n * logn) * log (值域）

代码：

#include <bits/stdc++.h>
#define LL long long
#define ls (o << 1)
#define rs (o << 1 | 1)
using namespace std;
const int maxn = 200010;
LL sum[maxn];
LL a[maxn];
LL b[maxn];
int dp[maxn], mx[maxn * 4];
int n, m, tot;
void build(int o, int l, int r) {
	if(l == r) {
		mx[o] = -1;
		return;
	}
	int mid = (l + r) >> 1;
	build(ls, l, mid);
	build(rs, mid + 1, r);
	mx[o] = max(mx[ls], mx[rs]);
}
void update(int o, int l, int r, int p, int val) {
	if(l == r) {
		mx[o] = max(mx[o], val);
		return;
	}
	int mid = (l + r) >> 1;
	if(p <= mid) update(ls, l, mid, p, val);
	else update(rs, mid + 1, r, p, val);
	mx[o] = max(mx[ls], mx[rs]);
}
int query(int o, int l, int r, int ql, int qr) {
	if(ql > qr) return -1;
	if(l >= ql && r <= qr) {
		return mx[o];
	}
	int mid = (l + r) >> 1, ans = -1;
	if(ql <= mid) ans = max(ans, query(ls, l, mid, ql, qr));
	if(qr > mid) ans = max(ans, query(rs, mid + 1, r, ql, qr));
	return ans;
}
bool solve(LL mid) {
	build(1, 1, tot);
	update(1, 1, tot, lower_bound(b + 1, b + 1 + tot, 0) - b, 0);
	for (int i = 1; i <= n; i++) {
		int p = lower_bound(b + 1, b + 1 + tot, sum[i] - mid) - b;
		int p1 = lower_bound(b + 1, b + 1 + tot, sum[i]) - b;
		int tmp =  query(1, 1, tot, p, tot);
		if(tmp == -1) dp[i] = -1;
		else dp[i] = tmp + 1;
		if(dp[i] >= m) return 0;
		update(1, 1, tot, p1, dp[i]);
	}
	return 1;
}
int main() {
	int T;
//	freopen("input.txt", "r", stdin);
//	freopen("1.in", "r", stdin);
	scanf("%d", &T);
	while(T--) {
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= n; i++) {
			scanf("%lld", &a[i]);
			sum[i] = sum[i - 1] + a[i];
			b[i] = sum[i];
		}
		b[n + 1] = 0;
		sort(b + 1, b + 1 + n + 1);
		tot = unique(b + 1, b + 1 + n + 1) - (b + 1);
		LL l = -2e14, r = 2e14;
		while(l < r) {
			LL mid = (l + r) >> 1;
			if(solve(mid)) l = mid + 1;
			else r = mid;
		}
		printf("%lld\n", l);
	}
}

　　

@hdu - 6584@ Meteor

@hdu - 6584@ Meteor

[toc]

@description@

询问第 k 小的分子分母 ≤ n 的既约分数。

Input 第一行包含一个整数 T(T≤10^2)，表示数据组数。 接下来 T 行每行两个整数 n, k，表示一组询问。保证询问的答案在 (0,1] 范围内。

Output 输出 T 行，每行包含一个分数 p/q，要求 gcd(p, q) = 1。

Sample Input 5 4 6 5 1 9 9 3 4 7 11 Sample Output 1/1 1/5 1/3 1/1 3/5

Hint 杭电支持 __int128。

@solution@

寻找第 k 小，不难想到使用二分法。 则假如二分到一个值 x，≤ x 的既约分数可以用如下式子计算： $$ans = \sum_{i=1}^{n}\sum_{j=1}^{\lfloor x*i\rfloor}[gcd(i, j) = 1]$$

对其进行反演可得： $$ans = \sum_{i=1}^{n}\sum_{d=1}^{d|i}\mu(d)\lfloor\frac{xi}{d}\rfloor \ = \sum_{ab\le n}\mu(a)\lfloor xb \rfloor \ = \sum_{i=1}^{n}\mu(i)\sum_{j=1}^{\lfloor\frac{n}{i}\rfloor}\lfloor x*j\rfloor$$

后面那一项如果以 j 为横坐标，x 为常数，可以看成直线 y = x*j 下的整点数量，联想到类欧几里得算法。 但是 x 是个实数的话类欧几里得是不可行的。不过假如我们二分直接使用分数进行二分的话，就的确可以使用类欧几里得算法。 加上预处理莫比乌斯函数前缀和 + 整除分块的话，可以在 $O(\sqrt{n}*\log n)$ 的时间内完成一次计算。

实数二分需要一个迭代次数，那么我们多少次才能保证精度呢？ 假如 a/b 与 c/d 都是两个分子分母 ≤ n 的不相等的分数，则 a/b - c/d = (ad - bc)/(b*d) 最小时，分子 ad - bc = 1，分母 b*d = n*n。 所以精度的一个上限是 1/(n*n)，于是取 log(n*n) 次二分就可以保证精度。这样最大次数为 40。

下一个问题是，我们如何找到 > p/q 且最小的既约分数呢？ 我们可以在 SB tree（Stern-Brocot Tree）上进行寻找。这棵树在具体数学上有介绍它的性质，WC2019 上也有讲一点。 这里有一篇简略的博客。

我们这道题只需要知道 SB Tree 的生成方式，以及它的几个性质： （1）SB Tree 是一个既约分数的二叉搜索树。 （2）SB Tree 父亲的分母小于儿子的分母。 而这些足以让我们实现我们的目的。寻找答案的这个过程是 O(n)。

@accepted code@

#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
typedef long long ll;
const int MAXN = 1000000;
__int128 gcd(__int128 a, __int128 b) {return (b == 0) ? a : gcd(b, a % b);}
struct frac{
	__int128 a, b;
	frac(__int128 _a=0, __int128 _b=0):a(_a), b(_b) {}
	friend bool operator < (frac a, frac b) {return a.a*b.b < b.a*a.b;}
	friend frac operator + (frac a, frac b) {
		__int128 d = gcd(a.b*b.a + a.a*b.b, a.b*b.b);
		return frac((a.b*b.a + a.a*b.b)/d, a.b*b.b/d);
	}
	friend frac operator / (frac a, __int128 k) {return frac(a.a, k*a.b);}
};
int n; ll k;
bool search_answer(frac p) {
	frac ans = frac(1, 1), a = frac(0, 1), b = frac(1, 1);
	while( a.b + b.b <= n ) {
		frac c = frac(a.a + b.a, a.b + b.b);
		if( p < c )
			ans = b = c;
		else a = c;
	}
	printf("%d/%d\n", int(ans.a), int(ans.b));
}
ll smiu[MAXN + 5];
__int128 func(__int128 A, __int128 B, __int128 C, __int128 n) {
	if( A/C ) return func(A % C, B, C, n) + A/C*(n + 1)*n/2;
	if( B/C ) return func(A, B % C, C, n) + B/C*(n + 1);
	if( A == 0 ) return 0;
	__int128 m = (A*n + B) / C;
	if( m == 0 ) return 0;
	return m*n - func(C, C - 1 - B, A, m - 1);
}
ll check(frac x) {
	ll ans = 0; int p = 1, q = 1;
//	printf("? %d %d\n", int(x.a), int(x.b));
	while( p <= n ) {
		q = p, p = (n/(n/q));
		ll s = smiu[p] - smiu[q - 1];
		ans += s*func(x.a, 0, x.b, n/p);
	//	printf("! %lld\n", ans);
		p++;
	}
	return ans;
}
void solve() {
	scanf("%d%lld", &n, &k);
	int lim = log2(1LL*n*n) + 1;
	frac le = frac(0, 1), ri = frac(1, 1);
	for(int i=0;i<=lim;i++) {
		frac mid = (le + ri) / 2;
		if( check(mid) < k )
			le = mid;
		else ri = mid;
	}
	search_answer(le);
}
bool nprm[MAXN + 5];
void init() {
	for(int i=1;i<=MAXN;i++)
		smiu[i] = 1;
	for(int i=2;i<=MAXN;i++) {
		if( !nprm[i] ) {
			for(int j=i;j<=MAXN;j+=i) {
				nprm[j] = true;
				if( (j/i) % i == 0 )
					smiu[j] = 0;
				else smiu[j] *= -1;
			}
		}
	}
	for(int i=1;i<=MAXN;i++)
		smiu[i] += smiu[i-1];
}
int main() {
	init();
	int T; scanf("%d", &T);
	while( T-- ) solve();
}

@details@

算是还不错的一道题，不过涉及到的知识点比较冷门。。。 我才不会说理解类欧几里得算法花了我一个晚上的时间。

找答案的时候还不能在树上递归找，不然会爆栈。正确的操作是迭代找答案。

今天关于HDU - 5845 Best Division dp + 字典树和字典树详解的讲解已经结束，谢谢您的阅读，如果想了解更多关于2016"百度之星" - 资格赛（Astar Round1）（hdu5685（线段树、乘法逆元），hdu5686（大数），hdu5687（字典树），hdu5688）、2019 年牛客多校第一场 I 题 Points Division 线段树 + DP、2019HDU 多校第三场 Distribution of books 二分 + DP、@hdu - 6584@ Meteor的相关知识，请在本站搜索。

本文标签：

上一篇CLion 配置编译器 (MinGW)（clion配置编译环境）

下一篇$Poj1220/AcWing124 Number Base Convertion$ 进制转换+高精除（进制转换1248如何运用）

相关文章