水原_

分类

ACM(13) 题解(28)

/ 注册

全部文章（共41篇）

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

单调队列

求每个固定长度区间最值顾名思义,单调队列即是一个单调的队列. 这里只考虑求区间最小值. 建立一个单调递增的队列,队首是最小值. 开始队列为空,每次添元素的时候,从队尾向前比较, 直到找到最靠前的比自己小的数,将待添加元素添加到这个数后面, 舍弃后面的所以数.(这是因为新添加的数一定比后面的数更优)...

2020-01-02

0 601

最长上升子序列

算法: 记为以结尾的最长上升子序列长度, 对于每个更新 for(int i=1;i<=n;i++)f[i]=1; for(int j=2;j<=n;j++) for(int i=1;i<j;i++) if(a[i]<a[j]) f[j...

2020-01-02

0 587

P1080 国王游戏

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

2020-01-02

0 472

全排列的最长公共子序列

最长公共子序列 #include<iostream> #define maxn 100010 using namespace std; int A[maxn],B[maxn],C[maxn],f[maxn],f1[2333][2333]; int main(){ 将A序列一一映...

2020-01-02

0 544

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