NOIAC做题记录

NOIAC做题记录
如果没看懂我题意,可以看noiac离线版

目前在比赛页-第三版可以看到这些比赛

好题:permu、substring、287染色、道路

NOI2019第二轮省选模拟赛 第四场

179 matching

题意:两个带?的通配符字符串匹配,输出所有匹配位置

请先思考后再展开

经典FFT问题,我写的是$O(nlogn \sum)$,code

比较优美的写法见OI之路-多项式全家桶

180 divisors

题意:求$\sum_{i=1}^n \sum_{d \mid i} GCD(d,\frac{i}{d})$,$n \le 1e13$,保证答案在ll内

请先思考后再展开

考虑枚举那个gcd,而gcd其实就是质因子次幂做min,$\sum_d d*\sum_{d^2|i} 2^{i/d^2 的质因子种数}$

那我们就是要筛$f_i=2^{i的质因子种数}$在每个$n=\lfloor \frac{N}{d^2} \rfloor$的前缀和F,min25筛速度不太行

思考发现$F_n=\sum_{i=1}^n |\mu(i)|* \lfloor \frac{n}{i} \rfloor$,然而并没有什么卵用


而且非常打击人的是,我充分观察抓住特点去做毫无成果的同时,看了眼题解,第一步是不动脑子直接莫反,回来试了试就做完了……那这种题有啥意义啊

$\sum_{g} g \sum_d \mu(d) \sum_{i=1}^{n/gd} \lfloor \frac{n}{(gd)^2i} \rfloor=\sum_T ( \sum_{g|T} g*\mu(T/g) )*( \sum_{i=1}^{n/T^2} \lfloor \frac{n}{T^2i} \rfloor )$

左边括号就是$id*\mu=\varphi$,而$T^2 \le n$可以线性预处理;右边就是$h_n=\sum_{i=1}^n \lfloor \frac{n}{i} \rfloor$,无脑数论分块复杂度$\sum_i \sqrt { n/i^2 }=O(\sqrt n* ln (\sqrt n))$

1
2
3
4
5
6
7
8
9
10
11
pre();mem(ok,0x3f);
ll n=qread(),ans=0;
fo(T,1,sqrt(n))
{
ll m=n/T/T,sum=0;
int pos=(m<=UB?m:UB+n/m);//乱写一通
if(m<UB) sum=hh[m];
else if(ok[pos]!=ok[0]) sum=ok[pos];
else for(ll l=1,r;l<=m;l=r+1) {ll t=m/l;r=m/t,sum+=t*(r-l+1);}
ans+=phi[T]*sum;ok[pos]=sum;
}write(ans);//卡了一波常才过

181 permu

题意:给出K的排列B,统计$n\le 1e4$的排列A满足$\forall 1 \leq i \leq n, A_{A_i}=i$且B为其子序列

请先思考后再展开

A是由若干个大小为1或2的轮换组成的,每种长度的A的方案数可以简单$dp_n=dp_{n-1}+dp_{n-2}(n-1)$求出

设$A_{b_i}=B_i(\forall i<j,b_i<b_j)$,则$A_{B_i}=b_i$

核心观察:如果枚举恰前m个$b_i \le K$,那么就是要把$B_{1 \sim m}填到A_{B_{1 \sim m}}中,且A_{B_t}填第t小$,这个是唯一的。不过还不一定合法,判完以后$s=2K-m$,方案数为剩下去右边选,即$C_{n-K}^{K-m}*dp_{n-(2K-m)}$。

插入排序,$O(n+k^2)$

1
2
3
4
5
fo(m,0,K){
sm[m]=B[m];fd(i,m,2) if(sm[i-1]>sm[i]) swap(sm[i-1],sm[i]); else break;
bool gg=0;fo(i,1,m) A[B[i]]=sm[i];fo(i,1,m) if(A[sm[i]]!=B[i]) {gg=1;break;}
if(!gg) add(ans, C(n-K,K-m)*dp[n-(K*2-m)]%MOD );
}write(ans);

