大一暑假集训最终考试(一)（2019.8.31）

D题nefu 1866 这是一道难题思路树状数组模板题。还有就是树状数组的单点修改只支持加减不支持直接修改修改时先减去原来的数再加上修改后的数即可。坑的地方没说查询时一定满足xyAC代码#includebits/stdc.husing namespace std;typedeflonglongll;constintN1e510,mod1e97;ll tr[N];intn,m,a[N],x,y,opt;voidadd(inti,intk){while(in){tr[i]k;i(i-i);}}llsum(inti){ll s0;while(i){str[i]%mod;i-(i-i);}returns%mod;}intmain(){scanf(%d%d,n,m);for(inti1;in;i){scanf(%d,a[i]);add(i,a[i]);}while(m--){scanf(%d%d%d,opt,x,y);if(opt0){add(x,-a[x]);//先减去原来的数add(x,y);//再加上现在的数a[x]y;//修改原数组}else{if(xy)swap(x,y);//巨坑这个地方wa了4次printf(%lld\n,sum(y)-sum(x-1));}}return0;}B题nefu 1878 Alice和Bob的分组游戏(一)思路sg函数打表。AC代码#includebits/stdc.husing namespace std;constintN1e410;typedeflonglongll;bool vis[N];intn,m,x,t;ll sg[N],sum;voidget_sg(){memset(sg,0,sizeof(sg));for(inti2;iN;i)//有i个糖果{memset(vis,0,sizeof(vis));for(intj2;jmin(i,m);j)//分成j堆{if(i%j0){ti/j;//每堆t个if(j1)vis[sg[t]]1;//奇数堆后继状态的sg值为sg[t]elsevis[0]1;//偶数堆后继状态的sg值为0}}for(intj0;;j)if(vis[j]0){sg[i]j;break;}}}intmain(){while(scanf(%d%d,n,m)!-1)//没有多组输入wa了一发气死我了{get_sg();sum0;for(inti1;in;i){cinx;sum^sg[x];}if(sum)printf(Alice\n);elseprintf(Bob\n);}return0;}E题nefu 1870 这是一道签到题思路找规律异或值显然与[x,y]区间长度的奇偶有关。查询时用线段树维护。设dy-x1当d为奇数时说明x、y均为奇数或者x、y均为偶数此时F(x,y)a[x]^a[x2]^…^a[y-2]^a[y]比如区间[1,5]F(1,5)a[1]^a[3]^a[5]当d为偶数时F(x,y)0恒成立。对于d是奇数的情况我们可以用两个线段树分别维护x、y均为奇数以及x、y均为偶数时的区间异或值。还有这根本就不是签到题难度啊啊啊啊AC代码#includebits/stdc.husing namespace std;typedeflonglongll;constintN1e510;ll n,d,m,x,y,opt,cnt1,cnt2,a1[N],a2[N],tre1[4*N],tre2[4*N];voidpushup(ll tr[],ll i){tr[i]tr[2*i]^tr[2*i1];}voidbuild(ll tr[],ll a[],ll i,ll l,ll r){if(lr){tr[i]a[l];return;}ll midlr1;build(tr,a,2*i,l,mid);build(tr,a,2*i1,mid1,r);pushup(tr,i);}voidupdate(ll tr[],ll i,ll l,ll r,ll x,ll y){if(xr||xl)return;if(lrlx){tr[i]y;return;}ll midlr1;update(tr,2*i,l,mid,x,y);update(tr,2*i1,mid1,r,x,y);pushup(tr,i);}llquery(ll tr[],ll i,ll l,ll r,ll x,ll y){if(ly||rx)return0;if(lxry)returntr[i];intmidlr1;returnquery(tr,2*i,l,mid,x,y)^query(tr,2*i1,mid1,r,x,y);}intmain(){ios::sync_with_stdio(false);while(cinnm){cnt1cnt20;for(ll i1;in;i){cinx;if(i1)a1[cnt1]x;//a1保存下标为奇数的值方便之后查询[x,y]x、y均为奇数的情况elsea2[cnt2]x;//a2保存下标为偶数的值方便之后查询[x,y]x、y均为偶数的情况}build(tre1,a1,1,1,cnt1);//tre1保存a1数组的区间异或值build(tre2,a2,1,1,cnt2);//tre2保存a2数组的区间异或值for(ll i1;im;i){cinoptxy;if(opt0){if(x1)update(tre1,1,1,cnt1,(x1)/2,y);elseupdate(tre2,1,1,cnt2,x/2,y);}else{if(xy)swap(x,y);dy-x1;if(d%20)printf(0\n);else{if(x1)printf(%lld\n,query(tre1,1,1,cnt1,(x1)/2,(y1)/2));elseprintf(%lld\n,query(tre2,1,1,cnt2,x/2,y/2));}}}}return0;}C题nefu 1867 why的考号思路根据递推方程构造矩阵再用矩阵快速幂。递推方程(n3)f[n]2*f[n-2]f[n-1]n3设矩阵相乘等式为A*BC难点就是怎么去构造A矩阵。首先不能像我这样构造我们要想办法把(n1)3用B矩阵的元素表示出来但是这样A矩阵有一个元素[(n1)/n]3显然是不行的因为A矩阵中有元素[(n1)/n]3再快速幂误差很大正确做法是把(n1)3拆开(n1)3n33*n23*n1要想(n1)3用B矩阵的元素表示出来需要增添B矩阵的元素在B矩阵下方再加三个数n2、n、1。那么A*BC就变成了这样最后再处理一下OK数学公式推导到此结束。把上面的那个最终公式推出来代码就很好写了。AC代码#includebits/stdc.husing namespace std;constintmod123456789;typedeflonglongll;ll n,t,cas,ans;structnode{ll m[6][6];};node s,A{0,2,0,0,0,0,1,1,1,0,0,0,0,0,1,3,3,1,0,0,0,1,2,1,0,0,0,0,1,1,0,0,0,0,0,1};nodemul(node x,node y)//两矩阵x、y相乘{node s;memset(s.m,0,sizeof(s.m));for(inti0;i6;i)for(intj0;j6;j)for(intk0;k6;k)s.m[i][j]x.m[i][k]*y.m[k][j]%mod;returns;}nodequickpow(node a,ll b)//矩阵快速幂求矩阵a的n次方{memset(s.m,0,sizeof(s.m));for(inti0;i6;i)s.m[i][i]1;//s初始化为单位矩阵while(b){if(b1){b--;smul(s,a);}amul(a,a);bb/2;}returns;}intmain(){ios::sync_with_stdio(false);cint;while(t--){cinn;printf(Case %d: ,cas);if(n1){printf(000000001\n);continue;}squickpow(A,n-2);//n2anss.m[1][0]*2%mods.m[1][1]*2%mods.m[1][2]*27%mods.m[1][3]*9%mods.m[1][4]*3%mods.m[1][5]%mod;printf(%09lld\n,ans%mod);}return0;}【未完待续。。。】