GuKaifeng's Blog

传送门：POJ 1061 - 青蛙的约会 题目大意：在同一条纬度线上，青蛙 A, B 分别以 $x,y$ 为起点向西跳，A 青蛙每次能跳 $m$ 米，B 青蛙每次能跳 $n$ 米，两个青蛙跳一次时间相同，纬度线总长为 $L$ ，问跳多少次以后两青蛙相遇，如果始终不能相遇输出 “Impossible”。 解题思路：因为都朝西跳，所以如果有可能相遇，那么相遇时两只青蛙总路程 “A 青蛙的跳跃距离加上 A 青蛙起点” 与 “B 青蛙的跳跃距离加上 B 青蛙的起点” 的差值一定是纬度线总长 $L$ 的整数倍数。设相遇时跳跃次数为 $t$，相遇时总路程差值是 $L$ 的 $c$ 倍($c\in Z$，不过这个 $c$ 并不重要)，可得 $(mt+x)-(nt+y)=Lc$，化为我们需要的形式得 $(m-n)t-Lc=y-x$ ($t,c$ 为未知数)，可以看出这个式子是二元一次方程，所以可以使用扩展欧几里得算法求解，然后将 $t$ 化为最小正整数解即可。又因为该算法只能求得整数解，所以如果无解，就说明两个青蛙始终无法相遇。注意题目数据范围较大，数据类型使用 long long。 通过代码：123 ...

今年5月份的时候，准备要去打 CCPC 河北省赛了，在百度的学长知道了以后，就和我们说，拿了省一带我们去百度参观。 比赛还算顺利，虽然成绩不是太好，但好在混了个一等奖，所以就可以去百度参观啦！因为还要准备其他的比赛，所以大家最后决定在 8/27 去北京，也就是 CCPC 网络赛之后两天，订了 27 号一大早的高铁，一伙人就出发啦。 八点多点到了北京，和学长说好了十点多些在百度见，大家本以为时间很充足，两个多小时嘛，然而因为大家都不熟悉路线，一路跟着导航，再加上地铁确实有那么点挤，然后……反正没迟到吧！ 到了百度，真的是第一眼就被震撼到了，太帅了，那么多栋大楼连成一片，在外观上，也是科技感十足。我们到了约定的那个门口以后，并没有见到学长，他在 QQ 上要了我们的一些信息，然后我们几个人便陆续收到了允许以访客身份进入百度的短信和二维码凭证，凭借这个，我们进到了百度的大院子。 院子里很漂亮，有花有草有泉水，如果不是我知道这里是百度，第一眼看上去我会以为这里是个休闲度假的地方，院子四周就是百度的各个大楼了，很壮观。在院子里漫无目的的晃了一会儿（其实是迷路不知道该往哪个方向走=。=），终 ...

传送门：ACM-ICPC 2018 南京赛区网络预赛 G 题 题目大意：有 n 个房间，每个房间里有一定数量的白炽灯泡（数量不同），Lpl 每个月会购买 m 个节能灯泡去替换每个房间原有的白炽灯泡。房间有编号，每次换灯泡从第一个房间开始，如果 Lpl 手里的节能灯泡数量比房间的白炽灯泡数量多，那就把这个房间的灯泡全换了，并且以后不再看这个房间，如果不够，那就整个房间的都不换，往后找其他房间。如果手里的节能灯泡都换完了，就停止换灯泡（下个月还是从第一个房间开始换，不是接着停下的位置换），如果查完所有房间，手里还有剩余节能灯泡没有换，那就把剩下的节能灯泡留着，等下个月新买了灯泡后再换。当所有房间都换完以后，Lpl 就不再买节能灯泡了。问到第 d 个月的时候，有多少个房间已经换完了灯泡，此时 Lpl 手里还剩多少个节能灯泡。 解题思路：考虑直接模拟 Lpl 的换灯泡过程，问题在于查找白炽灯泡数小于等于 Lpl 手里节能灯泡数的房间，暴力查找复杂度过高，我们采用线段树，维护每一小段连续房间的最小灯泡数，这样每次查找只需要 log n 的复杂度，当某个房间换完灯泡以后，把这个房间的灯泡数修改成 ...

传送门：ACM-ICPC 2018 南京赛区网络预赛 E 题 题目大意：有 $n$ 道题目，Dlsj 已经知道了每一道题的答案，可以直接提交并 AC，每道题的提交时间间隔为 1 分钟，提交题目 $i$ 的得分为 $t×a_i+b_i$，($t$ 为提交时间，$a_i, b_i$已知)。想要提交某道题需要已经 AC 了特定的某几个题，否则不可以提交。例如题目告诉你说，提交第 5 题前，必须要先过了第 2 题和第 6 题，那么想要提交第 5 题，就需要第 2 题、第 6 题已经 AC。可以有些题目不做，因为 $a_i, b_i$ 可能是负数，做了反而分数更低，当然如果有题目不做，那么需要这个题已经 AC 才能提交的题目也做不了。问 Dlsj 能达到的最高分是多少。 解题思路：因为 $n$ 最大为 20，一道题只有两个状态（已经 AC 了，或者还没做），所以一共最多有 $2^{20}$ 个状态。对于每个状态，我们可以用一个 int 类型的数（二进制）来表示，右数第 i 位为 1 表示题目 $i$ 已经 AC 了，为 0 表示题目 $i$ 还没做。所以我们需要一个大小为 $2^{ ...

扩展欧几里得是用来在 已知 $a, b$ 求解一组 $x, y$，使它们满足贝祖等式：$ax+by=gcd\left(a,b\right)$（解一定存在，根据数论中的相关定理）。扩展欧几里得常用在求解模线性方程及方程组中。贝祖定理：设 $a,b$ 是不全为零的整数，则存在整数 $x,y$，使得 $ax+by=gcd\left(a,b\right)$。 1234567891011int exgcd(int a, int b, int &x, int &y){ if (b == 0) { x = 1, y = 0; return a; } int q = exgcd(b, a % b, y, x); y -= a / b * x; return q;} 关于最小正整数解的问题，是使 $x,y$ 中某一个为最小正整数即可，求得某一个的最小正整数值后再根据这个值去计算另一个。方程的解 $x$ 具有周期 $\frac{b}{gcd\left(a,b\right)}$, $y$ ...

欧几里得算法又称辗转相除法，是指用于计算两个正整数 $a,b$ 的最大公约数。应用领域有数学和计算机两个方面。计算公式 $gcd(a,b)=gcd(b, a\bmod b)$。基本性质 $gcd(a,b)=gcd(b,a)=gcd(-a,b)=gcd(|a|,|b|)$。代码比较简单，设参数1和参数2分别为 $x,y$，且 $x\geq y$，于是 $x,y$ 的最大公约数就等于 $y,x\%y$ 的最大公约数，若 $x\%y$ 等于0，那么 $y$ 即为两个数的最大公约数。1234int gcd(int a, int b){ return b == 0 ? a : gcd(b, a % b);}