NOI2019第二轮省选模拟赛 第五场

164 字符串游戏

题意:$T \le 1e3$组数据,两人轮流对一个初始为空的01串操作,在任意位置插入一个0、1,如果串S作为子串出现先手获胜,问先手能否在有限时间内获胜,$|S| \le 1e3$

请先思考后再展开

发现后手总是能让字符串不出现相邻两个相同,因此S中相邻相同的不超过1个。感受一下这似乎就是充分条件

165 染色

题意:给出n点m边二分图,找到最大的正整数K,能够用$2^K$种颜色给边染色,且每个点能在相邻的边上找到所有颜色,且每种颜色的边数量相等(主语同上句),输出一组染色方案,$n,m \le 1e5$

请先思考后再展开

核心观察:点度为偶,考虑K=1,可以跑欧拉回路后交错染边

先找到最大的$2^{K1}|gcd(\forall x,deg_x)$,构造证明一定有解:染色,分成K-1的两个子问题,$f(m)=2f(m/2)+O(m)=O(mlogm)$,遍历点的话因为$n \le O(m/2^K)$,暴力搞就是对的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
bool used[N];queue<pii> to[N];vc<int> cir;
void eular(int x)
{
while(sz(to[x]))
{
int y=to[x].front().FR,id=to[x].front().SE;to[x].pop();
if(used[abs(id)])continue;used[abs(id)]=1;
eular(y);cir.PB(id);
}
}
pii edge[N];int n,m,ans[N];
void solve(vc<int> ee,int cl,int cr)
{
if(cl==cr){ for(auto in:ee) ans[in]=cl;return; }
for(auto in:ee) used[in]=0;cir.clear();for(auto in:ee) to[edge[in].FR].push({edge[in].SE,in}),to[edge[in].SE].push({edge[in].FR,in});
fo(x,1,n) if(sz(to[x])) eular(x);//不一定连通,一开始以为不存在这种情况
vc<int> e[2];fo(t,0,sz(cir)-1) e[t&1].PB(cir[t]);solve(e[0],cl,(cl+cr)/2),solve(e[1],(cl+cr)/2+1,cr);
}
int deg[N];
void main()
{
while(1)
{
n=qread(),m=qread();if(!n) return;
vc<int> ee(m);fo(i,1,m){ int x=qread(),y=qread();deg[x]++,deg[y]++;edge[i]={x,y};ee[i-1]=i; }
int g=0,gg=0;fo(i,1,n) { if(!deg[i])gg=1; g=gcd(g,deg[i]),deg[i]=0;}
int K=0;while(g%bin(K+1)==0) K++;
if(!K or gg) write2(-1); else { write2(K);solve(ee,1,bin(K));fo(i,1,m) write1(ans[i]);puts(""); }
}
}

树的直径

题意:大小为$n \le 2e3$的边带非负整数权树,修改边权为非负实数权,要求$\sum |\Delta| \le K$,最小化直径

不会告辞

NOI2019第二轮省选模拟赛 第六场

191 sea

题意:给出$n,k \le 50$,统计满足割边数不超过k的n点带标号图

请先思考后再展开

先求出连通条件下,然后卷起来,卷的部分是$O(n^4)$,所以下面不用在乎复杂度,随便写就行了

连通部分,边双计数可以但麻烦,可以先算出存在割边的,在用连通图个数减去,设n点边双数为$no(n)$

存在割边,缩点为c个,就是个树计数,拓展prufer搞一搞就没了

