正文 

当前位置： 首页 > 程序 > java教程

2022百度之星程序设计大赛-初赛-第二场1001和(代码片段)

小哈里 小哈里     2022-12-01     178

关键词：

problem


solution

题意：

  • 给出长为n的序列，q次询问区间是否存在<=k个数之和>=x。
  • n,q < 1e5， k <10.

思路：

  • 因为要和>=x，所以让和尽可能大，即判断区间中最大的k个数之和是否大于x即可。
  • 即区间最大，倒数第2大，倒数第3大，倒数第k大之和即可，k<10，可以暴力。
  • 对于区间从小到大第x个数（即第x大的数），主席树板子即可，复杂度O(qklogn)。
#include<bits/stdc++.h>
using namespace std;
const int N = 100000 + 5;

int a[N], b[N], rt[N * 20], ls[N * 20], rs[N * 20], sum[N * 20];
int n, k, tot, sz, ql, qr, x, q, T;
int kk, xx;

void Build(int& o, int l, int r)
    o = ++ tot;
    sum[o] = 0;
    if(l == r) return;
    int m = (l + r) >> 1;
    Build(ls[o], l, m);
    Build(rs[o], m + 1, r);

void update(int& o, int l, int r, int last, int p)
    o = ++ tot;
    ls[o] = ls[last];
    rs[o] = rs[last];
    sum[o] = sum[last] + 1;
    if(l == r) return;
    int m = (l + r) >> 1;
    if(p <= m)  update(ls[o], l, m, ls[last], p);
    else update(rs[o], m + 1, r, rs[last], p);

int query(int ss, int tt, int l, int r, int k)
    if(l == r) return l;
    int m = (l + r) >> 1;
    int cnt = sum[ls[tt]] - sum[ls[ss]];
    if(k <= cnt) return query(ls[ss], ls[tt], l, m, k);
    else return query(rs[ss], rs[tt], m + 1, r, k - cnt);

void work()
    scanf("%d%d", &ql, &qr);
    int len = (qr-ql+1);
    int res = 0;
    for(int i = len; i > len-kk; i--)
        //从小到大第i个数
        int ans = query(rt[ql - 1], rt[qr], 1, sz, i); 
        res += b[ans];
    
    if(res >= xx)printf("Y\\n");
    else printf("N\\n");

int main()
    scanf("%d%d%d%d", &n, &q, &kk, &xx);
    for(int i = 1; i <= n; i ++) scanf("%d", a + i), b[i] = a[i];
    sort(b + 1, b + n + 1);
    sz = unique(b + 1, b + n + 1) - (b + 1);
    tot = 0;
    Build(rt[0],1, sz);
    for(int i = 1; i <= n; i ++)a[i] = lower_bound(b + 1, b + sz + 1, a[i]) - b;
    for(int i = 1; i <= n; i ++)update(rt[i], 1, sz, rt[i - 1], a[i]);
    while(q --)work();
    return 0;

2021年百度之星·程序设计大赛-初赛二1001签到（找规律，快速幂）(代码片段)

problem签到Accepts:6141Submissions:13643TimeLimit:2000/1000MS(Java/Others)MemoryLimit:32768/32768K(Java/Others)ProblemDescription给a,ba,b，每次a,ba,b会变为a+b,a-ba+b,a−b，问kk次之后变成了哪两个数 查看详情

2018“百度之星”程序设计大赛-初赛（a）(代码片段)

第二题还算手稳+手快？最后勉强挤进前五百（期间看着自己从两百多掉到494名）1001 度度熊拼三角  （hdoj6374）链接：http://acm.hdu.edu.cn/showproblem.php?pid=6374签到题 题意：给n根木棒求可以拼出的周长最长的三角形可以... 查看详情

2021百度之星初赛第二场1002.随机题意(贪心)(代码片段)

