• 等级
  • 21979 访问
  • 294 原创
  • 0 转发
  • 15984 排名
  • 8 评论
  • 6 获赞

POJ - 2464 Brownie Points II 【树状数组 + 离散化】【好题】

题目链接 http://poj.org/problem?id=2464 题意 在一个二维坐标系上 给出一些点 Stan 先画一条过一点的水平线 Odd 再画一条 过Stan那条水平线上的任一点的垂直线 这两条线将坐标系分成了四个区域 Stan的得分为右上角区域的点数+左下角区域的点数 Ollie的得分为左上角区域的点数+右下角区域的点数 线上的点 不归任何人所有 两人都采用最...

2018-07-01 11:24:25

离散数学 图论基础知识总结

无序对: 两个元素构成的集合{a,b}{a,b}\{a, b\}称为无序对, 若A,BA,BA, B为两个集合,则 {{a,b}|a∈A∧b∈B}{{a,b}|a∈A∧b∈B}\{\{a, b\} | a\in A \land b \in B\} 为AAA与BBB 构成的无序积 与笛卡尔积的区别在于构成笛卡尔积是由有序对构成 无序积 中的无序对的两个元素不分次序同时又可以是相同的 ...

2018-06-13 15:03:09

2018 ACM-ICPC 西安邀请赛记录

想了很久,还是决定记录一下吧。毕竟ACM的征程说远也不远了,如果大三退役的话,也就只有两年了。 这大概是我的第一场ICPC的比赛吧。 和之前在浙大参加的校赛,省赛完全不一样。 系统是Ubuntu 提交用PC^2 提交代码交的是文件,返回的结果如果正确了不是AC 而是YES 怪不得别人写记录的一发A都是1Y 坐了十几个小时的火车,的确是身心疲惫,在城站的火车站还碰到浙大城院的队伍。听JSW讲起...

2018-06-04 20:43:08

The Maximum Unreachable Node Set 【17南宁区域赛】 【二分匹配】

题目链接 https://nanti.jisuanke.com/t/19979 题意 给出n个点 m 条边 求选出最大的点数使得这个点集之间 任意两点不可达 题目中给的边是有向边 思路 这道题 实际上是求 二分图的最大独立集 二分图的最大独立集 = 顶点数 - 二分图最大匹配 相关概念: https://blog.csdn.net/whosemario/article/deta...

2018-05-17 20:12:50

17 南宁区域赛 F - The Chosen One 【规律】

题目链接 https://nanti.jisuanke.com/t/19972 题意 给出一个n 然后将 n 个数 标号为 1 -> n 按顺序排列 每次抽掉 奇数位的数 然后求最后剩下那个数字的编号 思路 可以模拟一下过程 就可以发现规律 比如 n = 9 那么 1 2 3 4 5 6 7 8 9 抽掉后 就是 2 4 6 8 我们可以把这四个数字 / ...

2018-05-17 12:16:37

17南宁区域赛 I - Rake It In 【DFS】

题目链接 https://nanti.jisuanke.com/t/19975 题意 Alice 和 Bob 玩游戏 在一个4x4 的方格上 每个人 每次选择2x2的区域 将里面的四个值求和加到最后的分数当中(两个人共用一个分数),然后逆时针翻转他们,Alice 想要分数尽量打 Bob 想要分数尽量小 两个人每次的选择 都是最优的 求最后的分数 思路 玩的次数为 2k k最大为3 数...

2018-05-17 12:04:38

17南宁区域赛 J - Rearrangement 【规律】

题目链接 https://nanti.jisuanke.com/t/19976 题意 给出 一个n 然后 给出 2*n 个数 可以重新排列成两行 然后 相邻的两个数 加起来 不能被三整除 可以上下相邻 也可以 左右相邻 思路 因为相加 根据同余定理 我们可以先把 每个数 模3 因为 可以重新排列 那么我们不妨 以最优的方式去排 看能不能得到 YES 很显然 , 0 和 0...

2018-05-17 10:06:09

CodeForces - 691E Xor-sequences 【矩阵快速幂】

题目链接 http://codeforces.com/problemset/problem/691/E 题意 给出一个长度为n的序列,从其中选择k个数 组成长度为k的序列,因为(k 有可能 > n) 那么数字是可以重复选择的 使得 aj 属于 a1 -> ak-1 满足 aj ^ aj + 1 中二进制表示中1的个数是3的倍数 思路 很显然 当k == 1的时候,不存在 ...

2018-05-17 09:13:36

c/c++ 输入输出技巧

