首页 > 其他分享 >P6123 [NEERC2016] Hard Refactoring 题解

P6123 [NEERC2016] Hard Refactoring 题解

时间:2024-05-03 09:11:06浏览次数:18  
标签:输出 le 标记 题解 Hard ge 数组 NEERC2016

本题说白了,就是一道big模拟!!!

题意不再赘述,我们直接看思路。这里作者借鉴了某差分思想:

  1. 末尾加空格,用于判断最后一个条件;

  2. 若只有 \(\le\),对给出的数字和数组第一个进行标记。标记的时候要+32769,因为数组中不存在负数下标,以免越界;

  3. 若只有 \(\ge\),就标记给出的数字和数组最后一个;

  4. 若都有,就标记本条件中给出的数据对应的下标;

  5. 若错开(如,\(x \le 7 \ \&\& \ x \ge 4567\)),不标记;

  6. 若所有的输入条件都出现了错开(如,\(x \le 7 \&\& x \ge 4567\))的情况,就输出false

  7. 从头到尾扫一遍,若s一直不为0(除了最后一个),输出true

  8. 剩下的和区间一样,输出要做特殊处理:

  • 建一个bool,存的是true即为前面输出过,反之亦然;
  • 输出过的话,就先输出||再输出数据;

代码就不贴了

标签:输出,le,标记,题解,Hard,ge,数组,NEERC2016
From: https://www.cnblogs.com/cath20/p/18170931

相关文章

  • 5.2考试题解
    T1[NOIP2017提高组]时间复杂度大模拟……#include<bits/stdc++.h>#definelllonglongusingnamespacestd;intt,n,k,as,nw,tr,ed[105];intc[26],str[105],b[105];stringtim;stack<int>st;structAadd{strings,t,fr,ed;}ad[105];intdfs(intx){i......
  • P4921 题解
    linkHint:错排计数。\(ans_k=C_n^k\timesA_n^k\times2^k\timesg(n-k)\)\(g(i)\)代表\(i\)对情侣全部错开的方案数。解释一下\(ans_k\)的表达。我们从\(n\)对情侣中无序地抽出\(k\)对情侣,有序地放到\(k\)排座位上,这里的方案数是\(C_n^k\timesA_n^k\)。由于两个......
  • D2. Reverse Card (Hard Version)
    D2.ReverseCard(HardVersion)Thetwoversionsaredifferentproblems.Youmaywanttoreadbothversions.Youcanmakehacksonlyifbothversionsaresolved.Youaregiventwopositiveintegers$n$,$m$.Calculatethenumberoforderedpairs$(a,b)$......
  • UVA1362 Exploring Pyramids 题解
    题目传送门前置知识欧拉序|区间DP|乘法原理解法DFS序可近似理解为欧拉序,故考虑区间DP。设\(f_{l,r}\)表示\([l,r]\)对应的二叉树的个数,状态转移方程为\(f_{l,r}=\begin{cases}1&l=r\\[s_{l}=s_{r}]\times\sum\limits_{i=l+2}^{r}[s_{l}=s_{i}]\timesf_{......
  • Educational Codeforces Round 165 (Rated for Div. 2) C. Minimizing the Sum题解
    题意CodeforcesRound809(Div.2)D1.ChoppingCarrots(EasyVersion)给你两个整数\(n(1\len\le3e5),k(0\lek\le10)\),一个数组\(a(1\lea_i\le10^9)\)。你可以进行如下操作最多\(k\)次:选定一个数\(i(1\lei\len)\),让其变为相邻的数(变为\(a_{i-1},a_{i......
  • P1017 [NOIP2000 提高组] 进制转换 题解
    题目简述给定一个十进制数$n$,将其转换成一个$-R$进制数。题目分析十进制数转负进制,同样可以使用短除取余法,但是会出现余数为负的情况,例如$-11\div-2=5~\cdots\cdots-1$,此时我们可以用如下法方解决此问题:我们设被除数为$a$,除数为$b$,余数为$c$,商为$d$,其中$c<0$......
  • P2192 HXY玩卡片 题解
    题目简述给定一些$5$和$0$的数字,让你在其中选择一些数进行排列成为一个非负整数,使得这个数字能被$90$整除,且是所有满足条件的数中最大的一个,无解输出$-1$。题目分析如果一个数能被$90$整除,那么它一定能被$9$和$10$整除。能被$10$整除,那就说面答案的个位数一定......
  • [题解]P4597 序列 sequence
    P4597序列sequence是CF13CSequence的加强版,\(N\leq5*10^5\)。如果想了解\(O(N^2)\)的DP解法请看此文。给定\(N\)个数,每次操作可以选其中一个数\(+1\)或\(-1\)。请问要让这个数列不降,最少需要多少次操作?看到数据范围发现不能用\(O(N^2)\)的dp了,需要换一种思路。我们用类......
  • [题解]CF13C Sequence
    CF13CSequence给定\(N\)个数,每次操作可以选其中一个数\(+1\)或\(-1\)。请问要让这个数列不降,最少需要多少次操作?我们用DP解决。对\(a\)从小到大排序,存在\(c\)中。我们用\(f[i][j]\)表示让前\(i\)个元素满足条件,而且这些元素最大值不超过\(c[j]\)的最小操作次数。状态转移方......
  • 异或与区间加题解
    异或与区间加题解简要题意给定\(n,m,K,a_{1...n}\),和\(m\)个三元组\((x_i,y_i,z_i)\),定义\(calc(l,r)=a_l\bigoplusa_{l+1}\bigoplus...\bigoplusa_r\)。对于每个三元组\((x,y,z)\),对所有满足\(x\lel\ler\ley\,\calc(l,r)=K\)的区间\((l,r)\)内的每个数\(b......