一套比一套炸,果然我只會做B卷,雖然我B也很差但沒差到這種地步

$math$

題解

看似沒法做但總會有突破口

$70\%$

發現和小凱的誘惑很像,于是看$gcd$是否為$1$只要為$1$可以湊齊所有數

$n^2$枚舉兩兩$gcd$

$80\%$

我考試時思路

找到每一個數和$mod$的$gcd$,發現只要是任一$gcd$倍數就可以湊出來,于是枚舉每一個數和$mod$的$gcd$,瓶頸在于統計答案

#include<bits/stdc++.h> using namespace std; #define ll long long #define A 2222222 ll n,k,cnt=0; ll a[A],dl[A],ok[A]; ll read(){ll x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return f*x; } ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y); } int main(){n=read(),k=read(); for(ll i=1;i<=n;i++)a[i]=read(),dl[++dl[0]]=a[i];for(ll i=1;i<=dl[0];i++){ll g=gcd(dl[i],k);if(g==1){printf("%lld\n",k);for(ll j=0;j<=k-1;j++){printf("%lld ",j);}return 0;}else {for(ll i=g;i<k;i+=g){ok[i]=1;}ok[0]=1;}}for(ll i=0;i<=k;i++){if(ok[i]) cnt++;}printf("%lld\n",cnt);for(ll i=0;i<=k;i++){if(ok[i]) printf("%lld ",i);}printf("\n"); } View Code

$100\%$

其實從$80\%$我們就應該看出可以找到所有數$gcd$,然后只有為$gcd$倍數才可以湊出來

考試時我連這個都沒有想到!

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long #define A 1010101 ll n,k,cnt=0; ll a[A],dl[A]; ll read(){ll f=1,x=0;char c=getchar();while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return f*x; } ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y); } int main(){n=read(),k=read();for(ll i=1;i<=n;i++){a[i]=read();while(a[i]<0){a[i]+=k;}}ll g=gcd(a[1],a[2]);g=gcd(g,k);for(ll i=3;i<=n;i++)g=gcd(a[i],g);for(ll i=0;i<k;i+=g){cnt++;dl[++dl[0]]=i;}printf("%lld\n",cnt);for(ll i=1;i<=dl[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_{j=1}^{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(l>r) return ;lef[now]=l,rig[now]=r;if(l==r) {len[now]=r-l+1;return ;}maxn=-1,ida=0;if(l<=now-1){ seg_max(1,l,now-1);pre(l,now-1,ida,maxn);}maxn=-1,ida=0;if(now+1<=r){seg_max(1,now+1,r);pre(now+1,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 i=1;i<=n;i++)root[i]=newnode(),insert(root[i-1],root[i],a[i]);for(ll i=1;i<=n;i++){ll tmp=0;if(rig[i]-i>i-lef[i])for(ll j=lef[i];j<=i;j++)tmp=(tmp+query(root[i-1],root[rig[i]],a[j],a[i]))%mod;if(rig[i]-i<=i-lef[i])for(ll j=i;j<=rig[i];j++)tmp=(tmp+query(root[lef[i]-1],root[i],a[j],a[i]))%mod;ans2=(ans2+tmp*a[i])%mod;} } ll query(ll F,ll C,ll now,ll big){ll ans=0;for(ll i=20;i>=0;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) F=ch[F][nowbit^1],C=ch[C][nowbit^1];else F=ch[F][nowbit],C=ch[C][nowbit],ans=(ans+num[nowbit^1]%mod); }return ans; }

總代碼

