不要温驯地走进那良宵。
Do not go gentle into that good night.
Codeforces Round #469（div2）
A. 一句话：循环解决的分类讨论大小的混沌问题，均可以用swap规定大小解决。
这样复杂度O（a）-->O（1）
1 2 3 | while(a--){}等同于while(a){a--;} |
B.模拟指针解决O(m+n)
使用数据结构维护前缀和O((m+n)log(m+n))
★前缀和思想：
a与b在p、q处(p<q)前缀和相等<==>a[p+1]+...+a[q]=b[p'+1]+...+b[q']，故直接对前缀和进行查询操作即可！
1 2 3 | set<long long> s; for(int i=1;i<=n;i++)scanf("%I64d",&a[i]),a[i]+=a[i-1],s.insert(a[i]);for(int i=1;i<=m;i++)scanf("%I64d",&b[i]),b[i]+=b[i-1],ans+=s.count(b[i]); |
1）边读入边累加前缀和，注意是a[i]+=a[i-1]
2）由题意知a[i]均为正，故累加和不存在相同的情况，count(b[i])只可能是0或1，起到了查询的效果
C.
D.思路题。数列是固定的，并且n很大，所以一定要通过找规律解决。
找规律的两种思路：1）打表，观察 http://blog.csdn.net/xiangAccepted/article/details/79506332
2）分奇偶，分析：#include <cstdio>
1 2 3 4 5 6 7 8 9 10 11 | long long n,x;int q;int main(){ scanf("%I64d%I64d",&n,&q); while(q--){ scanf("%I64d",&x); while(!(x&1)) x=(x>>1)+n; printf("%I64d\n",(x+1)>>1); } return 0;} |
E.希望以后的题面和题解写得能够友好一点...不要再这么晦涩还有语法错误了...
评论 (0)
