HDU1518 Square
http://acm.hdu.edu.cn/showproblem.php?pid=1518
DFS 开始的时候回朔问题没有考虑清楚
#include<stdio.h>#include<stdlib.h>#include<string.h>int stick[22];int k[22];int n,sum,average,temp;
int cmp ( const void *a , const void *b ){ return *(int *)b - *(int *)a;}
void dfs(int numbers,int sticks,int real_time_sum...
求完数算法
#include<stdio.h>#include<math.h>int main(){ __int64 a[8]={2,3,5,7,13,17,19,31}; // perfect=( 2^( n-1 ) )*(2^n-1) //( 2^n - 1 ) is a prime number ,
// and n==a[ i ]--->prime number __int64 i,n,k,perfect[8]; whi...
整数划分算法
for(i=1; i<=101; i++) f[0][i]=f[1][i]=f[i][1]=1; for(; i<=1001; i++) f[i][1]=1; for(i=2; i<=1001; i++) { for(j=2; j<=101; j++) if(i>=j) f[i][j]=f[i-j][j]+f[i][j-1]; else for(; j<=101; j++) f[i][j]=f[i][i];
HDU 2169Geek Challenge [SKRZAT] (Base Minus Two)
http://acm.hdu.edu.cn/showproblem.php?pid=2169
#include<stdio.h>#include<string.h>int main(){ int n,i,j,k,sum,len,q,w = 1,p; char c,a[16]; scanf("%d",&n); while(n--) { getchar(); scanf("%c ",&c); if(c=='b') { k=1; sum=0; scanf("%s",a); len=strlen(a); for(i=len-1;i>=0;i--) ...
HDU 1176 免费馅饼
http://acm.hdu.edu.cn/showproblem.php?pid=1176
简单dp
#include<stdio.h>#include<string.h>int fallx[100010][11];int a[100001][11];int main(){ int i,n,x,t,max,total,sum,q,j; while (scanf("%d",&n)!=EOF&&n){ memset(fallx,0,sizeof(fallx)); memset(a,0,sizeof(a)); for(max=0,i=0;i<n;i++){ ...
HDU 1058Humble Numbers
http://acm.hdu.edu.cn/showproblem.php?pid=1058
水题 也贴一下
#include<stdio.h>int humble[5843];int min(int a, int b, int c, int d){ a=a>b?b:a; a=a>c?c:a; a=a>d?d:a; return a;}void main(){ int e1=1,e2=1,e3=1,e4=1,a1,a2,a3,a4,i,n; humble[1]=1; for(i=2;i<=5842;i++) { a1=2*humble[e1];...
HDU 1799 循环多少次？
http://acm.hdu.edu.cn/showproblem.php?pid=1799
公式推出来以后就是简单题了，呵呵
就是求n! / (m)! / (n-m)! 简单来说就是求C(n)m
#include <stdio.h>int c[2002][2002] = {0};int main(){ int i,j,t,n,m; for(i=1;i<=2000;i++) { c[i][0]=1; c[i][1]=i%1007; } for(i=2;i<=2000; i++) for(j=2;j<...
HDU1232 畅通工程
http://acm.hdu.edu.cn/showproblem.php?pid=1232
赤裸裸的并查集
#include<stdio.h>int a[1010];int findx(int x){ while(a[x]!=x) //寻找根节点 x=a[x]; return x;}void merge(int x,int y){ int fx,fy; fx=findx(x); fy=findx(y); if(fx!=fy) a[fx]=fy;}int main(){ int n,m,count,i,x,y; while(scanf("%d",&n)!=...
HDU 1692 Destroy the Well of Life
http://acm.hdu.edu.cn/showproblem.php?pid=1692
模拟题 比赛的时候居然没有看这道题 哎 还是卡死在那个一直被我们认为是dp的该死的floyed上了啊
#include<stdio.h>int w[100001];int l[100001];int p[100001];int main(){ int n,t,k=0,j,i,min,energy,water; scanf("%d",&t); while(t--) { k++; scanf("%d",&n); for(i=1;i<=n;i++) scanf("%...
PKU 1160 Post Office
http://acm.pku.edu.cn/JudgeOnline/problem?id=1160
DP题
在一条笔直的公路上有一排城镇，要在城镇上建邮局，首先输入城镇数和要建的邮局数，问：所有城镇距离最近邮局的距离总和是多少？
题目思路：用w[i][j]记录把前i个邮局建到前j个村庄中的最优解，用distance[i][j]记录所有在i到j村庄中，建1个邮局的最小代价。显然邮局应该设到中点。让前i个邮局覆盖前j个村庄，第i+1个邮局覆盖第j+1至j+k个村庄(j+k<=n)，则状态转移方程为w[i+1][j+k]=min{w[i][j]+distance[j+1][j+k];} ...
HDU 1690 Bus System
http://acm.hdu.edu.cn/showproblem.php?pid=1690
才做了几天的DP专题，昨天的杭电全国邀请赛上居然就从头到尾都把它当DP做了
队里的3个人居然还会一致认为是DP，郁闷啊。。。。
其实只要floyed就可以过了的。。。。想复杂了啊。。。。。
#include<stdio.h>#include<string.h>__int64 l[5],c[5];__int64 cost(__int64 len){ if(len==0) return 0; else if(len<=l[1]) return c[1]; else if(len<=l[2...
Floyed
从有向图的带权的邻接矩阵 cost出发，对有向图的n个顶点加以编号，若从i到j有弧（i=1，2，...，n，j=1，2，...，n），则从i到j 存在一条长度为cost(i，j)的路线。但该路径不一定是最短路径，尚需修改，修改的方法是进行n次试探。首先考虑路径（i，1，j）（即在i，j中插进点1），看〈i，1〉，〈1，j〉是否存在，若存在，再比较 （i，j）与（i，1，j）这两条路径，长度较短者为当前求得的最短路径。于是这条求得的最短路径的 中间点序号不大于1。然后再在各对点i，j中插进一个点2，看〈i，...，2〉，〈2，...，j〉是否存在， 若不存在，那么当前的最短路径仍是上次求得...
HDU 1466计算直线的交点数
//相交直线数
http://acm.hdu.edu.cn/showproblem.php?pid=1466
典型的DP #include<stdio.h>int main(){ int i,j,n,f[21][191]; //f[i][j]表示i条边时，是否能产生j个结点，能，返回1，不能，返回0 for(i=0;i<21;i++) for(j=0;j<191;j++) f[i][j]=(j==0); //f[i][0]都置1 for(n=2;n<21;n++) for(i=n-1;i>=1;i--) for(j=0;j<191;j++) if(f[n...
HDU 1788 Chinese remainder theorem again
http://acm.hdu.edu.cn/showproblem.php?pid=1788
简单题 不过一开始还是被迷惑住了 以为是用中国剩余定理写的
不过后来发现原来只要求所有数的最大公约数减去a就是结果了
#include<stdio.h>__int64 gcd(__int64 a,__int64 b){ if(b==0)return a; else return gcd(b,a%b);}int main(){ __int64 n,a,k1,k2,k[10],i; while(scanf("%I64d%I64d",&n,&a)!=EOF&&a...
pku 1006Biorhythms
http://acm.pku.edu.cn/JudgeOnline/problem?id=1006
这道题是用中国剩余定理写的 直接套用公式了。。。。。
#include <stdio.h>int main(){ int p,e,i,d,a,t=0; while(scanf("%d%d%d%d",&p,&e,&i,&d)!=EOF) { if(p==-1&&e==-1&&i==-1&& d==-1)break; a=(5544*p+14421*e+1288*i-d+21252)%21252; i...
“中国剩余定理”算理及其应用（转）
今天在做北大acm1006题，找了一些诶资料。
“中国剩余定理”算理及其应用：
为什么这样解呢？因为70是5和7的公倍数，且除以3余1。21是3和7的公倍数，且除以 5余1。15是3和5的公倍数，且除以7余1。（任何一个一次同余式组，只要根据这个规律求出那几个关键数字，那么这个一次同余式组就不难解出了。）把 70、21、15这三个数分别乘以它们的余数，再把三个积加起来是233，符合题意，但不是最小，而105又是3、5、7的最小公倍数，去掉105的倍 数，剩下的差就是最小的一个答案。
用歌诀解题容易记忆，但有它的局限性，只能限于用3、5、7三个数去除，用其它的数去除就不行了。后来我国...
HDU 1684 Projects
http://acm.hdu.edu.cn/showproblem.php?pid=1684
这是一个二维的DP简单题 最近在做DP专题 呵呵 还是第一次做到二维的呢 爽
A题不多 只求在比赛前能多熟悉下DP的各种类型。。。。。
#include<stdio.h>#include<string.h>int p[101][101];int dp[101][101];int a[101];int reward[101];int punishment[101];int main(){ int m,n,t,max,i,j,k,salary,w; scanf("%d",&a...
ZJU 2956Another Horizontally Visible Segments
http://acm.zju.edu.cn/show_problem.php?pid=2956
这道题很郁闷啊 ，当时题目居然看错了，一开始的时候是理解对的 ，后来发现x输入怎么一点用都没有的，就开始郁闷了，这道题有这么难么？？都怪自己审题不清，还不肯重新看题。。。。
#include<stdio.h>#include<string.h>int count[10001];int main(){ int T,n,i,x[4001],y1[4001],y2[4001],sum,max; scanf("%ld",&T); while (T--) { scanf("%d",&...
ZJU2014 Piggy-Bank
http://acm.zju.edu.cn/show_problem.php?pid=2014
这些天在做DP专题，所以从HDU转战到ZJU找DP，没想到第一个就A到这道题，感觉有点变态！
这道DP花了我三天时间（资质比较差，没办法），终于搞定了，哈哈！！！
其实前几天我A的几个DP都是一个模板的，核心思想都是一个模板的。而这道题有点区别：
1、题目要求是在存钱罐里存入一定质量的钱，使得最少可以存钱
2、存钱罐必须存满
#include<stdio.h>#include<string.h>int p[10001],q[10001];int price[501],weight[...
HDU1203 I NEED A OFFER!
http://acm.hdu.edu.cn/showproblem.php?pid=1203
虽然是01背包问题，但是完全可以用贪心解决此题，如果用了动态，我认为反而把简单问题麻烦化了
此解法时间效率不高，有时间再重新看看……
#include<stdio.h>int main(){ int m,n,a[1001],i,j,t; double b[1001],k[1001],t1,s; while(scanf("%d%d",&m,&n)!=EOF&&!(m==0&&n==0)) { for(i=1...
文章归档
最新评论
- honesty2008：要是有些解题思路就更好了
- 狂人老大：<div class="xspace-quote">原帖由BCCN 网友于2008-05-08...
- zl芊芊zl：看了3道，好久都不算了，好累呀，改天有兴趣继续
- zl芊芊zl：天呢？啥叫公倍数来着？ 小学时候学的呀，都忘光了。。。。
- 狂人老大：<div class="xspace-quote">原帖由BCCN 网友于2008-05-14...