WORIA

https://acm.ecnu.edu.cn/contest/361/ E. 护花行动   题意：给定一个矩阵网格，有一些格子是黑色的，其余是白色的，多次询问，问有几个 x×yx\times yx×y 的子矩形。 单调栈+前缀和 对于每个格子预处理出能向左延伸的最远距离。 对于每一列单独处理。处理一列时，维护一个严格递增的单调栈，遍历每一行，当比单调栈顶短时，说明出现了极大的矩形，因为这个栈是严格递增的，所以长度等于当前长度与栈次顶长度的最大值+1，宽度等于当前行与栈次顶行之间的行数。 假设下图阴影部分是找出的一个极大子矩形。则其中包含了多个右边界与该极大子矩形相同的子矩形。 因此需要前缀和处理，可以发现上图有一个从行数为 4 到行数为 1 的递减的等差数列，这可以通过对行做两次前缀和得到。 又由于上图这些框出来的子矩形把左边界向右靠时对每一个左边界又有会有个数相同的子矩形，所以还要对列做一次前缀和。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950 ...

http://acm.csu.edu.cn/csuoj/problemset/problem?pid=2318 题意：给定一个有向图，边数 m≤200000m\leq 200000m≤200000，每条边有 RGBRGBRGB 之一的颜色，要求不能路径上有连续大于 424242 条边同色，给出一种方案。 把所有边按拓扑序分为 424242 个大组，组间连边为 RRR，每个大组内部再分 424242 个小组，小组间连边为 GGG，小组内部连边为 BBB。 本题利用了边数小于 42342^3423 的特点，分成 424242 组就一定不会有连续同色数大于 424242 的情况。 dfs相邻边不同色是不对的，虽然在csu的OJ上能过，但在EOJ上会WA。 12345678910111213141516171819202122232425262728293031323334353637383940414243#include <bits/stdc++.h>using namespace std;#define ll long longtypedef pair<int, int ...

