当前位置: 代码迷 >> 综合
 解决方案列表
  • [综合] codeforces732D Exams(二分)

    题意: 给出一串数字,代表了第i天能够进行哪场考试,如果为0就不能考试,每天只能考一场。一共要考m场试,每门科目要a[i]的复习时间,所以问最快第几天能够考完所有科目。 要点: 一开始我觉得BFS可以做,后来发现状态量没法表示,网上看了一下,原来可以用二分做,因为当第i天时考科目d[i]时,你最多可...

    36
    热度
  • [综合] codeforces732F Tourist Reform(边双连通分量)

    题意: 给出一个无向图,要求转变为有向图,使所有点能到达的点数的最小值最大。 要点: 就是一个边双连通分量,不过我没学过,看了一下白书,觉得就是无向图中的强连通分量,但是其中有很多细节有点难推敲,基本思路就是:边双连通分类对应无向图,找出其中内部点数最多的边双连通分量,它的内部所有点都可以到其余点(...

    60
    热度
  • [综合] POJ3370 Halloween treats(数论:鸽巢原理)

    题意: 给出一系列数,其中选取任意数量数,使总和能整除c,只要输出一种结果即可。 要点: 这题虽说是鸽巢原理,但其实就是证明用了一下,主要还是用巧妙的手段来降低了很多复杂度,我想的是用先整除c后DP或DFS,后来觉得有点麻烦就看了网上的方法:用sum数组记录从1到i的总和整除c,如果出现sum[i]...

    45
    热度
  • [综合] codeforces732E Sockets(贪心)

    题意: 给出一些给定功率的电脑和插座,只有功率匹配才能连接,另外有一些适配器,连在插座上可以把插座功率降为1/2,求最多匹配电脑数和需要的适配器数以及具体映射。 要点: 这题就是贪心+STL的应用,主要是贪心的证明,具体证明看下面这个博客: 参考博客:点击打开链接 #include<iost...

    88
    热度
  • [综合] HDU3749 Financial Crisis(点双连通分量+并查集)

    题意: 给出一个图和一系列查询,查询是给出两个点,问两点之间有多少条点不重复的路径 要点: 明显是点双连通,如果u,v不连通(并查集处理)输出0;如果u,v处于同一个点双连通分量,输出2(注意这里如果这个分量只有两个点一条边输出1);如果不同,输出1即可。 注意这题有个地方要处理,我们知道割顶可以是...

    89
    热度
  • [综合] HDU3394 Railway(点双连通分量)

    题意: 给出一个无向图,求出它的冲突边数和多余边数,冲突边就是那些同时存在于多个环中的边,而多余边是不在任何一个环中的边.。 要点: 多余边很明显就是桥,我们可以推断除冲突边只能在点双连通分量中,感觉边双应该也行,主要就是求出分量后看分量中点数n和边数m的关系,如果n<m,整个分量中所有的边都...

    18
    热度
  • [综合] codeforces721C Journey(DP)

    题意: 给出一个图,问从点1到n,在总时间为T的情况下最多能经过多少城市? 要点: 一看就知道是DAG里的DP,直接递推比较难写,用记忆化搜索比较方便,基本思路就是用dp[i][j]存储从i开始经过j个城市所需最少时间,最后找出时间小于等于T的j的最大值即可。 #include<iostre...

    76
    热度
  • [综合] codeforces721D Maxim and Array(贪心)

    题意: 给出一系列数,要求可以进行k次操作,每次可以将数列中一个数+x或-x,求这些数的乘积的最小值。 要点: 这题就是贪心,如果负数是奇数个,就将当前数列中绝对值最小的数远离0,如果是偶数个,就靠近0。自己算算觉得还是挺靠谱的,感觉自己做还是不敢这么写。 #include<iostream...

    1
    热度
  • [综合] 【?】codeforces721E Road to Home(DP+单调队列)

    转换关系搞清楚了,但是关于那个单调性来处理DP的地方,还是不明白,应该是单调队列优化DP这个点不会,补一下代码,先学一下单调队列优化DP, 参考博客:点击打开链接 #include<iostream> #include<cstring> #include<algori...

    48
    热度
  • [综合] HDU3401 Trade(单调队列优化DP)

    最近做CF的时候遇到单调队列优化DP的问题,看了一下网上这种题也很少,而且都很难理解,下面是两个解释的比较好的博客: 单调队列优化DP的基本思路:点击打开链接 两道例题详解:点击打开链接 下面讲一下我自己对单调队列优化dp的理解,首先不是所有dp都可以使用单调队列优化的,只有形如dp[i]=max/...

    69
    热度
  • [综合] codeforces712E Memory and Casinos(区间树)

    题意: 有n个赌场,你在i赌场时,有pi的概率走到i+1,有1?pi的概率走到i?1.保证任何时候pi≤pi+1有q次操作,修改一个赌场的p值;或者询问[l,r]表示从第l个赌场走到r的概率,他在走的过程中不会离开区间[l,r]. 要点: 比较容易看出是区间树,但是这个概率的处理很复杂,基本思路可以...

    93
    热度
  • [综合] 【Dijkstra模板】codeforces715B Complete The Graph(最短路径)

    记录一下Dijkstra的模板,主要加了一个优先队列,时间复杂度变成O(mlogn),速度快了很多。 structEdge {intfrom,to,dist;Edge(intu,intv,intw):from(u),to(v),dist(w){} }; structHeapNode {intd,u...

    15
    热度
  • [综合] HYSBZ2118 墨墨的等式(最短路径)

    这题是校周赛上碰到的,很经典的一道题,里面的思想很巧妙。 题意: 中文题不解释 要点: 一开始根本想不到是最短路径,我们先把{an}中最小的值找到为a1,这样将所有的an%a1,这样最后的结果就是相当于x+k*a1,那么我们就要求这个x,也就是所有an%a1后组合可以达到的数。可以简单的看出x<...

    60
    热度
  • [综合] codeforces742B Arpa’s obvious problem and Mehrdad’s terrible solution(水)

    题意: 给出一系列数字,求两两异或为x有几对。 要点: 看范围10^5就知道直接循环肯定gg,所以用一个num[x]存储x出现过几次,一般用两个for可以简化,像下面这样: #include<cstdio> #include<iostream> #include<cs...

    31
    热度
  • [综合] 有环图求环的个数和具体节点数

    这个问题一直没仔细写过,cf上做到了就写一下,就是用栈存储+回溯,很简单。 #include<iostream> #include<cstring> #include<stack> #include<vector> #include<algor...

    45
    热度
  • [综合] codeforces741C Arpa’s overnight party and Mehrdad’s silent entering(二分图)

    题意: 有2n个人围成一圈坐在桌子边上,每个人占据一个位子,对应这2n个人是n对情侣,要求情侣不能吃同一种食物,并且桌子上相邻的三个人的食物必须有两个人是不同的,只有两种食物(1或者是2),问一种可行分配方式。 要点: 想不出来,后来看了网上的题解豁然开朗,题目要求情侣颜色不一样所以将情侣之间连无向...

    52
    热度
  • [综合] multimap的使用方法

    multimap主要用于一个key值对应多个value的情况,比如一个人可以有很多个电话号码,其他的使用都还简单,主要记录一下怎么遍历: /*multimap的遍历方法,主要利用multimap中同一个key对应的value值连续存储这一特性*/ #include<iostream> ...

    35
    热度
  • [综合] POJ3731 Escape(组合数学)

    题意: 给你一个方格图,你在(0,0),最大是(x,y),x是横坐标,y纵坐标,你的基地在(sx,sy),然后你开头是面朝y轴正方向,你每次只能往前走一格,或者右转一格,问你有多少种不同的方法到达基地。 要点: 挺难的,还是看网上的题解。基本思路就是从(sx,sy)将方格图分成4个象限,这样考虑右转...

    60
    热度
  • [综合] POJ1981 Circle and Points(计算几何)

    题意: 给出一系列点,这些点之间的距离都在2附近,求一个单位圆最多能包含几个点。 要点: 极限情况就是2个点在圆的边上,这样就可以求出圆心,再枚举看其他点在不在圆内即可,复杂度是n^3。 #include<cstdio> #include<cstdlib> #include...

    97
    热度
  • [综合] 栈实现迷宫问题

    很久没写代码了,主要是现在学了一下JAVA,顺便把上课的内容实现一下。栈实现迷宫问题也就是栈实现dfs,主要是顺便把路径记录在栈里,所以稍微有些复杂,下面是代码: JAVA实现: packagecom.stack;importjava.util.Stack;classnode{intx,y,dir...

    53
    热度