You are playing a computer game. In this game, you have to fight 𝑛 monsters. To defend from monsters, you need a shield. Each shield has two parameters: its current durability 𝑎 and its defence rating 𝑏. Each monster has only one parameter: its strength 𝑑. Whe…

2020年9月16日 0条评论 2点热度 阅读全文

F. Upgrading Cities 题意 给你一个n个点m条边的DAG(有向无环图),问有多少个点的可到达的点数+可以被到达的点数>=n-1 做法 由于是有向无环图,我们首先考虑拓扑排序,如果A能够到达B,那么A,B肯定不会同时出现在队列中,所以如果队列中同时存在的点超过两个,这些点肯定都是不能互相到达的,也就是说对答案肯定没有贡献,之后考虑如果队列中只有一个点,那么所有没进队的点肯定都能到达,之后考虑如果队列中恰好有两个点,设两个点分别为A,B,B有一条边指向一个入度为1的点C,那么A肯定不能到达C,所…

2019年1月16日 0条评论 3点热度 阅读全文

E. Andrew and Taxi 题意 给你一个有边权的有向图,反转一条边的代价是这条边的边权,反转多个边的代价是所有反转边里面边权最大的那条边的边权,问让这个图不存在环的最小代价,以及被反转的边的编号。 做法 首先求最小代价,我们只需要二分这个代价,check就是看删除所有小于这个代价的边之后是否有环。 输出边集,要用到拓扑排序的一个性质 一个图进行拓扑排序后,对于每一个有向边u->v都存在u的拓扑序<v的拓扑序,则这个图上无环 之后我们就枚举所有小于当前代价的边,对所有不满足条件的边反转就可以。…

2019年1月15日 0条评论 3点热度 阅读全文

E. Andrew and Taxi time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output Andrew prefers taxi to other means of transport, but recently most taxi drivers have been acting inappropriately. In order to earn more…

2019年1月14日 0条评论 5点热度 阅读全文

文章目录 前言 题目 思路 代码 前言 这里的Dp定义很容易和KMP的Fail数组搞混… 题目 传送门: CodeForces Vjudge 题目大意: 你现在有一个长度为n的字符串S,现在让你求它的一个最长子串T使其既为S前缀,又为S后缀,并且在S中非前缀非后缀中出现过一次 数据范围: 1 ≤ n ≤ 1 0 6 1 \le n \le 10^6 1≤n≤106 思路 思路很简单,定义: D p [ i ] 为 i 为 末 尾 的 子 串 的 后 缀 与 能 够 匹 配 的 整 个 串 S 的 最 长 的 前 缀…

2018年10月25日 0条评论 5点热度 阅读全文

B. Table Tennis time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output n people are standing in a line to play table tennis. At first, the first two players in the line play a game. Then the loser goes to the …

2017年11月19日 0条评论 3点热度 阅读全文

题目传送门 There are n cities and n - 1 roads in the Seven Kingdoms, each road connects two cities and we can reach any city from any other by the roads. Theon and Yara Greyjoy are on a horse in the first city, they are starting traveling through the roads. But the…

2017年8月13日 0条评论 4点热度 阅读全文

B. Code For 1 time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output Jon fought bravely to rescue the wildlings who were attacked by the white-walkers at Hardhome. On his arrival, Sam tells him that he wants t…

2017年2月24日 0条评论 4点热度 阅读全文

题目链接:点击打开链接 A. Contest time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output Misha and Vasya participated in a Codeforces contest. Unfortunately, each of them solved only one problem, though successfully s…

2016年9月22日 0条评论 8点热度 阅读全文

题目连接 : http://codeforces.com/problemset/problem/55/D ——————————-. D. Beautiful numbers time limit per test4 seconds memory limit per test256 megabytes inputstandard input outputstandard output Volodya is an odd boy and his taste is strange as well. It seems to…

2016年8月26日 0条评论 7点热度 阅读全文