矩陣游戲

考試時思路一度和正解一樣，考試到最后還是打了80分思路，結果80分打炸了只得了40分暴力分

題解

算出來第一列的總值，每次通過加每兩列之間的差值得出下一列的總值

算第一列我們只需要讓當前點*行增倍的數量就行了

for(ll i=1;i<=n;i++){nowlie=(nowlie+elephant(i,1)*hang[i])%mod;sum=(sum+hang[i]);}

算其他列

nowlie=(nowlie+sum)%mod;

可能這一列會加倍只需乘上就行了

ans=(ans+nowlie*lie[i])%mod;

思路簡單代碼好打，然而考試我還是打炸了

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long #define A 1010101 const ll mod=1e9+7; ll n,m,nowlie=0,sum=0,ans=0,k; ll lie[A],hang[A]; char c[5]; ll elephant(ll i,ll j){return ((i-1)*m%mod+j)%mod; } int main(){scanf("%lld%lld%lld",&n,&m,&k);for(ll i=1;i<=1000000;i++){hang[i]=1;lie[i]=1;}for(ll i=1,a,x;i<=k;i++){scanf("%s",c+1);scanf("%lld%lld",&a,&x);if(c[1]=='S'){lie[a]=lie[a]*x%mod;}if(c[1]=='R'){hang[a]=hang[a]*x%mod;}}for(ll i=1;i<=n;i++){nowlie=(nowlie+elephant(i,1)*hang[i])%mod;sum=(sum+hang[i]);}for(ll i=1;i<=m;i++){ans=(ans+nowlie*lie[i])%mod;nowlie=(nowlie+sum)%mod;}cout<<ans<<endl; }

t2，t3卡常題目，AC不了的

跳房子

看了一晚上第三題又看了掃描線，又打了一晚上，又理解了圖論tarjan來做第三題，所以我用兩個小時把t2A了？？？？？？？

莫名和考試時思路相似 ? 其實一點也不相似

$85\%$算法

暴力找循環節，剩下數據經過特殊構造你AC不了的，，，，，，，，，

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long char s[10]; #define A 11111111 ll vis[5100][5100],a[5100][5100]; inline int read(){register int ret=0,f=1;register char r;r=getchar();while(!isdigit(r)){if(r=='-') f=-1;r=getchar();}while(isdigit(r)){ret=ret*10+r-'0';r=getchar();}return f*ret; } ll p,nowx=1,nowy=1,top=0,n,m; ll stax[A],stay[A]; void work(ll x){ll tot=0;while(x){ll nx=nowx,ny=nowy,d2=nx+1,d3=nx-1;(nx+1==n+1)?d2=1:d2=nx+1;(nx-1==0)?d3=n:d3=nx-1;if(ny==m) ny=0;ll z1=a[nx][ny+1],z2=a[d2][ny+1],z3=a[d3][ny+1];if(z1>z2&&z1>z3) nowx=nx,nowy=ny+1;else if(z2>z1&&z2>z3) nowx=d2,nowy=ny+1;else if(z3>z1&&z3>z2) nowx=d3,nowy=ny+1;x--;top++;stax[top]=nowx,stay[top]=nowy;if(!vis[nowx][nowy])vis[nowx][nowy]=top;else{tot=top-vis[nowx][nowy];x=x%tot;}}while(top){ll x=stax[top],y=stay[top];vis[x][y]=0;top--;}printf("%lld %lld\n",nowx,nowy); } int main(){n=read(),m=read();for(ll i=1;i<=n;i++)for(ll j=1;j<=m;j++)a[i][j]=read();p=read();for(ll i=1,aa,bb,cc;i<=p;i++){scanf("%s",s+1);if(s[1]=='m'){cc=read();work(cc);}if(s[1]=='c'){aa=read(),bb=read(),cc=read();a[aa][bb]=cc;}} }

$100\%$算法

和找循環節類似但又有很大區別，

思考循環節問題出現在那？

可能會遍歷整張圖才找到一個循環節，即使你預處理了找到循環節，那么出現change正好改掉循環節，再move找循環節，再change 再move你就被卡死了，復雜度本身就有問題

那么沒辦法做了嗎

建立置換，走到一個點，如果步數大就直接置換，步數小就暴力走

我們用一個線段樹來維護這個置換如果從1--m建樹，那么t[1]就表示走m步置換成哪里

每次走m步

走的次數就是v/m

根據置換的運算$t^k$就是走了k次每次走t步

通過快速冪算出置換得出結果

那么我們經過%可以快速算出來剩下的，剩下的步數暴力走即可

順便學了置換的運算

