购物节优惠卷网站怎么做,拼多多一件代发免费货源,东莞部门网站建设,wordpress 喜欢 按钮一套比一套炸,果然我只会做B卷,虽然我B也很差但没差到这种地步 $math$ 题解 看似没法做但总会有突破口 $70\%$ 发现和小凯的诱惑很像,于是看$gcd$是否为$1$只要为$1$可以凑齐所有数 $n^2$枚举两两$gcd$ $80\%$ 我考试时思路 找到每一个数和$mod$的$gcd$,发现只要是任一$gcd$倍数… 一套比一套炸,果然我只会做B卷,虽然我B也很差但没差到这种地步 $math$ 题解 看似没法做但总会有突破口 $70\%$ 发现和小凯的诱惑很像,于是看$gcd$是否为$1$只要为$1$可以凑齐所有数 $n^2$枚举两两$gcd$ $80\%$ 我考试时思路 找到每一个数和$mod$的$gcd$,发现只要是任一$gcd$倍数就可以凑出来,于是枚举每一个数和$mod$的$gcd$,瓶颈在于统计答案 #includebits/stdc.h
using namespace std;
#define ll long long
#define A 2222222
ll n,k,cnt0;
ll a[A],dl[A],ok[A];
ll read(){ll x0,f1;char cgetchar();while(!isdigit(c)){if(c-)f-1;cgetchar();}while(isdigit(c)){xx*10c-0;cgetchar();}return f*x;
}
ll gcd(ll x,ll y){if(y0) return x;return gcd(y,x%y);
}
int main(){nread(),kread(); for(ll i1;in;i)a[i]read(),dl[dl[0]]a[i];for(ll i1;idl[0];i){ll ggcd(dl[i],k);if(g1){printf(%lld\n,k);for(ll j0;jk-1;j){printf(%lld ,j);}return 0;}else {for(ll ig;ik;ig){ok[i]1;}ok[0]1;}}for(ll i0;ik;i){if(ok[i]) cnt;}printf(%lld\n,cnt);for(ll i0;ik;i){if(ok[i]) printf(%lld ,i);}printf(\n);
} View Code $100\%$ 其实从$80\%$我们就应该看出可以找到所有数$gcd$,然后只有为$gcd$倍数才可以凑出来 考试时我连这个都没有想到! 代码 #includebits/stdc.h
using namespace std;
#define ll long long
#define A 1010101
ll n,k,cnt0;
ll a[A],dl[A];
ll read(){ll f1,x0;char cgetchar();while(!isdigit(c)){if(c-) f-1;cgetchar();}while(isdigit(c)){xx*10c-0;cgetchar();}return f*x;
}
ll gcd(ll x,ll y){if(y0) return x;return gcd(y,x%y);
}
int main(){nread(),kread();for(ll i1;in;i){a[i]read();while(a[i]0){a[i]k;}}ll ggcd(a[1],a[2]);ggcd(g,k);for(ll i3;in;i)ggcd(a[i],g);for(ll i0;ik;ig){cnt;dl[dl[0]]i;}printf(%lld\n,cnt);for(ll i1;idl[0];i){printf(%lld ,dl[i]);}printf(\n);
} View Code $english$ 题解 破题打了很久从$23$日打到$27$日 然而考试两个人当场$AC$ 思路还算比较简单,然而很难打,不用说了我码力太弱 $ans1$还算比较简单,和学数数那个题很像, 我们找到以每一个值为最大值的最左$l$,最右$r$ 设当前值位置为$now$ 那么因为是异或,造成贡献的只有$now-l$中与$r-now$中二进制位相反的 设$0[x][j]$表示$1--x$中第$j$位为$0$数有多少个(这是前缀和) 类似设$1[x][j]$表示$1--x$中第$j$位为$1$数有多少个 那么$now$贡献就为$\sum\limits_{j1}^{j最高位} (0[now][j]-0[l-1][j])*(1[r][j]-1[now-1][j])(1[now][j]-1[l-1][j])*(0[r][j]-0[now-1][j])$ 然后问题又转化为了找到以每一个值为最大值的最左$l$,最右$r$ 这里我还是用的我的老方法(愚蠢至极) void pre(ll l,ll r,ll now,ll nowmax){if(lr) return ;lef[now]l,rig[now]r;if(lr) {len[now]r-l1;return ;}maxn-1,ida0;if(lnow-1){ seg_max(1,l,now-1);pre(l,now-1,ida,maxn);}maxn-1,ida0;if(now1r){seg_max(1,now1,r);pre(now1,r,ida,maxn);}
} 二分套线段树 复杂度玄学说是$n*{log(n)^2}$然而实际跑起来只比单调栈慢$400ms$,学数数还比单调栈快 $ans2$稍难但是还是寻找突破口 先放官方题解 这是很好的转化,我的实现和他不一样 (启发式合并太难打了,事实上我打了但根本没发调) 我用的可持久化$tire$, 可持久化$tire$可以查区间 要找到右面区间有多少个$xor$当前$a[j]$比最大值大 放进$tire$树里看如果最大值当前位为$1$,你不可能比它大,必须选相反位,为$0$比它大个数就是$size$了(size下所有都比它大) 放一下实现 void work2(){root[0]newnode();for(ll i1;in;i)root[i]newnode(),insert(root[i-1],root[i],a[i]);for(ll i1;in;i){ll tmp0;if(rig[i]-ii-lef[i])for(ll jlef[i];ji;j)tmp(tmpquery(root[i-1],root[rig[i]],a[j],a[i]))%mod;if(rig[i]-ii-lef[i])for(ll ji;jrig[i];j)tmp(tmpquery(root[lef[i]-1],root[i],a[j],a[i]))%mod;ans2(ans2tmp*a[i])%mod;}
} ll query(ll F,ll C,ll now,ll big){ll ans0;for(ll i20;i0;i--){ll num[2];num[0]sz[ch[C][0]]-sz[ch[F][0]];num[1]sz[ch[C][1]]-sz[ch[F][1]];ll nowbit(now(i))1,bigbit(big(i))1;if(bigbit) Fch[F][nowbit^1],Cch[C][nowbit^1];else Fch[F][nowbit],Cch[C][nowbit],ans(ansnum[nowbit^1]%mod); }return ans;
} 总代码 #includebits/stdc.h
using namespace std;
#define ll long long
#define A 222222
const ll mod1e97;
ll n,q,mx,mn0x7fffffffff,ida,maxn,idb,thebigest,thebigestid,ans1,ans2;
ll a[A],sum[A],b[A],ls[A],rs[A],len[A],_0[A][33],_1[A][33],lef[A],rig[A],sta[A];
ll root[A];
ll sz[11111111];
ll ch[11111111][2];
ll totnode1,top0;
char c[10];
struct tree{ll l,r,val,id;
}tr[A];
void init(){for(ll i1;in;i){while(topa[sta[top]]a[i]) rig[sta[top--]]i-1;sta[top]i;}while(top) rig[sta[top--]]n;for(ll in;i1;--i){while(topa[sta[top]]a[i]) lef[sta[top--]]i1;sta[top]i;}while(top) lef[sta[top--]]1;
}
void pushup(ll p){if(tr[p1].valtr[p1|1].val){tr[p].valtr[p1].val;tr[p].idtr[p1].id;}else {tr[p].valtr[p1|1].val;tr[p].idtr[p1|1].id;}
}
void built(ll p,ll l,ll r){tr[p].ll,tr[p].rr;if(lr){tr[p].vala[l];tr[p].idl;return ;}ll mid(lr)1;built(p1,l,mid);built(p1|1,mid1,r);pushup(p);
}
void seg_max(ll p,ll l,ll r){if(tr[p].lltr[p].rr){if(tr[p].valmaxn){maxntr[p].val;idatr[p].id;}return ;}ll mid(tr[p].ltr[p].r)1;if(midl)seg_max(p1,l,r);if(midr)seg_max(p1|1,l,r);
}
void pre(ll l,ll r,ll now,ll nowmax){if(lr) return ;lef[now]l,rig[now]r;if(lr) {len[now]r-l1;return ;}maxn-1,ida0;if(lnow-1){ seg_max(1,l,now-1);pre(l,now-1,ida,maxn);}maxn-1,ida0;if(now1r){seg_max(1,now1,r);pre(now1,r,ida,maxn);}
}
void work1(){for(ll j0;j20;j)for(ll i1;in;i){_0[i][j]_0[i-1][j];_1[i][j]_1[i-1][j];if((a[i](1j))) _1[i][j];else _0[i][j];}for(ll i1;in;i){ll tmp0;for(ll j0;j20;j){ll l0_0[i][j]-_0[lef[i]-1][j],r0_0[rig[i]][j]-_0[i-1][j],l1_1[i][j]-_1[lef[i]-1][j],r1_1[rig[i]][j]-_1[i-1][j];tmp(tmp(l0*(r1%mod*(1j)%mod)))%mod;tmp(tmp(l1*(r0%mod*(1j)%mod)))%mod;}ans1(ans1tmp*a[i])%mod;}
}
ll newnode(){memset(ch[totnode],0,sizeof(ch[totnode]));sz[totnode]0;return totnode;
}
//F之前树 C现在树
inline void insert(ll F,ll C,ll val){for(ll i20;i0;i--){ll bit(vali)1;if(!ch[C][bit]){ch[C][bit]newnode();ch[C][!bit]ch[F][!bit];sz[ch[C][bit]]sz[ch[F][bit]];}Cch[C][bit],Fch[F][bit];sz[C];}
}
ll query(ll F,ll C,ll now,ll big){ll ans0;for(ll i20;i0;i--){ll num[2];num[0]sz[ch[C][0]]-sz[ch[F][0]];num[1]sz[ch[C][1]]-sz[ch[F][1]];ll nowbit(now(i))1,bigbit(big(i))1;if(bigbit) Fch[F][nowbit^1],Cch[C][nowbit^1];else Fch[F][nowbit],Cch[C][nowbit],ans(ansnum[nowbit^1]%mod); }return ans;
}
void work2(){root[0]newnode();for(ll i1;in;i)root[i]newnode(),insert(root[i-1],root[i],a[i]);for(ll i1;in;i){ll tmp0;if(rig[i]-ii-lef[i])for(ll jlef[i];ji;j)tmp(tmpquery(root[i-1],root[rig[i]],a[j],a[i]))%mod;if(rig[i]-ii-lef[i])for(ll ji;jrig[i];j)tmp(tmpquery(root[lef[i]-1],root[i],a[j],a[i]))%mod;ans2(ans2tmp*a[i])%mod;}
}
int main(){scanf(%lld%lld,n,q);for(ll i1;in;i){scanf(%lld,a[i]);if(a[i]mx)idai,mxa[i];mnmin(mn,a[i]);}thebigestidida;built(1,1,n);pre(1,n,ida,a[ida]);work1();work2();if(q1)printf(%lld\n,ans1);if(q2)printf(%lld\n,ans2);if(q3)printf(%lld\n%lld\n,ans1,ans2);
} View Code $chinese$ 题解 炼字简称练字(其实是我懒得改了) 真·吃了语文的亏 考试一直在做这个题($2$小时左右)然而还是只会暴力(然后更加蠢的是我打了暴力没有打表,别人打表$60$分,我暴力$45$) 首先题目中式子含义要搞清楚 其实他就是让你统计所有方案有多少个练字 你放一个练字那么贡献就是当前所有方案数$*1$ 当前方案数如何求呢? 假设当前在$x$,$y$填练字,,练字为$i$ 那么$x$所在行剩下$m-1$个位置只能小$(i-1)^{(m-1)}$ 类似的$y$所在列剩下$(i-1)^{(n-1)}$ 剩下位置随便填 这样为什么是对的,(即为什么是练字个数) 假设你随便填里有一个练字,你算当前练字个数算了一个,下一次考虑时又考虑当前这个 或者你这么想,在这$(i-1)^{(n-1)}*(i-1)^{(m-1)}*k^{(n-1)*(m-1)}$每一种方案都计算了当前这个练字,,每种方案贡献为$1$ 代码 #includebits/stdc.h
using namespace std;
#define ll long long
ll n,m,ans0;
const ll mod1e97;
ll meng(ll x,ll k){ll ans1;for(;k;k1,xx*x%mod){if(k1)ansans*x%mod;}return ans;
}
ll k;
int main(){scanf(%lld%lld%lld,n,m,k);for(ll i1;ik;i)ans(ansmeng(i-1,n-1)%mod*meng(i-1,m-1)%mod*meng(k,(n-1)*(m-1))%mod)%mod;ans(ans*n%mod*m%mod)%mod;printf(%lld\n,ans);
} View Code $biology$ 题解 $dp$,思路没有见过,还是要多见见, 首先暴力转移枚举每一个方格最小的复杂度$n^2*m^2$ 思考优化 绝对值很恶心,考虑去掉绝对值 拆成$-x-y$,$xy$,$-xy$,$x-y$ 然后发现一个性质我们把一个原本应该是$-x-y$的拆成$4$个另外三个并不会比$-x-y$变优 于是我们愉快维护四个最大值变量就行了 代码 #includebits/stdc.h
using namespace std;
#define ll long long
#define maxn 2101
ll n,m,cnt0,st0,ans0,mx10,mx20,mx30,mx40;
ll tmp1,tmp2,tmp3,tmp4,sta;
ll read(){ll x0,f1;char cgetchar();while(!isdigit(c)){if(c-)f-1;cgetchar();}while(isdigit(c)){xx*10c-0;cgetchar();}return f*x;
}
struct node{ll x,y,val;friend bool operator (const node a,const node b){return a.valb.val;}
}c[maxn*maxn];
ll b[maxn][maxn],f[maxn*maxn];
int main(){nread(),mread();for(ll i1;in;i)for(ll j1,a;jm;j){scanf(%lld,a);if(a0) continue;cnt;c[cnt].xi;c[cnt].yj;c[cnt].vala;}for(ll i1;in;i)for(ll j1;jm;j){scanf(%lld,b[i][j]);}sort(c1,ccnt1);for(ll icnt;i2;i--){if(c[i].val!c[i-1].val){stai;}}for(ll i1;ista;i){ll xc[i].x,yc[i].y;f[i]b[c[i].x][c[i].y];
// printf(f[%lld]%lld x%lld y%lld\n,i,f[i],x,y);tmp1max(tmp1,f[i]-x-y);tmp2max(tmp2,f[i]-xy);tmp3max(tmp3,f[i]x-y);tmp4max(tmp4,f[i]xy);ansmax(ans,f[i]);}for(ll ista;icnt;i){ll xc[i].x,yc[i].y;if(c[i].val!c[i-1].val){mx1max(mx1,tmp1);mx2max(mx2,tmp2);mx3max(mx3,tmp3);mx4max(mx4,tmp4);}
// printf(mx1%lld 2%lld 3%lld 4%lld\n,mx1,mx2,mx3,mx4);ll an0;anmax(an,mx1xy);anmax(an,mx2x-y);anmax(an,mx3-xy);anmax(an,mx4-x-y);f[i]anb[c[i].x][c[i].y];tmp1max(tmp1,f[i]-x-y);//左上tmp2max(tmp2,f[i]-xy);//右上tmp3max(tmp3,f[i]x-y);//左下tmp4max(tmp4,f[i]xy);//右下ansmax(ans,f[i]);}
// for(ll i1;icnt;i){
// printf(%lld\n,f[i]);
// }printf(%lld\n,ans);
} View Code $physics$ 题解 前缀和? 为什么选择前缀和,前缀和查询$O(1)$我们主要时间在查询上$n^3$(或)$n^2*log(n)$,修改$n^2$绝对可以接受 于是前缀和就完了 满足二分性质可以进行二分,然而我没有打 类似于二分答案枚举当前可以分成的$n^2*log(n)$ void ask(){int l1,rans;while(lr){int mid(lr)1;if(judge(mid)) lmid1;else rmid-1;}
} 我暴力$$剪枝$AC$思考怎么剪枝 首先枚举是越修改越小的,我们可以记录下当前答案,然后下次验证时在当前答案基础上验证就行了 然后还有记录当前所有符合答案 cnt;mo[cnt].xx,mo[cnt].yy,mo[cnt].ok1,mo[cnt].leni; 验证时 for(ll j1;jcnt;j)if(mo[j].ok){if(xmo[cnt].xxmo[cnt].xmo[cnt].len-1ymo[cnt].yymo[cnt].ymo[cnt].len-1) mo[j].ok0;else allok1;}if(allok) printf(%d\n,nowans);else pre(),printf(%d\n,nowans); 复杂度与变化次数相关 代码 #includebits/stdc.h
using namespace std;
#define ll int
#define A 1111
char a[A][A];
ll cnt0,n,m,k,maxx,nowans,nowlefx,nowlefy,nowrigx,nowrigy,llll,upup;
ll sum[A][A];
struct node{ll x,y,len,ok;
}mo[1111111];
void pre(){cnt0;for(ll inowans;i1;i--){for(ll x1;xn-i1;x){for(ll y1;yn-i1;y)if(sum[xi-1][yi-1]sum[x-1][y-1]-sum[x-1][yi-1]-sum[xi-1][y-1]0){ cnt;mo[cnt].xx,mo[cnt].yy,mo[cnt].ok1,mo[cnt].leni;nowansi;}}if(cnt) return ;}
}
int main(){scanf(%d%d%d,n,m,k);for(ll i1;in;i){scanf(%s,a[i]1);for(ll j1;jm;j)if(a[i][j]-) sum[i][j]1;}ll x,y;scanf(%d%d,x,y);sum[x][y]1;for(ll i1;in;i)for(ll j1;jm;j)sum[i][j]sum[i][j]sum[i-1][j]sum[i][j-1]-sum[i-1][j-1];nowansn;pre();printf(%d\n,nowans);for(ll i2,x,y;ik;i){scanf(%d%d,x,y);for(ll ix;in;i)for(ll jy;jm;j)sum[i][j];ll allok0;for(ll j1;jcnt;j)if(mo[j].ok){if(xmo[cnt].xxmo[cnt].xmo[cnt].len-1ymo[cnt].yymo[cnt].ymo[cnt].len-1) mo[j].ok0;else allok1;}if(allok) printf(%d\n,nowans);else pre(),printf(%d\n,nowans);}
} View Code 转载于:https://www.cnblogs.com/znsbc-13/p/11428910.html
