水题第二弹题解
改过的标题很具有迷惑性哦！
A POJ3414本次代码量最大的一题，思想是搜索，详细解题报告，请见点击打开链接
B巨水，不要被题目迷惑了，连通图的性质最少需要（n-1）条边，所以可删 m-n+1条。
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
int n,m;
cin>>n>>m;
for(int i=0;i<m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
}
cout<<m-n+1<<endl;
return 0;
}C 贪心
如果两个物品(v11,v12),(v21,v22)先选哪个？
先选1后2，空间v11+v22；先2后一，空间v21+v12,每次都要占空间最小，所以按这个条件排序。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<math.h>
#include<map>
#include<queue>
using namespace std;
struct node
{
int v1,v2;
}a[1005];
bool cmp(const node &a,const node &b)
{
return a.v1+b.v2<a.v2+b.v1;
}
int main()
{
int t;
cin>>t;
while(t--)
{
int v,n;
scanf("%d%d",&v,&n);
for(int i=0;i<n;i++)
scanf("%d%d",&a[i].v1,&a[i].v2);
sort(a,a+n,cmp);
int sum=0,i;
for(i=0;i<n;i++)
{
if(v-sum<a[i].v2)
break;
sum+=a[i].v1;
}
if(i==n)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
return 0;
}D POJ1837
背包的思想，详解点击打开链接
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int loc[25];
int w[25];
int dp[25][15100];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>loc[i];
for(int i=1;i<=m;i++)
cin>>w[i];
memset(dp,0,sizeof(dp));
dp[0][7500]=1;
for(int i=1;i<=m;i++)
for(int j=0;j<=15000;j++)
if(dp[i-1][j])
for(int k=1;k<=n;k++)
dp[i][j+w[i]*loc[k]]+=(dp[i-1][j]);
cout<<dp[m][7500]<<endl;
return 0;
}E 暴力模拟
我先写了一个字典树MLE了，考虑到这题的数据范围不大，时限也很长，可以用模拟的方法。
关于映射的方法，用hash是最快的，但是对这题用stl中的map已经足够了
基本属于模拟的范畴
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<math.h>
#include<map>
#include<queue>
using namespace std;
int shop[10005];
int main()
{
int n,t,p,pos;
while(cin>>n)
{
memset(shop,0,sizeof(shop));
map <string,int> m;
string s;
for(int i=0;i<n;i++)
{
cin>>s;
if(s=="memory")
pos=i;
m[s]=i;
}
cin>>t;
while(t--)
{
for(int i=0;i<n;i++)
{
cin>>p>>s;
shop[m[s]]+=p;
}
int rank=1;
for(int i=0; i<n; i++)
if(shop[i]>shop[pos])
rank++;
cout<<rank<<endl;
}
}
return 0;
}F YY或数学
如果你不知道欧拉公式（万恶的欧拉），可以手推几组数据YY一下。
证明非一言两语可以说清，需深入学习数学知识
#include<iostream>
using namespace std;
int main()
{
long long n,m;
while(cin>>n>>m&&(n||m))
cout<<n+m-2<<endl;
return 0;
}G 树状数组或线段树
将输入的数据按升序排序，转化为求逆序数的问题，用树状数组或线段树可求解
写一个树状数组调了好久。。。。。。
/****************************************************
file name: 3067.cpp
author: huangjipeng
creat time: 2014年07月27日 星期日 11时39分36秒
***************************************************/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
using namespace std;
int n,m,k;
struct node
{
int a,b;
}a[1005*1005];
int c[1005];
bool cmp(const node &a,const node &b)
{
if(a.a==b.a)
return a.b<b.b;
return a.a<b.a;
}
int lowbit(int x)
{
return x&(-x);
}
void update(int x)
{
while(x<=m)
{
c[x]++;
x+=lowbit(x);
}
}
int getsum(int x)
{
int ans=0;
while(x>0)
{
ans+=c[x];
x=x-lowbit(x);
}
return ans;
}
int main()
{
int t,cases=0;
cin>>t;
while(t--)
{
cin>>n>>m>>k;
for(int i=0;i<k;i++)
{
int t1,t2;
scanf("%d%d",&t1,&t2);
a[i].a=t1;
a[i].b=t2;
}
memset(c,0,sizeof(c));
sort(a,a+k,cmp);
long long ans=0;
for(int i=0;i<k;i++)
{
update(a[i].b);
ans+=(i+1-getsum(a[i].b));
}
++cases;
cout<<"Test case "<<cases<<": "<<ans<<endl;
}
return 0;
}
//391ms/****************************************************
file name: 3067.cpp
author: huangjipeng
creat time: 2014年07月27日 星期日 11时39分36秒
***************************************************/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
using namespace std;
int n,m,k;
struct node
{
int a,b;
}a[1005*1005];
struct tree
{
int l,r,sum;
}tree[10005<<2];
bool cmp(const node &a,const node &b)
{
if(a.a==b.a)
return a.b<b.b;
return a.a<b.a;
}
void build(int l,int r,int now)
{
tree[now].l=l;
tree[now].r=r;
tree[now].sum=0;
if(l==r)
return ;
int mid=(l+r)>>1;
build(l,mid,now<<1);
build(mid+1,r,now<<1|1);
}
int query(int l,int r,int now)
{
if(tree[now].l==l && tree[now].r==r)
{
return tree[now].sum;
}
int mid=(tree[now].l+tree[now].r)>>1;
if(l>mid)
return query(l,r,now<<1|1);
else if(r<=mid)
return query(l,r,now<<1);
else
return query(l,mid,now<<1)+query(mid+1,r,now<<1|1);
}
void update(int t,int now)
{
if(tree[now].l==tree[now].r)
{
tree[now].sum++;
return ;
}
int mid=(tree[now].l+tree[now].r)>>1;
if(t<=mid)
update(t,now<<1);
else
update(t,now<<1|1);
tree[now].sum=(tree[now<<1].sum+tree[now<<1|1].sum);
}
int main()
{
int t,cases=0;
cin>>t;
while(t--)
{
cin>>n>>m>>k;
for(int i=0;i<k;i++)
{
int t1,t2;
scanf("%d%d",&t1,&t2);
a[i].a=t1;
a[i].b=t2;
}
sort(a,a+k,cmp);
build(1,m,1);
long long ans=0;
for(int i=0;i<k;i++)
{
ans+=(i-query(1,a[i].b,1));
update(a[i].b,1);
}
++cases;
cout<<"Test case "<<cases<<": "<<ans<<endl;
}
return 0;
}
//610ms初学的同学可以对比两种做法。
H hash基础题
hash的方法多种多样，这题的方法也很多，提供一种最简单粗暴的方式
暴力枚举5层循环，肯定会T，将三个变量移动至方程一边，另外两个放在另一边，就可以成功将复杂度 O(n^5)变成O(n^2+n^3)
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
short hash[25000000];
int main()
{
int a1,a2,a3,a4,a5;
int s=0;
cin>>a1>>a2>>a3>>a4>>a5;
memset(hash,0,sizeof(hash));
for(int i=-50;i<=50;i++)
{
if(!i)
continue;
for(int j=-50;j<=50;j++)
{
if(!j)
continue;
int sum=a1*i*i*i+a2*j*j*j;
if(sum<0)
sum+=(25000000);
hash[sum]++;
}
}
for(int i=-50;i<=50;i++)
{
if(!i)
continue;
for(int j=-50;j<=50;j++)
{
if(!j)
continue;
for(int k=-50;k<=50;k++)
{
if(!k)
continue;
int sum=a3*i*i*i+a4*j*j*j+a5*k*k*k;
if(sum<0)
sum+=(25000000);
if(hash[sum])
s+=(hash[sum]);
}
}
}
cout<<s<<endl;
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2014-07-30 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读