• 等级
  • 39778 访问
  • 294 原创
  • 0 转发
  • 17007 排名
  • 10 评论
  • 12 获赞

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\inA\landb\inB\}为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那么123456789抽掉后就是2468我们可以把这四个数字/...

2018-05-17 12:16:37

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

题目链接https://nanti.jisuanke.com/t/19975题意Alice和Bob玩游戏在一个4x4的方格上每个人每次选择2x2的区域将里面的四个值求和加到最后的分数当中(两个人共用一个分数),然后逆时针翻转他们,Alice想要分数尽量打Bob想要分数尽量小两个人每次的选择都是最优的求最后的分数思路玩的次数为2kk最大为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输出的话是会自动四舍五入的比如说doublee=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/BA=魔法路链接的两座城市...

2018-04-25 22:59:21

CodeForces - 580C Kefa and Park 【BFS】

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

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

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