C: 小数的四舍五入问题 小数用 %.xf 输出的话 是会自动四舍五入的 比如说 double e = 2.718, c = 3.141; printf("%.2lf\n", e); printf("%.2lf\n", c); printf("%.2lf\n", (int)(e * 100) / 100.0); printf("%.2lf\n"...

2018-05-12 22:02:24

ZOJ - 1505 Solitaire 【双向BFS】

题目链接 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1505 题意 一个8 * 8 的棋盘上面有四个棋子 棋子可以上下左右移动,如果隔壁有个棋子 那就可以跳一步,只能跳一步。 给出 初始状态,和末尾状态 求能不能在8步之内达到 思路 如果是单向BFS (4 * 4)^ 8 = 2 ^ 32 个状态数 ...

2018-05-12 18:23:08

HDU - 5550 Game Rooms 【DP+前缀和】

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=5550 题意 一撞大楼有N层楼,然后每层楼都有一部分人喜欢打羽毛球,一部分人喜欢打乒乓球 但是每层楼只能选择建一个羽毛球馆或者建一个乒乓球馆 那么每个人到它喜欢的球馆的距离就是一个权值 求出怎么规划 使得所有人到它喜欢的球馆的距离之和最小 思路 其实当时在训练的时候 有在想 当时训练的...

2018-05-12 15:13:05

UVALive - 7045 Last Defence 【数学】

题目链接 https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5057 题意 给出两个数 递推式是 |s[i - 1] - s[i - 2]| 然后求这个数列 出现的不同数字的个数 思路 因为 X 和 Y ...

2018-05-10 19:07:23

HDU - 1175 连连看 【DFS】【BFS】

2018-05-10 11:14:35

POJ - 1094 Sorting It All Out 【拓扑排序】

题目链接 http://poj.org/problem?id=1094 题意 给出n个点,m对关系 判断 是否能够有一个确定的排列,或者矛盾,或者没有确定的排列 思路 在代码下面的注释中 AC代码 #include <cstdio> #include <cstring> #include <ctype.h> #include <cstdl...

2018-05-01 16:54:56

浙江省第十五届大学生程序设计竞赛 记录

其实还是非常激动,当初浙大校赛只有三题,然后后来通过 tryout 幸运得以参加省赛 其实当初天梯赛没有被选上,就以为大概是没有希望打省赛了。。 虽然说不是所有的努力都会得到应有的回报,但是没有努力的确也是没有回报的。 上午也是坐着校车 第二次来到浙江大学紫金港校区,其实还是非常喜欢浙江大学紫金港的 毕竟是自己心心念念梦想的大学。 其实看到人家的路牌 都是校徽的模样 早上去试机,热身...

2018-04-29 22:09:02

CodeForces - 597C Subsequences 【DP + 树状数组】

题目链接 http://codeforces.com/problemset/problem/597/C 题意 给出一个n 一个 k 求 n 个数中 长度为k的上升子序列 有多少个 思路 刚开始就是想用dp 复杂度 大概是 O(n ^ 2 * k) T了 但是 思路还是一样的 只是用树状数组 优化了一下 第三层循环 dp[i][j] 表示 第 i 个数 长度为 j 时 那...

2018-04-27 22:23:31

UVA - 10870 Recurrences 【矩阵快速幂】

题目链接 https://odzkskevi.qnssl.com/d474b5dd1cebae1d617e6c48f5aca598?v=1524578553 题意 给出一个表达式 算法 f(n) 思路 n 很大 自然想到是 矩阵快速幂 那么问题就是 怎么构造矩阵 我们想到的一种构造方法是 n = 2 时 n = 3 时 然后大概就能够发现规律了吧 。。 AC代码...

2018-04-27 22:12:31

HDU - 4081 Qin Shi Huang's National Road System 【次小生成树】

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=4081 题意 给出n个城市的坐标 以及 每个城市里面有多少人 秦始皇想造路 让每个城市都连通 (直接或者间接都可以) 然后 有一个特别厉害的大臣 可以造一条魔法路 不用耗费资金 但是要求 这条路链接的两座城市的人要尽量多 定义了一个 value = A/B A = 魔法路链接的两座城市...

2018-04-25 22:59:21

CodeForces - 580C Kefa and Park 【BFS】

题目链接 http://codeforces.com/problemset/problem/580/C 题意 根节点是 1 然后所有的叶子结点都是饭店 从根节点到叶子结点的路径上 如果存在 大于m 个 连续的结点都有猫 那么这条路径就是不可行的 求 最后能到达几个饭店 思路 BFS 就可以了 一层一层往下搜 但是要注意 这个输入的时候 xi yi 没有说 那个是父...

2018-04-25 22:44:10

HDU - 1430 魔板 【BFS + 康托展开 + 哈希】

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=1430 思路 我刚开始 想到的 就是 康托展开 但是这个题目是 多组输入 即使用 康托展开 也是会T的 正解应该是 预处理 然后我想到的预处理 因为每个状态 都是能够扩展出三种状态的 也就是说 每个状态都可以有三个儿子 这样 就像一棵树 我先把这棵树 建好 然后 询...

2018-04-25 22:41:01

Dup4

关注
  • 中国
奖章
  • 持之以恒