$$
对于一个确定的长度为c的大小分配a,\prod a_i*(\sum a_i=n)^{c-2}*\prod no(a_i) \\
直接EGF,F(n,c>1)=n^{c-2} \frac{n!}{c!}x^n*i*\frac{x^i}{i!} )^c
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const int N=1e2+10;
ll f[N],dp[2][N],no[N];
ll h[N][N],h2[N][N];
void main(){
PRE();
int n=qread(),K=qread();
fo(nn,1,n){ no[nn]=qpower(2,C(nn,2));fo(i,1,nn-1) add(no[nn], MOD-C(nn-1,i-1)*no[i]%MOD*qpower(2,C(nn-i,2))%MOD );deb(no[nn]); }
fo(nn,1,n)
{
fo(i,1,nn-1) f[i]=dp[0][i]=no[i]*facinv[i]%MOD*i%MOD;
fo(c,2,nn)
{
mem(dp[1],0);fo(ii,1,nn) fo(i,1,ii-1) add(dp[1][ii], dp[0][i]*f[ii-i]%MOD );
swap(dp[0],dp[1]);
h[nn][c-1]=dp[0][nn]*qpower(nn,c-2)%MOD*fac[nn]%MOD*invm(fac[c])%MOD;
add(no[nn], MOD-h[nn][c-1] );debug("dp(%d,%d)=%d\n",nn,c,h[nn][c-1]);
}
deb(no[nn]);h[nn][0]=no[nn];
}memcpy(h2,h,sizeof h);
fo(ij,1,n) fo(iijj,0,ij)
{
fo(j,1,ij-1) fo(jj,0,j) add(h[ij][iijj],h[ij-j][iijj-jj]*h2[j][jj]%MOD*C(ij-1,j-1)%MOD );
debug("h(%d,%d)=%d\n",ij,iijj,h[ij][iijj]);
}
ll ans=0;fo(c,0,K) add(ans,h[n][c]);write(ans);
}

192 substring

题意:给出$n \le 200,m \le 50,字符集大小K \le 1e3$,统计$\sum_{|S|=n} \sum_{|T|=m} T是S子串$

请先思考后再展开

前置:概率论-概率生成函数中的掷骰子匹配字符串的思想

对于一个确定的T,计算其border集合B,设f未结束g恰结束,$f_i=\sum_{j \in B} g_{i+j}\ ,\ f_i*K=f_{i+1}+g_{i+1}$

写成递推的形式,$f_i=f_{i-1}*k-g_i\ ,\ g_i=f_{i-m}-\sum_{j \in B,j \ne m} g_{i-m+j}$,对应可用的S的数量为,$K^n-f_n$

根据在字符串-其他里面介绍的搜索border的科技,复杂度为$状态数*(m^2+nm)$,其中状态数为2249

1
2
3
4
5
6
7
8
9
10
11
12
Border_Search::n=m,Border_Search::K=K;Border_Search::dfs(1);
ll ans=0;
for(auto in:Border_Search::Border)
{
f[0]=1;
fo(i,1,n)
{
if(i>=m){ g[i]=f[i-m];fo(j,1,m-1) if(in.FR[j]) add(g[i],MOD-g[i-m+j]); }
f[i]=(f[i-1]*K+MOD-g[i])%MOD;
}
add(ans, (qpower(K,n)+MOD-f[n])*in.SE%MOD );
} write(ans);

193 schedule

题意: $m$ 台机器完成 $n$ 个任务,第 $i$ 个任务必须在$[l_i,r_i]$这段时间内开始并结束,总耗时$k_i$。任务开始后可以暂停,可以切换到其他机器,但不能并行;同一个任务不能同时运行在不同机器上。回答是否可行,$n,m \le 100,时间 \le 1e6$

请先思考后再展开

自闭,看完题解还是自闭,直到我注意到潜意思是可以不同时在不同机器上

那就按题意最大流就好了啊,这种题有啥意义啊

具体而言就是离散化时间,然后$[l,r)的容量为m*(r-l)$,构造法为当做m行的 矩阵,一行一行填,肯定每个任务不会同时做

code

NOI2019省选模拟赛 第一场

253 A

题意:$n \times m$的棋盘,给出初始位置,每次在$不会走出去的位移 \subseteq {向下,向左,向右,不动}$中等概率选择,到最后一行就结束,问期望步数,$n,m \le 1e3$

请先思考后再展开

