水原_

题解

ACM(13)

/ 注册

全部文章 / 题解（共28篇）

P1805 关灯

f[n] =0,n=0 else =f[n-1],s[n]=0 else =2^n-1,s[i]=0,1<=i<=n-1 else =f[k-1]+2^n-2^k,k为1到n-1中最后一个一位数 #include<iostream> #include<cstring&g...

2020-01-02

0 694

P1590 失踪的7

本题的解法实在神奇。 7不存在，那么可能的数位就有： 1,2,3,4,5,6,8,9,0 九种情况。那么就可以看作是0-8，也就是九进制数。然后将输入的数看作九进制数转成十进制就好了。 #include<iostream> #define ll long long int #defi...

2020-01-02

0 585

P3937 Changing

对于出题人大大的证法表示太高深。这里用高考范围内的知识给出更为简洁，严谨的证明。为了方便起见，一下中的按理解。首先，我们要证的命题是若对于任意的正整数及任意的自然数，有，则对任意的自然数， . 现对用数学归纳法证明命题。当时，显然. 假设时命题成立，即对任意的自然数, 有. 则当时，对...

2020-01-02

0 1191

P1080 国王游戏

对于本题而言,记为前面的人的左手乘积, 比优等价于: 等价于可以推出故按照排序即可.

2020-01-02

0 472

P4889 kls与flag

看了题解发现自己想的十分复杂。现在来说一下不一样的方法。题目要求放倒后可以重合的竹竿的对数，自然会想到去研究：两个什么样的竹竿可以重合。设第个竹竿是的高度为，那么对于任意的，它们倒地重合有三种情况：一起倒在中间:，这等价于。一起倒在左边:，这等价于。一起倒在左边:，这等价于。...

2020-01-02

0 496

P1340 兽径管理

首先依次加边，直到整个图联通为止，之前均输出，图刚连通时跑一遍正常的克鲁斯卡尔。然后将用到的边存起来（只有条），之后每加一条边，就对将这条边排序，再跑就可以了。复杂度（快排）（插入排序） #include<algorithm> #include<iostream>...

2020-01-02

0 517

P1070 道路游戏

观察下题目的状态，可设计出一个较为直接的方程。对于，代表当前时间，代表机器人即将走第几步，表示从第几个工厂出发。则有: 时，时, （一开始写的时候把时的方程写错了，丑）边界就是然后空间是不够的，易见第一维可以滚掉。然后优化下就可以卡过此题。 #include<iostream&...

2020-01-02

0 672

P2577 [ZJOI2005]午餐

首先可以数学地证明：可对所有人按吃饭时间从大到小排序然后会想到表示前个人,一队用时间打饭，另一队用时间打饭的最小用时。思想就是知道，就可以保证没有后效性。但数组开不下，这时发现,便可以去掉以为一维。还有要注意的就是初始化的问题了。 #include<algorithm> #inc...

2020-01-02

0 444

P2629 好消息，坏消息

主思想就是对每个，判断是否可行。 (1): 对于每个，首先判断是否满足。考虑到可以递推，将从到循环，用表示的最小值（）则易得那么得到了，只需判断是否不小于即可。 (2): 后半部分对于的判断则更加简单。预处理，其中那么只要判断是否不小于即可。总复杂度 #include<i...

2020-01-02

0 508

P3916 图的遍历

基本的想法就是对于每个点来一次bfs，求出它所能到达的点中最大的。这样是。对于某个点，如果点能到达它，那么比小的点都不必再搜。于是可以想到一个优化：反向建边，点能到达点即代表点能到达点。基于上面的想法，只要从大往小搜，已经访问过的点不搜，即可保证答案的合法性。（这是因为若之前访问过了，那么以...

2020-01-02

0 531