HAPPY2020暑假训练前复习

A.计蒜客 - T1381

输出hello world 万恶之源

B.51Nod - 2060

全排列输出 不要用STL的next_permutation,会超时

#include <bits/stdc++.h> using namespace std; const int maxn=14; int dt[maxn]; int vis[maxn]; int n; void dfs(int depth) { if(depth==n) { for(int i=0;; ++i) { if(i==n)break; if(i==0)cout<<dt[i]; else cout<<" "<<dt[i]; } cout<<endl; return ; } for(int i=1; i<=n; ++i) { if(vis[i]==0) { vis[i]=1; dt[depth]=i; dfs(depth+1); vis[i]=0; } } } int main() { cin>>n; dfs(0); return 0; }

C HDU - 1715

求斐波那契数列（不过比较大到1000） 用数组来存每一位，模拟进制运算

#include<iostream> #include<cstdio> #include<cstring> typedef long long LL; using namespace std; int f[1005][605]; void init() { f[1][0] = f[2][0] = 1; f[1][1] = f[2][1] = 1; int len = 1; for(int i = 3;i <= 1000;i ++) { for(int j = 1;j <= len;j ++) { f[i][j] += f[i-1][j] + f[i-2][j]; if(f[i][j] >= 10) { f[i][j+1] += f[i][j] / 10; f[i][j] %= 10; } } while(f[i][len+1]) len ++; f[i][0] = len; } } int main() { int n, t; init(); scanf("%d",&t); while(t --) { scanf("%d",&n); for(int i = f[n][0];i >= 1;i --) printf("%d", f[n][i]); printf("\n"); } return 0; } #include <iostream> #include <algorithm> #include <string> #include <map> #include <set> #include <vector> #include <stack> #include <queue> #include <cstdio> #include <cmath> #include <cstdlib> #include <cstring> using namespace std; typedef long long ll; int main(){ int n,q,i,j,temp=0; cin>>q; while(q--) { cin>>n; char a[10010]="1",b[10010]="1",c[10010]={0}; for(i=0;i<n-2;i++){ int len=max(strlen(a),strlen(b)); for(j=0;j<len;j++){ //模拟加法 temp=0; if(a[j]>='0'){ //短的数不加 temp+=a[j]-'0'; } if(b[j]>='0'){ temp+=b[j]-'0'; } if(temp>=10){ //判断进位 if(c[j]>='0'){ c[j]+=temp-10; } else{ c[j]+=temp-10+'0'; } c[j+1]=1+'0'; } else{ if(c[j]>='0'){ if(temp==9){ //若前位进位了,而且加上的数字是9,那么还要进位!!! c[j]='0'; c[j+1]='1'; } else{ c[j]+=temp; } } else{ c[j]+=temp+'0'; } } } strcpy(a, b); strcpy(b, c); memset(c, 0, sizeof(c)); } int len=strlen(b); for(i=len-1;i>=0;i--){ //倒着输出 printf("%c",b[i]); } printf("\n"); } return 0; }

D POJ - 2251

三维迷宫BFS搜就完事了

#include<iostream> #include<stdio.h> #include<algorithm> #include<queue> #include<string.h> using namespace std; const int maxn=32; struct node { int x; int y; int z; int step; } start,fin; char a[maxn][maxn][maxn]; bool vis[maxn][maxn][maxn]; int dx[]={0,0,1,-1,0,0}; int dy[]={1,-1,0,0,0,0}; int dz[]={0,0,0,0,1,-1}; int l,r,c; bool flag=false; queue<node> q; void bfs() { while(q.size()) q.pop(); memset(vis,false,sizeof(vis)); q.push(start); vis[start.x][start.y][start.z]=true; while(!q.empty()) { node temp=q.front(); q.pop(); if(temp.x==fin.x && temp.y==fin.y && temp.z==fin.z) { flag=1; printf("Escaped in %d minute(s).\n",temp.step); return ; } for(int i=0;i<6;i++) { node next; next.x=temp.x+dx[i]; next.y=temp.y+dy[i]; next.z=temp.z+dz[i]; if( next.x>=0&&next.x<l && next.y>=0&&next.y<r && next.z>=0&&next.z<c &&!vis[next.x][next.y][next.z] && a[next.x][next.y][next.z]!='#') { vis[next.x][next.y][next.z]=true; next.step=temp.step+1; q.push(next); } } } } int main() { while(cin>>l>>r>>c) { if(l==0&&r==0&&c==0) { break; } for(int i=0;i<l;i++) { for(int j=0;j<r;j++) { for(int k=0;k<c;k++) { cin>>a[i][j][k]; if(a[i][j][k]=='S') { start.x=i; start.y=j; start.z=k; start.step=0; } if(a[i][j][k]=='E') { fin.x=i; fin.y=j; fin.z=k; fin.step=0; } } } } flag=0; bfs(); if(!flag) { cout<<"Trapped!"<<endl; } } return 0; }

