【模拟赛 2020/3/28】 A. 【NOIP2006 提高组】作业调度方案 B. 【NOIP2006 提高组】2k 进制数 C. 【NOIP2008 提高组】传纸条 D. 【NOIP2008 提高组】双栈排序
思路：先看懂题目，按照题目所给的方法模拟，写的时候还要特别加一个last[]数组保存最后建造时间。
1 #include<bits/stdc++.h> 2 #define LL long long 3 using namespace std; 4 const int mxn=500; 5 int read(){ 6 int x=0,f=1;char ch=getchar(); 7 while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();} 8 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} 9 return x*f; 10 } 11 int n,m; 12 int ord[mxn]; 13 int mac[mxn][mxn]; 14 int use[mxn][mxn]; 15 int step[mxn]; 16 int last[mxn]; 17 bool sp[mxn][mxn]; 18 int main(){ 19 m=read();n=read(); 20 int i,j; 21 int cnt=m*n; 22 for(i=1;i<=cnt;++i){ 23 ord[i]=read(); 24 } 25 for(i=1;i<=n;i++) 26 for(j=1;j<=m;j++) 27 mac[i][j]=read(); 28 for(i=1;i<=n;i++) 29 for(j=1;j<=m;j++) 30 use[i][j]=read(); 31 int ans=0; 32 for(int k=1;k<=cnt;k++){ 33 int od=ord[k]; 34 step[od]++; 35 int now=step[od]; 36 int unow=mac[od][now]; 37 int tct=0; 38 for(i=last[od]+1;i<500;i++){ 39 if(!sp[unow][i])tct++; 40 else tct=0; 41 if(tct>=use[od][now]){ 42 last[od]=i; 43 for(j=i-tct+1;j<=i;j++){sp[unow][j]=1;} 44 ans=max(ans,last[od]); 45 break; 46 } 48 } 49 } 50 printf("%d ",ans); 51 return 0; 52 }
B. 【NOIP2006 提高组】2k 进制数
待。。。
C. 【NOIP2008 提高组】传纸条
思路：这道题我们先来康康如果只有一张纸条的情况
如果只有一张纸条，从（1，1）->（n，m），很明显的状态转移方程为：
dp[i][j] = max(dp[i-1][j] , dp[i][j-1]);
但现在有两个纸条，也就是说这个图上要出现两条不相交的路线，并使得权值最大
现在我们设四维dp ijkl；
为了解决不能路径相交，所以我们两个纸条一起进行传递，
方程就为：
dp[i][j][k][l]=max(max(dp[i][j-1][k][l-1],dp[i][j-1][k-1][l]),max(dp[i-1][j][k][l-1],dp[i-1][j][k-1][l]))+a[i][j]+a[k][l];
我们可以将四层循环优化成三层
由于ij kl 两个纸条是一起移动 所以i+j=k+l;
所以l可以由ijk算出
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 int a[52][52]; 5 int dp[52][52][52][52]; 6 7 int main() { 8 int i,j,k,l,m,n,ans; 9 scanf("%d%d",&m,&n); 10 ans=0; 11 for(i=1; i<=m; i++) { 12 for(j=1; j<=n; j++) 13 scanf("%d",&a[i][j]); 14 } 15 for(i=1; i<=m; i++) { 16 for(j=1; j<=n; j++) { 17 for(k=i+1; k<=m; k++) { 18 l=i+j-k; 19 if(l<=0) continue; 20 dp[i][j][k][l]=max(max(dp[i][j-1][k][l-1],dp[i][j-1][k-1][l]),max(dp[i-1][j][k][l-1],dp[i-1][j][k-1][l]))+a[i][j]+a[k][l]; 21 } 22 } 23 24 } 25 ans=max(max(dp[m][n-1][m][n-1],dp[m][n-1][m-1][n]),max(dp[m-1][n][m-1][n],dp[m-1][n][m][n-1])); 26 printf("%d ",ans); 27 }
D. 【NOIP2008 提高组】双栈排序
i,j能够被压入同一个栈中的条件是不存在满足如下条件的元素k：
a[k]<a[i]<a[j]， i<j<k
因为当把j压入栈中时要先将i弹栈，而把i弹栈之前必定已经将k弹栈，这和i，j，k的顺序是矛盾的。
将不能放入同一个栈中的元素两两连边，之后二分图判定，解决可行性之后贪心解决字典序问题即可
所以如果输入数据不能使得所有限制成立则无解，然后就可以转化成二分图染色来判定
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int Max=1010; 5 int n,m=1,size,tot1,tot2,p1[Max],p2[Max]; 6 int first[Max],f[Max],num[Max],vis[Max]; 7 struct shu{int to,next,len;}edge[Max*Max]; 8 char s[Max<<1]; 9 int cnt; 10 11 int read(){ 12 int x=0,f=1;char ch=getchar(); 13 while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();} 14 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} 15 return x*f; 16 } 17 18 inline void build(int x,int y) 19 { 20 edge[++size].next=first[x],first[x]=size,edge[size].to=y; 21 edge[++size].next=first[y],first[y]=size,edge[size].to=x; 22 } 23 24 inline void pre() 25 { 26 f[n]=num[n]; 27 for(int i=n-1;i>=1;i--) f[i]=min(f[i+1],num[i]); 28 for(int i=1;i<=n;i++) 29 for(int j=i+1;j<=n;j++) 30 if(f[j]<num[i]&&num[i]<num[j]) build(i,j); 31 } 32 33 inline bool dfs(int p,int color) 34 { 35 vis[p]=color; 36 for(int u=first[p];u;u=edge[u].next) 37 { 38 int to=edge[u].to; 39 if(!vis[to]) dfs(to,3-color); 40 else if(color==vis[to]) return 0; 41 } 42 return 1; 43 } 44 45 int main() 46 { 47 n=read(); 48 for(int i=1;i<=n;i++) num[i]=read(); 49 pre(); 50 for(int i=1;i<=n;i++) if(!vis[i]&&!dfs(i,1)) {puts("0");return 0;} 51 for(int i=1;i<=n;i++) 52 { 53 if(vis[i]==1)p1[++tot1]=num[i],s[++cnt]='a'; 54 else p2[++tot2]=num[i],s[++cnt]='c'; 55 while(m==p1[tot1]||m==p2[tot2]) 56 { 57 if(m==p1[tot1]) tot1--,s[++cnt]='b'; 58 else tot2--,s[++cnt]='d'; 59 m++; 60 } 61 } 62 putchar(s[1]); 63 for(int i=2;i<=cnt;i++){ 64 putchar(' '); 65 putchar(s[i]); 66 } 67 return 0; 68 }