博客首页 → ACM

最新文章列表

[DP]zoj 3310：Unrequited Love

大致题意：    给出一个长度为n的数字环，现在要取出某些位置的数字使得取出的数字的和最大且这些数字的位置两两不相邻。   大致思路：    要分为两种情况，取第一个和不取第一个，分别dp两次求最大值即可。   #include<iostream> #include<cstring> #include<cstdio> using namespa ...
dp动态规划acmzoj 3310bbezxcy 
暴风雪 评论(0) 有935人浏览 2012-06-19 15:21

[最大流]zoj 3305：Get Sauce

大致题意：     有n种原材料，每种一件。现在给出m个组合，每个组合包含k种原材料，代表这k种材料可以加工成一个成品。求最多能加工出多少成品。   大致思路：     先把每个点拆做a和a'。连接a->a'。设容量为1。对于每k个原材料，每个点a连接他后面的那个数拆出的点b‘。k个数中的头和尾分别连接到原点和汇点上。求出最大流即可。       吐槽一句，想出构图之后，又手贱看了 ...
网络流acmzoj 3305bbezxcy 
暴风雪 评论(0) 有978人浏览 2012-06-19 10:04

[最小费用流]zoj 3308：Move the Knights

大致题意：     一个国际象棋棋盘上有n个马分布在不同的黑色格子上，这些棋子共有三种，“金马”移动的能量损耗是P(row1,col1) x P(row2,col2)，“银马”是P(row1,col1) + P(row2,col2)，铜马是max(P(row1,col1) , P(row2,col2))。现在允许n个棋子中有k个棋子移动一步，求移动的马数量最多时最少能量消耗是多少。   大致思 ...
费用流图论acmzoj 3308bbezxcy 
暴风雪 评论(0) 有1033人浏览 2012-06-15 15:45

[最小路径覆盖]hdoj 3335：Divisibility

大致题意：    给出不超过1000个数字，现在要取出k个数字，使得这k个数字两两之间互质，问k最大是多少。   大致思路：      把问题转化为二分图最大匹配问题，把每个点i拆做 i 和 i' ，如果a>b且a可以整除b则连接a->b'。求出最小路径覆盖即可。   #include<iostream> #include<cstring> # ...
最小路径覆盖hdoj 3335acmbbezxcy 
暴风雪 评论(0) 有1213人浏览 2012-06-14 21:47

[费用流+拆点]hdoj 2686&&hdoj 3376：Matrix&&Matrix Again

大致题意：    给出一个n*n的矩阵，现在要从左上角走到右下角，规定除了（0，0）（n-1，n-1）之外不能走重复的路，求来回路径覆盖到的数字之和最大是多少，两题除了数据量之外的，其他完全一样。   大致思路：     把矩阵的每个元素拆点，用于限制每个点经过的次数，并且与其下面的点和右边的点相连。然后对左上角和右下角特殊处理……求出费用流即可。因为只要增广两次，所以3376的数据量并不需要 ...
费用流hdoj 2686hdoj 3376acmbbezxcy 
暴风雪 评论(0) 有918人浏览 2012-06-14 09:27

[最长不降子序列]zoj 3523：Bookcase

大致题意：    一个书架共有n层，每层m本书，现在要使得每一层的书都按照字典序不降的排列，每次可以把一本书移动到这本书所在层的另一个位置，求完成所有n层所需要的最少移动次数。   大致思路：    对于每层，移动次数等于m-lis。统计每一层的再相加即可。   #include<iostream> #include<cstring> #include< ...
lisdpacmzoj 3523bbezxcy 
暴风雪 评论(0) 有1099人浏览 2012-06-12 17:29

[DP]zoj 3331：Process the Tasks

大致题意：    有两个机器a，b。要处理n个部件，第i个部件在机器a上完成需要atime[i]，在b机器上需要btime[i]，每个部件只能选择一个机器来完成。且当地i个部件开始加工时前[1，i-1]部件必须已经完成或者正在被加工。求加工完所有n个部件的最小时间是多少。   大致思路：    好神的dp，开始时乱想了几个状态都觉得不靠谱，膜拜了众犇的博客才明白怎么做，大神敬请bs。这里的状态表 ...
dp动态规划acmzoj 3331bbezxcy 
暴风雪 评论(0) 有1577人浏览 2012-06-12 11:39

[模拟]zoj 3326：An Awful Problem

大致题意：     给出两个日期，求出两个日期中，月份为质数且日期为质数的日期有多少，包含两个端点日期。   大致思路：     纯模拟，要注意考虑端点就为素数的情况。   #include<iostream> #include<cstring> #include<cstdio> using namespace std; int isle ...
模拟zoj 3326acmbbezxcy 
暴风雪 评论(0) 有1046人浏览 2012-06-08 17:45

[模拟+二分]zoj 3470：Magic Squares

大致题意：     如题目中给出的图片 对于这样的一个无线扩展出去的图，输入一个数n，求出数字上下左右的4个数字，按造升序输出。   大致思路：     突破点在，对于每一圈右下角的数字都是（a*2-1）*（a*2-1），a为当前在第a圈。如此，通过二分枚举判定出这个点在第几个圈内。然后在推导这个点和上下左右点的关系。   #include<iostream> #i ...
二分acm模拟zoj 3470bbezxcy 
暴风雪 评论(0) 有1050人浏览 2012-06-08 14:37

[状态压缩DP]zoj 3471：Most Powerful

