思路： 在a数组中，如果a[i]后面没有比它还大的数，那就直接把这个数输出,否则这个位置输出的数就会比a[i]小，那么字典序就会更小。 用一个数组maxn来记录每个数后面的最大值，从后往前循环，求出a[i]到a[n]的最大值 代码： #include<bits/stdc++.h> using namespace std; const int N=1000010; int a[N],maxn[N]; int main(){ int n; cin>>n; stack<int> s; for(int i=1;i<=n;...

题意： 一个能向左移动1格或两格，向右能移动1格或两格，也能移动0格的人，在水平宽为W，高度为H的区域内，能接到的馅饼的分值最大为多少。馅饼给出了它掉落的初始时刻、水平位置、掉落速度、分值。 思路： 和数塔类似，把饼落到人高度的时间算出来（人占一格高），然后以时间为横坐标，水平位置为纵坐标，创建一个二维数组，先把馅饼落到人身上的时刻的位置赋上这个馅饼的分数，并且找到落到人身上最后的馅饼的时刻，往0时刻计算，dp[0][W/2]就是最后的答案。状态就是dp[i][j]=下一个时刻他能到达的5个位置里的最大值+dp[i][j] 代码： #include<iostream> #inclu...

题意： 你有n种装备，每种装备有两个属性值，你要在这两个属性值里选一个，使得这些属性值是1、2、3、4......这些从1开始连续的数，题目求最多能连续到多少。 思路： 假设这些连在一起的数都在一个连通块里，那么如果这个连通块内有大于n-1条边，连通块内里的数就都能用上，否则就只能用到这个连通块内第二大的数。可以用并查集来维护连通块，也可以用dfs来维护。 代码： dfs #include<iostream> #include<algorithm> #include<cstring> #include<vector> using namespac...

题意： 司机的大炮是前四行，小齐的大炮是后四行，小齐先开炮，然后司机开炮，小齐可以打司机任意一个大炮，但司机只能打小齐打自己的大炮的大炮，问小齐把司机的大炮打完最多能剩几个大炮。 思路： 因为一个大炮被打完后会产生一个 3 * 3 的波及范围，所以可以用一个dfs来搜索这个大炮的周围是否还有大炮，有大炮就继续搜下去，否则就停止,每次如果搜到了大炮，要把 '*' 改成 '.' , 因为已经把这个大炮记录下来了，并且往周围8个方向去搜索了，就相当于这个位置没大炮了。 小齐的最优策略：用连通块块内大炮数量少的去打司机就好了，注意小齐是先手，所以当司机的连通块和小齐的连通块一样多时，小齐还是赢...

题意： 在每个士兵都有一个对团队人数的限制下，选出战斗力最高的一个团队 思路： 根据每个士兵对团队人数限制的大小，从人数多的到少的，枚举一下对每个人的判断，看一下这个人要不要进来，进来后要不要把一些人删掉。如果人数超了，肯定是要把队里战力最小的拿出去，就可以用一个小根堆来维护。这样维护只要每次删除一些人，或者不加一些人进来，删除一些人肯定是比增加一些人方便的，并且一个团队的大小是由最小的团队人数决定的，这样就相当于把所有的团队组成形式列举出来，选出当前团队人数的战力最大值。 代码： #include<iostream> #include<queue> #include&...

题意： 求出最大的可以用矩形覆盖的面积 思路： 这题和[USACO 2009 Mar S]Look Up类似，我们只要找到每个矩形左边第一个比它矮的地方和右边第一个比它矮的地方，然后 这两个距离之差 * 矩形高 就行了，从左往右走，如果遇到一个比之前遇到的最高的矮，那就说明那个最高的矩形的面积最大也只能到这了，算出面积后这个矩形就可以不要了。也就是说存的时候是有个单调性的，从矮到高，而且一次操作只对当前最高的矩形进行处理，就能用个栈来存储。 代码： #include<bits/stdc++.h> using namespace std; const int N=100100; in...

思路： 三分，三分要满足函数是先增后减或者先减后增的，这里可以三分用第一个方案的次数，假设第一个方案用了n次，那么第二个方案的个数就是min( (x-2n)/4 , y-3n )，对于单调性的证明，参考下面的博客。 https://blog.csdn.net/RunningBeef/article/details/113836764?utm_medium=distribute.pc_relevant.none-task-blog-2~default~baidujs_title~default-0.pc_relevant_default&spm=1001.2101.3001.4242....

