Codeforces Round #276 (Div. 1)_html/css_WEB-ITnose

这个场由于系统出问题 unrated了

题目都还挺短小精悍的

A

题目大意是

有n个询问(10^4)，每个询问是找出在[l,r]区间内二进制位1最多的数

l,r范围是10^18

然后就是贪心。 用 l 从低位往上贪就行了，0变1如果不超范围就变

long long l, r;int n;int main(){    scanf("%d", &n);    for(int i = 0; i   <br>  <br>  <p></p>  <p>B</p>  <p>给一个序列a，长度2*10^5，每个数的范围是10^6</p>  <p>然后问最大的a[i]%a[j]  其中要求的是a[i] >= a[j]</p>  <p>一看这个范围基本就是专卡nlognlogn的了</p>  <p>试了一下果然T了</p>  <p>然后有nlogn的做法</p>  <p>就是对任意的a[i]，标记为1，然后</p>  <p>从1到mx，扫一遍统计比当前数小的最大的a[i]是多少，其中mx应该是2000000</p>  <p>然后枚举，对每个数，枚举倍数</p>  <p>如果该数为x,倍数为y，  则去找比x * y小的最大的a[i]，用a[i] - x *(y -1) 就求出了一个可能的解</p>  <p><br> </p>  <p></p>  <pre name="code" class="sycode">bool v[2111111];int pre[2111111];int a[222222];int n;int main() {    scanf("%d", &n);    for(int i = 0; i   <br>  <br>  <p></p>  <p>C  没做 留坑</p>  <p><br> </p>  <p>D</p>  <p>给出一个序列 长度10^6 </p>  <p>然后要分组，每组是这个序列中某一段连续的子序列，不能为空</p>  <p>然后每组计算一个 maxvalue - minvalue </p>  <p>最后求和</p>  <p>问怎么分组，这个和最大</p>  <p><br> </p>  <p>裸的dp方程是  dp[i] =max( dp[j- 1] + mx[j][i] - mi[j][i] )</p>  <p>肯定不行啊。复杂度太高了</p>  <p>有两种做法。</p>  <p><br> </p>  <p>1. 我们把这个序列看成由若干单增单降的序列组成的，</p>  <p>那么显然，将这个序列划分为若干这些个单增单降的连续子序列 会 最优</p>  <p>那么对一个极点，划分有两种情况，左边或者右边，取最优即可</p>  <p></p>  <pre name="code" class="sycode">int a[1111111];long long dp[1111111];int main() {    int n;    scanf("%d", &n);    for(int i = 1; i = a[i - 1] && a[i] >= a[i + 1]) pos = i;        if(a[i]   <br>  <br>  <p></p>  <p>2.对dp方程进行变化</p>  <p>有两种情况</p>  <p>第一种，当前位置的值可能是最大值</p>  <p>那么dp[i] =(dp[j- 1] - mi[j][i]  )+ a[i]</p>  <p>另一种，就是当前位置是最小值，</p>  <p>dp[i] = (dp[j - 1] + mx[j][i]) - a[i]</p>  <p>其他情况， 都是无效的状态，即使你更新也不会影响到结果</p>  <p>对于这两种情况</p>  <p>将(dp[j- 1] - mi[j][i]  ) 和(dp[j - 1] + mx[j][i]) 进行维护即可</p>  <p>维护时也并不是像这个式子显示的这么复杂</p>  <p>对于到i位置时，我们只要取当前位置之前最大的dp[j]，然后假设a[i]为最大值和最小值，去更新这两个式子即可</p>  <p>可以发现覆盖到了所有情况</p>  <p></p>  <pre name="code" class="sycode">int main() {    int n;    scanf("%d", &n);    long long ans = 0, x = 0, y = 0;    int a;    for(int i = 0; i  x) x = ans - a;        if(!i || ans + a > y) y = ans + a;        ans = max(ans, x + a);        ans = max(ans, y - a);    }    printf("%I64d\n", ans);    return 0;}

E 没做。留坑