NOIP模拟51
「茅山道术·泰拳警告·万猪拱塔·抑郁刀法」on 9.12
樱花满地集于我心，楪舞纷飞祈愿相随
前言
太菜了，人手切掉两个题，我竟然一道都不会。。
改 T3 的时候整个人的心态都崩掉了，一部分原因可能是语文素养不高导致我看不懂题解。
另一部分可能就是系太不太好，受不了打击。。。（又菜又玩不起
后来稍微又看了一下题才发现自己 T3 少看了 w 互不相同这个条件，难怪感觉题解越想越不对。。
T1 茅山道术
解题思路
动态规划
设 \(f_i\) 表示前 \(i\) 个的方案数，状态可以由 \(i-1\) 或者 \(i\) 位置的这个颜色的上一个出现位置转移过来，正确性显然。
假设位置 \(i\) 颜色上一次出现位置为 \(las_i\) 则 \(f_i=f_{i-1}+f_{las_i}\times[las_i\ne i-1]\)，边界是 \(f_0=1\)
code
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define f() cout<<"Failed"<<endl
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=1e6+10,M=2e3+10,mod=1e9+7;
int n,ans,s[N],las[N],bef[N],f[N];
signed main()
{
freopen("magic.in","r",stdin);
freopen("magic.out","w",stdout);
n=read();
for(int i=1;i<=n;i++) s[i]=read();
for(int i=1;i<=n;i++)
{
las[i]=bef[s[i]];
bef[s[i]]=i;
}
f[0]=1;
for(int i=1;i<=n;i++)
{
int j=las[i];
f[i]=f[i-1];
if(j) f[i]=(f[i]+f[j]*(j<i-1))%mod;
}
printf("%lld",f[n]);
return 0;
}
T2 泰拳警告
解题思路
枚举输赢局总数进行计算。
假设输赢局总数是 \(i\) 那么赢的局数一定要多于一半，对于一局我们把平局的方案数看作是 \(p\) 种，输赢的情况数各为 \(1\) 种，最后的答案除去 \((p+2)^n\) 就好了。
那么可以像官方题解一样看作 \((x+x^{-1})^i\) 次幂大于 \(0\) 其实也就是赢的局数大于输的局数，然后二项式展开。
通俗理解的话就是从 \(i\) 场中最少赢 \(\lfloor\dfrac{i+1}{2}\rfloor\) 场才算合法的情况，那么方案数也就是 \(t(i)=\sum\limits_{j=0}^iC_i^j\times[j\ge\lfloor\dfrac{i+1}{2}\rfloor]\)
对于偶数奇数分别计算，显然 \(i\) 为奇数的时候 \(t(i)=\dfrac{\sum\limits_{j=0}^i C_j^j}{2}\) 也就是 \(t(i)=2^{i-1}\)
对于偶数的时候只需要去掉中间的一项就好了 \(t(i)=2^{i-1}-\dfrac{C^{\frac{i}{2}}_{i}}{2}\)
然后对于剩下的平局就有 \(p^{n-i}\) 种方案，对于 \(n\) 局进行排列，并且去掉等效的局数内部的排序，因此我们需要在乘上 \(\dfrac{A_n^n}{A_i^i\times A_{n-i}^{n-i}}\)
code
一般观赏版
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define f() cout<<"Failed"<<endl
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=3e6+10,mod=998244353;
int n,p,ans,fac[N],ifac[N];
int power(int x,int y)
{
int temp=1;
while(y)
{
if(y&1) temp=temp*x%mod;
x=x*x%mod; y>>=1;
}
return temp;
}
int C(int x,int y){return fac[x]*ifac[y]%mod*ifac[x-y]%mod;}
int A(int x,int y){return fac[x]*ifac[x-y]%mod;}
signed main()
{
freopen("fight.in","r",stdin);
freopen("fight.out","w",stdout);
n=read(); p=read(); fac[0]=ifac[0]=1;
for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
ifac[n]=power(fac[n],mod-2);
for(int i=n-1;i>=1;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
for(int i=1;i<=n;i++)
{
int pre=ans;
if(i&1) ans=(ans+power(2,i-1)*(n-i+1)%mod*power(p,n-i)%mod*fac[n]%mod*ifac[i]%mod*ifac[n-i])%mod;
else ans=(ans+(power(2,i-1)-C(i,i/2)*power(2,mod-2)%mod+mod)%mod*(n-i+1)%mod*power(p,n-i)%mod*fac[n]%mod*ifac[i]%mod*ifac[n-i])%mod;
}
printf("%lld",ans*power(power(p+2,n),mod-2)%mod);
return 0;
}
极致压行版
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=3e6+10,mod=998244353;
int n,p,ans,inv2,invp,fac[N],ifac[N];
int power(int x,int y){int temp=1;while(y){if(y&1) temp=temp*x%mod;x=x*x%mod; y>>=1;}return temp;}
int C(int x,int y){return fac[x]*ifac[y]%mod*ifac[x-y]%mod;}
int A(int x,int y){return fac[x]*ifac[x-y]%mod;}
signed main(){
freopen("fight.in","r",stdin); freopen("fight.out","w",stdout);
n=read(); p=read(); inv2=power(2,mod-2); invp=power(p,mod-2);
fac[0]=ifac[0]=1; for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
ifac[n]=power(fac[n],mod-2); for(int i=n-1;i>=1;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
for(int i=1,base=1,basep=power(p,n-1);i<=n;i++,base=base*2%mod,basep=basep*invp%mod)
if(i&1) ans=(ans+base*(n-i+1)%mod*basep%mod*fac[n]%mod*ifac[i]%mod*ifac[n-i])%mod;
else ans=(ans+(base-C(i,i/2)*inv2%mod+mod)%mod*(n-i+1)%mod*basep%mod*fac[n]%mod*ifac[i]%mod*ifac[n-i])%mod;
printf("%lld",ans*power(power(p+2,n),mod-2)%mod);
return 0;
}
T3 万猪拱塔
解题思路
非常非常恶心的一道题。。。
正解的思路就非常玄学，非常非常玄学。。。
考虑判定权值在区间 \([l,r]\) 内的所有数所在的格子是否形成了一个矩形，因为题目保证各个点的值不相同，因此满足条件的矩形一定包括了 \([Min,Max]\) 中的所有的点。
记值在 \([l,r]\) 格子的颜色为黑色，其它的格子颜色为白色。
考虑所有的 \((n + 1)\times(m + 1)\) 个 \(2\times 2\) 的小正方形 (部分超出边界也算)。
则所有黑色格子形成一个矩形，当且仅当恰好有 \(4\) 个小正方形内部有 \(1\) 个黑色格子，并且没有任何一个小正方形内部有 \(3\) 个黑色格子，所谓有 \(1\) 个黑色格子的小正方形其实就是矩形的四个角，然后 有 \(2\) 个，\(4\) 个黑色格子的就是边缘以及矩形内部的。
从小到大枚举 \(r\) ，对每个 \(l\le r\) ，记 \(f(l)\) 表示染黑权值在 \([l,r]\) 内的格子后，有多少小正方形内部有 1 个或 3 个黑色格子。
\(f(l) \ge 4,f(r) = 4\)，于是只需要对每个 \(l\) 维护 \(f(l)\) 最小值，最小值的数目和取得最小值的所有 \(l\) 之和。
每次小格子的更改只会影响到周围四个小正方形内部的黑色格子的数量，然后就是根据当前的格子状态进行修改。
假设四个格子的大小从小到大是 \(l_1,l_2,l_3,r\) 那么我们进行 对于 \(r\) 格子的染色之后就会有， \([l_3+1,r]\) 区间染色是有一个有 \(1\) 个黑色格子的小正方形，染色之前有 一个有 \(0\) 个黑色格子的小正方形。
因此我们给 \([l_3+1,r]\) 区间的 \(f(l)\) 加 \(1\)。同样的道理 \([l_2+1,l_3]\) 区间减去 \(1\)，\([l_1+1,l_2]\) 区间加 \(1\) , \([1,l_1]\) 区间减去 \(1\)
线段树维护即可，注意一个点，一开始的 \(f(l)\) 是 \(0\) 我们是不会算入最小值的，但是当我们区间加值之后就会被计入答案，因此需要维护每个区间剩余 \(0\) 的数量以及 \(l\) 之和。
code
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define f() cout<<"Failed"<<endl
#define ls x<<1
#define rs x<<1|1
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int mod=998244353,N=5e5+10,INF=1e18;
int n,m,ans,d[10],fro[N];
vector<int> s[N];
pair<int,int> id[N];
struct Segment_Tree{int cnt,dat,sum,laz,res,tot;}tre[N<<2];
void push_up(int x)
{
tre[x].res=tre[ls].res+tre[rs].res;tre[x].tot=tre[ls].tot+tre[rs].tot;
if(tre[ls].dat==tre[rs].dat) return tre[x].dat=tre[ls].dat,tre[x].cnt=tre[ls].cnt+tre[rs].cnt,tre[x].sum=tre[ls].sum+tre[rs].sum,void();
if(!tre[ls].dat) return tre[x].dat=tre[rs].dat,tre[x].cnt=tre[rs].cnt,tre[x].sum=tre[rs].sum,void();
if(!tre[rs].dat) return tre[x].dat=tre[ls].dat,tre[x].cnt=tre[ls].cnt,tre[x].sum=tre[ls].sum,void();
if(tre[ls].dat>tre[rs].dat) return tre[x].dat=tre[rs].dat,tre[x].cnt=tre[rs].cnt,tre[x].sum=tre[rs].sum,void();
if(tre[rs].dat>tre[ls].dat) return tre[x].dat=tre[ls].dat,tre[x].cnt=tre[ls].cnt,tre[x].sum=tre[ls].sum,void();
}
void build(int x,int l,int r)
{
if(l==r) return tre[x].dat=0,tre[x].cnt=1,tre[x].sum=l,tre[x].res=1,tre[x].tot=l,fro[l]=x,void();
int mid=(l+r)>>1; build(ls,l,mid); build(rs,mid+1,r); push_up(x);
}
void push_down(int x,int l,int r)
{
if(!tre[x].laz) return ;
int mid=(l+r)>>1;
tre[ls].dat+=tre[x].laz;tre[ls].laz+=tre[x].laz;
if(!tre[ls].dat) tre[ls].cnt=tre[ls].res=mid-l+1,tre[ls].sum=tre[ls].tot=(l-1)*(mid-l+1)+mid-l+1;
if(tre[x].laz>0&&tre[ls].res) tre[ls].dat=tre[x].laz,tre[ls].cnt=tre[ls].res,tre[ls].sum=tre[ls].tot,tre[ls].res=tre[ls].tot=0;
tre[rs].dat+=tre[x].laz;tre[rs].laz+=tre[x].laz;
if(!tre[rs].dat) tre[rs].cnt=tre[rs].res=r-mid,tre[rs].sum=tre[rs].tot=(mid-1)*(r-mid)+r-mid;
if(tre[x].laz>0&&tre[rs].res) tre[rs].dat=tre[x].laz,tre[rs].cnt=tre[rs].res,tre[rs].sum=tre[rs].tot,tre[rs].res=tre[rs].tot=0;
tre[x].laz=0;
}
void insert(int x,int l,int r,int L,int R,int num)
{
if(L<=l&&r<=R)
{
tre[x].laz+=num; tre[x].dat+=num;
if(!tre[x].dat) tre[x].cnt=r-l+1,tre[x].sum=(l-1)*(r-l+1)+r-l+1,tre[x].res=r-l+1,tre[x].tot=(l-1)*(r-l+1)+r-l+1;
if(num&&tre[x].res) tre[x].dat=tre[x].laz,tre[x].cnt=tre[x].res,tre[x].sum=tre[x].tot,tre[x].res=tre[x].tot=0;
return ;
}
int mid=(l+r)>>1; push_down(x,l,r);
if(L<=mid) insert(ls,l,mid,L,R,num);
if(R>mid) insert(rs,mid+1,r,L,R,num);
push_up(x);
}
void work(int num)
{
sort(d+1,d+5);int pos=lower_bound(d+1,d+5,num)-d;d[0]=0;
for(int j=1,temp=pos-j+1;j<=pos;j++,temp=pos-j+1)
if(temp==1) insert(1,1,n*m,d[j-1]+1,d[j],1);
else if(temp==2) insert(1,1,n*m,d[j-1]+1,d[j],-1);
else if(temp==3) insert(1,1,n*m,d[j-1]+1,d[j],1);
else if(temp==4) insert(1,1,n*m,d[j-1]+1,d[j],-1);
}
signed main()
{
freopen("pig.in","r",stdin); freopen("pig.out","w",stdout);
n=read(); m=read(); build(1,1,n*m);
for(int i=0;i<=m+1;i++) s[0].push_back(n*m+1),s[n+1].push_back(n*m+1);
for(int i=1;i<=n;i++) s[i].push_back(n*m+1);
for(int i=1;i<=n;i++)for(int j=1,x;j<=m;j++) x=read(),s[i].push_back(x),id[x]=make_pair(i,j);
for(int i=1;i<=n;i++) s[i].push_back(n*m+1);
for(int i=1;i<=n*m;i++)
{
int x=id[i].first,y=id[i].second,pos;
d[1]=s[x-1][y];d[2]=s[x][y-1];d[3]=s[x-1][y-1];d[4]=i;work(i);
d[1]=s[x-1][y];d[2]=s[x][y+1];d[3]=s[x-1][y+1];d[4]=i;work(i);
d[1]=s[x+1][y];d[2]=s[x][y-1];d[3]=s[x+1][y-1];d[4]=i;work(i);
d[1]=s[x+1][y];d[2]=s[x][y+1];d[3]=s[x+1][y+1];d[4]=i;work(i);
if(tre[1].dat==4) ans=(ans+i*tre[1].cnt%mod-tre[1].sum+tre[1].cnt+mod)%mod;
}
printf("%lld",ans);
return 0;
}
T4 抑郁刀法
欲学此法，必先抑郁，由于我还没有抑郁，因此。。。