大致题意：     有n颗原子，给出一个n*n的矩阵map。map[i][j]=a，则代表第i个原子和第j个相撞，且第j个原子会消失，并且释放出a的能量，现在求释放能量的最大值是多少。   大致思路：    dp[b]表示状态b下的最大能量值，比如b=10，则可以二进制转化为1010，在这里我们把0看作保留这一位的原子，1看作这一位的原子消失。则dp[10]可看作第2，4位的原子消失，其他位的 ...
状态压缩动态规划acmzoj 3471bbezxcy 
暴风雪 评论(0) 有1306人浏览 2012-06-05 17:00

分享一下我的vimrc

  "编码设置 set enc=utf-8 set fencs=utf-8,ucs-bom,shift-jis,gb18030,gbk,gb2312,cp936 "语言设置 set langmenu=zh_CN.UTF-8 set helplang=cn if has("syntax") syntax ...
vimrcacmlinux 
暴风雪 评论(0) 有1335人浏览 2012-06-05 10:24

[DP]zoj 3468：Dice War

大致题意：    输入a,b(a,b<=8)，求出扔a个骰子得到的数字总和大于扔b个骰子的概率。   大致思路：    很水的DP，水到我这种水人都能1A。     DP[i][j]代表投i个骰子的时候，数字为j的概率。先预处理出dp数组，等输入a,b时直接计算输出即可。   #include<iostream> #include<cstring> ...
DP动态规划zoj 3468acmbbezxcy 
暴风雪 评论(0) 有1108人浏览 2012-06-04 17:35

python深搜&回朔

好久没有做题了，以前都是用C++做ACM题目，但是自从发现python,发现python写算法更优雅。 所以以后决定一有时间就坚决要来做做题。因为ZOJ的OJ支持python语言的，所以决定选择ZOJ了。 题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=2 这道题目比较简单，这里就不做解释了，直接贴源码了! def ...
pythonacm算法 
Mr_Lian 评论(0) 有1452人浏览 2012-05-31 16:06

[DP]zoj 3463：Piano

大致题意：     用两只手弹钢琴，当两个拇指不动的时候，左手可以摸到拇指左边的九个键，右手可以摸到拇指右侧的九个键。两只手移动拇指x个长度单位需要f(x) = floor(sqrt(x))的花费。现在给出两个拇指的初始位置，以及n个音符的键位，求出弹出n各音符的最小话费。   大致思路：    简单的dp，dp[a][b][c]表示弹到第a个音符，左手在b，右手在c的最小花费。   ...
dpzoj 3463acmbbezxcy 
暴风雪 评论(0) 有943人浏览 2012-05-31 10:14

[二分+匈牙利]zoj 3460：Missile

大致题意：    用n个导弹发射塔攻击m个目标。每个发射架在某个时刻只能为一颗导弹服务，发射一颗导弹需要准备t1的时间，一颗导弹从发射到击中目标的时间与目标到发射架的距离有关。每颗导弹发射完成之后发射架需要t2的时间进入下个发射流程。现在问最少需要多少时间可以击毁所有m个目标。   大致思路：    二分枚举这个最大时间的最小值，每次按照这个枚举的时间构出二分图，求最大匹配来判定枚举值是否符合要 ...
zoj 3460图论acm二分图bbezxcy 
暴风雪 评论(0) 有1280人浏览 2012-05-26 16:16

[usaco] Chapter2-Bigger Challenges(Section 2.4)

  /* ID: bbezxcy1 PROG: ttwo LANG: C++ */ #include<iostream> #include<cstring> #include<fstream> #include<cstdio> using namespace std; char map[20][20]; bool vis[15] ...
usacobbezxcyacmicpc 
暴风雪 评论(0) 有889人浏览 2012-05-26 08:53

【扩展欧几里德】SGU 106

KIDx的解题报告   题目链接：http://acm.sgu.ru/problem.php?contest=0&problem=106   题意：求ax + by + c = 0在[x1, x2], [y1, y2]区间内有多少组解？  
KIDx数论ACMC++编程 
基德KID.1412 评论(0) 有2397人浏览 2012-05-22 23:57

[usaco] Chapter2-Bigger Challenges(Section 2.3)

  /* ID: bbezxcy1 PROG: prefix LANG: C++ */ #include<fstream> #include<iostream> #include<cstring> #include<cstdio> using namespace std; char cha[203][15],str[200005] ...
usacobbezxcyacmicpc 
暴风雪 评论(0) 有897人浏览 2012-05-21 22:29

ACM-XZNU-1124 菲波那契数列(2) java 解题报告

  1124:菲波那契数列(2)
ACM大数据 
jiangwt100 评论(0) 有1771人浏览 2012-05-18 08:49

【数论+容斥】POJ 1091 跳蚤

KIDx的解题报告   题目链接：http://poj.org/problem?id=1091   假设卡片上标号分别是a1, a2, ..., an, M，跳蚤跳对应号的次数分别为x1, x2, ..., xn，跳M个单位长度的次数是xn+1，那么要满足已知条件只需满足方程： a1x1+a2x2+...+anxn+Mxn+1 = 1 有解，即： gcd (a1, a2, ..., ...
KIDxACMC++编程算法 
基德KID.1412 评论(2) 有3364人浏览 2012-05-17 13:11

最近博客热门TAG

Java(141747) C(73651) C++(68608) SQL(64571) C#(59609) XML(59133) HTML(59043) JavaScript(54918) .net(54785) Web(54513) 工作(54116) Linux(50906) Oracle(49876) 应用服务器(43288) Spring(40812) 编程(39454) Windows(39381) JSP(37542) MySQL(37268) 数据结构(36423)

博客人气排行榜

    博客电子书下载排行

      >>浏览更多下载

      相关资讯

      相关讨论

      Global site tag (gtag.js) - Google Analytics