问题 A: Three-Axis Views
给出一个立方体的三个视图，问这样的立方体是否存在。
最初的思路是通过图1 , 2的z坐标确定出( x , y )，看这样的( x , y )在图3里是否也存在。
但是应该对x坐标确定的( y , z )和y坐标确定的( x , z )也做相同的检查。
int n; int mp[4][110][110]; char s[110]; int b[4][110][110]; int las[110][110][110]; int main(){ n=read; rep(i,0,2){ for(int j=1,t=n;j<=n;j++,t--){ cin>>s+1; for(int k=1;k<=n;k++){ if(s[k]=='1'){ mp[i][k][t]=1; } } } } rep(i,1,n) rep(j,1,n) rep(k,1,n) if(mp[0][j][k]&&mp[1][k][i]&&mp[2][i][j]) b[0][j][k]=b[1][k][i]=b[2][i][j]=1; rep(i,0,2) rep(j,1,n) rep(k,1,n){ if(b[i][j][k]!=mp[i][j][k]){ cout<<"No";return 0; } } cout<<"Yes"; return 0; }
B: Secrets of Legendary Treasure
题意：
给出一个长度为n的序列a和长度为m的序列b。其中a , b里非0的位置要填充上[ 1 , n + m ]的整数，并且每个数只能够出现一次。输出方案数。
思路：
记录下序列a , b里非0位的数值和位置，每次取最小的，将中间的一段填上数。
注意：
每次填数的时候从1开始，填未被填过的数并且填的数的大小也合法
如果序列的最后一个位置是0的话，要再记录一下n + 1或m + 1的位置
const int maxn=2e5+100,inf=0x3f3f3f3f; const double eps=1e-5; int n,m,a[maxn],b[maxn]; bool vis[maxn]; vector<PII>pa,pb; int main(){ n=read,m=read; rep(i,1,n){ int x=read; a[i]=x; if(x!=0) pa.push_back({x,i}); vis[x]=1; } if(a[n]==0) pa.push_back({n+m+1,n+1}); rep(i,1,m){ int x=read; b[i]=x; if(x!=0) pb.push_back({x,i}); vis[x]=1; } if(b[m]==0) pb.push_back({n+m+1,m+1}); int now=1,cnta=0,cntb=0,ta=0,tb=0,lasta=1,lastb=1; while(ta<pa.size()||tb<pb.size()){ int nowa=1e9,nowb=1e9; if(ta<pa.size()) nowa=pa[ta].first; if(tb<pb.size()) nowb=pb[tb].first; now=1; if(nowa<nowb){ for(int i=lasta;i<=pa[ta].second-1;i++){ while(vis[now]||now<cnta) now++; a[i]=now;vis[now]=1; } a[pa[ta].second]=nowa;vis[nowa]=1; lasta=pa[ta].second+1; cnta=pa[ta].first; ta++; } else{ for(int i=lastb;i<=pb[tb].second-1;i++){ while(vis[now]||now<cntb) now++; b[i]=now;vis[now]=1; } b[pb[tb].second]=nowb;vis[nowb]=1; lastb=pb[tb].second+1; cntb=pb[tb].first; tb++; } } rep(i,1,n) cout<<a[i]<<" "; puts(""); rep(i,1,m) cout<<b[i]<<" "; return 0; }
