![[jzoj NOIP2018模拟10.29]](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1 "[jzoj NOIP2018模拟10.29]")
OI生涯的最高分，来了纪中这么多天，在经历了这么多场“NOIP难度”的模拟赛之后，终于看到了真正的NOIP
今天考场上效率很高，很快码完了全部的题目，留下了足够的时间对拍和...发呆。不得不说看着电脑页面上看着三个bat心里还是很有成就感的，对拍过的代码自然而然分就高了
没有犯什么小错误，数组越界变量写错什么的都没有，只有T3代码出现了一丝纰漏但也通过对拍查到了错。这告诉我们，对拍是很重要的，与其去追求没有把握的正解不如踏踏实实拿到可以拿的分数
T1：列队
题目链接：
https://jzoj.net/senior/#contest/show/2543/0
题目：
Sylvia是一个热爱学习的女孩子。
在平时的练习中，他总是能考到std以上的成绩，前段时间，他参加了一场练习赛，众所周知，机房是一个 的方阵。这天，他又打爆了std，感到十分无聊，便想要hack机房内同学的程序，他会挑选一整行或一整列的同学进行hack ( 而且每行每列只会hack一次 )，然而有些同学不是那么好惹，如果你hack了他两次，他会私下寻求解决,Sylvia十分害怕，只会hack他们一次。假设Sylvia的水平十分高超，每次hack都能成功，求他最 多能hack多少次？
题解：
发现特殊的同学要么从所在行被hack，要么从所在列被hack
每一行看成一个点，每一列看成一个点
棋盘是一个很显然的二分图模型，把不能共存的行和列连边显然得到的是二分图。那么问题：一共最多取出多少行和列就转化为二分图上最大独立集问题
二分图的最大独立集
定义：选出一些顶点使得这些顶点两两不相邻，则这些点构成的集合称为独立集。找出一个包含顶点数最多的独立集称为最大独立集。
方法：最大独立集=所有顶点数-最小顶点覆盖
跑一遍匈牙利或者网络流就是了
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std; const int N=4e3+;
int n,X,tot;
int match[N],head[N],vis[N];
struct EDGE{
int to,nxt;
}edge[N];
inline int read(){
char ch=getchar();int s=,f=;
while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}
while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=getchar();}
return s*f;
}
void link(int u,int v){
edge[++tot]=(EDGE){v,head[u]};
head[u]=tot;
}
bool dfs(int x)
{
for (int i=head[x];i;i=edge[i].nxt){
int y=edge[i].to;
if (vis[y]) continue;
vis[y]=;
if (!match[y]||dfs(match[y]))
{
match[y]=x;
return ;
}
}
return ;
}
int main()
{
freopen("phalanx.in","r",stdin);
freopen("phalanx.out","w",stdout);
n=read();X=read();
for (int i=,x,y;i<=X;i++)
{
x=read();y=read();
link(x,y);
}
int ans=;
for (int i=;i<=n;i++)
{
memset(vis,,sizeof(vis));
if (dfs(i)) ++ans;
}
printf("%d\n",(*n-ans)*n);
return ;
}
T2:小凯学数学
题目链接：
https://jzoj.net/senior/#contest/show/2543/1
题目：
由于小凯上次在找零问题上的疑惑，给大家在考场上带来了很大的麻烦，他决心好好学习数学
本次他挑选了位运算专题进行研究 他发明了一种叫做“小凯运算”的运算符：
a$b =( (a&b) + (a|b) )>>1
他为了练习，写了n个数在黑板上(记为a[i]) 并对任意相邻两个数进行“小凯运算”，把两数擦去，把结果留下 这样操作n-1次之后就只剩了1个数，求这个数可能是什么？
将答案从小到大顺序输出
0<=a[i]<=7
题解：
发现a数组无论如何运算结果都是在$[0,7]$这个区间里的
于是我们定义$dp_{l,r}$表示区间$[l,r]$可以合并成的数，考虑到取值范围很小，我们可以用二进制状压起来
发现暴力转移的时间复杂度是$O(64n^3)$的，考场上笔者认为跑不过去
其实可以预处理从两个二进制数合并得到的新的二进制数，这样优化到了$O(n^3)$
大水
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std; const int N=+;
const int M=<<;
int n;
int a[N],dp[N][N],tmp[M][M];
int merge(int x,int y)
{
int re=;
for (int i=;i<=;i++)
if (x&(<<i))
{
for (int j=;j<=;j++)
if (y&(<<j))
{
int p=(i+j)/;
re|=<<p;
}
}
return re;
}
void init()
{
for (int i=;i<M;i++)
for (int j=;j<M;j++)
tmp[i][j]=merge(i,j);
}
int main()
{
freopen("math.in","r",stdin);
freopen("math.out","w",stdout);
init();
scanf("%d",&n);
for (int i=;i<=n;i++) scanf("%d",a+i),dp[i][i]=<<a[i];
for (int len=;len<=n;len++)
{
for (int l=;l<=n;l++)
{
int r=l+len-;
if (r>n) continue;
for (int k=l;k<r;k++)
{
dp[l][r]|=tmp[dp[l][k]][dp[k+][r]];
}
}
}
for (int i=;i<=;i++) if (dp[][n]&(<<i)) printf("%d ",i);
return ;
}
T3：逛公园
题目链接：
https://jzoj.net/senior/#contest/show/2543/2
题目：
![[jzoj NOIP2018模拟10.29]](https://image.shishitao.com:8440/aHR0cHM6Ly9pbWcyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTQxODM2My8yMDE4MTAvMTQxODM2My0yMDE4MTAyOTE5NDUyNzkzOS0xMjU0OTkyNDIwLnBuZw%3D%3D.png?w=700&webp=1 "[jzoj NOIP2018模拟10.29]")
q次询问，每次给出l,r，要求输出答案
题解：
考虑$O(qn)$怎么做？（这种复杂度在考场上得到了完美的85分）。暴力从 l 循环到 r，每次的起始值都是逛完上个景点的最大值和X0的最大值这样对于每个询问都能 O(n)得出答案
以下内容大部分来自题解
记 $F(i,j,x_0)$表示以初始代价 $x_0$ 依次经过第 $i$ 景点到第 $j$ 景点后的答案 有两个性质：
1.对于 $a>=b，F(i,j,a)>=F(i,j,b)$
2.记 $G(i,j)$为 $F(i,j,inf)$，其中 $inf $是正无穷，$S(i,j)$为 $i$ 到 $j$ 的 $D$ 值之和。 则有 $F(i,j,x0)=min( G(i,j), x0+S(i,j) )$。（$G(i,j)$就是一定会在$l$处被卡。这个性质没有严谨的证明，感性理解一下）
推论：对于询问的 $l,r$，如果两个子串都被包含在$[l,r]$中，且有 $G1>=G2 且 S1>=S2$，显然第二个子串是一定不会取到的（由性质二得到）。
那么考虑对于一段区间我们怎么做？首先我们把所有的子区间取出来，按$G$值从小到大排序，维护单调栈去掉一定不会取到的子区间，那么剩下的显然就是$G$值单调递增，$S$值单调递减一个个子区间。由于我们是取min，可以在这段区间上二分（当然三分大概也可以，但好像有点傻），找到那个$G$和$S+x0$最接近的区间就是目标区间
发现这样的复杂度还不如之前的做法，但是我们可以分块
块内的贡献：每块大小$\sqrt{n}$，子串个数就是 $O(n)$个可以把每个子串 的 $G$ 值和 $S$ 值都求出来，根据推论把没用的都扔掉。每次询问给出 $X_0$，最大的点一定中间某处（答案是 min 函数），二分即可得出块内的答案
块间的贡献：一共有 2 种
1. 从当前块开始到后面的某一块结束
2. 从之前的某一块开始到当前块结束
参照暴力的策略，那么我们就可以维护一个 $Y$ 值代表上一个块给 这一个块带来的贡献，同时再维护前缀以及后缀的 $G、S$ 值
利用前缀和 $Y$ 值，我们可以采用和之前块内一样的二分来算出答案
利用后缀我们可以算出这一块给下一块的 $Y$ 值,也有三种情况：
1 从上个 $Y$ 走满整块到下个 $Y$
2 从某个后缀开始
3 直接取 $X_0$
三者的最大值即为 $Y$
对于每次询问，我们散块暴力，整块二分再连接就好了
时间复杂度应该是$O(n\sqrt{n}logn+q\sqrt{n}logn)$
好像只是比暴力好那么一点
我的代码跑的好慢
#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<cmath>
using namespace std; const int N=5e4+;
const int M=+;
const int inf=1e9;
int n,q,blo,tcnt,tp;
int d[N],li[N],belong[N],st[N],ed[N],sumd[N];
int F[M][M][M];
struct node{
int G,S;
}T[N],sta[N];
bool operator < (node a,node b) {return a.G<b.G||(a.G==b.G&&a.S<b.S);}
vector <node> vec[M],pre[M],suf[M];
inline int read(){
char ch=getchar();int s=,f=;
while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}
while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=getchar();}
return s*f;
}
int G(int l,int r)
{
return F[belong[l]][l-st[belong[l]]][r-st[belong[l]]];
}
int S(int l,int r)
{
return sumd[r]-sumd[l-];
}
void calc(vector <node> &V)
{
//printf("%d\n",T[tcnt].S);
sort(T+,T++tcnt);
tp=;
sta[++tp]=T[];
for (int i=;i<=tcnt;i++)
{
while (tp&&T[i].G>=sta[tp].G&&T[i].S>=sta[tp].S) tp--;
sta[++tp]=T[i];
}
for (int i=;i<=tp;i++) V.push_back(sta[i]);
}
void init(int id)
{
for (int l=st[id];l<=ed[id];l++)
{
int x0=inf;
for (int r=l;r<=ed[id];r++)
{
x0=min(li[r],d[r]+x0);
F[id][l-st[id]][r-st[id]]=x0;
}
}
tcnt=;
for (int l=st[id];l<=ed[id];l++)
for (int r=l;r<=ed[id];r++)
{
T[++tcnt]=(node){G(l,r),S(l,r)};
}
calc(vec[id]);
tcnt=;
for (int r=st[id];r<=ed[id];r++)
{
T[++tcnt]=(node){G(st[id],r),S(st[id],r)};
}
calc(pre[id]);
tcnt=;
for (int l=st[id];l<=ed[id];l++)
{
T[++tcnt]=(node){G(l,ed[id]),S(l,ed[id])};
}
calc(suf[id]);
}
int ef(vector <node> Vec,int x0)
{
int l=,r=Vec.size()-;
while (l+<r)
{
int mid=l+r>>;
if (Vec[mid].G>Vec[mid].S+x0) r=mid;
else l=mid;
}
int re=min(Vec[l].G,Vec[l].S+x0);
re=max(re,min(Vec[r].G,Vec[r].S+x0));
if (l+<Vec.size()-)
{
++l;
re=max(re,min(Vec[l].G,Vec[l].S+x0));
}
return re;
}
void solve(int l,int r,int x0)
{
if (belong[l]==belong[r])
{
int mx=x0,Y=x0;
for (int i=l;i<=r;i++)
{
Y=min(max(Y,x0)+d[i],li[i]);
mx=max(mx,Y);
}
printf("%d\n",mx);
return;
}
int Y=x0,mx=x0;
for (int i=l;i<=ed[belong[l]];i++)
{
Y=min(max(Y,x0)+d[i],li[i]);
mx=max(mx,Y);
}
Y=max(Y,x0);
for (int i=belong[l]+;i<=belong[r]-;i++)
{
mx=max(mx,ef(pre[i],Y));
mx=max(mx,ef(vec[i],x0));
Y=min(G(st[i],ed[i]),Y+S(st[i],ed[i]));//从上个Y走满整块到下个Y
Y=max(Y,ef(suf[i],x0));//从某个后缀开始
Y=max(Y,x0);//直接取X0
}
for (int i=st[belong[r]];i<=r;i++)
{
Y=min(max(Y,x0)+d[i],li[i]);
mx=max(mx,Y);
}
printf("%d\n",mx);
}
int main()
{
freopen("park.in","r",stdin);
freopen("park.out","w",stdout);
n=read();q=read();
for (int i=;i<=n;i++) d[i]=read(),sumd[i]=sumd[i-]+d[i];
for (int i=;i<=n;i++) li[i]=read();
blo=sqrt(n);
for (int i=;i<=n;i++) belong[i]=(i-)/blo+;
for (int i=;i<=belong[n];i++)
{
st[i]=(i-)*blo+;
ed[i]=min(i*blo,n);
init(i);
}
while (q--)
{
int l=read(),r=read(),x0=read();
solve(l,r,x0);
}
return ;
}