正文

Codeforces 912 质因数折半 方格数学期望

IP云
IP云V管理员/6 阅读
12/02
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

A

B 

#include <bits/stdc++.h>

#define PI acos(-1.0)

#define mem(a,b) memset((a),b,sizeof(a))

#define TS printf("!!!\n")

#define pb push_back

#define inf 1e9

//std::ios::sync_with_stdio(false);

using namespace std;

//priority_queue<int,vector<int>,greater<int>> que; get min

const double eps = 1.0e-10;

const double EPS = 1.0e-4;

typedef pair<int, int> pairint;

typedef long long ll;

typedef unsigned long long ull;

//const int maxn = 3e5 + 10;

const int turn[][] = {{, }, { -, }, {, }, {, -}};

//priority_queue<int, vector<int>, less<int>> que;

//next_permutation

ll Mod = ;

set<int> need;

map<int, bool> mp[];

vector<int> ans;

int main()

{

        ll n, k;

        cin >> n >> k;

        ll cnt = ;

        for (ll i = ; i >= ; i--)

        {

                if ((1LL << i)&n)

                {

                        cnt = i;

                        break;

                }

        }

        if (k == )

        {

                cout << n << endl;

        }

        else

        {

                cout << (1LL << (cnt + )) -  << endl;

        }

        return ;

}

D

每个点(i,j)在min(i,min(r,n-r+1))*min(j,min(r,m-r+1))个正方形内

这个点的贡献为number*在多少个正方形内/(n-r+1)/(m-r+1) 

#include <bits/stdc++.h>

#define PI acos(-1.0)

#define mem(a,b) memset((a),b,sizeof(a))

#define TS printf("!!!\n")

#define pb push_back

#define inf 1e9

//std::ios::sync_with_stdio(false);

using namespace std;

//priority_queue<int,vector<int>,greater<int>> que; get min

const double eps = 1.0e-10;

const double EPS = 1.0e-4;

typedef pair<int, int> pairint;

typedef long long ll;

typedef unsigned long long ull;

//const int maxn = 3e5 + 10;

const int turn[][] = {{, }, { -, }, {, }, {, -}};

//priority_queue<int, vector<int>, less<int>> que;

//next_permutation

ll Mod = ;

ll area;

ll chang, kuang;

ll n, m, r, k;

double anser = ;

map<ll, bool> mp[];

struct node

{

        ll x, y, sum;

        friend operator<(node a, node b)

        {

                return a.sum < b.sum;

        }

};

priority_queue<node> que;

ll judge(int x, int y)

{

        if (x == (n + ) /  && (n & ) && y == (m + ) /  && (m & ))

        {

                return ;

        }

        if ((x == (n + ) /  && (n & )) || (y == (m + ) /  && (m & )))

        {

                return ;

        }

        return ;

}

int main()

{

        cin >> n >> m >> r >> k;

        chang = min(r, n - r + ), kuang = min(r, m - r + );

        area = (n - r + ) * (m - r + );

        node cnt;

        cnt.x = (n + ) / , cnt.y = (m + ) / , cnt.sum = min(cnt.x, chang) * min(cnt.y, kuang);

        que.push(cnt);

        while (!que.empty() && k)

        {

                node cur = que.top();

                que.pop();

                ll number = judge(cur.x, cur.y);

                number = min(number, k);

                k -= number;

                anser += 1.0 * number * cur.sum / area;

                node todo;

                todo.x = cur.x - , todo.y = cur.y, todo.sum = min(todo.x, chang) * min(todo.y, kuang);

                if (todo.x >=  && todo.y >=  && mp[todo.x][todo.y] == )

                {

                        que.push(todo);

                        mp[todo.x][todo.y]++;

                }

                todo.x = cur.x, todo.y = cur.y - , todo.sum = min(todo.x, chang) * min(todo.y, kuang);

                if (todo.x >=  && todo.y >=  && mp[todo.x][todo.y] == )

                {

                        que.push(todo);

                        mp[todo.x][todo.y]++;

                }

        }

        printf("%.10f\n", anser);

}

E

给你一个大小为N(N<=16)的集合

然后再给你个N个质数 要求你求第K小的一个满足要求的数 一个数满足要求当且仅当其质因数都在集合内

二分搜索 分成两个集合各自乘积 然后从一个集合的number[0].size()开始 递减 从另外一个 number[1].size()开始递增 用一个cur来维护每个number[0][i]的贡献

因为当最坏的情况时后面的数比前面的大  所以折半的时候前面的集合要适当小一点不然会T 

#include <bits/stdc++.h>

#define PI acos(-1.0)

#define mem(a,b) memset((a),b,sizeof(a))

#define TS printf("!!!\n")

#define pb push_back

#define inf 1e9

//std::ios::sync_with_stdio(false);

using namespace std;

//priority_queue<int,vector<int>,greater<int>> que; get min

const double eps = 1.0e-10;

const double EPS = 1.0e-4;

typedef pair<int, int> pairint;

typedef long long ll;

typedef unsigned long long ull;

//const int maxn = 3e5 + 10;

const int turn[][] = {{, }, { -, }, {, }, {, -}};

//priority_queue<int, vector<int>, less<int>> que;

//next_permutation

ll Mod = ;

ll k;

ll limit = 1e18;

ll num[];

double anser = ;

vector<ll> number[];

void dfs(int l, int r, ll x, int pos)

{

        number[pos].push_back(x);

        for (int i = l; i <= r; i++)

        {

                if (limit / num[i] >= x)

                {

                        dfs(i, r, x * num[i], pos);

                }

        }

}

ll check(ll x)

{

        ll sum = ;

        ll cur = ;

        for (int i = number[].size() - ; i >= ; i--)

        {

                while (cur < number[].size() && number[][cur] <= x / number[][i])

                {

                        ++cur;

                }

                sum += cur;

        }

        return sum;

}

int main()

{

        int n;

        cin >> n;

        for (int i = ; i <= n; i++)

        {

                cin >> num[i];

        }

        sort(num + , num +  + n);

        cin >> k;

        //TS;

        dfs(, min(, n), , );

        dfs(min(, n) + , n, , );

        cout << number[].size() << "    " << number[].size() << endl;

        //TS;

        sort(number[].begin(), number[].end());

        sort(number[].begin(), number[].end());

        ll l = ;

        ll r = 1e18;

        while (l < r - )

        {

                ll mid = (l + r) >> ;

                if (check(mid) >= k)

                {

                        r = mid;

                }

                else

                {

                        l = mid;

                }

        }

        cout << r << endl;

}

相关阅读

目录[+]