WORIA

  二分+贪心 二分确定最终每个人分到的最大值。 注意二分时的下限要设置为一本书的最大页数，否则这本书永远无法分配，则问题无解。 接着从后往前分配页数，由于贪心地使后面大，所以前面有可能分到0，所以，还需要从后往前使没分到的人从分到的人处拿出一张。 输出格式可能有点坑。WA了很多发。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788#include<bits/stdc++.h>using namespace std;typedef pair<int, int> pii;#define ll long longconst int INF = 0x3f3f3f3f;const int maxn = 1e5 + 5;ll t, m, k;ll a[505];bool check(ll ...

  考虑最后赢的情况，一定是1和某一个它能打败的队。因此，如果始终保持原始的条件，即1能打败至少一半的队伍，且不能直接打败的队伍都能被间接打败，那么直到最后决赛，2支队伍中必定有一个是1能打败的。则1获得冠军。 构造题 对于所有1不能打败的队伍，将他们尽可能地与1能打败的队伍配对。因为题目条件，所以最终被配对的能被1打败的队伍一定可以打败所有的不能被1打败的队伍。将选中的能被1打败的队伍留到下一轮，则可以确保不能被1打败的队伍始终可以被间接打败。 给1随便分配一个未被配对的能被1打败的队伍。 剩下的不能被1打败的队伍内部打，如果多出来1个，则混入能被1打败的队伍中。 剩下的能被1打败的队伍，可能还有混进来的那个队，内部打。 剩下来的队伍晋级下一轮。 本题的关键在于： 能看出始终保持原始条件则1能夺冠。 先将两种队伍配对，以确保不能被1打败的队伍始终被间接打败。 让不能被1打败的队伍内斗，以最安全的方式确保其数量少于总数一半。 1234567891011121314151617181920212223242526272829303132333435363738394041424 ...

  分治 找到第一个唯一的字符。再递归找它左边和右边的部分。 找到一个唯一的字符，则说明只要包含该字符的子串一定是non-boring的，则只需要再验证其左边和右边的子串。 再来考虑从哪里开始找这唯一的子串，如果从头开始找，则最坏的复杂度为O(n2)O(n^2)O(n2) ，必然不行。所以考虑从两边往中间找，或者从中间往两边找。则复杂度为O(nlog⁡n)O(n\log n)O(nlogn)。 不过有个问题，我从中间往两边找还是超时了，改成两边往中间找AC。是因为数据问题吗？复杂度应该是一样的啊。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include<bits/stdc++.h>using namespace std;#define ll long longconst int maxn = 2e5 + 10;const int INF = 0x3f3f3f3f;int t, n;int a[maxn], p1[maxn], p2 ...

  本题需要看出最终总能将输入个数减为1个。 由于输入只是x，所以这个电路的功能只有4种情况。 常数0 常数1 x反 x 先验证前两种，x分别取0和1，若输出都为0，则为第一种；若输出都为1，则为第二种。如果是这两种的一个，则输入全为0或全为1即可。 若两种都不是，则先将所有输入x都设为0，从第1个开始改成1，注意改完之后不要再改回来。当改到某一个x为1时，输出变了。则说明该位置可以控制整个电路的输出，则把该位置设为x，其它已经改为1的就还是1，没改的就还是0. 这么做是正确的，因为最终整个电路总会随着设为x的那个位置变化而变化，且电路功能不会改变。因为改到x位置之前一位时，电路输出与全为0时输出相同，就是说x位置为0时与所有输入为0时输出相同，而x为1时与所有输入为1时输出相同。 当然，直接找的话会超时。所以二分。 本题二分是可行的。因为当所有输入为1时，答案一定与所有输入为0时不同。所以我们要找的两种答案的分界点一定是存在的。即使随着1的个数过多，输出可能又会变成输入为0时结果，但它与输入全为1时之间一定还有一个分界点，可能这个分界点不是1的个数最小的情况。但由于题中未要求1 ...

  给定一个数组，要从中删除一段连续的子数组，使得新的数组的连续递增子序列最长。 要删除一个连续区间，则考虑区间端点，设左端点为j，右端点为i，且新的数组最长连续递增子序列包含i，j。 则新数组的连续递增子序列为 pre[j]+suf[i]pre[j]+suf[i]pre[j]+suf[i]，其中 pre[j]pre[j]pre[j] 表示以 jjj 为右端点的最长连续递增子序列长度，suf[i]suf[i]suf[i] 表示以 iii 为左端点的最长连续递增子序列长度。这两者都可以 O(n)O(n)O(n) 地预处理出来。 接下来问题就转化为求一对 (i,j)(i,j)(i,j)，使得 pre[j]+suf[i]pre[j]+suf[i]pre[j]+suf[i] 最大。 枚举 iii，对每一个i，存它之前的所有j，并且每次用最长的 pre[j]pre[j]pre[j]。 考虑用set维护最长的 pre[j]pre[j]pre[j]。以a[i]为关键字。当存入一个pre[i]时，比较它与已经在set中的，前一个节点的pre值大于pre[i]，则没有必要把pre[i]存入set，否则 ...

  给定一串01序列，寻找某一段区间中1的个数与区间长度的比值最大，且区间长度大于等于L。 首先，求区间内1的个数肯定用前缀和处理。 问题转换为有一个离散的函数f(x)f(x)f(x) ，求函数中间隔大于等于L的任意两点的最大斜率。 画出图来观察，发现当有三个点组成了上凸时，凸点与这三点右边的任意点的斜率一定小于等于那两个非凸点。所以每次循环中在求斜率之前，先把集合中整理一遍，把所有凸点都删除。 用数组模拟双端队列，每次新加入一个点之前，先把队列中的凸点都去掉，使得队列中的相邻两点斜率是递增的，形成单调队列。每次都会检查上一次新加入的点，若上一次加入的点与它左端的点斜率小于等于1，则把它删掉，否则这一轮再加入点后，上一次加入的点就会成为凸点。 每次都确保在非凸点中寻找答案。由于从左到右斜率会先变大后变小，所以当斜率停止变小，即当当前点右边的点与目标点的斜率大于等于当前点与目标点的斜率时，停止搜索。 因为只有当总的点数大于等于3时，才会有凸点，所以在新加点之前应确保已有点数大于等于2。 由于每次要求答案斜率更大，所以每次搜索的左端点一定是非递减的，否则斜率一定会小于等于当前答案。这就限 ...

  递归+前缀和 直接按照上下限递归的话解答树规模可能达到 2k2^k2k。 所以考虑 cal(k,i)cal(k,i)cal(k,i) 表示第 kkk 个小时前 iii 行的红气球个数。这样答案可以表示为 cal(k,b)−cal(k,a−1)cal(k,b)-cal(k,a-1)cal(k,b)−cal(k,a−1) ，分两类：i≤2k−1i\leq 2^{k-1}i≤2k−1 和 i>2k−1i>2^{k-1}i>2k−1，第二种情况可以预处理出满的时候气球数。 12345678910111213141516171819202122232425262728293031323334353637383940#include<bits/stdc++.h>using namespace std;typedef pair<int, int> pii;#define ll long longconst int INF = 0x3f3f3f3f;const int maxn = 1e5 + 5;int T, k, a, b;ll p[35];ll p ...

  滑动窗口 最多只有s种情况，分别对应s种窗口。事先检查总共n个长度为s或者最后几个不完整的窗口分别是否只包含不重复元素。再枚举s种情况，如果对应窗口都正确，则答案+1. 检查是否只包含不重复元素，和Unique Snow题中类似，用到了滑动窗口。 本题就是在处理两端不完整窗口时需要小心。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980#include<bits/stdc++.h>using namespace std;#define ll long longconst int maxn = 1e6 + 10;const int INF = 0x3f3f3f3f;int t, n, m;int a[maxn], pl[maxn], pr[maxn];map<int, int>mpl, mpr;bool ok ...

  给定一个数组，求数组中最长连续无重复元素的区间的长度。 滑动窗口。 先预处理处每个位置与该位置上数字相等的在该位置左边的最近的下标。 L和R从0开始，若R+1所在位置上数字最近的重复元素不在当前区间内，则R++，否则L跳到该重复元素所在位置+1，R++。 123456789101112131415161718192021222324252627282930313233343536373839404142#include<bits/stdc++.h>using namespace std;#define ll long longconst int maxn = 1e6 + 10;int t, n;int a[maxn];map<int, int>mp;int pos[maxn];int main() { scanf("%d", &t); while (t--) { mp.clear(); scanf("%d", &n); for (int i = 0; i < n; i+ ...

  题意：给出一张有向图，每次可以任选一个点和一个整数d，把以它为起点的边权值+d，以它为终点的边权值-d，最终要让所有边权值为正，且边权最小值最大。 最小值最大自然二分。 问题在于如何判断边权最小值为mid的情况是否可行。 差分约束 设点 i 被操作的值的总和 sum[i] 次，点 j 被操作的值总和为 sum[j] ，则边 i->j 的边权为原始边权 w[i][j]+sum[i]−sum[j]≤midw[i] [j] + sum[i] - sum[j]\leq midw[i][j]+sum[i]−sum[j]≤mid，，对每一条边得到一个不等式，转化为 sum[i]−sum[j]≤mid−w[i][j]sum[i]-sum[j]\leq mid-w[i] [j]sum[i]−sum[j]≤mid−w[i][j]。 这样的方程组就是差分约束问题，可以看到把sum[i]看作有向图上i到源点的距离d[i]，问题就类似于在有向图上连一条j到i，权值为 mid−w[i][j]mid-w[i] [j]mid−w[i][j] 的边，再把从新建一个超级源点向每个点连权值为0的边，再用Bel ...