武安网站建设价格,开发区网站建设,石家庄是哪个省,全国网站设计公司问题 C: 二进制 时间限制: 1 Sec 内存限制: 128 MB提交: 8 解决: 2[提交] [状态] [讨论版] [命题人:]题目描述 pupil发现对于一个十进制数#xff0c;无论怎么将其的数字重新排列#xff0c;均不影响其是不是3的倍数。他想研究对于二进制#xff0c;是否也有类似的性质。于… 问题 C: 二进制 时间限制: 1 Sec 内存限制: 128 MB提交: 8 解决: 2[提交] [状态] [讨论版] [命题人:] 题目描述 pupil发现对于一个十进制数无论怎么将其的数字重新排列均不影响其是不是3的倍数。他想研究对于二进制是否也有类似的性质。于是他生成了一个长为n的二进制串希望你对于这个二进制串的一个子区间能求出其有多少位置不同的连续子串满足在重新排列后可包含前导0是一个3的倍数。两个位置不同的子区间指开始位置不同或结束位置不同。由于他想尝试尽量多的情况他有时会修改串中的一个位置并且会进行多次询问。 输入 输入第一行包含一个正整数n表示二进制数的长度。之后一行n个空格隔开的整数保证均是0或1表示该二进制串。之后一行一个整数m表示询问和修改的总次数。之后m行每行为1 i表示pupil修改了串的第i个位置0变成1或1变成0或2 l r表示pupil询问的子区间是[l,r]。串的下标从1开始。 输出 对于每次询问输出一行一个整数表示对应该询问的结果。 样例输入 4
1 0 1 0
3
2 1 3
1 3
2 3 4样例输出 2
3提示 对于第一个询问区间[2,2]只有数字0是3的倍数区间[1,3]可以重排成011(2)3(10)是3的倍数其他区间均不能重排成3的倍数。 对于第二个询问全部三个区间均能重排成3的倍数注意00也是合法的。 对于20%的数据1≤n,m≤100 对于50%的数据1≤n,m≤5000 对于100%的数据1≤n,m≤100000l≤r。 Solution 设cnt0cnt1分别为[l,r]区间内的1和0的个数易得 1. if cnt11 不可整除3 2. if cnt11 and cnt02 不可整除3 简单证明上述结论 显然结论1是成立的1n不可能整除3当cnt1为偶数时显然也一定可以整除3而当cnt11时 先考虑这种情况将一个二进制数将其两位两位拆分并求和得到sum显然如果 sum%30 则该二进制数的十进制一定可以整除3。 如111010001(01,11,01,00,01)sum131016。 那么对于奇数个1从中挑出cnt1-3个“1”两两组合确保对sum%3的结果无贡献后再看剩下的3个“1”的情况 ①、sum(111)4 无法整除。【区间内无0】 ②、sum(1101)4,sum(1011)5 无法整除。【区间内只含有一个0】 ③、sum(10101)3 可整除。【区间内至少含有两个0】 综上 我们用线段树去维护上述两种不合法情况再用【总数-不合法数合法数】来得到答案。 其中dl/dr[2][2] 代表经过左右节点后cnt00/1cnt11?1:0。 fl/fr[3] 代表经过左右节点后满足cnt11 and cnt00/1的方案数。 L/R表示经过左右节点后连续0的长度。 代码 1 #include iostream2 #include string3 #include cstdio4 #include cmath5 #include cstring6 #include algorithm7 #include vector8 #include queue9 #include deque10 #include map11 #include set12 #define range(i,a,b) for(auto ia;ib;i)13 #define LL long long14 #define ULL unsigned long long15 #define elif else if16 #define itrange(i,a,b) for(auto ia;i!b;i)17 #define rerange(i,a,b) for(auto ia;ib;--i)18 #define fill(arr,tmp) memset(arr,tmp,sizeof(arr))19 #define IOS ios::sync_with_stdio(false);cin.tie(0)20 using namespace std;21 int n,m,op,l,r,A[int(1e55)];22 class SegTree{23 private:24 struct node{25 LL s,dl[2][2],dr[2][2],fl[3],fr[3],L,R;26 int cnt0,cnt1;27 void reset(){28 range(i,0,1)range(j,0,1)dl[i][j]dr[i][j]0;29 fl[0]fl[1]fr[0]fr[1]fl[2]fr[2]LRscnt0cnt10;30 }31 node(){reset();}32 }tree[int(1e55)2];33 node comb(node A,node B){34 node tmp;35 range(i,0,1)range(j,0,1){36 tmp.dl[i][j]A.dl[i][j];37 tmp.dr[i][j]B.dr[i][j];38 if(iA.cnt0)tmp.dl[i][j]B.dl[i-A.cnt0][j^(A.cnt11)];39 if(iB.cnt0)tmp.dr[i][j]A.dr[i-B.cnt0][j^(B.cnt11)];40 }41 range(i,0,2){42 tmp.fl[i]A.fl[i];43 tmp.fr[i]B.fr[i];44 if(!A.cnt1)tmp.fl[min(2,iA.cnt0)]B.fl[i];45 if(!B.cnt1)tmp.fr[min(2,iB.cnt0)]A.fr[i];46 }47 if(A.cnt11 and B.L){48 tmp.fl[min(2LL,A.cnt0B.L)];49 tmp.fl[2]B.L-1;50 }51 if(B.cnt11 and A.R){52 tmp.fr[min(2LL,B.cnt0A.R)];53 tmp.fr[2]A.R-1;54 }55 tmp.L(!A.cnt1?A.cnt0B.L:A.L);tmp.R(!B.cnt1?B.cnt0A.R:B.R);56 tmp.cnt0A.cnt0B.cnt0;tmp.cnt1A.cnt1B.cnt1;tmp.sA.sB.s;57 tmp.sA.dr[0][1]*(B.dl[1][0]B.dl[0][0])A.dr[1][0]*B.dl[0][1];58 tmp.sA.dr[0][0]*(B.dl[1][1]B.dl[0][1])A.dr[1][1]*B.dl[0][0];59 if(B.L)tmp.s(A.fr[1]A.fr[2])*B.LA.fr[0]*(B.L-1);60 if(A.R)tmp.s(B.fl[1]B.fl[2])*A.RB.fl[0]*(A.R-1);61 return tmp;62 }63 void pushup(node tmp,int x){64 tmp.reset();65 if(x)tmp.stmp.fl[0]tmp.fr[0]tmp.dl[0][1]tmp.dr[0][1]tmp.cnt11;66 else tmp.dl[1][0]tmp.dr[1][0]tmp.Ltmp.Rtmp.cnt01;67 };68 public:69 void build(int l,int r,int rt1){70 if(lr){71 pushup(tree[rt],A[l]);72 return;73 }74 int m(lr)1;75 build(l,m,rt1);76 build(m1,r,rt1|1);77 tree[rt]comb(tree[rt1],tree[rt1|1]);78 }79 void update(int l,int r,int rt,int L){80 if(lr){81 pushup(tree[rt],A[l]);82 return;83 }84 int m(lr)1;85 if(Lm)update(l,m,rt1,L);86 else update(m1,r,rt1|1,L);87 tree[rt]comb(tree[rt1],tree[rt1|1]);88 }89 node query(int l,int r,int rt,int L,int R){90 if(Ll and rR)return tree[rt];91 int m(lr)1;92 if(Rm)return query(l,m,rt1,L,R);93 if(Lm)return query(m1,r,rt1|1,L,R);94 return comb(query(l,m,rt1,L,m),query(m1,r,rt1|1,m1,R));95 }96 }segTree;97 void init(){98 scanf(%d,n);99 range(i,1,n)scanf(%d,Ai);
100 segTree.build(1,n);
101 scanf(%d,m);
102 }
103 void solve(){
104 while(m--){
105 scanf(%d%d,op,l);
106 if(op1)A[l]^1,segTree.update(1,n,1,l);
107 else{
108 scanf(%d,r);
109 printf(%lld\n,1LL*(r-l1)*(r-l2)/2-segTree.query(1,n,1,l,r).s);
110 }
111 }
112 }
113 int main() {
114 init();
115 solve();
116 return 0;
117 } View Code 转载于:https://www.cnblogs.com/Rhythm-/p/9455281.html