解方程裸题,一行一行解,上一行是常量,第一个主元推过去

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ll f[N];pll g[N];
pll operator + (pll x,pll y){ return {x.FR+y.FR,x.SE+y.SE}; }
pll operator + (pll x,ll y){ return {x.FR,x.SE+y}; }
pll operator - (pll x,pll y){ return {x.FR-y.FR,x.SE-y.SE}; }
pll operator - (pll x,ll y){ return {x.FR,x.SE-y}; }
pll operator * (pll x,ll y){ return {x.FR%MOD*y%MOD,x.SE%MOD*y%MOD}; }
void main()
{PRE();
int n=qread(),m=qread(),xx=qread(),yy=qread();
if(m==1){ write(2*(n-xx));return; }
fd(hh,n-1,xx)
{
g[1]={1,0};g[2]=g[1]*2-f[1]-3;
fo(i,2,m-1) g[i+1]=g[i]*3-4-f[i]-g[i-1];
pii gm=(g[m-1]+f[m]+3)*invm(2);
assert(gm.FR!=g[m].FR);
f[1]=(gm.SE-g[m].SE)%MOD*invm((g[m].FR-gm.FR)%MOD)%MOD;
fo(i,2,m) f[i]=(g[i].FR*f[1]+g[i].SE)%MOD;
}write((f[yy]+MOD)%MOD);
}

254 B

题意:优化$dp_1=-w_1,dp_i=\min_{j<i} dp_j+(h_i-h_j)^2-w_i,ans=dp_n+\sum w_t$,其中$n \le 1e5,h \in [0,1e6],w \in [-1e6,1e6]$

请先思考后再展开

李超线段树板子题

1
2
3
int n=qread();fo(i,1,n) h[i]=qread();ll sum=0;fo(i,1,n) sum+=(w[i]=qread());
#define ins(jj) SGT::insert({-2*h[jj],dp[jj]+h[jj]*h[jj]})
dp[1]=-w[1],ins(1);fo(i,2,n) dp[i]=SGT::ask(h[i])-w[i]+h[i]*h[i],ins(i);write(dp[n]+sum);

255 C

题意:n个$[1,n]$的数,求$\sum_{选出n个数的子集A,B满足A\cap B=\emptyset} [A异或和>B异或和]$

请先思考后再展开

$ans=(\sum_{i=0}^{n} C_n^i2^i-\sum_{不重子集A,B} 异或和相等)/2=(3^n-\sum_{子集S异或和=0} 2^{|S|})/2$,即黎明前的巧克力,OI之路fwt有

NOI2019省选模拟赛 第三场

286 集合

题意:给出$n,K,A$,求$S \subseteq {1,2,\cdots,n}且|S|=K时,A^{min\ S}$的期望,$K \le 1e7$

请先思考后再展开

$$
ans=\sum_{i=1}^n A^iC_{n-i}^{K-1}/C_n^K=F(n-1,K-1,A^{-1})A^{n}/C_n^K,F(n,K,A)=\sum_{i=0}^n C_i^k A^i \\
组合数递推式拆开,F(n,K,A)/A=F(n,K-1,A)+F(n,K,A)-A^n(C_{n}^{K-1}+C_n^K)
$$
记得特判A=1,复杂度为$O(K)$

287 染色

题意:$n \le 1e5$个点的树,m种颜色,统计染色方案,满足有同色点对,且$\min_{x \ne y,col_x=col_y} dis_{x,y} \in [L,R]$

请先思考后再展开

用到一个小结论:bfs序加入树上点的话,$若dis_{i,x} \le K,dis_{j,x} \le K则dis_{i,j} \le K$;证明考虑$path_{x,i}和path_{x,j}$的第一个分叉点w且i在w子树内,则$dis_{i,j} \le dis_{x,j} \le K$

回到题目,其实就是要求同色点距离都大于K的方案数。而现在按bfs序加入节点x的话,本来是要求所有距离x不超过K的都不能相同,现在只需要满足x与他们都不同就行了,他们一定是互不相同的,于是只需要统计这个点集的大小。

