Dup4'Blog

原创 [WIP] 博客迁移通知

本博客正在迁移：[WIP] 跟 TI1050 相关的内容，会迁移至以下地址：https://ti-1050.github.io/wikihttps://dup4.com/TI1050https://acm.hznu.edu.cn/team/TI1050

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

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

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

无序对: 两个元素构成的集合{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 ACM-ICPC 西安邀请赛记录

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

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

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

原创 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我们可以把这四个数字 / ...

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

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

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

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

原创 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的时候，不存在 ...

原创 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"...

原创 ZOJ - 1505 Solitaire 【双向BFS】

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

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

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

原创 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 ...

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

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

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

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

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

原创 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 时那...

原创 UVA - 10870 Recurrences 【矩阵快速幂】

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

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

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

原创 CodeForces - 580C Kefa and Park 【BFS】

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

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

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

原创 HDU - 1134 Game of Connections 【DP】

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=1134题意 给出一个n 然后有2n个点 给两个点连一条边，最后连N条边，要求所有的边不能够交叉 问最多有几分连边的方式思路我们可以发现 一个点 可以和它相隔偶数个点 的点连一条边 如果相隔奇数个点 比如说那么 2号点 要是想连一条边 必然会经过点1和点3 连的边 ...

原创 HDU - 1598 find the most comfortable road 【最小生成树】

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=1598思路用kruskal 算法将边排序后 跑 kruskal然后依次将最小边删除 再去跑 kruskal 直到不能成功跑成通路为什么要删掉最小边 因为边是按从小到大排序的那么也就是说 我每次加入的边 都是必须加入的 最小的边 那么如果 最高速与最低速的差 还大了 ...

原创 HDU - 3081 Marriage Match II 【二分匹配】

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=3081题意有n对男女 女生去选男朋友如果女生从来没和那个男生吵架 那么那个男生就可以当她男朋友 女生也可以选择从来没和自己闺蜜吵过架的男生当男朋友如果 女生A和女生B是闺蜜 女生A和男生C吵过架 但是女生B和男生C从来没吵过架那么女生A是可以选择男生C当男朋友的。看来 讨好...

原创 UVALive - 7427 the math 【二分匹配】

题目链接https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5449题意给出一个n 然后有n行 每行给出两个数 这两个数之间可以用三种操作 分别是 + - *如果这n对数通过操作后 得到的结果都是不同...

原创 HDU - 4965 Fast Matrix Calculation 【矩阵快速幂】

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=4965题意给出两个矩阵 一个A: n * k 一个B: k * nC = A * B M = (A * B) ^ (n * n) 然后将M中所有的元素对6取余后求和思路矩阵结合律。。M = (A * B) * (A * B) * (A * B) * (A * B) * (...

原创 UVALive - 6257 K - Chemist's vows 【DFS】【BFS】【DP】

题目链接https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4268题意 给出化学元素周期表，然后给出一个字符串，判断字符串里面的字符，能不能够完全由元素周期表里面的元素构成或者换一种说法，将字符串切割成若干...

原创 ZOJ - 3761 Easy billiards 【并查集+DFS】

题目链接http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3761题意在一个桌面上，给出一些球 如果在A球的某个方向的前方有B球 那个A球就可以朝那个方向滚 然后 滚到B球的位置后 ，B球往前滚，A球停在B球的位置上求这样操作后，最后最少剩下多少球，然后要输出操作的方式思路其实可以发现，一个球经过一次...

原创 HDU - 5695 Gym Class 【拓扑排序】

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=5695思路给定一些关系 进行拓扑排序 但是有一个要求 对于哪些没有确切的位置的点 要按照ID大小 ID大的排在前面 这个就可以用 优先队列 如果不用优先队列 而是每次从大到小去遍历 是不可行的因为 可能存在 一个点出队后 然后后面有点入队 这个点的ID比当前已经在队伍中的点的ID要...

原创 [kuangbin带你飞]专题一 简单搜索 学习笔记&题解

搜索问题DFS : 一般适用于 枚举每一条路径的情况，比如八皇后问题，或者棋盘问题，但是有时候枚举出所有路径没超时，所以我们可能需要去加入剪枝，剪掉显然不能满足条件的情况BFS： 一般适用于求最短路径，或者说给出一张图，然后有多个地方要到达，我们可以直接BFS一遍，将每个能到达的点表上步数，这样我们搜索一遍，就能知道到达每个地方的最短路径了，这样面对给出一张图，然后很多...

原创 牛客小白月赛2 题解

A_数字方阵思路 假如 我们按照 1 2 3 4 5 6 7 8 9就会发现 每一行 每一列 都不一样 但是 两条对角线上的元素是一样的这样的话 1 2 7 3 4 8 5 6 9我将前两列按照 这样的顺序 排 然后最后一排改一下 就可以了。其实不一定是这样 还是有很多其它排列的方法的AC代码#include <cstdio>#in...

原创 Kattis - names Palindrome Names 【字符串】

题目链接https://open.kattis.com/problems/names题意 给出一个字符串 有两种操作 0.在字符串的最末尾加一个字符 1.更改字符串中的一个字符求最少的操作步数使得字符串变成回文串思路 由于回文串具有对称关系 所以给出一串回文串 最多的操作步数 就是 len / 2 只改一半不同的字符就可以了所以我们可以先将字符串倒置然后依次...

原创 Floyd 学习笔记

#include <cstdio>#include <cstring>#include <ctype.h>#include <cstdlib>#include <cmath>#include <climits>#include <ctime>#include <iostream&

原创 HDU - 1114 Piggy-Bank 【完全背包】

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=1114题意 给出一个储钱罐 不知道里面有多少钱 但是可以通过重量来判断 先给出空储钱罐的重量 再给出装满钱币后储钱罐的重量 之后给出N种货币 pi wi pi 表示 第i件货币的价值 wi 表示第i件货币的重量 最后要求 储钱罐里面最少有多少钱思路 完全背包模板问题 要注...

原创 HDU - 1176 免费馅饼 【DP】

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=1176思路 因为刚开始的起点是固定的 但是终点不是固定的 所以我们可以从终点往起点推dp[i][j] 表示 在时刻为t的时候 坐标为j 的时刻 可以获得的最多馅饼数dp[i][j] += max(dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j +...

原创 POJ - 3414 Pots 【BFS】

题目链接http://poj.org/problem?id=3414题意 给出两个杯子 容量分别为 A B 然后给出C 是目标容量 有三种操作 1 将一个杯子装满 2.将一个杯子全都倒掉 3.将一个杯子的水倒到另一个杯子里面 如果某个杯子里面的水 能够达到 目标容量 那么就输出步骤思路 BFS 并且要存储步骤每一步一共有六步操作 记得标记AC代码#i...

原创 HDU - 2089 不要62 【数位DP】

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=2089思路 一切都在代码注释中AC代码#include <cstdio>#include <cstring>#include <ctype.h>#include <cstdlib>#include <cmath>#in...

原创 2018年长沙理工大学第十三届程序设计竞赛 G 逃离迷宫 【BFS】

链接：https://www.nowcoder.com/acm/contest/96/G 来源：牛客网时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32768K，其他语言65536K 64bit IO Format: %lld 题目描述 给你一个n*m的图，地图上’.’代表可以走的地方，而’#’代表陷阱不能走， ‘P’代表人物位置，’K’代表钥匙，’E’代表出口。...

原创 2018年长沙理工大学第十三届程序设计竞赛 C 取手机 【概率】

链接：https://www.nowcoder.com/acm/contest/96/C 来源：牛客网时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32768K，其他语言65536K 64bit IO Format: %lld 题目描述 durong有a台iphonex和b台s8，并且放在一个保险箱里，durong现在一台一台从保险箱随机拿出这些手机，现在他想知道第...

原创 2018年长沙理工大学第十三届程序设计竞赛 E 小木乃伊到我家 【最短路】

时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32768K，其他语言65536K 64bit IO Format: %lld 题目描述 AA的欧尼酱qwb是个考古学家，有一天qwb发现了只白白圆圆小小的木乃伊，它是个爱哭鬼却很努力。qwb想把这么可爱的小木乃伊送给 AA，于是便找上了快递姐姐，这下可让快递姐姐犯愁了，因为去往AA家的路实在太难走了（甚至有可能没有路能...