bzoj5108 [CodePlus2017]可做题

bzoj5108 [CodePlus2017]可做题

​​ Description qmqmqm希望给sublinekelzrip出一道可做题。于是他想到了这么一道题目：给一个长度为n的非负整数序列ai,你需 要计算其异或前缀和bi,满足条件b1=a1,bi=bi?1 xor ai(i≥2).但是由于数据生成器出现了问题，他生成的序列a 的长度特别长，并且由于内存空间不足，一部分ai已经丢失了，只剩余m个位置的元素已知。现在qmqmqm找到你， 希望你根据剩余的ai,计算出所有可能的a序列对应的b序列中∑=bi(1<=i<=N)的最小值。

Input 输入第一行两个非负整数n,m,分别表示原始序列a的长度及剩余元素的个数。 之后m行，每行2个数i,ai，表示一个剩余元素的位置和数值。 1<=N<=10^9,0<=M<=Min(n,10^5),0<=ai<=10^9 注意未知的 ai 可以超过已知 ai 的范围。 保证输入中所有的 i 不同，且满足 1 ≤ i ≤ n。

Output 输出一个整数表示可能的最小值

Sample Input 5 3 4 0 3 7 5 0 Sample Output 7 已知的 a 序列为： X, X, 7, 0, 0, 其中X表示这个位置丢失了。一种可能的 a 序列为 0, 7, 7, 0, 0, 对应的 b 序列为 0, 7, 0, 0, 0, 和最小为 7。可以证明不存在和更小的情况 HINT 来自 CodePlus 2017 11 月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。 Credit：idea/卢政荣　命题/卢政荣　验题/何昊天 Git Repo：​​​ 本次比赛的官方网址：cp.thusaac.org 感谢腾讯公司对此次比赛的支持。 求异或前缀和的最小值 thuwc的试机题 我菜到现在才搞定 qwq 没看题解 有很多细节没太想清楚的 设dp[i][1/0] 表示我现在做到了第i位我这一位 为0/1的最小代价 我首先分开按位讨论 因为位与位之间是互不影响的 做的时候就递推直接搞就可以 但是注意 如果前一位是空的我随意添加数字来构造 注意我存在我当前位置和前一个位置只差一个的情况 这样的话我就需要特判 避免我这一位同时被我钦定为1或者0 如果紧挨着上一位 那么我必须直接从上一位继承过来 如果不是紧挨着我得按照可能出现的0，1情况枚举比较一下

#include#include#include#define N 110000#define ll long long#define inf 1LL<<60using namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();} while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc(); return x*f;}struct node{ int v,pos;}d[N];ll dp[N][2],ans;int bin[40],n,m;inline bool cmp(const node &a,const node &b){return a.pos

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。