noip模拟51 solutions
好像是和别的学校一起考得
然后我交错比赛了，变成了\(IOI\)赛制，交上去就是俩\(AC\)
所以这次的题前两个过于水了。。。。
T1 茅山道术
就是找在当前条件下的，序列不重合划分的方案数，直接\(DP\),类似前缀和优化一下
AC_code
#include<bits/stdc++.h>
using namespace std;
#define re register int
const int N=1e6+5;
const int mod=1e9+7;
int n,c[N];
vector<int> vec[N];
int dp[N],sum[N],pos[N];
signed main(){
freopen("magic.in","r",stdin);
freopen("magic.out","w",stdout);
scanf("%d",&n);
for(re i=1;i<=n;i++)scanf("%d",&c[i]);
n=unique(c+1,c+n+1)-c-1;
for(re i=1;i<=n;i++)vec[c[i]].push_back(i),pos[i]=vec[c[i]].size()-1;
dp[0]=0;
for(re i=1;i<=n;i++){
dp[i]=dp[i-1];
if(pos[i])dp[i]=(dp[i]+sum[vec[c[i]][pos[i]-1]-1]+pos[i])%mod;
if(pos[i])sum[i-1]=(dp[i-1]+sum[vec[c[i]][pos[i]-1]-1])%mod;
else sum[i-1]=dp[i-1];
//cout<<dp[i]<<" "<<sum[i-1]<<" "<<sum[vec[c[i]][pos[i]-1]-1]<<" "<<pos[i]<<endl;
}
//cout<<endl;
printf("%d",dp[n]+1);
}
T2 泰拳警告
直接找规律，然后统计答案就好了
枚举平了多少局，后面第一个人必须胜一半以上
AC_code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register int
const int N=3e6+5;
const int mod=998244353;
int n,p,pf[N],pg[N],jc[N],inv[N],ans,n2,m2[N];
int ksm(int x,int y){
int ret=1;
while(y){
if(y&1)ret=ret*x%mod;
x=x*x%mod;
y>>=1;
}
return ret;
}
int C(int x,int y){
return jc[x]*inv[y]%mod*inv[x-y]%mod;
}
signed main(){
freopen("fight.in","r",stdin);
freopen("fight.out","w",stdout);
scanf("%lld%lld",&n,&p);
pf[0]=pg[0]=1;n2=ksm(2,mod-2);
pf[1]=ksm(p+2,mod-2);pg[1]=p*ksm(p+2,mod-2)%mod;
jc[0]=jc[1]=1;m2[0]=1;m2[1]=2;
for(re i=2;i<=n;i++){
pf[i]=pf[i-1]*pf[1]%mod;
pg[i]=pg[i-1]*pg[1]%mod;
jc[i]=jc[i-1]*i%mod;
m2[i]=m2[i-1]*2%mod;
}
inv[0]=1;inv[n]=ksm(jc[n],mod-2);
for(re i=n-1;i>=1;i--)inv[i]=inv[i+1]*(i+1)%mod;
//cout<<ksm(9,mod-2)<<" "<<ksm(3,mod-2)<<endl;
for(re i=0;i<=n;i++){
int tmp;
if((n-i)&1)tmp=m2[n-i]*n2%mod*C(n,i)%mod;
else tmp=(m2[n-i]*n2%mod+mod-C(n-i,n-i>>1)*n2%mod)%mod*C(n,i)%mod;
ans=(ans+pg[i]*pf[n-i]%mod*(i+1)%mod*tmp%mod)%mod;
//cout<<pf[i]<<" "<<pg[n-i]<<" "<<ans<<endl;
}
printf("%lld",ans);
}
T3 万猪拱塔
首先看题要看准，\(k\)是互不相同的
所以我当前矩形的数一定是一个连续的区间
直接枚举这个区间判断是否构成矩形
按着题解上说的，枚举右端点，更新所在的四个小矩形，线段树
AC_code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register int
const int N=2e5+5;
const int mod=998244353;
int n,m,ans,rp;
vector<int> jz[N],id[N];
struct position{
int i,j;
position(){}
position(int x,int y){i=x;j=y;}
}ti[N];
struct XDS{
#define ls x<<1
#define rs x<<1|1
int sum[N*4],csm[N*4],res[N*4],tag[N*4];
int re_csm,re_res;
void pushup(int x){
sum[x]=min(sum[ls],sum[rs]);csm[x]=0;res[x]=0;
if(sum[x]==sum[ls])csm[x]+=csm[ls],res[x]+=res[ls];
if(sum[x]==sum[rs])csm[x]+=csm[rs],res[x]+=res[rs];
}
void pushdown(int x){
if(!tag[x])return ;
tag[ls]+=tag[x];
tag[rs]+=tag[x];
sum[ls]+=tag[x];sum[rs]+=tag[x];
tag[x]=0;
}
void build(int x,int l,int r){
if(l==r){
csm[x]=1;sum[x]=0;res[x]=l;
return ;
}
int mid=l+r>>1;
build(ls,l,mid);
build(rs,mid+1,r);
pushup(x);
return ;
}
void ins(int x,int l,int r,int ql,int qr,int v){
if(ql>qr)return ;
if(ql<=l&&r<=qr){
sum[x]+=v;tag[x]+=v;
return ;
}
pushdown(x);
int mid=l+r>>1;
if(ql<=mid)ins(ls,l,mid,ql,qr,v);
if(qr>mid)ins(rs,mid+1,r,ql,qr,v);
pushup(x);return ;
}
void query(int x,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr){
if(sum[x]==4)re_csm+=csm[x],re_res+=res[x];
return ;
}
pushdown(x);
int mid=l+r>>1;
if(ql<=mid)query(ls,l,mid,ql,qr);
if(qr>mid)query(rs,mid+1,r,ql,qr);
pushup(x);
}
#undef ls
#undef rs
}xds;
int ji[5],cnt;
signed main(){
freopen("pig.in","r",stdin);
freopen("pig.out","w",stdout);
scanf("%lld%lld",&n,&m);
jz[0].resize(m+5);jz[n+1].resize(m+5);
for(re i=1;i<=n;i++){
jz[i].resize(m+5);
id[i].resize(m+5);
for(re j=1;j<=m;j++){
scanf("%lld",&jz[i][j]);
ti[jz[i][j]]=position(i,j);
}
}
//cout<<"Sb"<<endl;
xds.build(1,1,n*m);
for(re i=1;i<=n*m;i++){
int x=ti[i].i,y=ti[i].j;
cnt=0;
if(jz[x-1][y-1]<i)ji[++cnt]=jz[x-1][y-1];
if(jz[x][y-1]<i)ji[++cnt]=jz[x][y-1];
if(jz[x-1][y]<i)ji[++cnt]=jz[x-1][y];
sort(ji+1,ji+cnt+1);
xds.ins(1,1,n*m,ji[cnt]+1,i,1);
for(re j=cnt,bas=-1;j>=1;j--)xds.ins(1,1,n*m,ji[j-1]+1,ji[j],bas),bas=-bas;
cnt=0;
if(jz[x-1][y+1]<i)ji[++cnt]=jz[x-1][y+1];
if(jz[x][y+1]<i)ji[++cnt]=jz[x][y+1];
if(jz[x-1][y]<i)ji[++cnt]=jz[x-1][y];
sort(ji+1,ji+cnt+1);
xds.ins(1,1,n*m,ji[cnt]+1,i,1);
for(re j=cnt,bas=-1;j>=1;j--)xds.ins(1,1,n*m,ji[j-1]+1,ji[j],bas),bas=-bas;
cnt=0;
if(jz[x+1][y-1]<i)ji[++cnt]=jz[x+1][y-1];
if(jz[x][y-1]<i)ji[++cnt]=jz[x][y-1];
if(jz[x+1][y]<i)ji[++cnt]=jz[x+1][y];
sort(ji+1,ji+cnt+1);
xds.ins(1,1,n*m,ji[cnt]+1,i,1);
for(re j=cnt,bas=-1;j>=1;j--)xds.ins(1,1,n*m,ji[j-1]+1,ji[j],bas),bas=-bas;
cnt=0;
if(jz[x+1][y+1]<i)ji[++cnt]=jz[x+1][y+1];
if(jz[x][y+1]<i)ji[++cnt]=jz[x][y+1];
if(jz[x+1][y]<i)ji[++cnt]=jz[x+1][y];
sort(ji+1,ji+cnt+1);
xds.ins(1,1,n*m,ji[cnt]+1,i,1);
for(re j=cnt,bas=-1;j>=1;j--)xds.ins(1,1,n*m,ji[j-1]+1,ji[j],bas),bas=-bas;
xds.re_csm=xds.re_res=0;
xds.query(1,1,n*m,1,i);
//cout<<xds.re_res<<" "<<xds.re_csm<<endl;
(ans+=1ll*i*xds.re_csm-xds.re_res+xds.re_csm)%=mod;
}
printf("%lld",ans);
}