默认的cb调试器是MinGW，gdb32. 在codeblocks安装目录的**MinGW/bin/**下新建一个文本文件，输入以下： 123456pythonimport syssys.path.insert(0,'D:\codeblocks\MinGW\share\gcc-5.1.0\python\libstdcxx\v6')from printers import register_libstdcxx_printersregister_libstdcxx_printers (None)end 改名为 pp.gdb 打开codeblocks，setting --> debugger settings --> default 修改可执行路径为D:\codeblocks\MinGW\bin\gdb32.exe 初始化命令（那个最大的框）中填入D:\codeblocks\MinGW\bin\pp.gdb 方框下第一个选项禁用，把 ‘√’ 取消掉。 注意根据实际安装目录改代码

差分与前缀和 这两个常常一起用，所以记在一起。 差分： 设原数组为a[i]. 维护一个数组A[i],使得A[i]=a[i]-a[i-1]; 前缀和中**a[i]=A[i]-A[i-1],**恰好相反。 差分突出的是每个元素个体间的差异，而前缀和突出整体的融合。 先来看具体应用： 当对一个区间**[L,R]**内的每一元素都进行+k操作时，若直接暴力常TLE，这时就能用差分。 对一个区间[L,R]内的每一元素都进行+k操作相当于==arr[L]比arr[L-1]大k，arr[R]比arr[R+1]大k==， 所以只需对区间两端操作, arr[L]+=k;arr[R+1]-=k; 来分析一下： arr[i]相当于A[i]，且本题中原数组抽象，初始时，arr[i]=0, 表明所有元素无差别，所有i有a[i]-a[i-1]=0. 当对某一区间[L,R], 操作时，a[L]-a[L-1]=k,a[R+1]-a[R]=-k. 而对其他的i，a[i]-a[i-1]不变，仍为0. 就相当于产生了一种向上凸出的形状。 接着i从L到R，arr[i]=arr[i]+arr[i-1]，可以理解为把k的差距从首 ...

http://codeforces.com/contest/1508 A. Binary Literature   题意：给定三个 2n 长度的01串，要求构造一个长度不超过 3n 的01串，是的给定的三个串中至少有两个是构造出的串的子序列。 构造 假设有两个串都满足：0的个数大于等于1的个数，那么0的个数一定大于等于n。则先选其中一个一个串，再把另一个串插入其中，必定满足需要插入的次数小于等于n。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859#include <bits/stdc++.h>#define debug(x) cout << #x << ":\t" << (x) << endl;using namespace std;#define ll long long#define ull unsigned llconst int ...

https://codeforces.com/contest/1503 C. Travelling Salesman Problem   题意：有 nnn ，2≤n≤1052\le n\le 10^52≤n≤105 座城市，有魅力值 aia_iai​，最低票价 cic_ici​，现在从 1 号城市出发，经过每个城市恰一次，最终回到 1 号城市，从 iii 到 jjj 的代价等于 max⁡(ci,aj−ai)\max(c_i,a_j-a_i)max(ci​,aj​−ai​)，0≤ai,ci≤1090\le a_i,c_i\le 10^90≤ai​,ci​≤109。问最少总代价。 思维+贪心 首先要发现路径是个环，所以从哪个城市出发都是一样的，无非就是环从哪里断开。 要经过所有城市恰一次，那么 ∑ci\sum c_i∑ci​ 是至少的。因此先把 ∑ci\sum c_i∑ci​ 加到答案里，这样从 iii 到 jjj 的代价就变成了 max⁡(0,aj−ai−ci)\max(0,a_j-a_i-c_i)max(0,aj​−ai​−ci​)。 再发现如果 aj<aia_j<a_ia ...

http://codeforces.com/contest/1498 D. Bananas in a Microwave   题意：你有一个数 kkk，初始为 000，给定 nnn 轮操作，每轮操作给定 t,x,yt,x,yt,x,y，若 t=1t=1t=1，则可以向你手中的数进行不超过 yyy 次 k:=⌈(k+xi)⌉k:=\lceil (k + x_i) \rceilk:=⌈(k+xi​)⌉；若 t=2t=2t=2，则可以向你手中的数进行不超过 yyy 次 k:=⌈(k⋅xi)⌉k:=\lceil (k \cdot x_i) \rceilk:=⌈(k⋅xi​)⌉。给定 mmm，问对于 1≤i≤m1\le i\le m1≤i≤m，最少几轮操作后可以得到 iii。 滑动窗口+dp dp[i][j]=0/1dp[i][j]=0/1dp[i][j]=0/1 表示第 iii 轮，不能/能 凑出 jjj。 第一种操作比较简单，由于每次加完后都要上取整，所以相当于先把 xix_ixi​ 上取整，之后就直接 $k:=k + x_i $。 则有 dp[i][j]=∣k=j−p∗x∧p≤ydp[i] ...

http://codeforces.com/contest/1483 C. Skyline Photo   题意：给定 nnn 栋楼，每栋有高度 hih_ihi​ 且互不相同，还有魅力值 aia_iai​，要求分割成几块，每块的魅力值等于该块内最矮的楼的魅力值。要求最大化魅力值之和。 dp+线段树+单调栈 dp[i]dp[i]dp[i] 表示前 iii 栋楼魅力值之和最大值。 枚举 iii 所在块长度，则转移显然 dp[i]=max⁡j=1i(dp[j−1]+a[k])dp[i]=\max\limits_{j=1}^{i}(dp[j-1]+a[k])dp[i]=j=1maxi​(dp[j−1]+a[k])，其中 kkk 为 [j⋯i][j\cdots i][j⋯i] 的中最矮的楼。 那么可以发现对于一些 jjj，他们对应的 kkk 可能是相同的，这样就可以放在一起求最大值。 维护递增的单调栈，则满足 stack[top]stack[top]stack[top] 是 [stack[top]⋯i][stack[top]\cdots i][stack[top]⋯i] 中最矮的。 线段树维护 ...

http://codeforces.com/contest/1500 A. Going Home   题意：给定一个数列 aaa，求四个不同的位置 x,y,z,wx, y, z, wx,y,z,w 满足 ax+ay=az+awa_x + a_y = a_z + a_wax​+ay​=az​+aw​。(1≤ai≤2.5⋅106)(1 \leq a_i \leq 2.5 \cdot 10^6)(1≤ai​≤2.5⋅106) 暴力枚举+复杂度计算 如果是普通题目，复杂度至少是 O(n2)O(n^2)O(n2)，肯定不行。 但是发现这个数列元素很小，两个元素的和最多只有 5×1065\times 10^65×106。 直接暴力枚举 ai,aja_i,a_jai​,aj​，如果之前出现过 (x,y)(x,y)(x,y) 满足 ax+ay=ai+aja_x+a_y=a_i+a_jax​+ay​=ai​+aj​，则得到答案。 注意到 ai+aj≤5×106a_i+a_j\le 5\times 10^6ai​+aj​≤5×106，则由鸽笼原理得到在最多 5×1065\times 10^65×106 次 ...

https://codeforces.com/contest/1495 B. Let’s Go Hiking   题意：给定一个 n 的排列，两个人轮流操作：第一次时先选一个初始位置放棋子，之后先手可以移动到两边一个比当前位置权值小的位置，后手可以移动到两边一个比当前位置权值大的位置。问先手有几个初始位置可以必胜。 博弈 思路比较直接，但是细节有点多，要考虑全面。 枚举每个位置作为先手的初始位置，分类讨论。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include <bits/stdc++.h>#define debug(x) cout << #x << ":\t" << (x) << endl;using namespace std;#define ll long long#define ull unsigned llconst int N = 5e6 + 10;c ...