地址：http://www.bnuoj.com/bnuoj/contest_show.php?cid=3114
A题 ： HDU 1969 二分
注意PI要用acos(-1.0)表示
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<iostream>
const double pi = acos(-1.0);
const double eps = 1e-6;
using namespace std;
double s[10005];
int main()
{
int i,n,f,t,ri,sum;
double mid,max,min;
scanf("%d",&t);
while(t--)
{
max=min=0;
scanf("%d%d",&n,&f);
f++;
for(i=0;i<n;i++)
{
scanf("%d",&ri);
s[i]=ri*ri*pi;
if(s[i]>max) max=s[i];
}
while(max-min>=eps)
{
sum=0;
mid=(max+min)/2;
for(i=0;i<n;i++) sum+=s[i]/mid;
if(sum<f) max=mid;
else min=mid;
}
printf("%.4lf\n",mid);
}
return 0;
}
B题：POJ 1852 水题
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string.h>
#include<ctype.h>
#include<stack>
#include<queue>
#include<set>
#include<algorithm>
#include <limits.h>
using namespace std;
int a[100005];
int main()
{
int t,i,l,n,maxm,b;
scanf("%d",&t);
while(t--)
{
maxm=0;
scanf("%d%d",&l,&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
b=min(l-a[i],a[i]);
if(b>maxm) maxm=b;
}
sort(a,a+n);
printf("%d %d\n",maxm,max(l-a[0],a[n-1]));
}
return 0;
}
C题： HDU 2102 三维BFS
三维的BFS，看似麻烦其实也差不多，莫名其妙MLE了好几次
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string.h>
#include<ctype.h>
#include<stack>
#include<queue>
#include<set>
#include<algorithm>
#include <limits.h>
using namespace std;
char mapp[2][11][11];
int dir[4][2]= {-1,0,0,-1,1,0,0,1};
typedef struct {
int x,y,time,floor;
}Node;
int main()
{
char x;
int t,n,m;
int ex,ey,ez;
int c,i,j;
scanf("%d",&c);
while(c--)
{
scanf("%d%d%d",&n,&m,&t);
x=getchar();
for(i=0; i<n; i++)
{
for(j=0; j<m; j++)
{
cin>>mapp[0][i][j];
if(mapp[0][i][j]=='P')
{
ex=0;
ey=i;
ez=j;
}
}
}
for(i=0; i<n; i++)
{
for(j=0; j<m; j++)
{
cin>>mapp[1][i][j];
if(mapp[1][i][j]=='P')
{
ex=1;
ey=i;
ez=j;
}
}
}
queue<Node>q;
Node th,ne;
th.x=0;
th.y=0;
th.floor=0;
th.time=0;
mapp[th.floor][th.x][th.y]='*';
q.push(th);
int safe=0;
while(!q.empty())
{
th=q.front();
q.pop();
if(th.time>t)
{
break;
}
if(th.x==ey&&th.y==ez&&th.floor==ex)
{
safe=1;
break;
}
for(i=0; i<4; i++)
{
ne.x=th.x+dir[i][0];
ne.y=th.y+dir[i][1];
ne.time=th.time+1;
ne.floor=th.floor;
if(ne.x<0||ne.y<0||ne.x>=n||ne.y>=m)
continue;
if(mapp[ne.floor][ne.x][ne.y]=='#')
{
mapp[ne.floor][ne.x][ne.y]='*';
ne.floor^=1;
if(mapp[ne.floor][ne.x][ne.y]=='#')
{
mapp[0][ne.x][ne.y]=mapp[1][ne.x][ne.y]='*';
continue;
}
}
if(mapp[ne.floor][ne.x][ne.y]=='.'||mapp[ne.floor][ne.x][ne.y]=='P')
{
q.push(ne);
mapp[ne.floor][ne.x][ne.y]='*';
}
}
}
if(safe)
cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
D题： HDU 4337 DFS
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<iostream>
const double pi = acos(-1.0);
const double eps = 1e-6;
using namespace std;
int visit[160];
int mapp[160][160];
int n,lu[160],flag;
bool dfs(int x,int t)
{
if(visit[x]) return false;
lu[t]=x;
visit[x]=1;
if(t==n&&mapp[1][x])
{
flag=1;
return true;
}
else
{
for(int i=1;i<=n;i++)
{
if(mapp[i][x]&&!visit[i])
{
if(dfs(i,t+1))
return true;
}
}
}
visit[x]=0;
return false;
}
int main()
{
int i,x,y,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(visit,0,sizeof(visit));
memset(mapp,0,sizeof(mapp));
for(i=0;i<m;i++)
{
scanf("%d%d",&x,&y);
mapp[x][y]=1;
mapp[y][x]=1;
}
flag=0;
dfs(1,1);
if(flag)
{
for(i=1;i<n;i++) printf("%d ",lu[i]);
printf("%d\n",lu[i]);
}
else printf("no solution\n");
}
return 0;
}
E题：HDU 4325 线段树
这道题hdu数据超水，达不到10^9，10^5数组标记就能过，那时候不会线段树，这是之前的代码
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string.h>
#include<ctype.h>
#include<stack>
#include<queue>
#include<set>
#include<algorithm>
#include <limits.h>
using namespace std;
int a[100005];
int main()
{
int t,n,m,i,j,s,e,k=1,x;
scanf("%d",&t);
while(t--)
{
memset(a,0,sizeof(a));
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
{
scanf("%d%d",&s,&e);
for(j=s;j<=e;j++)
a[j]++;
}
printf("Case #%d:\n",k++);
for(i=0;i<m;i++)
{
scanf("%d",&x);
printf("%d\n",a[x]);
}
}
return 0;
}
这是正确的做法：10^9树建不起来，需要用离散化，我想更加熟悉线段树就手敲了一发。我交题真的感觉没有任何问题，可是就是RE成狗，数组开小是T，数组开大就RE，超郁闷，最后根据网上的改自己的代码才AC，但是我依然没有发现我为何RE。还是觉得unique和lower_bound的离散化更加飘逸，我比较喜欢那种
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define MAXN 100100
int sum[MAXN<<2],cover[MAXN<<2];
int dat[MAXN*3];
int x[MAXN],y[MAXN];
int q[MAXN];
map<int,int> mp;
void pushdown(int rt){
if(cover[rt]){
cover[rt<<1] += cover[rt];
cover[rt<<1|1] += cover[rt];
sum[rt<<1] += cover[rt];
sum[rt<<1|1] += cover[rt];
cover[rt] = 0;
}
}
void build(int l,int r,int rt){
sum[rt] = 0;
cover[rt] = 0;
if(l==r) return ;
int m = (l+r)>>1;
build(lson);
build(rson);
}
void update(int L,int R,int l,int r,int rt){
if(L<=l&&r<=R){
cover[rt]++;
sum[rt]++;
return ;
}
pushdown(rt);
int m = (l+r)>>1;
if(L<=m) update(L,R,lson);
if(R>m) update(L,R,rson);
}
int query(int w,int l,int r,int rt){
if(l==r){
return sum[rt];
}
pushdown(rt);
int m = (l+r)>>1;
if(w<=m) return query(w,lson);
else return query(w,rson);
}
int main(){
int t,n,m,i,tot,k = 1;
scanf("%d",&t);
while(t--){
printf("Case #%d:\n",k++);
tot = 0;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
scanf("%d%d",&x[i],&y[i]);
dat[++tot] = x[i];
dat[++tot] = y[i];
}
for(i=1;i<=m;i++){
scanf("%d",&q[i]);
dat[++tot] = q[i];
}
sort(dat+1,dat+tot+1);
int cnt = 0;
dat[++cnt] = dat[1];
for(i=2;i<=tot;i++){
if(dat[i]!=dat[cnt]){
dat[++cnt] = dat[i];
}
}
build(1,cnt,1);
for(i=1;i<=cnt;i++){
mp[dat[i]] = i;
}
for(i=1;i<=n;i++){
update(mp[x[i]],mp[y[i]],1,cnt,1);
}
for(i=1;i<=m;i++){
printf("%d\n",query(mp[q[i]],1,cnt,1));
}
}
return 0;
}
F题： HDU 1231 最大连续子段和
方法很多
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string.h>
#include<ctype.h>
#include<stack>
#include<queue>
#include<set>
#include<algorithm>
#include <limits.h>
using namespace std;
int a[10005],x,y;
int maxsequence(int a[], int len)
{
int maxsum, maxhere;
int xx,yy;
xx=yy=x=y=a[0];
maxsum = maxhere =a[0];
for (int i=1; i<len; i++)
{
if (maxhere <= 0)
{
maxhere = a[i];
xx=yy=a[i];
}
else
{
maxhere += a[i];
yy=a[i];
}
if (maxhere > maxsum)
{
x=xx;
y=yy;
maxsum = maxhere;
}
}
return maxsum;
}
int main()
{
int k,i,maxm;
while(scanf("%d",&k),k)
{
for(i=0; i<k; i++)
scanf("%d",&a[i]);
maxm=maxsequence(a,k);
if(maxm<0)
printf("%d %d %d\n",0,a[0],a[k-1]);
else
printf("%d %d %d\n",maxm,x,y);
}
return 0;
}
G题：HDU 1412 水题
貌似题目本意是用STL去做
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<ctype.h>
#include<algorithm>
using namespace std;
int a[20005];
int main()
{
int n,m,i;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=0;i<n+m;i++)
scanf("%d",&a[i]);
sort(a,a+n+m);
printf("%d",a[0]);
for(i=1;i<n+m;i++)
{
if(a[i]!=a[i-1])
printf(" %d",a[i]);
}
printf("\n");
}
return 0;
}
H题：POJ 2001 字典树
才学的，做了几道题，直接套模板
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string.h>
#include<ctype.h>
#include<stack>
#include<queue>
#include<set>
#include<algorithm>
#include <limits.h>
#define PI acos(-1)
#define MAX 26
using namespace std;
char str[1005][25];
typedef struct Trie
{
Trie *next[MAX];
int v; //根据需要变化
};
Trie root;
void createTrie(char *str)
{
int len = strlen(str);
Trie *p =&root, *q;
for(int i=0; i<len; ++i)
{
int id = str[i]-'a';
if(p->next[id] == NULL)
{
q = new Trie;
q->v = 0;
for(int j=0; j<MAX; ++j)
q->next[j] = NULL;
p->next[id] = q;
}
p->next[id]->v++;
p = p->next[id];
}
}
void findTrie(char *str)
{
int len = strlen(str);
Trie *p =&root;
for(int i=0; i<len; ++i)
{
int id = str[i]-'a';
p=p->next[id];
printf("%c",str[i]);
if(p->v==1) break;
}
printf("\n");
}
int main()
{
int i,n=0;
while(scanf("%s",str[n])!=EOF)
{
createTrie(str[n++]);
}
for(i=0;i<n;i++)
{
printf("%s ",str[i]);
findTrie(str[i]);
}
return 0;
}
I题： POJ 3041 二分图匹配
也是才学的，模板题
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string.h>
#include<ctype.h>
#include<stack>
#include<queue>
#include<set>
#include<algorithm>
#include<limits.h>
#define PI acos(-1)
using namespace std;
bool mapp[505][505];
bool visit[505];
int link[505];
int n;
bool find(int v)
{
int i;
for(i=1; i<=n; i++)
{
if(mapp[v][i]&&!visit[i])
{
visit[i]=true;
if(link[i]==0||find(link[i]))
{
link[i]=v;
return true;
}
}
}
return false;
}
int main()
{
int k,i,x,y,ans=0;
scanf("%d%d",&n,&k);
for(i=0;i<k;i++)
{
scanf("%d%d",&x,&y);
mapp[x][y]=true;
}
for(i=1; i<=n; i++)
{
memset(visit,0,sizeof(visit));
if(find(i)) ans++;
}
printf("%d\n",ans);
return 0;
}
小结：这次周赛卡题了，我第一眼看到第三题标题是中文就点开了，结果被卡了很久，浪费了很多时间，不然应该还能做出A题和D题。卡题对心情影响挺大的，想做出来又觉得耽误了很多时间，不做出来又不甘心，有点蛋疼