尝试用点分治处理树上路径问题,每个分治重心时给所有点排序,用个树状数组询问前缀和即可,当然需要容斥掉来自同一个子树的点对,$O(nlog^2n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
const int N=1e5+10;int dfn[N];
vc<int> to[N];bool ban[N];
int G,SUM,mxs[N],siz[N];
void getrt(int x,int fa=0)
{
mxs[x]=0;siz[x]=1;
for(auto y:to[x]) if(y!=fa and !ban[y]) getrt(y,x),siz[x]+=siz[y],chmax(mxs[x],siz[y]);
chmax(mxs[x],SUM-siz[x]);if(mxs[x]<mxs[G]) G=x;
}
namespace BIT
{
int bit[N];int lowbit(int x){return x&-x;}
void ad(int x,int c){ while(x<N) bit[x]+=c,x+=lowbit(x); }
int ask(int x){ int ret=0;while(x>=1) ret+=bit[x],x-=lowbit(x);return ret; }
};
int dis[N];int hh[N],top;
void dfs(int x,int fa=0){ hh[++top]=x;siz[x]=1;for(auto y:to[x]) if(y!=fa and !ban[y]) dis[y]=dis[x]+1,dfs(y,x),siz[x]+=siz[y]; }
int K,ct[N];
void calc(int op)
{
sort(hh+1,hh+top+1,[&](int x,int y){return dfn[x]<dfn[y];});
fo(i,1,top) ct[hh[i]]+=BIT::ask(1+K-dis[hh[i]])*op,BIT::ad(1+dis[hh[i]],1);
fo(i,1,top) BIT::ad(1+dis[hh[i]],-1);
}
void solve(int rt)
{
top=0,dis[rt]=0,dfs(rt),calc(1);ban[rt]=1;
for(auto y:to[rt]) if(!ban[y]) { top=0,dfs(y),calc(-1); mxs[G=0]=INF,SUM=siz[y],getrt(y),solve(G); }
}
void main()
{//PRE();
int n=qread(),m=qread(),L=qread(),R=qread();fo(i,2,n){ int x=qread(),y=qread();to[x].PB(y),to[y].PB(x); }
dfs(1);sort(hh+1,hh+n+1,[&](int x,int y){return dis[x]<dis[y];});fo(i,1,n) dfn[hh[i]]=i;
K=L-1;mem(ct,0);mem(ban,0);mxs[G=0]=INF,SUM=n,getrt(1),solve(G);ll ans1=1;fo(i,1,n) ans1=ans1*max(0,m-ct[i])%MOD;
K=R ;mem(ct,0);mem(ban,0);mxs[G=0]=INF,SUM=n,getrt(1),solve(G);ll ans2=1;fo(i,1,n) ans2=ans2*max(0,m-ct[i])%MOD;
write(mm(ans1+MOD-ans2));
}

NOI2019省选模拟赛 第四场

289 电梯没过

这题我过了拍没过数据,下面给出我理解的题意,并且我认为如果题意是这样我应该是对的

题意:先排序,且$t*=2$,则$dp_i=\min_{dp_j} {max(dp_j,t_{i})+max(x_{j+1 \sim i})}$,保证t互不相同,优化该过程,$n \le 1e6$

请先思考后再展开

为了方便,让$x’*i=x*{i+1}$
$$
dp_i=t_{i}+\min_{dp_j \le t_i} {max(x’_{j \sim i-1})}\\
dp_i=\min_{t_i<dp_j} {dp_j+max(x’_{j \sim i-1})}
$$
第一个式子:直接取最后一个

第二个式子:dp不递减,每个maxx相同的块取第一个,可删堆维护单调队列内的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
struct Heap
{
priority_queue< ll,vc<ll>,greater<ll> > A,B;
void upd(){while(sz(A) and sz(B) and A.top()==B.top()) A.pop(),B.pop();}
void push(ll num){A.push(num);} void erase(ll num){B.push(num);}
int size(){return sz(A)-sz(B);} ll top(){upd();return A.top();}
}qq;
const int N=1e6+10;
pii a[N];//{t,x*2}
ll dp[N];
pii q[N];int tou=1,wei=0;//单调队列
void main()
{//PRE();
int n=qread();fo(i,1,n) a[i].FR=qread(),a[i].SE=qread()*2;sort(a+1,a+n+1);fo(i,0,n-1) a[i].SE=a[i+1].SE;
mem(dp,0x3f);dp[0]=0;
int pos=0;//dpi<=t[i]分界点
fo(i,1,n)
{
while(dp[pos+1]<=a[i].FR) pos++;
#define V(ii) dp[q[ii].FR]+a[q[ii].SE].SE
while(tou<=wei and q[tou].FR<=pos) {
qq.erase(V(tou));q[tou].FR=pos+1;
if(q[tou].FR>q[tou].SE) tou++; else qq.push(V(tou));
}
dp[i]=a[i].FR+max(a[pos].SE,tou<=wei?a[q[tou].SE].SE:0);
if(sz(qq)>0) chmin(dp[i],qq.top());
pii now={i,i};
while(tou<=wei and a[q[wei].SE].SE<=a[i].SE) now.FR=q[wei].FR,qq.erase(V(wei)),wei--;
q[++wei]=now;qq.push(V(wei));
}write(dp[n]);
}

290 道路

题意:给出一张$n \le 50$点有向图,$A_{i,j}=i到j的边数$,给定常数K和$T \le 50$

分别求出所有点对间,$\sum_{L=0}^{K-1} 长度为L的路径个数*L^T \%998244353$

请先思考后再展开

记$dp_{mx}(x,y,t)=x \to y长度不超过mx的路径的C_{ln}^t之和$,快速幂mx,那么每次就是合并「不超过L1」和「不超过L2」,则$dp_{L1+L2}(x,y,t)=dp_{L2}(x,y,t)+(dp_{L1}(x,z,tt)-[x=z且tt=0])*[z \to y长度恰L2路径数]*C_{L2}^{t-tt}$

无脑写是$O(logkn^3T^2)$,动动脑子把枚举z和枚举tt分两次做,小常数$O(logk*(n^3T+n^2T^2))$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
const int N=51;
int n,T;
struct Mat
{
int a[N][N][N],b[N][N];Mat(){mem(a,0);mem(b,0);}
}AA;
int CC[N];//C(L2,j)
Mat Mul(Mat A,Mat B,int L2)
{
CC[0]=1;fo(j,1,T) CC[j]=1ll*CC[j-1]*Inv[j]%MOD*(L2-j+1)%MOD;
Mat ret;fo(x,1,n) fo(y,1,n) fo(z,1,n) add(ret.b[x][y], 1ll*A.b[x][z]*B.b[z][y]%MOD );
fo(x,1,n) fo(y,1,n) fo(z,1,n) fo(i,0,T) add(ret.a[x][y][i], 1ll*(A.a[x][z][i]+MOD-(i==0 and x==z) )*B.b[z][y]%MOD );
fo(x,1,n) fo(y,1,n) fd(i,T,0) fo(j,1,i) add(ret.a[x][y][i], 1ll*ret.a[x][y][i-j]*CC[j]%MOD );
// fo(x,1,n) fo(y,1,n) fo(z,1,n) fo(i,0,T) fo(j,0,T-i) add(ret.a[x][y][i+j], 1ll*(A.a[x][z][i]+MOD-(i==0 and x==z) )*B.b[z][y]%MOD*CC[j]%MOD );
fo(x,1,n) fo(y,1,n) fo(i,0,T) add(ret.a[x][y][i],B.a[x][y][i]);
return ret;
}
Mat solve(int L)
{
if(L==1) return AA;
Mat ret=solve(L/2);ret=Mul(ret,ret,L/2);
if(L&1) ret=Mul(AA,ret,L-1);return ret;//这部分可以选择优化掉,常数/=2
}
ll S2[N][N];
void main()
{PRE();
S2[0][0]=1;fo(i,1,N-1) fo(j,1,i) S2[i][j]=(S2[i-1][j-1]+S2[i-1][j]*j)%MOD;
int K,q;scanf("%d%d%d%d",&n,&K,&q,&T);
fo(i,1,n) fo(j,1,n){ int val=qread();AA.a[i][j][0]=val+(i==j),AA.b[i][j]=AA.a[i][j][1]=val; }
if(K<=1){ while(q--) write2(0);return; }
Mat A=solve(K-1);while(q--){ int x=qread(),y=qread();ll ans=0;fo(j,0,T) add(ans,1ll*S2[T][j]*fac[j]%MOD*A.a[x][y][j]%MOD);write2(ans); }
}

NOI2019省选模拟赛 第五场

309 Mas的童年

bzoj5092 [Lydsy1711月赛]分割序列

311 战棋游戏

题意:给一行$n \le 1e18$个格子染$c \le 2^{60}$种颜色,给出其中$k \in [1,20]$个特殊位置,要求若干对特殊位置的颜色不同,相邻格子和首尾两个格子颜色也不能相同,模$1e9+7$,保证c与模数互质,3s

请先思考后再展开

相当于一个大小为k的环,存在一些颜色不同的限制,环上相邻两点间的权值只关心原本长度和这两点颜色是否相同(随便矩乘下就能求出)

状压dp可以用子集卷积优化,那其实是个元素为「大小为$2^k$的集合幂级数」的k次多项式的c次方,这个多项式的系数就是考虑某个颜色恰是这个集合的贡献(每个点去考虑它左边那条边,一定能直接知道是否同色)

做c次幂的话,因为是首零多项式,直接ln+exp算就好了,对集合幂级数套多项式算法不熟的可见多项式全家桶,$O(2^nn^2)$

NOI2019省选模拟赛 第六场

283 唐时月夜

题意:有一个n行m列的矩阵,每次对某个子矩形左右翻转或上下翻转,或转置某个子正方形。输入方式为$给定常数A、B、C,f_0=C,f_i=A\times f_{i-1}+B\ (i\geq 1)$,初始矩阵$A_{i,j}=f_{(i-1)\times M+j}$,最后输出$\sum_{i=1}^{N}\sum_{j=1}^{M}A_{i,j}\times f_{(i-1)\times M+j} \% 2^{32}$

$n,m \le 4e3$,操作数$Q \le 2e5$,保证每次操作的区域包含上次操作的区域

请先思考后再展开

将操作区域完全相同的分为一组,则最多$O(n)$组询问,对于每组询问,记录三个01变量abc,行翻转就a^=1,列翻转就b^=1,倒置就c^=1且swap(a,b),最后再统一做,这样是$O(n^3)$。继续想下去,你会发现这段话最后没用

发现每次做完一个区域,这个区域已经不会变了,到下个时刻相当于存在一个大格子和若干个小格子,大格子是不会变的。

因此我们倒着做,每次要保证复杂度只和小格子有关,然后告诉上一个操作应该把大格子如何填到何处,复杂度为$O(n^2+q)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
int n,m,fm[N][N],to[N][N];
typedef unsigned int ui;ui A,B,F[N*N];
int op[NN];pii xx[NN],yy[NN];
void solve(int id,pii tx,pii ty,bool a,bool b,bool c);
void move(pii fmx,pii fmy,pii nx,pii ny,int tx,int ty,bool a,bool b,bool c,int id=0)
{
if(nx.FR>nx.SE or ny.FR>ny.SE) return;
int h=fmx.SE-fmx.FR+1,w=fmy.SE-fmy.FR+1;
if(id>0)
{
pii dx={nx.FR-fmx.FR,nx.SE-fmx.FR},dy={ny.FR-fmy.FR,ny.SE-fmy.FR};
if(a) dy={w-1-dy.SE,w-1-dy.FR};if(b) dx={h-1-dx.SE,h-1-dx.FR};if(c) swap(dx,dy);
solve(id,{tx+dx.FR,tx+dx.SE},{ty+dy.FR,ty+dy.SE},a,b,c);
}
else fo(i,nx.FR,nx.SE) fo(j,ny.FR,ny.SE)
{
int dx=i-fmx.FR,dy=j-fmy.FR;
if(a) dy=w-1-dy;if(b) dx=h-1-dx;if(c) swap(dx,dy);
to[tx+dx][ty+dy]=fm[i][j];
}
}
void solve(int id,pii tx,pii ty,bool a,bool b,bool c)//左右、上下、倒置,依次处理
{
if(op[id]==1) a^=1;if(op[id]==2) b^=1;if(op[id]==3) swap(a,b),c^=1;
move(xx[id],yy[id],xx[id],{yy[id].FR,yy[id-1].FR-1},tx.FR,ty.FR,a,b,c);//左
move(xx[id],yy[id],xx[id],{yy[id-1].SE+1,yy[id].SE},tx.FR,ty.FR,a,b,c);//右
move(xx[id],yy[id],{xx[id].FR,xx[id-1].FR-1},yy[id],tx.FR,ty.FR,a,b,c);//上
move(xx[id],yy[id],{xx[id-1].SE+1,xx[id].SE},yy[id],tx.FR,ty.FR,a,b,c);//下
move(xx[id],yy[id],xx[id-1],yy[id-1],tx.FR,ty.FR,a,b,c,id-1);
}
void main()
{
qread();n=qread(),m=qread();int q=qread();
A=qread(),B=qread();F[0]=qread();fo(i,1,n*m) F[i]=F[i-1]*A+B;
fo(i,1,n) fo(j,1,m) fm[i][j]=to[i][j]=F[(i-1)*m+j];
fo(i,1,q) op[i]=qread(),xx[i].FR=qread(),yy[i].FR=qread(),xx[i].SE=qread(),yy[i].SE=qread();
xx[0]=xx[1],yy[0]=yy[1],xx[0].SE=xx[0].FR,yy[0].SE=yy[0].FR;solve(q,xx[q],yy[q],0,0,0);
ui ans=0;fo(i,1,n) fo(j,1,m) ans+=(ui)to[i][j]*F[(i-1)*m+j];write(ans);
}

284 附耳而至

题意:二维坐标系上n个点m条边,保证是平面图且连通,并且保证任何一个被分割出来的非无穷大区域是简单多边形,非无穷大区域的并也是简单多边形。每个点有两个数a和b,非无穷大区域$a=\sum_{顶点}a_i$,无穷大区域$a=\sum_{顶点的补集} a_i$,b同理。将所有区域分为两个集合,最大化$\sum_{i \in A集合} a_i+\sum_{i \in B集合} b_i-\sum_{两侧区域所属集合不同的每条边i} c_i$

$n,区域数 \le 4e4,m \le 2e5,a_i,b_i \le 1e3,c_i \le 1e6,坐标 \le 2e4$,没有重点

请先思考后再展开

搜出所有区域,直接最小割,边数为m

因为过于拼题,鸽置

285 星辰大海

题意:给出二维平面上$n \le 5e5$个点,坐标绝对值$\le 1e6$,没有重点。

现在点1会被移动,使得移动后$\forall 不同的i,j,k,有向角度\angle P_iP_jP_k\in(-\pi,\pi]$符号(正、负、零)不变,问点1能去往的区域面积,点1移动后坐标绝对值不超过1e6

请先思考后再展开

发现条件其实就是,$\forall 1<i<j$,用原本点1所在的半平面做半平面交。枚举每个点,那么只需要加入,该点与点1连线两侧夹角最小的两个点的半平面。然而不好求,正解是以点1为原点极角排序,对于与点i相邻的线段,考虑连接1和i,则考虑加入直线两侧,与i相邻的两点和与i距离最远的两点(两侧故两点),建议感性理解

完结撒花~

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/513e4085.html
转载请注明出处,谢谢!