?? ??? ???? c.g[i]=a.g[t.g[i]];

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long #define A 1010101 ll n,m,k,nowx=1,nowy=1; ll f[2100][2100]; char znsbc[10]; struct node{ll g[2100];node(){for(ll i=1;i<=n;i++)g[i]=i;}node operator *(const node &a){node t=*this,c;for(ll i=1;i<=n;i++)c.g[i]=a.g[t.g[i]];return c;} }nxt[2100]; struct tree{ll l,r,f;node t; }tr[10100]; inline void up(ll p){tr[p].t=tr[p<<1].t*tr[p<<1|1].t;return ; } inline void built(ll p,ll l,ll r){tr[p].l=l,tr[p].r=r;if(l==r){tr[p].t=nxt[l];return ;}ll mid=(l+r)>>1;built(p<<1,l,mid);built(p<<1|1,mid+1,r);up(p); } inline void add(ll p,ll o){ // printf("l=%lld r=%lld\n",l,r);if(tr[p].l==tr[p].r){tr[p].t=nxt[o];return ;}ll mid=(tr[p].l+tr[p].r)>>1;if(mid>=o)add(p<<1,o);elseadd(p<<1|1,o);up(p); } inline node meng(node x,ll k){node ans;for(;k;k>>=1,x=x*x)if(k&1) ans=ans*x;return ans; } inline ll get(ll k,ll flag){if(k==(flag?m+1:n+1))return 1;if(!k)return flag?m:n;return k; } inline void change(ll xx,ll yy){ll maxn=0;xx=get(xx,0);yy=get(yy,1);for(ll i=-1;i<=1;i++){ll x=get(xx+i,0),y=get(yy+1,1);if(maxn<f[x][y]) maxn=f[x][y],nxt[yy].g[xx]=x;}return ; } inline void move(ll x){while(x)x--,nowx=nxt[nowy].g[nowx],nowy=get(nowy+1,1)/*,printf("x=%lld\n",x)*/; } int main(){scanf("%lld%lld",&n,&m);for(ll i=1;i<=n;i++)for(ll j=1;j<=m;j++)scanf("%lld",&f[i][j]);for(ll i=1;i<=n;i++)for(ll j=1;j<=m;j++)change(i,j);built(1,1,m);scanf("%lld",&k);for(ll i=1,a,b,c,v,o;i<=k;i++){scanf("%s",znsbc+1);if(znsbc[1]=='m'){scanf("%lld",&v);ll len=min(v,m-nowy+1);move(len);v-=len;if(v){nowx=meng(tr[1].t,v/m).g[nowx];v%=m;if(v){move(v);}}printf("%lld %lld\n",nowx,nowy);}else{scanf("%lld%lld%lld",&a,&b,&c);f[a][b]=c;for(ll j=-1;j<=1;j++)change(a+j,b-1)/*,printf("*****\n");*/;o=get(b-1,1);add(1,o);}} }

?隨機數據生成

#include<bits/stdc++.h> #define ll long long using namespace std; ll random(ll n) {return rand()%n; } bool a[3210520]; int main() {freopen("mkd.txt","w",stdout); srand((unsigned)time(0));ll n=random(5)+5,m=random(5)+5;printf("%lld %lld\n",n,m);for(ll i=1;i<=n;i++,puts(""))for(ll j=1;j<=m;j++){ll x=random(550);while(a[x]) x=random(550);printf("%lld ",x);}ll k=random(50)+50;printf("%lld\n",k);for(ll i=1;i<=k;i++){ll op=random(2);if(op) {printf("move ");printf("%lld\n",random(50000)+50000);}else{printf("change ");ll l=random(n)+1;ll r=random(m)+1;printf("%lld %lld %lld\n",l,r,random(50)+50); }}fclose(stdout); } View Code

t3做法尤其玄學

傻逼卡常題，傻逼卡常題，傻逼卡常題，毒瘤出題人，毒瘤數據，毒瘤做法

做法1，把序列問題轉化為圖論？？？？？？？？線段樹優化建邊+tarjan縮點+線段樹維護圖中內容我不會

做法2，掃描線，一條性質，若a<=b<=c<=d并且a--c是好區間，b--d是好區間，那么a--d是好區間

假設我們掃描到i i+1，那么如果i i+1在好區間里，那么val[i] val[i+1]都在好區間里,

設好的二元組為相鄰兩個數,那么區間若為好區間好二元組數量為r-l

用一棵線段樹維護二元組數量設為v,若v+l=r則是好區間,假設我們當前掃描到了a[i],那么處于a[i]-1? a[i]+1的位置都要加1

線段樹維護一下,細節比較多

做法3,性質若r-l=maxval-minval那么就是一個好區間

那么若maxval到minval之間全部出現那么是一個好區間,那么位置最左最右值出現即可,,

線段樹維護一下||st表維護一下

