% Day1 Solution
% Wearry
% Stay determined!
养花
考虑当 确定的时候如何求答案,
显然对于所有形如
进一步观察发现, 这样的区间总个数只有 个.
考虑分块, 那么我们可以在 的时间复杂度内处理出一个块对于任意 的答案.
询问时复杂度是 的, 取 可以达到最优复杂度 .
#include
using namespace std;
const int MAXN = 100000;
const int B = 1000;
int n, m, A[MAXN+5], ans[MAXN/B+5][MAXN+5], b[MAXN+5];
int main ()
{
scanf("%d%d", &n, &m);
for(int i = 0; i b) for(int i = x; i
折射
若将所有点按照
考虑按照 排序转移, 并记录 表示以第 个点为顶端接下来向左或向右的折线方案数.
从左到右加点, 考虑前 个点构成的包含
第二种情况可以前缀和优化, 复杂度 .
#include
using namespace std;
#define file(x) freopen(x".in", "r", stdin);freopen(x".out", "w", stdout);
#define pii pair
namespace IO
{
inline void read(int &num)
{
char ch; int flag = 1;
while(!isdigit(ch=getchar()))if(ch=='-')flag=-flag;
for(num=ch-'0';isdigit(ch=getchar());num=num*10+ch-'0');
num *= flag;
}
}
using namespace IO;
const int MAXN = 100005;
const int mod = 1e9+7;
int n, dp[MAXN][2];
pii p[MAXN];
int main ()
{
read(n);
for(int i = 1; i
画作
不难证明猜到一个这样的结论: 存在一种最优方案使得每次操作的区域是上一次的子集且颜色与上一次相反.
考虑归纳证明, 记 为当前所有操作区域的并,
- 与 有交的情况一定可以转化成 被
-
与 交集为空时, 可以找一个连接 和 的集合 并操作 ,
并将之前的所有操作连接到更外的层以及外层的连接部分同时操作, 特殊处理最外层和第二层的情况. -
被 包含时, 落在某个完整区域内时等价于情况二,
否则一定连接若干个同色块, 这些块可以同时处理, 步数一定不会更劣.
知道这个结论就比较好做了, 我们可以枚举最后被修改的区域,
这时答案就是将同色边边权当作 , 异色边边权当作
#include
using namespace std;
const int MAXN = 55, MAXM = 55;
#define pii pair
#define mp make_pair
#define X first
#define Y second
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
char s[MAXN][MAXM];
int dis[MAXN][MAXM], n, m;
dequeq;
inline bool chkmin(int &A, int B) { return B A ? A = B, 1 : 0; }
int bfs(int u, int v)
{
memset(dis, -1, sizeof dis);
int ret = -1;
dis[u][v] = 0; q.push_back(mp(u, v));
while(!q.empty())
{
pii tp = q.front(); q.pop_front();
if(s[tp.X][tp.Y] == '1') chkmax(ret, dis[tp.X][tp.Y]);
for(int i = 0; i = 1 && (v=tp.Y+dy[i]) >= 1 && u
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.e1idc.net