WA & TLE 30pts 求调

P1312 [NOIP2011 提高组] Mayan 游戏

ttx 我帮你调出来了! 改了的地方有注释 ```cpp /* * @ Author: Xiaohuba * @ Usage: Luogu Problem * @ Language: C++ */ #include<bits/stdc++.h> using namespace std; #define ll long long #define lll __int128 #define pii pair<int,int> #define mkp make_pair #define vi vector<int> #define vs vector<string> #define viit vector<int>::iterator #define il inline #define Endl putchar('\n') #define Space putchar(' ') template <typename T> il void read(T & tmp){ tmp=0;char c=getchar();bool flg=0;while(!isdigit(c)) flg=c=='-',c=getchar();while(isdigit(c)) tmp=(tmp<<3)+(tmp<<1)+c-'0',c=getchar();if(flg) tmp*=-1; } template <typename T, typename... Args> il void read(T &tmp, Args &...tmps){ read(tmp);read(tmps...); } template <typename T> il void __write(const T &x){ if(x==0) return;__write(x/10);putchar(x%10+'0'); } template <typename T> il void write(const T &x){ if(x==0) putchar('0');if(x<0) putchar('-');__write((x<0 ? -x : x)); } template <typename T> il void write_with_space(T &x){ write(x);Space; } template <typename T> il void write_with_endl(const T &x){ write(x);Endl; } template <typename T, typename... Args> il void write(const T &x, const Args &...y){ write_with_space(x);write_with_space(y...); } il void __getline(istream & istr, string & str){ getline(istr,str);if(*(str.end()-1)=='\r') str.erase(str.end()-1); } #define getline __getline #define For(x,st,ed) for(register int x=st,END=ed;x<=END;++x) #define ForDown(x,st,ed) for(register int x=st,END=ed;x>=END;--x) #define sq(x) (x*x) #define Set(a,b) memset(a,b,sizeof(a)) #define Cpy(a,b) memcpy(a,b,sizeof(a)) /* ---File Head--- */ #define tr(i,j) ((i-1)*5+j) int b[36]; struct point { int a[36]; int step; int cnt; bool change[36]; int sum[11]; il bool fall()//改了 { bool droped=0; For(i,1,7) For(j,1,5) b[tr(i,j)]=a[tr(i,j)]; memset(a,0,sizeof(a)); For(j,1,5) { int cnt=0; For(i,1,7) if(b[tr(i,j)]) a[tr(++cnt,j)]=b[tr(i,j)]; For(i,1,7) if(a[tr(i,j)]!=b[tr(i,j)]) droped=1; } return droped; } il bool check() { memset(change,0,sizeof(change)); bool flg=0; For(i,1,7) For(j,1,5) { if(!a[tr(i,j)]) continue; int idx1=i,idx2=j; For(k,i+1,7){ if(a[tr(k,j)]==a[tr(i,j)]) idx1++; else break; } For(k,j+1,5) { if(a[tr(i,k)]==a[tr(i,j)]) idx2++; else break; } if(idx1-i+1>=3){ For(k,i,idx1) change[tr(k,j)]=1,flg=1; } if(idx2-j+1>=3){ For(k,j,idx2) change[tr(i,k)]=1,flg=1; } } return flg; } il void doit() { For(i,1,7) For(j,1,5) if(change[tr(i,j)]) sum[a[tr(i,j)]]--,a[tr(i,j)]=0,cnt--; } il void trans(int x, int y, int op)//改了 { swap(a[tr(x,y)],a[tr(x,y+op)]); bool flg=1; while(flg) { fall(); flg=check(); doit(); } } il bool valid() { For(i,1,10) if(sum[i]==1 || sum[i]==2) return 0; return 1; } }s; int n; struct operation { int x,y,op; }oper[10]; il void output() { For(i,1,n){ write(oper[i].x);Space;write(oper[i].y);Space;write(oper[i].op); Endl; } } void dfs(const point &data) { if(!data.cnt && data.step==n) { output(); exit(0); } if(data.step==n) return; For(j,1,5) For(i,1,7)//循环顺序反了 字典序是j优先 { if(!data.a[tr(i,j)]) continue; if(j<5) { point nd=data; nd.step++; nd.trans(i,j,1); oper[nd.step]=(operation){j-1,i-1,1}; if(nd.valid()) dfs(nd); } if(!data.a[tr(i,j-1)]&&j>1) { point nd=data; nd.step++; nd.trans(i,j,-1); oper[nd.step]=(operation){j-1,i-1,-1}; if(nd.valid()) dfs(nd); } //不必要浪费步数 } } signed main() { s.cnt=0; read(n); For(i,1,5) { int x,j=0; while(++j) { read(x); if(!x) break; s.a[tr(j,i)]=x; s.cnt++; } } s.step=0; dfs(s); puts("-1"); return 0; } ```
by junxis @ 2022-02-09 20:34:30


@[Xiaohuba](/user/356003)
by junxis @ 2022-02-09 20:41:40


@[spoonjunxi](/user/551375) sjx YYDS!thx thx %%%
by Moeebius @ 2022-02-10 12:58:34


@[Xiaohuba](/user/356003) lls YYYDS!
by junxis @ 2022-02-10 13:34:03


@[spoonjunxi](/user/551375) lls调的?!/yun
by Moeebius @ 2022-02-10 15:30:25


不是,我只是随便乱%
by junxis @ 2022-02-10 16:49:11


@[Xiaohuba](/user/356003)
by junxis @ 2022-02-10 16:49:27


@ab88608861
by junxis @ 2022-02-13 21:57:03


|