• 2024-09-18LOJ #3490. 「JOISC 2021 Day2」逃跑路线
    Description在IOI王国,人们使用Byou作为时间单位。IOI王国中的一天被分为了\(S\)个时间单位。每天从最开始经过\(x\(0\lex<S)\)Byou后的时间称为时刻\(x\)。IOI王国由\(N\)个城市组成,以\(0\)到\(N-1\)编号。其中有\(M\)条双向道路连接某些城市,以\(0\)
  • 2024-03-29P1821 [USACO07FEB] Cow Party S
    [P1821USACO07FEB]CowPartyS-洛谷|计算机科学教育新生态(luogu.com.cn)每次都求一遍从uuu到r
  • 2024-03-07ARC090E 题解
    Solution一道不错的计数题。因为直接求不相遇的方案十分复杂,所以考虑正难则反,用总的方案数减去相遇的方案数。求方案数很套路:在求最短路的时候开一个数组\(del\)记录到达点\(i\)的最短路条数,更新最短路时顺便更新即可。跑完最短路后,设\(dis1\)为\(s\)到\(t\)的最短路
  • 2024-02-17[ARC108F] Paint Tree
    本题有两种思路。首先,对于普通的树,到一个点最远的点一定是直径的端点之一。记\(S\)表示直径长度。做法\(1\)先求出一条直径,若直径的两个端点颜色相同,则最长距离一定为直径。否则,令两个端点分别为\(x,y\),并钦定\(x,y\)不同色。枚举答案\(d\),所有到\(x\)距离\(>d\)的
  • 2024-01-29洛谷题解-[ABC325E] Our clients, please wait a moment
    https://www.luogu.com.cn/problem/AT_abc325_e题目描述ある国には都市がNNN個あります。あなたは、都市111にある営業所から000個以上の都市を経由して都市NNNにある訪問先へ移動しようとしています。移動手段は社用車と電車の222種類があります。都市
  • 2024-01-27洛谷题解-P1821 [USACO07FEB] Cow Party S
    https://www.luogu.com.cn/problem/P1821题目描述寒假到了,nnn头牛都要去参加一场在编号为xxx的牛的农场举行的派对,农场之间有mmm条有向路,每条路都有一定的长度。每头牛参加完派对后都必须回家,无论是去参加派对还是回家,每头牛都会选择最短路径,求这nnn头牛的最短路径(一个
  • 2023-10-05[ABC257F] Teleporter Setting 题解
    1.题目洛谷传送门2.思路我们可以把不确定的点当成真实存在的\(0\)号点,建边的时候就正常连即可。然后我们来看一个样例:1-2-03-4-5当我们把\(0\)号点看成\(3\)号点时,答案就是\(1\)号点到\(0\)号点的距离加上\(3\)号点到\(5\)号点的距离。然后我们再
  • 2023-06-13「学习笔记」严格次短路
    出题人说:“有最短路,还要有次短路。”于是,就有了次短路这个东西。与次小生成树一样,目前不知道有啥用。本文求的是严格次短路!变量n:点数;m:边数;e:vector存图;dis1:储存最短路;dis2:储存次短路。过程我们要利用dijkstra的贪心思想和松弛操作。dijkstra的贪心思想,就是用目前路
  • 2023-02-07CF14D题解
    CF14DTwoPaths题解题目链接传送门题意简述给定一棵树,找出两条不经过相同点的最长路径,使得他们的长度乘积最大。题目分析首先,如果在一棵树上,两条路径没有共同的点,那
  • 2023-02-042023 二月 做题记录
    2.3P3119首先有显然结论:在一个环上反走一定是不值的,因为环上的点本来就相互可达。缩点后建立正反图跑最短路,设正图最短路数组为\(dis1\),反图最短路数组为\(dis2\),对于
  • 2022-12-14[IOI2011]crocodile
    \([IOI2011]crocodile\)这题没有题解,我就来发一篇。链接:https://www.luogu.com.cn/problem/P5845题目描述:给定出发点\(s\)与\(k\)个终点,有一个鳄鱼门卫可以在每一轮堵
  • 2022-10-251025模拟赛(兔子场)
    1025模拟赛(兔子场)感谢兔子女王&兔子公主不杀之恩。A「AGC008C」TetrominoTiling题意\(~~~~\)七种俄罗斯方块,已知每种的数量,(按照形状记为\(\text{I,O,T,L,J,S,Z
  • 2022-09-04GYM100851 F - Froggy Ford(最短路铜牌题)
    题意:​ 现在有一条河,河中有n个石头,你需要从河的一端到河的另一端。现在你有一次机会在任意位置放置一个石头,请问石头放在哪里可以使过河的最长路径最短。请输出放置的石头