首页 > 其他分享 >Codeforces Round 907 (Div. 2) B. Deja Vu(二分+后缀和+位运算)

Codeforces Round 907 (Div. 2) B. Deja Vu(二分+后缀和+位运算)

时间:2023-11-01 21:26:12浏览次数:54  
标签:tmp 907 int sum Codeforces mid Vu define size

Codeforces Round 907 (Div. 2) B. Deja Vu

思路:

预处理31位的 \(2^x\) 存在\(tmp_i\)

对于输入\(a_i\),通过查找最后一个二进制1位置,存在\(x0_i\)

由题意可知,对于输入的\(x\),如果有\(a_i\)可整除\(x\),则会使\(a_i\)加上\(2^{x-1}\)

所以之后除非是\(x-1\),否则无效,因此把输入\(x\)保存降序部分在vector

\(x\)从后往前,将\(2^{x_i}\)后缀和存在sum

对于\(a_i\),二分查找在\(x\)的第一个小于等于\(x0_i\)的位置

\(a_i\)加上后缀和

#define int long long
#define ld long double
#define pb push_back
#define pf push_front

using namespace std;

int t;
int tmp[32];
int a[100010];
int x0[100010];
vector<int>x;
deque<int>sum;

void ini()
{
    tmp[0] = 1;
    for (int i = 1; i <= 31; i++)
    {
        tmp[i] = tmp[i - 1] * 2LL;
    }
}

void ss(int f, int i)
{
    int cnt = 0;
    while (f)
    {
        if (f & 1)
        {
            x0[i] = cnt;
            return;
        }

        cnt++;
        f >>= 1;
    }
}

int check(int f)
{
    int l = 0, r = x.size() - 1;

    while (l < r)
    {
        int mid = (l + r) >> 1;

        if (x[mid] > f)
        {
            l = mid + 1;
        }
        else r = mid;
    }
    return sum[r];
}

void solve()
{
    x.clear();
    sum.clear();
    int n, q;
    cin >> n >> q;

    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];

        ss(a[i], i);
    }

    for (int i = 1; i <= q; i++)
    {
        int z;
        cin >> z;
        if (!x.size() || x[x.size() - 1]>z)
        {
            x.pb(z);
        }
    }

    for (int i = x.size()-1; i>=0; i--)
    {
        if (i == x.size() - 1)
        {
            sum.pf(tmp[x[i]-1]);
        }
        else
        {
            sum.pf(tmp[x[i] - 1] + sum.front());
        }
    }

    for (int i = 1; i <= n; i++)
    {
        if (x0[i]>=x[x.size()-1])
        {
            a[i] += check(x0[i]);
        }
        cout << a[i] << " ";
    }
    cout << endl;
}

signed main()
{
    ini();
    //t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }

    return 0;
}

标签:tmp,907,int,sum,Codeforces,mid,Vu,define,size
From: https://www.cnblogs.com/ikunhuaji/p/17804124.html

相关文章

  • 904-907 Prometheus自动发现机制 kube-state-metrics和metrics-server Prometheus监
    一、Prometheus自动发现机制服务发现机制:为了实现自动将被监控目标添加到PermethusPrometheus数据源的配置分为静态配置和动态发现,常见为以下几类:static_configs:静态服务发现,即将配置直接写到配置文件或Configmapfile_sd_config:文件服务器发现,创建一个专门配置target的配置文......
  • Codeforces Round 907 (Div. 2)
    CodeforcesRound907(Div.2)A.SortingwithTwos题意:给一个长度为n的数组,可以做任意次以下操作:选择一个整数m,将1-2m的数减1。若能使数组变为一个单调递增的数组则输出YES,否则输出NO分析:只需要保证2m+1-2m+1单调递增即可代码:#include<bits/stdc++.h>usingnamespace......
  • 【keng】 Vue2 多次传参进入同一页面 页面不走生命周期函数
    比如一个搜索跳转功能 搜索123进入页面加载数据再次搜索456 还是进入这个页面这个页面就不会走生命周期了 解决方案在App.vue上为router-view增加一个key 这个key就是随便写一个随机数就可以不要重复eg:  ......
  • Vue动态添加style样式
    最近在用uniapp开发安卓app,由于语法跟vue一致,就梳理了下动态添加style的方法:Object :style="{fontSize:fontSize+'px'}":style="{fontSize:(fontSize?fontSize:'12')+'px'}" Array :style="[baseStyles,otherStyle......
  • 如何在Vue组件中访问Vuex store中的状态?
    在Vue组件中访问Vuexstore中的状态,可以通过计算属性(computedproperties)或者直接通过$store.state来实现。下面是两种常见的方法:1:使用计算属性(computedproperties):在Vue组件中,定义一个计算属性来获取Vuexstore中的状态。计算属性会根据状态的变化自动更新。exportdefaul......
  • Vue 的最大的优势是什么?
    Vue作为一款轻量级框架、简单易学、双向数据绑定、组件化、数据和结构的分离、虚拟DOM、运行速度快,并且作者是中国人尤雨溪,对应的API文档对国内开发者优化,作为前端开发人员的首选入门框架Vue的优势:Vue.js可以进行组件化开发,使代码编写量大大减少,读者更加易于理解。Vue.j......
  • Vue学习
    tips-1vue组件的根标签只能有一个<div>正确示例如下:<template> <div> </div></template>错误示例如下:<template> <div> </div> <div> </div> <div> </div></template>tips-2资源路径获取在启动vue项......
  • vue 在模板/v-bind中使用方法methods 的问题
    每当渲染发生时,就会调用该方法并运行该函数。每次组件渲染时都会运行。模板中的函数调用会带来更大的性能成本。(相比computed)每次组件重新渲染时,vue模板中调用的函数都会执行。如果这些函数的计算成本很高,它们可能会降低应用程序的性能。你不希望这样,是吗?......
  • 前端vue学习中遇到问题
     在前端样式修改的过程中,发现样式不生效。后来知道是 scoped的原因Vue中的 scoped 属性可以将样式作用域限制在当前组件的范围内,避免全局污染。......
  • vue3 compositon api 和 common下写业务逻辑的区别
    区别:Vue3的CompositionAPI是一种处理和组织Vue组件内部逻辑的方式。它可以让你更灵活地组织和复用你的代码。使用compositionAPI可以将组件的逻辑拆分为小的、独立的函数或模块,并使用setup函数进行组合和重用。这对于一些复杂的业务逻辑或需要高内聚、低耦合的逻辑非......