CodeforcesRound#276(Div.1)_html/css_WEB-ITnose
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了CodeforcesRound#276(Div.1)_html/css_WEB-ITnose,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3223字,纯文字阅读大概需要5分钟。
内容图文
![CodeforcesRound#276(Div.1)_html/css_WEB-ITnose](/upload/InfoBanner/zyjiaocheng/400/350124cac005461b97cbca6565c52537.jpg)
题目都还挺短小精悍的
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 < n; i++) { scanf("%I64d%I64d", &l, &r); for(int j = 0; j < 61; j++) { long long tmp = 1LL << j; if(l & tmp) continue; else if((l ^ tmp) <= r) l ^= tmp; } printf("%I64d\n", l); } return 0;}
B
给一个序列a,长度2*10^5,每个数的范围是10^6
然后问最大的a[i]%a[j] 其中要求的是a[i] >= a[j]
一看这个范围基本就是专卡nlognlogn的了
试了一下果然T了
然后有nlogn的做法
就是对任意的a[i],标记为1,然后
从1到mx,扫一遍统计比当前数小的最大的a[i]是多少,其中mx应该是2000000
然后枚举,对每个数,枚举倍数
如果该数为x,倍数为y, 则去找比x * y小的最大的a[i],用a[i] - x *(y -1) 就求出了一个可能的解
bool v[2111111];int pre[2111111];int a[222222];int n;int main() { scanf("%d", &n); for(int i = 0; i < n; i++) { scanf("%d", &a[i]); v[a[i]] = 1; } int mx = 2000005; for(int i = 1; i < mx; i++) { pre[i] = pre[i - 1]; if(v[i - 1]) pre[i] = i - 1; } int ans = 0; for(int i = 1; i < mx; i++) { if(!v[i]) continue; for(int j = 2 * i; j < mx; j += i) { ans = max(ans, pre[j] + i - j); } } printf("%d\n", ans); return 0;}
C 没做 留坑
D
给出一个序列 长度10^6
然后要分组,每组是这个序列中某一段连续的子序列,不能为空
然后每组计算一个 maxvalue - minvalue
最后求和
问怎么分组,这个和最大
裸的dp方程是 dp[i] =max( dp[j- 1] + mx[j][i] - mi[j][i] )
肯定不行啊。复杂度太高了
有两种做法。
1. 我们把这个序列看成由若干单增单降的序列组成的,
那么显然,将这个序列划分为若干这些个单增单降的连续子序列 会 最优
那么对一个极点,划分有两种情况,左边或者右边,取最优即可
int a[1111111];long long dp[1111111];int main() { int n; scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); int pos = 1; for(int i = 2; i <= n; i++) { dp[i] = dp[pos - 1] + abs(a[i] - a[pos]); dp[i] = max(dp[i], dp[pos] + abs(a[i] - a[pos + 1])); if(a[i] >= a[i - 1] && a[i] >= a[i + 1]) pos = i; if(a[i] <= a[i - 1] && a[i] <= a[i + 1]) pos = i; } printf("%I64d\n", dp[n]); return 0;}
2.对dp方程进行变化
有两种情况
第一种,当前位置的值可能是最大值
那么dp[i] =(dp[j- 1] - mi[j][i] )+ a[i]
另一种,就是当前位置是最小值,
dp[i] = (dp[j - 1] + mx[j][i]) - a[i]
其他情况, 都是无效的状态,即使你更新也不会影响到结果
对于这两种情况
将(dp[j- 1] - mi[j][i] ) 和(dp[j - 1] + mx[j][i]) 进行维护即可
维护时也并不是像这个式子显示的这么复杂
对于到i位置时,我们只要取当前位置之前最大的dp[j],然后假设a[i]为最大值和最小值,去更新这两个式子即可
可以发现覆盖到了所有情况
int main() { int n; scanf("%d", &n); long long ans = 0, x = 0, y = 0; int a; for(int i = 0; i < n; i++){ scanf("%d", &a); if(!i || ans - a > 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 没做。留坑
内容总结
以上是互联网集市为您收集整理的CodeforcesRound#276(Div.1)_html/css_WEB-ITnose全部内容,希望文章能够帮你解决CodeforcesRound#276(Div.1)_html/css_WEB-ITnose所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。