2011年5月8日
f
#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
#define INF 5000000
int a[201];
int c[201][201];
int d[201][201];
int main()
{
int n;
int i,j,m,kk,k,p;
int max1;
scanf("%d",&n);
int l;
for(l=1;l<=n;l++)
{ memset(a,0,sizeof(a));
memset(c,0,sizeof(c));
memset(d,0,sizeof(d));
scanf("%d",&m);
for( i=0;i<m;i++)
scanf("%d",&a[i]);
for(i=0;i<m;i++)
for(j=0;j<m;j++)
{
scanf("%d",&d[i][j]);
if(d[i][j]==-1)
d[i][j]=INF;
}
max1=0;
for(k=0;k<m;k++)
for(i=0;i<m;i++)
for(j=0;j<m;j++)
{
if(d[i][j]>(d[i][k]+d[k][j]))
d[i][j]=d[i][k]+d[k][j];
}
kk=0;
for(p=0;p<m;p++)
{
if(p<m-1)
{
max1+=d[a[p]][a[p+1]];
if(d[a[p]][a[p+1]]==INF)
kk=1;
}
else
{
max1+=d[a[p]][a[0]];
if(d[a[p]][a[0]]==INF)
{kk=1;}
}
}
if(kk==1)
printf("impossible\n");
else
printf("%d\n",max1);
}
return 0;
}
2011年4月27日
2011年4月22日
#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
int a[101],c[101];
int num[100001],f[100001];
int main()
{
int n,m;
while(scanf("%d %d",&n,&m)!=EOF)
{
if(n==0&&m==0)
break;
int sum=0;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
scanf("%d",&c[i]);
memset(f,0,sizeof(f));
f[0]=1;
for(int i=1;i<=n;i++)
{
memset(num,0,sizeof(num));
for(int j=a[i];j<=m;j++)
{
if(!f[j]&&f[j-a[i]]&&num[j-a[i]]<c[i])
{
num[j]=num[j-a[i]]+1;
sum++;
f[j]=1;
}
}
}
printf("%d\n",sum);
}
return 0;
}
2011年4月8日
/**********************************
有一定的钱 存在银行里
给出可存的钱数 和相应利息
第一年的利息会加入到第二年的本金中
***********************************/
#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
int d[50000],v[12],w[12];//数组开大了会超时
int main()
{
int n;
//freopen("out.txt","w",stdout);
scanf("%d",&n);
for(int l=1;l<=n;l++)
{
int c,k;
int m;
scanf("%d %d",&c,&k);
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%d %d",&v[i],&w[i]);
v[i]/=1000;
}
while(k--)
{
int t=c/1000;//因为是1000的倍数 所以 都除以1000 优化一下子
memset(d,0,sizeof(d));
for(int i=1;i<=m;i++)
for(int j=0;j<=t;j++)
{ if(j>=v[i])
if(d[j]<(d[j-v[i]]+w[i]))
{
d[j]=d[j-v[i]]+w[i];
}
}
c=c+d[t];
}
printf("%d\n",c);
}
return 0;
}
2011年4月2日
strcmp: 用于比较两个字符串，原型如下：
int strcmp ( char const *s1, char const *s2）；
如果s1小于s2，strcmp函数返回一个小于零的值。如果s1大于s2，函数返回一个大于零的值。如果两个字符串相等，函数就返回零。
警告：初学者常常会编写下面这样的表达式
if ( strcmp (a, b))
他以为如果两个字符串相等，它的结果将是真。但是，这个结果将正好相反，因为在两个字符串相等的情况下返回值是零（假）。 把这个返回值当作布尔值进行测试是一种坏风格，因为它具有三个截然不同的结果：小于、等于和大于。 所以更好的方法是把这个返回值与零进行比较。
当然我们在实际工作中也经常会碰到将其返回值与布尔值进行判断，我们来看下面这个例子：
char a[];
……
if ( !strcmp( a, "5"))
{ printf(“equally！”);
}else{
printf("unequal！");
}
在这个例子中我们分析下：
如果a的值为5,则返回值为0，那么判断也就成为 if(!(0)) ，(0)取反后为1 ，1位TRUE则判断为 if( TRUE )
如果a的值小于5,则返回一个负数，而负数的取反是FALSE； 大于5，则返回一个正数，正数的取反也是FALSE;
因此上例中a 的值为5 则输出 equally ; 不等于5都输出 unequal
我们可以做一个小测试 -1 、 0 、 1三数分别取反，会得到 0、1、0 。
标准并没有规定用于提示不相等的具体值。它只是说如果第一个字符串大于第二个字符串就返回一个大于零的值，如果第一个字符串小于第二个字符串就返回一个小于零的值。一个常见的错误是一位返回值就是1和-1，分别代表大于和小于。这个假设并不总是成立。 （跟具体的编译器有关）
转自:
http://piao8163.blog.163.com/blog/static/96972478200981343957704/
1。qsort, 即快速排序, 包含在<cstdlib>或<stdlib.h>中,
函数有四个参数, 没有返回值 下面是一个典型的写法:
qsort(s,n,sizeof(s[0]),cmp);
其中, s是需要排序的数组名, 也可以理解成开始地址,
因为你如果只需要对数组的部分排序的话, s可以写成&s[i]的形式的
第二个参数n是参与排序的元素个数, 第三个参数是单个元素的大小,
通常我们用sizeof()来获取大小, 因为它足够放心 绝对无毒^_^
而且 很多时候我们需要对结构体进行排序的 你很难把握它的大小的~
最后一个参数, 也就是我今天对着愣了很久的东东了 什么鸟东西嘛,
搞得忒神密-_-!!!!
cmp是一个比较函数 不过这不是系统定义好的函数 而是需要自己手动写的 也就是说 你可以把它叫做abcd或是rubbish什么
因为是比较函数 我比较习惯用cmp
cmp的典型定义是
int cmp(const void *a,const void *b);
其中返回值必须是int,两个参数的类型必须都是const void *, 这样你可以对他进行强制转换成任何其他类型
有点想C#中的box 哈~~
假设是对int排序的话,如果是升序,那么就是如果a比b大cmp返回一个正值,小则负值,相等返回0
当然当你对具体的数组进行排序的话 cmp里面就要做具体的处理
2。 七种常见排法！！！
一、对int类型数组排序
int num[100];
Sample:
int cmp ( const void *a , const void *b )
{
return *(int *)a - *(int *)b;
}
qsort(num,100,sizeof(num[0]),cmp);
二、对char类型数组排序（同int类型）
char word[100];
Sample:
int cmp( const void *a , const void *b )
{
return *(char *)a - *(char *)b;
}
qsort(word,100,sizeof(word[0]),cmp);
三、对double类型数组排序（特别要注意）
double in[100];
int cmp( const void *a , const void *b )
{
return *(double *)a > *(double *)b ? 1 : -1;
}
qsort(in,100,sizeof(in[0]),cmp)；
四、对结构体一级排序
struct In
{
double data;
int other;
}s[100]
//按照data的值从小到大将结构体排序,关于结构体内的排序关键数据data的类型可以很多种，参考上面的例子写
int cmp( const void *a ,const void *b)
{
return (*(In *)a)->data > (*(In *)b)->data ? 1 : -1;
}
qsort(s,100,sizeof(s[0]),cmp)
五、对结构体二级排序
struct In
{
int x;
int y;
}s[100];//按照x从小到大排序，当x相等时按照y从大到小排序
int cmp( const void *a , const void *b )
{
struct In *c = (In *)a;
struct In *d = (In *)b;
if(c->x != d->x) return c->x - d->x;
else return d->y - c->y;
}
qsort(s,100,sizeof(s[0]),cmp);
六、对字符串进行排序
struct In
{
int data;
char str[100];
}s[100];
//按照结构体中字符串str的字典顺序排序
int cmp ( const void *a , const void *b )
{
return strcmp( (*(In *)a)->str , (*(In *)b)->str );
}
qsort(s,100,sizeof(s[0]),cmp);
七、计算几何中求凸包的cmp
int cmp(const void *a,const void *b) //重点cmp函数，把除了1点外的所有点，旋转角度排序
{
struct point *c=(point *)a;
struct point *d=(point *)b;
if( calc(*c,*d,p[1]) < 0) return 1;
else if( !calc(*c,*d,p[1]) && dis(c->x,c->y,p[1].x,p[1].y) < dis(d->x,d->y,p[1].x,p[1].y)) //如果在一条直线上，则把远的放在前面
return 1;
else return -1;
}
2011年3月31日
这题把前面两道题组合到了一起 判断最小生成树 和是否是一棵树
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int father[101];
bool flags[101];
struct country
{
int first;
int second;
int value;
}a[5001];
bool cmp(country x,country y)
{
return x.value<y.value;
}
int makeset(int n)
{
for(int i=1;i<=n;i++)
father[i]=i;
}
int findset(int x)
{
if(father[x]!=x)
{
father[x]=findset(father[x]);
}
return father[x];
}
int Union(int a,int b)
{
int x=findset(a);
int y=findset(b);
if(x==y)
return 1;
else
{
father[x]=y;
return 0;
}
}
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
if(n==0)
break;
int sum=0;
makeset(m);
memset(flags,false,sizeof(flags));
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&a[i].first,&a[i].second,&a[i].value);
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)
{
if(Union(a[i].first,a[i].second)==0)
{
sum=sum+a[i].value;
}
}
for(int i=1;i<=m;i++)
{
flags[findset(i)]=true;
}
int k=0;
for(int i=1;i<=m;i++)
{
if(flags[i]==true)
k++;
}
if(k!=1)
printf("?\n");
else
printf("%d\n",sum);
}
return 0;
}
2011年3月30日
为了学习最小生成树 这两天学习了并查集 做并查集的题碰到了一道最小生成树 自己搞定了这道题 非常的高兴哈~
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
int father[101];
void makeset(int n)
{
for(int i=1;i<=n;i++)
{
father[i]=i;
}
}
int findset(int x)
{
if(father[x]!=x)
{
father[x]=findset(father[x]);
}
return father[x];
}
int Union(int a,int b)
{
int x=findset(a);
int y=findset(b);
if(x==y)
return 1;//如果两个点在同一颗树中 那么这两个点添加以后会形成回路 返回1
else
{
father[x]=y;
return 0;
}
}
struct country
{
int first;
int second;
int distance;
}a[5001];
bool cmp(country x,country y)
{
return x.distance<y.distance;
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
if(n==0)
break;
makeset(n);
int sum=0;
for(int i=1;i<=n*(n-1)/2;i++)
{
scanf("%d %d %d",&a[i].first,&a[i].second,&a[i].distance);
}
sort(a+1,a+n*(n-1)/2+1,cmp);//将距离从小到大的排序
for(int i=1;i<=n*(n-1)/2;i++)
{
if(Union(a[i].first,a[i].second)==0)//如果两个点在同一颗树中 那么这两个点添加以后会形成回路 否则这两个点之间的路加入到最小生成树中
sum=sum+a[i].distance;
}
printf("%d\n",sum);
}
return 0;
}
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
bool flags[1001];
int father[1001];
void makeset(int n)
{
for(int i=1;i<=n;i++)
{
father[i]=i;
}
}
int findset(int x)
{
if(x!=father[x])
{
father[x]=findset(father[x]);
}
return father[x];
}
void Union(int a,int b)
{
int x=findset(a);
int y=findset(b);
if(x==y)
return;
father[y]=x;
}
int main()
{
int n,m;
while(scanf("%d %d",&n,&m)!=EOF)
{
memset(flags,false,sizeof(flags));
if(n==0)
break;
makeset(n);
int first,second;
for(int i=1;i<=m;i++)
{
scanf("%d %d",&first,&second);
Union(first,second);
}
for(int i=1;i<=n;i++)//判断树的棵数
{
flags[findset(i)]=true;
}
int k=0;
for(int i=1;i<=n;i++)
{
if(flags[i]==true)
k++;
}
printf("%d\n",k-1);//需要增加的路数等于树的棵树k-1
}
return 0;
}
#include<iostream>
#include<stdio.h>
using namespace std;
int sum,n,m;
int father[50001];
void makeset(int x)
{
for(int i=1;i<=x;i++)
{
father[i]=i;
}
}
int findset(int x)//查
{
if(x!=father[x])
{
father[x]=findset(father[x]);
}//回溯
return father[x];
}
void Union(int a,int b)
{
int x=findset(a);
int y=findset(b);
if(x==y)
return;
sum=sum-1;
father[y]=x;
}
int main()
{
int l;
scanf("%d",&l);
for(int j=1;j<=l;j++)
{ scanf("%d%d",&n,&m);
sum=n;
makeset(n);
int first,second;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&first,&second);
Union(first,second);
}
printf("%d\n",sum);
getchar();
}
return 0;
}
已知有n个大学生，其中有m对宗教信仰相同的学生，请你估算这n个学生中最多有多少种宗教信仰。
依旧是简单的并查集应用。宗教信仰的最大值为学生数n，因此一开始把n个学生作为n个集合，对给出的每对大学生 a 和 b ，如果他们在不同的集合，就合并他们，然后宗教数减一。 这次依旧用到了路径压缩，只不过上一次写的是非递归，这次写了一个递归版本。也就是搜索完成回溯的时候"顺便"将当前节点的父节点直接指向祖先节点。
题目大意解释来自Slyar Home (www.slyar.com) 转载请注明，谢谢合作。
/**//*如果两个学生的信仰一样
则总的宗教个数减一 */
#include<iostream>
#include<stdio.h>
using namespace std;
int sum,n,m;
int father[50001];
void makeset(int x)
{
for(int i=1;i<=x;i++)
{
father[i]=i;
}
}
int findset(int x)//查
{
if(x!=father[x])
{
father[x]=findset(father[x]);
}//回溯
return father[x];
}
void Union(int a,int b)
{
int x=findset(a);
int y=findset(b);
if(x==y)
return;
sum=sum-1;
father[y]=x;
}
int main()
{
int l=1;
while(scanf("%d%d",&n,&m)!=EOF)
{ if(n==0&&m==0)
break;
sum=n;
makeset(n);
int first,second;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&first,&second);
Union(first,second);
}
printf("Case %d: %d\n",l,sum);
l++;
}
return 0;
}
学习并查集做的第一道题 基本上就是套用模版的
#include<iostream>
#include<stdio.h>
using namespace std;
int n,m;
int father[30001],num[30001];
/**//*初始化数组*/
void makeset(int x)
{
for(int i=0;i<x;i++)
{
father[i]=i;
num[i]=1;
}
}
int findset(int x)//查
{
if(x!=father[x])
{
father[x]=findset(father[x]);
}//回溯
return father[x];
}
void Union(int a,int b)//并
{
int x=findset(a);
int y=findset(b);
if(x==y)
{
return;
}
if(num[x]>=num[y])
{
father[y]=x;
num[x]+=num[y];
}
else
{
father[x]=y;
num[y]+=num[x];
}
}
int main()
{
while(scanf("%d %d",&n,&m)!=EOF&&n!=0)
{
makeset(n);
for(int i=0;i<m;i++)
{ int l,first,b;
scanf("%d %d",&l,&first);
for(int j=1;j<l;j++)
{
scanf("%d",&b);
Union(first,b);
}
}
printf("%d\n",num[findset(0)]);//输出0的祖宗节点的秩
}
return 0;
}
2011年3月29日
2011年3月28日
2011年3月22日
freopen("out.txt","w",stdout);
freopen("in.txt","r",stdin);
今天复习了一下假期时候学的母函数，表示看到代码的时候比较迷糊，于是又找到了当时学习母函数的时候看的文章（http://www.wutianqi.com/?p=596写得比较清楚，我从中收益颇深）。最后发现的问题就是写程序的时候一定要写好注释，注释不仅仅是给别人看你写的程序时作为参考，也是自己一段时间之后再次看代码的时候的一个导航。也许看到注释之后立马就可以回忆起来当时的思路，而不是一行行的看代码，一次次重复当时的思考过程。总之，注释很重要，好好的写注释能减少很多不必要的麻烦。
2011年3月20日
2011年3月14日
2011年3月13日
摘要: An escape
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 227... 阅读全文
2011年3月6日
2011年3月5日
2011年2月15日
Fruit
Time Limit : 1000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 78 Accepted Submission(s) : 47
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
转眼到了收获的季节，由于有TT的专业指导，Lele获得了大丰收。特别是水果，Lele一共种了N种水果，有苹果，梨子，香蕉，西瓜……不但味道好吃，样子更是好看。
于是，很多人们慕名而来，找Lele买水果。
甚至连大名鼎鼎的HDU ACM总教头 lcy 也来了。lcy抛出一打百元大钞，"我要买由M个水果组成的水果拼盘，不过我有个小小的要求，对于每种水果，个数上我有限制，既不能少于某个特定值，也不能大于某个特定值。而且我不要两份一样的拼盘。你随意搭配，你能组出多少种不同的方案，我就买多少份！"
现在就请你帮帮Lele，帮他算一算到底能够卖出多少份水果拼盘给lcy了。
注意，水果是以个为基本单位，不能够再分。对于两种方案，如果各种水果的数目都相同，则认为这两种方案是相同的。
最终Lele拿了这笔钱，又可以继续他的学业了～
Input
本题目包含多组测试，请处理到文件结束(EOF)。
每组测试第一行包括两个正整数N和M(含义见题目描述，0<N,M<=100)
接下来有N行水果的信息，每行两个整数A,B(0<=A<=B<=100)，表示至少要买该水果A个，至多只能买该水果B个。
Output
对于每组测试，在一行里输出总共能够卖的方案数。
题目数据保证这个答案小于10^9
Sample Input
2 3
1 2
1 2
3 5
0 3
0 3
0 3
Sample Output
Author
Linle
Source
ACM程序设计期末考试——2008-01-02（3 教417）
1#include<stdio.h>
2int main()
3{
4 int i,n,m,j,k,a[101],b[101],c1[101],c2[101];
5 while(scanf("%d %d",&n,&m)!=EOF)
6 {
7 for(i=0;i<n;i++)
8 scanf("%d %d",&a[i],&b[i]);
9 for(i=0;i<=m;i++)
10 {
11 c1[i]=0;
12 c2[i]=0;
13 }
14 c1[0]=1;//第一次结束以后 k的就被赋值我为1了 可其余还为0 就算c1[j]中被用到还是没效果 只有1的c1[j]才会有效果
15 for(i=0;i<n;i++)
16 {
17 for(j=0;j<=m;j++)
18 for(k=a[i];k+j<=m&&k<=b[i];k++)
19 c2[j+k]+=c1[j];
20 for(j=0;j<=m;j++)
21 {
22 c1[j]=c2[j];
23 c2[j]=0;
24 }
25 }
26 printf("%d\n",c1[m]);
27 }
28 return 0;
29}
Holding Bin-Laden Captive!
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)
Total Submission(s) : 132 Accepted Submission(s) : 69
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
We all know that Bin-Laden is a notorious terrorist, and he has disappeared for a long time. But recently, it is reported that he hides in Hang Zhou of China!
“Oh, God! How terrible! ”
Don’t be so afraid, guys. Although he hides in a cave of Hang Zhou, he dares not to go out. Laden is so bored recent years that he fling himself into some math problems, and he said that if anyone can solve his problem, he will give himself up!
Ha-ha! Obviously, Laden is too proud of his intelligence! But, what is his problem?
“Given some Chinese Coins (硬币) (three kinds-- 1, 2, 5), and their number is num_1, num_2 and num_5 respectively, please output the minimum value that you cannot pay with given coins.”
You, super ACMer, should solve the problem easily, and don’t forget to take $25000000 from Bush!
Input
Input contains multiple test cases. Each test case contains 3 positive integers num_1, num_2 and num_5 (0<=num_i<=1000). A test case containing 0 0 0 terminates the input and this test case is not to be processed.
Output
Output the minimum positive value that one cannot pay with given coins, one line for one case.
Sample Input
Sample Output
Author
lcy
#include<stdio.h>
#include<string.h>
int main()
{
int i,j,k,a,b,c,d[10001];
while(scanf("%d %d %d",&a,&b,&c)!=EOF)
{
if(0==a&&0==b&&0==c)
break;
memset(d,0,sizeof(d));
for(j=0;j<=a;j++)
for(k=0;k+j<=a+2*b;k=k+2)
d[k+j]++;
for(j=0;j<=a+2*b&&d[j];j++)//&&a[j]是排除从0到a+2b之内不存在的项
for(k=0;k+j<=a+2*b+5*c;k=k+5)
d[k+j]++;
for(i=0;i<=a+2*b+5*c+1;i++)//+1是因为如果情况中的全满足 那么大于范围的第一个就是所求
{
if(d[i]==0)
{
printf("%d\n",i);
break;
}
}
}
return 0;
}