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;

}