NOI2017 简要题解
command_block
2021-06-16 08:10:32
$$\large\text{Current Score : 400}$$
# D1T1 [整数](https://www.luogu.com.cn/problem/P3822)
**题意** : 维护一个高精度二进制数 $S$，初始时为 $0$。
有下列 $n$ 个操作 ：
- 将 $S$ 加上 $a\times 2^b$ ，其中 $|a|\leq 10^9,b\leq 30n$
- 询问 $S$ 的某个 `bit`
$n\leq 10^6$。
------------
计算加法时，会产生进位。若只有加法，进位的复杂度是均摊正确的。
暴力逐位处理加法，复杂度为 $O(nw)$。
我们考虑维护两个数 $S_1,S_2$ 且 $S=S_1-S_2$ ，对于减法，我们将其加到 $S_2$ 上。
接下来考虑查询。需要判断 $O(1)$ 次减法是否借位，即比较 $S_1,S_2$ 的某个后缀的大小。
将 $S_1,S_2$ 分块，块大小为 $O(w)$ ，用 `set` 维护不同的块，复杂度为 $O(n\log n)$。
查询时先找到第一个不同的块，然后块内枚举，复杂度为 $O(nw)$。
```cpp
#include<algorithm>
#include<cstdio>
#include<bitset>
#include<set>
#define MaxN 30005000
using namespace std;
int n,o[MaxN>>5];
bitset<MaxN> a,b;
set<int> s;
void insert(int x)
{x>>=5;if (!o[x]++)s.insert(x);}
void erase(int x)
{x>>=5;if (!--o[x])s.erase(x);}
int qry(int x)
{
if (x<0)return 0;
int bl=x>>5<<5;
for (int i=x;i>=bl;i--)
if (a[i]^b[i])return b[i]>a[i];
int bp=*(--s.lower_bound(x>>5));
if (bp==-1)return 0;
bl=bp<<5;int br=bl+31;
for (int i=br;i>=bl;i--)
if (a[i]^b[i])return b[i]>a[i];
return 0;
}
void add(int x,int t)
{
bool fl=(x>0);if (x<0)x=-x;
for (int i=t;i<=n*30&&x;i++,x>>=1)
if (x&1){
if (fl){x+=a[i];a.flip(i);}
else {x+=b[i];b.flip(i);}
if (a[i]^b[i])insert(i);else erase(i);
}
}
int main()
{
scanf("%d%*d%*d%*d",&n);
s.insert(-1);
for (int i=1,op,x,y;i<=n;i++){
scanf("%d%d",&op,&x);
if (op==1){scanf("%d",&y);add(x,y);}
else printf("%d\n",a[x]^b[x]^qry(x-1));
}return 0;
}
```
------------
# D1T2 [蚯蚓排队](https://www.luogu.com.cn/problem/P3823)
------------
# D1T3 [泳池](https://www.luogu.com.cn/problem/P3824)
**题意** : 有一个宽为 $N$ 高为 $1001$ 的矩阵，每个格子可能是黑色或白色。选出一个紧贴下边界，且纯白的矩阵，记能选到的最大矩阵面积为 $S$。
每个格子有 $p$ 的概率为白色，$1-p$ 的概率为黑色，给出 $K$，求 $S=K$ 的概率。
答案对 $998244353$ 取模，$N\leq 10^9,K\leq 1000$。
------------
最大值等于 $K$ 难以处理，差分变为 $S<K$ 和 $S\leq K$ 的概率。考虑对于 $S\leq K$ 如何计算。
设 $G[n,t]$ 表示宽为 $n$，最低的黑格子高为 $\geq t$（高度从 $0$ 开始），能选择的矩阵大小不超过 $K$ 的概率。
若最低的黑格子高恰为 $t$，枚举第一个最低的黑格子的位置，有转移
$$G[n,t]=G[n,t+1]+[nt\leq K](1-p)p^t\sum_{l=1}^nG[l-1,t+1]G[n-l,t]$$
（该 DP 对应笛卡尔树的结构）
答案是 $G[N,0]$。
注意到 $G[n,t]$ 中 $nt\leq K$，在 $t\geq 1$ 时状态量是 $O(K\log K)$ 的，暴力转移总复杂度 $O(K^2\log K)$。
当 $t=0$ 时特殊处理，记 $F[n]=G[n,0]$，则
$$F[n]=G[n,1]+(1-p)\sum_{l=1}^{k+1}G[l-1,1]F[n-l]$$
求出 $F[1\sim k,0]$ 后，对于 $n>k$ 有
$$F[n]=(1-p)\sum_{l=1}^{k+1}G[l-1,1]F[n-l]$$
这是 $k+1$ 阶线性递推，套板子（暴力实现多项式乘法）复杂度 $O(K^2\log n)$。
```cpp
#include<algorithm>
#include<cstdio>
#include<vector>
#define MaxN 1050
#define S(A) A.size()
#define Poly std::vector<int>
const int _G=3,mod=998244353;
int powM(int a,int t=mod-2){
int ans=1;
while(t){
if(t&1)ans=1ll*ans*a%mod;
a=1ll*a*a%mod;t>>=1;
}return ans;
}
Poly operator * (const Poly &A,const Poly &B)
{
Poly C;C.resize(S(A)+S(B)-1);
for (int i=0;i<S(A);i++)
for (int j=0;j<S(B);j++)
C[i+j]=(C[i+j]+1ll*A[i]*B[j])%mod;
return C;
}
int frac(Poly P,Poly Q,int n)
{
if (!n)return 1ll*P[0]*powM(Q[0])%mod;
Poly Q0=Q;
for (int i=1;i<S(Q0);i+=2)Q0[i]=mod-Q0[i];
Q=Q*Q0;
for (int i=0;i<S(Q);i+=2)Q[i/2]=Q[i];
Q.resize((S(Q)+1)/2);
P=P*Q0;
for (int i=(n&1);i<S(P);i+=2)P[i/2]=P[i];
P.resize((S(P)+1-(n&1))/2);
return frac(P,Q,n/2);
}
void print(int x)
{
for (int q=1;q<=10000;q++){
int now=1ll*x*q%mod;
if (now<=10000){
printf(" %d/%d\n",now,q);
return;
}
}printf(" %d\n",x);
}
int N,K,_buf[MaxN*20],*tbuf=_buf,*G[MaxN];
int solve(int N,int K,int p)
{
G[0]=tbuf;tbuf+=K+2;
for (int i=0;i<=K+1;i++)G[0][i]=1;
for (int i=1;i<=K;i++)
{G[i]=tbuf;tbuf+=K/i+2;}
for (int t=0;t<=K;t++){
G[1][t]=mod+powM(p,t)-powM(p,K+1);
}
for (int n=2;n<=K;n++)
for (int t=K/n;t>=0;t--){
G[n][t]=(n*(t+1)>K) ? 0 : G[n][t+1];
int sav=0;
for (int l=1;l<=n;l++)
sav=(sav+1ll*G[l-1][t+1]*G[n-l][t])%mod;
G[n][t]=(G[n][t]+1ll*(mod+1-p)*powM(p,t)%mod*sav)%mod;
}
Poly F,C;F.resize(K+1);C.resize(K+2);
for (int i=0;i<=K;i++)F[i]=G[i][0];
C[0]=mod-1;
for (int i=1;i<=K+1;i++)C[i]=1ll*(mod+1-p)*G[i-1][1]%mod;
F=F*C;F.resize(K+1);
return frac(F,C,N);
}
Poly P,Q,P0,Q0;
int main()
{
int N,K,x,y,p;
scanf("%d%d%d%d",&N,&K,&x,&y);
p=1ll*x*powM(y)%mod;
printf("%d",(solve(N,K,p)-solve(N,K-1,p)+mod)%mod);
return 0;
}
```
------------
# D2T1 [游戏](https://www.luogu.com.cn/problem/P3825)
**题意** : 要写一个长度为 $n$ 的 `abc` 串。
每个位置都有一个限制 : 不能写 `a/b/c` 中的某一个。
特殊地，有一些位置没有限制（为 `x`），这样的位置不超过 $d\leq 8$ 个。
再额外加入若干限制 : 若第 $i$ 个位置写了 $h_i$ ,则在第 $j$ 个位置必须要写 $h_j$ 。
构造一个合法的串,或者指出无解。
------------
首先不考虑 `x` ，由于个位置至多适配两种字符，容易用 $\text{2-SAT}$ 解决。
现在考虑存在无限制位的情况,我们只需要将其替换成“$a$或$b$”或者“$a$或$c$”的约束即可。
这需要跑 $2^d$ 次 $\text{2-SAT}$，复杂度 $O(2^d(n+m))$。
```cpp
#include<algorithm>
#include<cstdio>
#include<queue>
#define pb push_back
#define MaxM 100500
#define MaxN 50500
using namespace std;
vector<int> g[MaxN<<1],g2[MaxN<<1];
int dfn[MaxN<<1],low[MaxN<<1],tim
,stk[MaxN<<1],top,col[MaxN<<1],Bcnt;
void tar(int u)
{
low[u]=dfn[u]=++tim;
stk[++top]=u;
for (int i=0,v;i<g[u].size();i++)
if (!dfn[v=g[u][i]]){
tar(v);
low[u]=min(low[u],low[v]);
}else if (!col[v])
low[u]=min(low[u],dfn[v]);
if (low[u]==dfn[u]){
Bcnt++;
while(stk[top+1]!=u)
col[stk[top--]]=Bcnt;
}
}
char s[MaxN],t[MaxN][2];
int n,m,d[MaxN<<1];
queue<int> q;
void topu()
{
for (int i=1;i<=Bcnt;i++)if (!d[i])q.push(i);
while(!q.empty()){
int u=q.front();q.pop();
dfn[u]=++tim;
for (int i=0;i<g2[u].size();i++)
if (!--d[g2[u][i]])q.push(g2[u][i]);
}
for (int i=1;i<=n;i++)
putchar((dfn[col[i]]>dfn[col[i+n]] ? t[i][0] : t[i][1])-'a'+'A');
}
struct Data{int u,v;char cu,cv;}b[MaxM];
void check()
{
for (int i=1;i<=n;i++){
if (s[i]=='a'){t[i][0]='b';t[i][1]='c';}
if (s[i]=='b'){t[i][0]='a';t[i][1]='c';}
if (s[i]=='c'){t[i][0]='a';t[i][1]='b';}
}
for (int i=1;i<=m;i++){
int u=b[i].u,v=b[i].v;char cu=b[i].cu,cv=b[i].cv;
if (s[u]==cu)continue;
int tu=(cu==t[u][1]);
if (s[v]==cv)g[u+tu*n].pb(u+(tu^1)*n);
else {
int tv=(cv==t[v][1]);
g[u+tu*n].pb(v+tv*n);
g[v+(tv^1)*n].pb(u+(tu^1)*n);
}
}
for (int i=1;i<=n+n;i++)if (!dfn[i])tar(i);
bool fl=0;
for (int i=1;i<=n;i++)if (col[i]==col[i+n])fl=1;
if (!fl){
for (int u=1;u<=n+n;u++)
for (int i=0;i<g[u].size();i++){
int v=col[g[u][i]];
if (col[u]!=v){g2[col[u]].pb(v);d[v]++;}
}
topu();exit(0);
}
for (int i=1;i<=n+n;i++){g[i].clear();dfn[i]=col[i]=0;}
Bcnt=0;
}
int tn,p[10];
int main()
{
scanf("%d%*d%s%d",&n,s+1,&m);
for (int i=1;i<=m;i++){
scanf("%d%s%d%s",&b[i].u,&b[i].cu,&b[i].v,&b[i].cv);
b[i].cu+='a'-'A';b[i].cv+='a'-'A';
}
for (int i=1;i<=n;i++)if (s[i]=='x')p[tn++]=i;
for (int t=0;t<(1<<tn);t++){
for (int i=0;i<tn;i++)s[p[i]]=(t>>i)&1 ? 'a' : 'b';
check();
}puts("-1");
return 0;
}
```
------------
# D2T2 [蔬菜](https://www.luogu.com.cn/problem/P3826)
见 [题解【P3826 [NOI2017] 蔬菜】](https://www.luogu.com.cn/blog/command-block/solution-p3826)
------------
# D2T3 [分身术](https://www.luogu.com.cn/problem/P3827)
**题意** ： 平面上有 $n$ 个点，每次询问删掉 $k$ 个（询问间独立），问其余点的凸包面积。
$n\leq 10^5,q\leq 10^5,k\leq 100,\sum k\leq 2\times 10^6$
------------
考虑分别求出上凸壳和下凸壳，答案等于“上凸壳下方的面积”减去“下凸壳下方的面积”。
将点按照 $x$ 坐标排序。删掉的 $k$ 个点将点集分成 $O(k)$ 段。
若能得到每一段的上凸壳，凸壳求公切线即可得到完整的上凸壳。
用猫树即可在 $O(n\log n)$ 预处理后 $O(1)$ 取出一个凸壳。
复杂度为 $O\big((n+\sum k)\log n\big)$。
```cpp
```