E 计蒜客 - T2028

跳石头，经典二分题目， noip原题

#include<bits/stdc++.h> using namespace std; long long int a[50004]; long long int d,n,m; bool judge(int x){ int tot=0; int i=0; int now=0; while(i<n+1){ i++; if(a[i]-a[now]<x)tot++; else now=i; } if(tot>m)return 0; else return 1; } int main() { cin>>d>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; } a[n+1]=d; int l=1; int r=d; int ans; while(l<=r){ int mid=(l+r)>>1; if(judge(mid)){ l=mid+1; ans=mid; } else r=mid-1; } cout<<ans<<endl; }

F HDU - 1702

#include<iostream> #include<cstdio> #include<queue> #include<stack> using namespace std; void cnd(int sum,bool f) { if(f==1) {//先进先出 queue<int>q; string a; int b; for(int i=1;i<=sum;i++) { cin>>a; if(a[0]=='I') { cin>>b; q.push(b); } else { if(q.empty()) { cout<<"None"<<endl; } else { cout<<q.front()<<endl; q.pop(); } } } while(!q.empty())q.pop(); } else { stack<int>s; string a; int b; for(int i=1;i<=sum;i++) { cin>>a; if(a[0]=='I') { cin>>b; s.push(b); } else { if(s.empty()) { cout<<"None"<<endl; } else { cout<<s.top()<<endl; s.pop(); } } } while(!s.empty())s.pop(); } } int main() { int n; cin>>n; int a; string s; for(int i=1;i<=n;i++){ cin>>a>>s; // cout<<s[0]<<endl; bool f; if(s[2]=='F')f=1;//先进先出 else f=0; cnd(a,f); } return 0; }

G POJ - 1011

详细题解

H POJ - 3494

求最大全1子矩阵的面积 题解

#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; const int MAXN = 2007; int n,m; int h[MAXN],s[MAXN],L[MAXN],R[MAXN]; int solve() { int t = 0; for(int i = 0; i < m; ++i) { while(t > 0 && h[s[t-1]] >= h[i])t--; if(t == 0) L[i] = 0; else L[i] = s[t-1]+1; s[t++] = i; }//找最左边 t = 0; for(int i = m-1; i >= 0; --i)//最右边 { while(t > 0 && h[s[t-1]] >= h[i]) t--; if(t == 0) R[i] = m-1; else R[i] = s[t-1]-1; s[t++] = i; } int ret = 0; for(int i = 0; i < m; ++i) ret = max(ret,h[i]*(R[i]-L[i]+1)); return ret; } int main() { int num; while(~scanf("%d %d",&n,&m)) { memset(h,0,sizeof(h)); int res = 0; for(int i = 0; i < n; ++i) { for(int j = 0; j < m; ++j) { scanf("%d",&num); if(num==1)h[j]++; else h[j]=0; } res = max(res,solve()); } printf("%d\n",res); } return 0; } /* 4 5 0 1 1 0 1 0 1 1 1 1 0 0 1 1 0 0 0 1 1 1 */ #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> int n,m,ans; int map[2333][2333]; int h[2333][2333],sta[2333],L[2333],R[2333]; //h[i][j]:第i行第j列元素往上最长的连续1长度 //维护单调非递减栈 void init(int row) { int top = 0,tmp; h[row][m+1] = 0; for(int j = 1;j <= m + 1;j ++) { while(1) { tmp = sta[top]; if(h[row][tmp] <= h[row][j]) break; //以j作为延伸点，确定边界，保证单调性。 R[tmp] = j; -- top; } L[j] = tmp; sta[++top] = j; } for(int j = 1;j <= m;j ++) { if(map[row][j] == 0) continue; int len = R[j] - L[j] - 1; ans = max(ans,h[row][j] * len); } } int main() { while(scanf("%d%d",&n,&m) != EOF) { for(int i = 1;i <= n;i ++) { for(int j = 1;j <= m;j ++) scanf("%d",&map[i][j]); } memset(h,0,sizeof(h)); for(int j = 1;j <= m;j ++) { for(int i = 1;i <= n;i ++) { if(map[i][j] == 1) { h[i][j] = 1; while(map[++i][j] == 1) h[i][j] = h[i-1][j] + 1; -- i; } } } ans = 0; for(int i = 1;i <= n;i ++) init(i); printf("%d\n",ans); } return 0; }