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;
}
京公网安备 11010502036488号