LINK对于aia_iai​,满足条件的bib_ibi​落在区间[ai−k,ai+k][a_i-k,a_i+k][ai​−k,ai​+k]中考虑对这些区间按左端点排序,问题转化为让最多的区间分配到点(一个点只能属于一个区间)考虑左端点最小的区间范围是[li,ri][l_i,r_i][li​,... 查看详情

2022百度之星程序设计大赛-复赛1001子序列(代码片段)

problem度度熊有一个大小为nn的整数数组a_1,a_2,\\cdots,a_na1​,a2​,⋯,an​。数组a_1,a_2,\\cdots,a_na1​,a2​,⋯,an​的一个子序列a_b_1,a_b_2,\\cdots,a_b_kab1​​,ab2​​,⋯,abk​​是非空的递增子序列当且仅当k\\geq1k≥1，且对于任意的i\\in[1... 查看详情

2017"百度之星"程序设计大赛-初赛（a）-1001.小c的倍数问题(hdu6108)1005.今夕何夕-蔡勒公式(hdu6112)

补完题？不存在的。这么久了，还是一条咸鱼，看一堆乱七八糟的东西，写一堆没用的水题，一点进步都没有，还是那么菜，菜的掉渣。这个百毒之星初赛A还会写两道最简单的水题，初赛B一点也不会，菜的难过。。。最近看的d... 查看详情

2017"百度之星"程序设计大赛-初赛（a）

2017"百度之星"程序设计大赛-初赛（A）hdu6108   求出n-1的因子个数即可#include<bits/stdc++.h>usingnamespacestd;#pragmacomment(linker,"/STACK:102400000,102400000")#definerep(i,a,b)for(inti=a;i<=b;++i)#de 查看详情

2018“百度之星”程序设计大赛-初赛（b）(代码片段)

degree  Accepts:1581  Submissions:3494 TimeLimit:2000/1000MS(Java/Others)  MemoryLimit:131072/131072K(Java/Others)ProblemDescription度度熊最近似乎在研究图论。给定一个有 NN 个 查看详情

2018“百度之星”程序设计大赛-初赛（b）(代码片段)

rank264，三题水过~hdu6380_degree#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintmaxn=200005;intin[maxn];intn,m,k;intmain()intt;scanf("%d",&t);while(t--)memset(in,0,sizeof(in) 查看详情

2018“百度之星”程序设计大赛-初赛（a）(代码片段)

度度熊拼三角  Accepts:2536  Submissions:4433 TimeLimit:2000/1000MS(Java/Others)  MemoryLimit:65536/65536K(Java/Others)ProblemDescription度度熊有 NN 根木棒，每根木棒的长度为a_ia? 查看详情

2021年百度之星·程序设计大赛-初赛二1004净化（模拟）(代码片段)

problemsolution//1004#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;constLLmod=998244353;constintmaxn=1e5+10;LLa[maxn];intmain() ios::sync_with_stdio(0),cin.tie( 查看详情

2020百度之星程序设计大赛初赛二(代码片段)

A.Poker(Hdu????)题目大意给定n个币，每次投至少m个，当投(x)个时，给回(lfloorx imes(1-p\%)floor)。问你最多能投多少次。解题思路很显然每次投(m)元是最优的，因为但凡投(m+1)元，给回的钱数不可能会增加二，要不不变要不减少。每次... 查看详情

hdu5253连接的管道(kruskal)(百度之星程序设计大赛-初赛)

连接的管道TimeLimit:2000/1000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):1323    AcceptedSubmission(s):519ProblemDescription老Jack有一片农田 查看详情

2021年百度之星·程序设计大赛-初赛二1005水题（贪心结论）(代码片段)

problemsolution开始还以为是CF987E，但是奇偶性并不一样，，结果是个贪心乱搞。。样例都没过交了能过，醉了。#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;intmain() ios::sync_with_stdio(0),ci 查看详情

2021年百度之星·程序设计大赛-初赛二1002随机题意（区间贪心）(代码片段)

problem随机题意Accepts:1411Submissions:3641TimeLimit:2000/1000MS(Java/Others)MemoryLimit:32768/32768K(Java/Others)ProblemDescription给一个整数数组a_1,a_2,\\cdots,a_na1​,a2​,⋯,an​和kk，你想要找到一个最大的值xx，使 查看详情

2017"百度之星"程序设计大赛-初赛（a）01，05，06

 小C的倍数问题   TimeLimit:2000/1000MS(Java/Others)  MemoryLimit:32768/32768K(Java/Others)ProblemDescription根据小学数学的知识，我们知道一个正整数x是3的倍数的条件是x每一位加起来的和是3的倍数。反之，如果一个数每一... 查看详情

hdu6114chess组合数（2017"百度之星"程序设计大赛-初赛（b））

ChessTimeLimit:2000/1000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):513    AcceptedSubmission(s):319ProblemDescription車是中国象棋中的一种棋 查看详情

2017"百度之星"程序设计大赛-初赛（a）

小C的倍数问题ProblemDescription根据小学数学的知识，我们知道一个正整数x是3的倍数的条件是x每一位加起来的和是3的倍数。反之，如果一个数每一位加起来是3的倍数，则这个数肯定是3的倍数。现在给定进制P，求有多少个B满足P... 查看详情

hdu6109数据分割并查集（2017"百度之星"程序设计大赛-初赛（a））

  数据分割TimeLimit:2000/1000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):1119    AcceptedSubmission(s):268ProblemDescriptio 查看详情