#include<bits/stdc++.h> using namespace std; #define ll long long #define A 222222 const ll mod=1e9+7; ll n,q,mx,mn=0x7fffffffff,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 totnode=1,top=0; char c[10]; struct tree{ll l,r,val,id; }tr[A]; void init(){for(ll i=1;i<=n;++i){while(top&&a[sta[top]]<a[i]) rig[sta[top--]]=i-1;sta[++top]=i;}while(top) rig[sta[top--]]=n;for(ll i=n;i>=1;--i){while(top&&a[sta[top]]<=a[i]) lef[sta[top--]]=i+1;sta[++top]=i;}while(top) lef[sta[top--]]=1; } void pushup(ll p){if(tr[p<<1].val>tr[p<<1|1].val){tr[p].val=tr[p<<1].val;tr[p].id=tr[p<<1].id;}else {tr[p].val=tr[p<<1|1].val;tr[p].id=tr[p<<1|1].id;} } void built(ll p,ll l,ll r){tr[p].l=l,tr[p].r=r;if(l==r){tr[p].val=a[l];tr[p].id=l;return ;}ll mid=(l+r)>>1;built(p<<1,l,mid);built(p<<1|1,mid+1,r);pushup(p); } void seg_max(ll p,ll l,ll r){if(tr[p].l>=l&&tr[p].r<=r){if(tr[p].val>maxn){maxn=tr[p].val;ida=tr[p].id;}return ;}ll mid=(tr[p].l+tr[p].r)>>1;if(mid>=l)seg_max(p<<1,l,r);if(mid<r)seg_max(p<<1|1,l,r); } void pre(ll l,ll r,ll now,ll nowmax){if(l>r) return ;lef[now]=l,rig[now]=r;if(l==r) {len[now]=r-l+1;return ;}maxn=-1,ida=0;if(l<=now-1){ seg_max(1,l,now-1);pre(l,now-1,ida,maxn);}maxn=-1,ida=0;if(now+1<=r){seg_max(1,now+1,r);pre(now+1,r,ida,maxn);} } void work1(){for(ll j=0;j<=20;j++)for(ll i=1;i<=n;i++){_0[i][j]=_0[i-1][j];_1[i][j]=_1[i-1][j];if((a[i]&(1<<j))) _1[i][j]++;else _0[i][j]++;}for(ll i=1;i<=n;i++){ll tmp=0;for(ll j=0;j<=20;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*(1<<j)%mod)))%mod;tmp=(tmp+(l1*(r0%mod*(1<<j)%mod)))%mod;}ans1=(ans1+tmp*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 i=20;i>=0;i--){ll bit=(val>>i)&1;if(!ch[C][bit]){ch[C][bit]=newnode();ch[C][!bit]=ch[F][!bit];sz[ch[C][bit]]=sz[ch[F][bit]];}C=ch[C][bit],F=ch[F][bit];sz[C]++;} } ll query(ll F,ll C,ll now,ll big){ll ans=0;for(ll i=20;i>=0;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) F=ch[F][nowbit^1],C=ch[C][nowbit^1];else F=ch[F][nowbit],C=ch[C][nowbit],ans=(ans+num[nowbit^1]%mod); }return ans; } void work2(){root[0]=newnode();for(ll i=1;i<=n;i++)root[i]=newnode(),insert(root[i-1],root[i],a[i]);for(ll i=1;i<=n;i++){ll tmp=0;if(rig[i]-i>i-lef[i])for(ll j=lef[i];j<=i;j++)tmp=(tmp+query(root[i-1],root[rig[i]],a[j],a[i]))%mod;if(rig[i]-i<=i-lef[i])for(ll j=i;j<=rig[i];j++)tmp=(tmp+query(root[lef[i]-1],root[i],a[j],a[i]))%mod;ans2=(ans2+tmp*a[i])%mod;} } int main(){scanf("%lld%lld",&n,&q);for(ll i=1;i<=n;i++){scanf("%lld",&a[i]);if(a[i]>mx)ida=i,mx=a[i];mn=min(mn,a[i]);}thebigestid=ida;built(1,1,n);pre(1,n,ida,a[ida]);work1();work2();if(q==1)printf("%lld\n",ans1);if(q==2)printf("%lld\n",ans2);if(q==3)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$

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long ll n,m,ans=0; const ll mod=1e9+7; ll meng(ll x,ll k){ll ans=1;for(;k;k>>=1,x=x*x%mod){if(k&1)ans=ans*x%mod;}return ans; } ll k; int main(){scanf("%lld%lld%lld",&n,&m,&k);for(ll i=1;i<=k;i++)ans=(ans+meng(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$,$+x+y$,$-x+y$,$+x-y$

然后發現一個性質我們把一個原本應該是$-x-y$的拆成$4$個另外三個并不會比$-x-y$變優

于是我們愉快維護四個最大值變量就行了

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long #define maxn 2101 ll n,m,cnt=0,st=0,ans=0,mx1=0,mx2=0,mx3=0,mx4=0; ll tmp1,tmp2,tmp3,tmp4,sta; ll read(){ll x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return f*x; } struct node{ll x,y,val;friend bool operator < (const node &a,const node &b){return a.val<b.val;} }c[maxn*maxn]; ll b[maxn][maxn],f[maxn*maxn]; int main(){n=read(),m=read();for(ll i=1;i<=n;i++)for(ll j=1,a;j<=m;j++){scanf("%lld",&a);if(a==0) continue;++cnt;c[cnt].x=i;c[cnt].y=j;c[cnt].val=a;}for(ll i=1;i<=n;i++)for(ll j=1;j<=m;j++){scanf("%lld",&b[i][j]);}sort(c+1,c+cnt+1);for(ll i=cnt;i>=2;i--){if(c[i].val!=c[i-1].val){sta=i;}}for(ll i=1;i<sta;i++){ll x=c[i].x,y=c[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);tmp1=max(tmp1,f[i]-x-y);tmp2=max(tmp2,f[i]-x+y);tmp3=max(tmp3,f[i]+x-y);tmp4=max(tmp4,f[i]+x+y);ans=max(ans,f[i]);}for(ll i=sta;i<=cnt;i++){ll x=c[i].x,y=c[i].y;if(c[i].val!=c[i-1].val){mx1=max(mx1,tmp1);mx2=max(mx2,tmp2);mx3=max(mx3,tmp3);mx4=max(mx4,tmp4);} // printf("mx1=%lld 2=%lld 3=%lld 4=%lld\n",mx1,mx2,mx3,mx4);ll an=0;an=max(an,mx1+x+y);an=max(an,mx2+x-y);an=max(an,mx3-x+y);an=max(an,mx4-x-y);f[i]=an+b[c[i].x][c[i].y];tmp1=max(tmp1,f[i]-x-y);//左上tmp2=max(tmp2,f[i]-x+y);//右上tmp3=max(tmp3,f[i]+x-y);//左下tmp4=max(tmp4,f[i]+x+y);//右下ans=max(ans,f[i]);} // for(ll i=1;i<=cnt;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 l=1,r=ans;while(l<=r){int mid=(l+r)>>1;if(judge(mid)) l=mid+1;else r=mid-1;} }

?

我暴力$+$剪枝$AC$思考怎么剪枝

首先枚舉是越修改越小的,我們可以記錄下當前答案,然后下次驗證時在當前答案基礎上驗證就行了

然后還有記錄當前所有符合答案

cnt++;mo[cnt].x=x,mo[cnt].y=y,mo[cnt].ok=1,mo[cnt].len=i;

驗證時

for(ll j=1;j<=cnt;j++)if(mo[j].ok){if(x>=mo[cnt].x&&x<=mo[cnt].x+mo[cnt].len-1&&y>=mo[cnt].y&&y<=mo[cnt].y+mo[cnt].len-1) mo[j].ok=0;else allok=1;}if(allok) printf("%d\n",nowans);else pre(),printf("%d\n",nowans);

復雜度與變化次數相關

代碼

#include<bits/stdc++.h> using namespace std; #define ll int #define A 1111 char a[A][A]; ll cnt=0,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(){cnt=0;for(ll i=nowans;i>=1;i--){for(ll x=1;x<=n-i+1;x++){for(ll y=1;y<=n-i+1;y++)if(sum[x+i-1][y+i-1]+sum[x-1][y-1]-sum[x-1][y+i-1]-sum[x+i-1][y-1]==0){ cnt++;mo[cnt].x=x,mo[cnt].y=y,mo[cnt].ok=1,mo[cnt].len=i;nowans=i;}}if(cnt) return ;} } int main(){scanf("%d%d%d",&n,&m,&k);for(ll i=1;i<=n;i++){scanf("%s",a[i]+1);for(ll j=1;j<=m;j++)if(a[i][j]=='-') sum[i][j]=1;}ll x,y;scanf("%d%d",&x,&y);sum[x][y]=1;for(ll i=1;i<=n;i++)for(ll j=1;j<=m;j++)sum[i][j]=sum[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];nowans=n;pre();printf("%d\n",nowans);for(ll i=2,x,y;i<=k;i++){scanf("%d%d",&x,&y);for(ll i=x;i<=n;i++)for(ll j=y;j<=m;j++)sum[i][j]++;ll allok=0;for(ll j=1;j<=cnt;j++)if(mo[j].ok){if(x>=mo[cnt].x&&x<=mo[cnt].x+mo[cnt].len-1&&y>=mo[cnt].y&&y<=mo[cnt].y+mo[cnt].len-1) mo[j].ok=0;else allok=1;}if(allok) printf("%d\n",nowans);else pre(),printf("%d\n",nowans);} } View Code

?

轉載于:https://www.cnblogs.com/znsbc-13/p/11428910.html

總結

以上是生活随笔為你收集整理的理科卷math·english·chinese·biology·chemistry·physics的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。