ww3113306

2018年6月6日

摘要：题面：羽毛球队有男女运动员各n人。给定2 个n×n矩阵P和Q。P[i][j]是男运动员i和女运动员j配对组成混合双打的男运动员竞赛优势；Q[i][j]是女运动员i和男运动员j配合的女运动员竞赛优势。由于技术配合和心理状态等各种因素影响，P[i][j]不一定等于Q[j][i]。男运动员i和女运动员j 阅读全文

posted @ 2018-06-06 09:17 ww3113306 阅读(1103) 评论(0) 推荐(0)

[NOI2015]荷马史诗

摘要：题面：追逐影子的人，自己就是影子 ——荷马 Allison 最近迷上了文学。她喜欢在一个慵懒的午后，细细地品上一杯卡布奇诺，静静地阅读她爱不释手的《荷马史诗》。但是由《奥德赛》和《伊利亚特》组成的鸿篇巨制《荷马史诗》实在是太长了，Allison 想通过一种编码方式使得它变得短一些。一部《荷马史阅读全文

posted @ 2018-06-06 09:07 ww3113306 阅读(173) 评论(0) 推荐(0)

2018年6月2日

[HAOI2010]计数数位DP+组合数

摘要：题面：你有一组非零数字（不一定唯一），你可以在其中插入任意个0，这样就可以产生无限个数。比如说给定{1,2},那么可以生成数字12,21,102,120,201,210,1002,1020,等等。现在给定一个数，问在这个数之前有多少个数。（注意这个数不会有前导0）. 样例输入：1020 样例输出阅读全文

posted @ 2018-06-02 14:36 ww3113306 阅读(223) 评论(0) 推荐(0)

[HNOI2005]狡猾的商人

摘要：题意：有一个数列，告诉你m组区间和，问区间和中是否有冲突（即错误）比如2 4 3 4 7 5 (你不知道这个数列，但都是正整数）告诉你：2 ~ 4 = 111 ～ 3 = 91 ～ 2 = 11这就不合法，虽然数列未知，但1~2的区间和比1~3的还小，这显然是不可能的题解：首先它告诉我们的是区间和阅读全文

posted @ 2018-06-02 14:10 ww3113306 阅读(429) 评论(0) 推荐(0)

2018年5月29日

[HNOI2004]树的计数 prufer数列

摘要：题面：一个有n个结点的树，设它的结点分别为v1, v2, …, vn，已知第i个结点vi的度数为di，问满足这样的条件的不同的树有多少棵。给定n，d1, d2, …, dn，你的程序需要输出满足d(vi)=di的树的个数。题解：乍一看是组合数学，，，当然了，实际上也是组合数。只不过要是知道p 阅读全文

posted @ 2018-05-29 21:01 ww3113306 阅读(479) 评论(0) 推荐(0)

[WC2008]游览计划状压DP，斯坦纳树

摘要：～～～题面～～～题解：这是一道斯坦纳树的题，用状压+spfa来解决什么是斯坦纳树？一开始还以为是数据结构来着，其实跟最小生成树很像，大致就是最小生成树只能在各个点之间直接相连，而斯坦纳树则允许间接相连。就是允许在图中添加新的点，再通过连接新的点来将指定点联通。这些新点可能是被限定的（给定点阅读全文

posted @ 2018-05-29 20:44 ww3113306 阅读(300) 评论(0) 推荐(0)

2018年5月27日

[USACO06NOV]玉米田Corn Fields 状压DP

摘要：题面：农场主John新买了一块长方形的新牧场，这块牧场被划分成M行N列(1 ≤ M ≤ 12; 1 ≤ N ≤ 12)，每一格都是一块正方形的土地。John打算在牧场上的某几格里种上美味的草，供他的奶牛们享用。遗憾的是，有些土地相当贫瘠，不能用来种草。并且，奶牛们喜欢独占一块草地的感觉，于是Jo 阅读全文

posted @ 2018-05-27 22:17 ww3113306 阅读(222) 评论(0) 推荐(0)

[HAOI2009]毛毛虫树形DP

摘要：题意：给你一棵树，从树中取出一部分满足：是一条链+一些直接连在这条链上的节点求节点数最多的合法取出部分。题解：其实这题还是不难? 观察到对于任意一条链，只有两种情况：一条路走到底 or 以某个点为中转 f[x]表示从x往下走，一路走到底的包括x的最优解, f[x]包括x也包括father 阅读全文

posted @ 2018-05-27 21:44 ww3113306 阅读(593) 评论(0) 推荐(0)

[NOI2001]炮兵阵地状压DP

摘要：题面：司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用“H” 表示），也可能是平原（用“P”表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：阅读全文

posted @ 2018-05-27 21:14 ww3113306 阅读(154) 评论(1) 推荐(0)

[GDOI2014]拯救莫莉斯状压DP

摘要：题面：莫莉斯·乔是圣域里一个叱咤风云的人物，他凭借着自身超强的经济头脑，牢牢控制了圣域的石油市场。圣域的地图可以看成是一个n*m的矩阵。每个整数坐标点(x , y)表示一座城市（ 1\le x\le n,1\le y\le m1≤x≤n,1≤y≤m ）。两座城市间相邻的定义为：对于城市(Ax, 阅读全文

posted @ 2018-05-27 20:58 ww3113306 阅读(172) 评论(0) 推荐(0)

鸽王了属于是

公告