题意： 求出a[i]后面的数+a[i]与a[i]的位数差的和 思路： 可以整体二分，然后分治。假设这个数组长度为n，把它分成两半，就是[1，mid]和[mid+1,n]，我们可以先求出[1，mid]和[mid+1,n]各自的位数差，然后求出[1，mid]里的数作为a[i]，[mid+1,n]里的数作为a[j]这样一个区间的位数差。 举个例子：数组为4 100 19 20 3999，那么会先分成[4,100,19]和[20,3999],先算出左边位数差，4和100，4和19，100和19，然后右边20和3999，那么还得求4、100、19分别和20、3999的位数差。 判断一个数与另...

二分条件要想清楚，题目是找到l到r里的平方数的个数，其实就是在l到r里找0、1、2、3、4.....到31622这些数的平方，可以找左边界假设是x1，要找到满足x1 * x1>=l的第一个数，然后找右边界假设是x2，要找到满足x2 * x2<=r的最后一个数，那么x1到x2之间的数就是l到r之间所有平方数对应的平方根，平方数的个数=x2-x1+1. 然后说一下我遇到的一个问题： Error on Xcode "No matching function for call to 'max'"，这个问题可能是max函数里的两个参数的类型不一致，我又去查了下不同类型的0，0（int），0L...

这题可以找规律，可以列出前几项看看，其实它是和n的二进制大小有关。 n f(n) n' n的二进制 0 0 0 0 1 1 1 1 2 1 1 10 ​3 2 3 11 ​4 1 1 100 ​5 2 3 101 ​6 2 3 110 ​7 3 7 111 ​8 1 1 1000 用a来表示n的二进制中1的个数，可以看出，f（n）的值与a相等，n'等于2 的a次方-1。 f[0]=0 f[1]=1; f[i]=f[i/2]+f[i%2];(i>=2) 其实这个式子就是不断把二进制的i右移一位，再看一下i是不是奇数（二进制最后一位是不是1...

开一个数组存放iloveyou的各位字符，开一个res[]数组，表示此时连接到这个字母的数有多少个，比如：res[2]=10，那么就表示此时为il的序列有10个。如果遇到了其中字符之一，假设为第j个，那么就把res[j]加上res[j-1]，因为res[j-1]的值是按照iloveyou的顺序排的序列数，并且j的顺序在j-1之后，所以直接加上就行了。最后结果就都存在res[8]中。 用一个例子来模拟： 假设有一个字符串 abcbbccab 过程： a: 1 b：1 a：1 b：2 a:1 b:3 a:2 b:5 ab的总数：5 #include<iostream&g...

思路：差分+离散化，将题目里涉及的点可以离散化为1，2，3，4，5.....这样的数组的下标，在离散化的同时还要记录对这个点的操作，如果是去除一人就在这下标+1，然后再在这个下标位置后m个地方记录-1的点来保证后面的数不受影响. #include<iostream> #include<algorithm> using namespace std; const int N=2000010; int n,m; struct alls{ int x,y; }all[N]; bool cmp(alls a,alls b){ return a.x<b.x; } i...

链接：https://ac.nowcoder.com/acm/problem/16438 来源：牛客网 在日常生活中，通过年、月、日这三个要素可以表示出一个唯一确定的日期。 牛牛习惯用8位数字表示一个日期，其中，前4位代表年份，接下来2位代表月份，最后2位代表日期。显然：一个日期只有一种表示方法，而两个不同的日期的表示方法不会相同。 牛牛认为，一个日期是回文的，当且仅当表示这个日期的8位数字是回文的。现 在，牛牛想知道：在他指定的两个日期之间包含这两个日期本身），有多少个真实存在的日期是回文的。 一个8位数字是回文的，当且仅当对于所有的i （ 1 <=i<= 8 )从左向右数的第...

链接：https://ac.nowcoder.com/acm/problem/16622 来源：牛客网 题目描述 一元n次多项式可用如下的表达式表示： f (x) = anxn+ an-1xn-1 + ... + a1x + a0，a0≠0 其中，aixi 称为i 次项，ai 称为i次项的系数。给出一个一元多项式各项的次数和系数，请按照如下规定的格式要求输出该多项式： 多项式中自变量为x，从左到右按照次数递减顺序给出多项式。 多项式中只包含系数不为0的项。 如果多项式n次项系数为正，则多项式开头不出现“+”号，如果多项式 n 次项系数为负，则多项式以“-”号开头。 对于不是最高...