Codeforces 948 数论推导 融雪前缀和二分check 01字典树带删除

A.

全部空的放狗

B.

先O（NLOGNLOGN）处理出一个合数质因数中最大的质数是多少

因为p1 x1 x2的关系是 x2是p在x1之上的最小倍数 所以x1的范围是[x2-p+1,x2-1]要使最后答案尽可能小 要包含尽可能多的选择

p0 x0  x1关系同上

#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  maxn = ;

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

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

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

//next_permutation

ll mod = 3e7;

int prime[];

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

void init()

{

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

        {

                if (prime[i])

                {

                        continue;

                }

                for (int j = i * ; j <= ; j += i)

                {

                        prime[j] = i;

                }

        }

}

int main()

{

        int n;

        init();

        cin >> n;

        int anser = INT_MAX;

        int now = prime[n];

        //cout << prime[n] << endl;

        int x1 = n - now + ;

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

        {

                if (!prime[i])

                {

                        continue;

                }

                anser = min(anser, i - prime[i] + );

                //cout << i - prime[i] + 1 << endl;

        }

        cout << anser << endl;

}

C.

前缀和题

作温度的前缀和

二分出第i块雪在第j天融化

#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 turn[][] = {{, }, { -, }, {, }, {, -}};

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

//next_permutation

ll mod = 3e7;

const int maxn=1e5+;

ll v[maxn];

ll t[maxn];

ll pre[maxn];

ll ans[maxn];

ll add[maxn];

int main()

{

       ll n;

       cin >> n;

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

       {

               scanf("%lld",v+i);

       }

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

       {

               scanf("%lld",t+i);

               pre[i]=pre[i-]+t[i];

       }

       pre[n+]=2e18+;

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

       {

               ll now=v[i]+pre[i-];

               int aim=upper_bound(pre,pre+n+,now)-pre;

               //cout<<aim<<endl;

               if(aim==n+)

                continue;

                add[aim]+=t[aim]-(pre[aim]-now);

                //cout<<t[aim]-(pre[aim]-now)<<endl;

                ans[aim]--;

       }

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

       {

               ans[i]+=ans[i-];

       }

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

       {

               ll anser=(ans[i]+i)*t[i]+add[i];

               cout<<anser<<" ";

       }

       cout<<endl;

}

D.01字典树带删除路径(用数组维护)

#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 turn[][] = {{, }, { -, }, {, }, {, -}};

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

//next_permutation

ll mod = 3e7;

const int maxn = 3e5 + ;

int n, m;

int ch[ * maxn][];

int sum[ * maxn];

int a[maxn];

int b[maxn];

int node_cnt;

inline void read(int &jqk)

{

        jqk = ;

        char c = ;

        int p = ;

        while (c < '' || c > '')

        {

                if (c == '-')

                {

                        p = -;

                }

                c = getchar();

        }

        while (c >= '' && c <= '')

        {

                jqk = (jqk << ) + (jqk << ) + c - '';

                c = getchar();

        }

        jqk *= p;

}

void Insert(int x)

{

        int cur = ;

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

        {

                int idx = (x >> i) & ;

                if (!ch[cur][idx])

                {

                        //ch[node_cnt][1] = ch[node_cnt][0] = 0;

                        ch[cur][idx] = ++node_cnt;

                }

                cur = ch[cur][idx];

                sum[cur]++;

        }

}

int getans(int x)

{

        int anser = ;

        int cur = ;

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

        {

                int idx = (x >> i) & ;

                if (!ch[cur][idx] || !sum[ch[cur][idx]])

                {

                        idx ^= ;

                        anser += ( << i);

                }

                cur = ch[cur][idx];

                sum[cur]--;

        }

        return anser;

}

int main()

{

        int n;

        read(n);

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

        {

                read(a[i]);

        }

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

        {

                read(b[i]);

                Insert(b[i]);

        }

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

        {

                cout << getans(a[i]) << " ";

        }

        cout << endl;

}