NOIP 提高组 2008

P1006 传纸条

//关键在于想到两个人一块做 #include<cstring> #include<cstdio> #include<iostream> using namespace std; int n,m,map[51][51],f[51][51][51][51]; int MAX(int a,int b,int c,int d){ return max(max(a,b),max(c,d)); } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&map[i][j]); for(int i=1,l;i<=n;i++) for(int j=1;j<=m;j++){ for(int k=1;k<=n;k++){ if(i+j-k>0) l=i+j-k; else continue; f[i][j][k][l]=MAX(f[i-1][j][k-1][l],f[i-1][j][k][l-1] ,f[i][j-1][k-1][l],f[i][j-1][k][l-1] )+map[i][j]+map[k][l]; if(i == k && j == l) f[i][j][k][l] -= map[i][j]; } } printf("%d\n",f[n][m][n][m]); return 0; }

P1125 笨小猴

#include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; char s[2000]; int num[2500],minn=1<<25-1,maxn=-250; inline bool Judge(int x){ if(x==0) return false; if(x==1) return false; if(x==2) return true; for(int i=2;i*i<=x;++i) if(x%i==0) return false; return true; } int main(){ scanf("%s",s+1); int len=strlen(s+1); for(int i=1;i<=len;++i) ++num[(int)s[i]]; for(int i=1;i<=len;++i) maxn=max(maxn,num[(int)s[i]]),minn=min(minn,num[(int)s[i]]); if(Judge(maxn-minn)){ printf("Lucky Word\n"); printf("%d\n",maxn-minn); return 0; } else{ printf("No Answer\n"); printf("%d\n",0); return 0; } return 0; }

P1149 火柴棒等式

//暴力搜索 #include<iostream> #include<cstring> #include<cstdio> using namespace std; int num[12]={6,2,5,5,4,5,6,3,7,6}; int n,ans=0; inline int matches(int x){ int ret=0,j=x; while(j!=0){ ret+=num[j%10]; j/=10; } if(x==0) ret+=num[0]; return ret; } int main(){ cin>>n; for(int i=0;i<=1000;++i) for(int j=0;j<=1000;++j) if(matches(i)+matches(j)+matches(i+j)+4==n) ++ans; cout<<ans; }

P1155 双栈排序

这个题并不是那么的水

/*二分图染色+模拟 1.首先考虑一个简单情况——单栈排序,显然有这样的一个事实： a[i]和a[j] 不能压入同一个栈⇔存在一个k,使得i<j<k且a[k]<a[i]<a[j] 时间复杂度为O(n^3).对于n<=1000仍显吃力,对此可以用动态规划的思想,将上述复杂度降到O(n^2)。 状态:f[i]=min(a[i],a[i+1], ... ,a[n]) 边界条件:f[n+1]=INF; 状态转移方程:f[i]=min(f[i+1],a[i]); 于是上述判断就转化为了f[j+1]<a[i] && a[i]<a[j] 2.扩展到双栈排序: 如果a[i]和a[j]不能在一个栈内，即连接一条i与j之间的无向边,接下来我们只需要判断这个图是否为二分图 由于题目中说编号的字典序要尽可能的小，那么就把编号小的尽可能放到stack1 判断二分图的方法可以采用黑白染色的方式，先从编号小的开始染,第一个顶点染成黑色,相邻的顶点染成不同的颜色,如果发现黑白冲突,那么说明这个图不是一个二分图,是不合法的,输出0. (DFS或BFS染色均可) 3.染色后所有黑色的点进stack1,所有白色的点进stack2，最后模拟输出过程就可以了.*/ #include<iostream> #include<cstring> #include<cstdio> #include<queue> #include<vector> #include<stack> #include<algorithm> using namespace std; #define MAXN 1005 #define INF 0x7f7f7f7f #define min(a,b) (a)<(b)?(a):(b) int n,a[MAXN],f[MAXN],color[MAXN]; vector<int> G[MAXN]; stack<int> s1,s2; void BFS(int s){ queue<int> q; q.push(s); color[s]=1; while(!q.empty()){ int u=q.front();q.pop(); for(int i=0;i<G[u].size();++i){ int v=G[u][i]; if(color[v]==-1) color[v]=color[u]^1,q.push(v); else if(color[v]!=(color[u]^1)){ printf("0"); exit(0); } } } } int main(){ memset(color,-1,sizeof color ); scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%d",&a[i]); f[n+1]=INF; for(int i=n;i>=1;--i) f[i]=min(f[i+1],a[i]); for(int i=1;i<=n;++i) for(int j=i+1;j<=n;++j) if(a[i]>f[j+1]&&a[i]<a[j]) G[i].push_back(j),G[j].push_back(i); for(int i=1;i<=n;++i) if(color[i]==-1) BFS(i); int cnt=1; for(int i=1;i<=n;++i){ if(color[i]==1) s1.push(a[i]),printf("a "); else s2.push(a[i]),printf("c "); while((!s1.empty()&&s1.top()==cnt)||(!s2.empty()&&s2.top()==cnt)){ if(!s1.empty()&&s1.top()==cnt) s1.pop(),printf("b "); else s2.pop(),printf("d "); ++cnt; } } return 0; }