但做法3本身復雜度不對,隨機數據下表現優秀,但會被特殊數據卡

分塊優化一下

#include<bits/stdc++.h> #define MAXN 100005 #define min(a,b) ((a<b)?(a):(b)) #define max(a,b) ((a>b)?(a):(b)) using namespace std; int mn[20][MAXN],mx[20][MAXN],mh[MAXN],a[MAXN],n,mnpos[20][MAXN],mxpos[20][MAXN],ans1[2005][2005],ans2[2005][2005],t; int bl[MAXN]; vector<int>ld; void pre() {for(int i=1;i<=n;i++)for(int j=17;j>=0;j--)if(i>=(1<<j)) {mh[i]=j;break;}for(int i=1;i<=17;++i)for(int j=1;j<=n;++j){mn[i][j]=min(mn[i-1][j],mn[i-1][j+(1<<(i-1))]);mx[i][j]=max(mx[i-1][j],mx[i-1][j+(1<<(i-1))]);mnpos[i][j]=min(mnpos[i-1][j],mnpos[i-1][j+(1<<(i-1))]);mxpos[i][j]=max(mxpos[i-1][j],mxpos[i-1][j+(1<<(i-1))]);}return ; } /*const int L=1<<20|1; char buffer[L],*S,*T; #define getchar() ((S==T&&(T=(S=buffer)+fread(buffer,1,L,stdin),S==T))?EOF:*S++)*/ inline int Rd() {int x=0;char c=getchar();while(c>'9'||c<'0')c=getchar();while(c>='0'&&c<='9'){x=x*10+c-48;c=getchar();}return x; } inline int gmax(int l,int r) {return max(mx[mh[r-l+1]][l],mx[mh[r-l+1]][r-(1<<mh[r-l+1])+1]); } inline int gmin(int l,int r) {return min(mn[mh[r-l+1]][l],mn[mh[r-l+1]][r-(1<<mh[r-l+1])+1]); } inline int qmax(int l,int r) {return max(mxpos[mh[r-l+1]][l],mxpos[mh[r-l+1]][r-(1<<mh[r-l+1])+1]); } inline int qmin(int l,int r) {return min(mnpos[mh[r-l+1]][l],mnpos[mh[r-l+1]][r-(1<<mh[r-l+1])+1]); } int main() { // freopen("sequence21.in","r",stdin);n=Rd();t=pow(n,0.7);for(int i=1;i<=n;i++) {a[i]=Rd();mn[0][i]=mx[0][i]=a[i];mnpos[0][a[i]]=mxpos[0][a[i]]=i;}int p=0,tot=0;while(p<n){ld.push_back(p+1);for(int i=1;i<=t;i++)bl[p+i]=tot;p+=t;tot++;}pre();memset(ans1,0x3f,sizeof(ans1));memset(ans2,-0x3f,sizeof(ans2));for(int i=0;i<ld.size();i++)for(int j=i;j<ld.size();j++){int l,r;l=ld[i];r=ld[j];int nowmin=gmin(l,r),nowmax=gmax(l,r);int pl=qmin(nowmin,nowmax),pr=qmax(nowmin,nowmax);while(l>pl||r<pr){if(l>pl){nowmin=min(nowmin,gmin(pl,l));nowmax=max(nowmax,gmax(pl,l));l=pl;}if(r<pr){nowmin=min(nowmin,gmin(r,pr));nowmax=max(nowmax,gmax(r,pr));r=pr;}pl=qmin(nowmin,nowmax);pr=qmax(nowmin,nowmax);}ans1[i][j]=l;ans2[i][j]=r;// cout<<ans1[i][j]<<' '<<ans2[i][j]<<endl; }int Q;Q=Rd();while(Q--){register int l,r,ll,rr;l=Rd();r=Rd();ll=bl[l]+1;rr=bl[r]-1;int nowmin=gmin(l,r),nowmax=gmax(l,r);int pl=qmin(nowmin,nowmax),pr=qmax(nowmin,nowmax);while(l>pl||r<pr){ll=bl[l]+1;rr=bl[r]-1;if(l>pl){nowmin=min(nowmin,gmin(pl,l));nowmax=max(nowmax,gmax(pl,l));l=pl;l=min(l,ans1[ll][rr]);}if(r<pr){nowmin=min(nowmin,gmin(r,pr));nowmax=max(nowmax,gmax(r,pr));r=pr;r=max(r,ans2[ll][rr]);}pl=qmin(nowmin,nowmax);pr=qmax(nowmin,nowmax);}printf("%d %d\n",l,r);}return 0; }

?

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

總結

以上是生活随笔為你收集整理的NOIP模拟测试13「矩阵游戏·跳房子·优美序列」的全部內容，希望文章能夠幫你解決所遇到的問題。

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