JZTXT

23.8.7 NOIP模拟赛

发布时间 2023-08-07 16:29:12作者: Shui_dream

纯菜，100+90+0+40。

T1

不会正解，发现每个位置 \(i\) 可以转到的位置 可以表示成 \(l,l+2,l+4...r\)

code ``` #include #define psb push_back typedef long long LL; using namespace std; const int N=1e5+5,M=2e6+5; vector> vt[M]; int n,k,m,S,gn,bd[N]; bool sp[N]; struct subT{ int bid[N<<2],fd[N]; void build(int p,int L,int R){ if(L==R) { fd[L]=bid[p]=++gn; return ;} bid[p]=++gn; int mid=(L+R)/2; build(p<<1,L,mid); build(p<<1|1,mid+1,R); vt[bid[p]].psb({bid[p<<1],0}); vt[bid[p]].psb({bid[p<<1|1],0}); } void Adde(int p,int L,int R,int lt,int rt,int s){ if(L>rt || Rrt) return ; if(L>=lt && R<=rt) { vt[s].psb({bid[p],0}); return; } int mid=(L+R)/2; Adde(p<<1,L,mid,lt,rt,s); Adde(p<<1|1,mid+1,R,lt,rt,s); } } T[2]; int f[M]; void BFS(){ deque q; q.psb(bd[S]); memset(f,-1,sizeof(f)); f[bd[S]]=0; while(!q.empty()){ int u=q.front(); q.pop_front(); for(auto i:vt[u]){ int v=i.first,w=i.second; if(f[v]!=-1) continue; f[v]=f[u]+w; if(w==0) q.push_front(v); else q.psb(v); } } } int main(){ scanf("%d%d%d%d",&n,&k,&m,&S); for(int i=1,x;i<=m;i++){ scanf("%d",&x); sp[x]=1;} T[0].build(1,1,n); T[1].build(1,1,n); for(int i=1;i<=n;i++){ bd[i]=T[i%2].fd[i]; if(sp[i]) continue; int p=++gn; vt[bd[i]].psb({p,1}); int lt=(i>=k)?i-(k-1):k-i+1; int rt=(i<=n-k+1)?i+(k-1):n-k+(n-i+1); T[(i%2) ^ (k%2==0)].Adde(1,1,n,lt,rt,p); } BFS(); for(int i=1;i<=n;i++){ if(sp[i]) f[bd[i]]=-1; printf("%d ",f[bd[i]]); } return 0; } ```
code 
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int N=1e6+5;
char ch[N];
int s1[N],s2[N],n;
struct date{
	int a,b,id;
} q1[N],q2[N];
bool cmp(date x,date y){
	return x.b>y.b;
}
struct Bit{
	int fd[2*N];
	inline void Addx(int x,int w){
		x+=n+1;
		for(int i=x;i<=2*n+2;i+=i & -i)
			fd[i]+=w;
	}
	inline int Ask(int x){
		x+=n+1; int y=0;
		for(int i=x;i;i-=i & -i)
			y+=fd[i];
		return y;
	}
	inline void clr(int x){
		x+=n+1;
		for(int i=x;i<=2*n+2;i+=i & -i)
			fd[i]=0;
	}
} T[2];
LL ans=0;
void CDQ(int L,int R){
	if(L==R) return ;
	int mid=(L+R)/2;
	int mn1=1e9,mn2=1e9,t1=0,t2=0;
	for(int i=mid+1;i<=R;i++){
		mn1=min(mn1,s1[i]); mn2=min(mn2,s2[i]);
		if(mn2>=s2[i+1]) q1[++t1]=(date){mn1,s2[i+1],i};
	}
	mn1=1e9,mn2=1e9;
	for(int i=mid;i>=L;i--){
		mn1=min(mn1,s1[i]); mn2=min(mn2,s2[i]);
		if(mn1>=s1[i-1]) q2[++t2]=(date){s1[i-1],mn2,i};
	}
	sort(q1+1,q1+t1+1,cmp); sort(q2+1,q2+t2+1,cmp);
	for(int i=1,j=1;i<=t1;i++){
		while(j<=t2 && q2[j].b>=q1[i].b)  T[q2[j].id%2].Addx(q2[j].a,1) ,j++;
		ans+= T[1-q1[i].id%2].Ask(q1[i].a);
	}
	for(int i=1;i<=t2;i++) T[q2[i].id%2].clr(q2[i].a);
	CDQ(L,mid); CDQ(mid+1,R);
}
int main(){
	scanf("%s",ch+1); n=strlen(ch+1);
	for(int i=1;i<=n;i++) s1[i]=s1[i-1]+((ch[i]==')')?-1:1);
	for(int i=n;i>=1;i--) s2[i]=s2[i+1]+((ch[i]=='(')?-1:1);
	CDQ(1,n);
	printf("%lld",ans);
	return 0;
}
code 
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
typedef long long LL;
using namespace std;
const int N=7505;
char ch[N];
int n,c[N],tt; LL ans;
struct BIT{
	LL fd[N<<1];
	LL ask(int x){
		int y=0;
		for(int i=x;i;i-=i & -i) y+=fd[i];
		return y;
	}
	void addx(int x,int w){
		for(int i=x;i<=2*n;i+=i & -i) fd[i]+=w;
	}
	void clr(){
		for(int i=1;i<=2*n;i++) fd[i]=0;
	}
} T1,T2;
int main(){
	scanf("%s",ch+1); n=strlen(ch+1);
	int ssg=0;
	for(int i=1;i<=n;i++) ssg+=(ch[i]=='G');
	if(ssg>n/2) for(int i=1;i<=n;i++) ch[i]=(ch[i]=='G')?'H':'G';
	for(int l=1;l<=n;l++){
		tt=0;
		for(int r=l;r<=n;++r){
			if(ch[r]=='G') c[++tt]=r;
			if(tt%2 && (r-l+1)%2==0) ans+=-1;
			else if(tt%2) ans+=(abs((l+r)/2-c[(tt+1)/2]));
		}
	}
	tt=0;
	for(int i=1;i<=n;i++) if(ch[i]=='G') c[++tt]=i;
	c[tt+1]=n+1;
	for(int i=1;i<=tt;i++){
		T1.clr(); T2.clr();  LL res=0;
		for(int j=1;i-j>=1 && i+j<=tt;++j){
			int p=c[i-j]+c[i+j];
			T1.addx(p,1); T2.addx(p,p);
			res+=p;
			for(int L=c[i-j-1]+1;L<=c[i-j];L++)
				for(int R=c[i+j];R<=c[i+j+1]-1;R++){
					if((R-L+1)%2==0) continue;
					LL s1=T1.ask(L+R),s2=T2.ask(L+R);
					ans+=s1*(L+R)-s2; ans+=(res-s2)-(j-s1)*(L+R);
				}
		}
	}	
	for(int i=1;i<tt;i++){
		T1.clr(); T2.clr(); LL res=0;
		for(int j=0;i-j>=1 && i+1+j<=tt;j++){
			int p=c[i-j]+c[i+1+j];
			T1.addx(p,1); T2.addx(p,p);
			res+=p;
			for(int L=c[i-j-1]+1;L<=c[i-j];L++)
				for(int R=c[i+1+j];R<=c[i+1+j+1]-1;R++){
					LL s1=T1.ask(L+R),s2=T2.ask(L+R);
					ans+=s1*(L+R)-s2; ans+=(res-s2)-(j+1-s1)*(L+R);
				}
		}
	}
	
	printf("%lld",ans);
	return 0;
}
code 
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int M=1<<16,Mod=998244353,MM=14348910;
LL Pow(LL x,LL k){
	LL xx=1;
	while(k){
		if(k & 1) xx=xx*x%Mod;
		x=x*x%Mod; k>>=1;
	}
	return xx;
}
const int iv4=Pow(10000,Mod-2);
int m,n,S,a[M],pw[17]; LL p[17],fp[M],ans[M];
int gd[MM],mi[MM],mg[MM],vl[MM];
void vmain(){
	scanf("%d%d",&m,&n); S=1<<m;
	for(int i=0,x;i<m;i++) {scanf("%d",&x); p[i]=1ll*x*iv4%Mod;}
	for(int i=1;i<S;i++){
		LL p1=1;
		for(int j=0;j<m;j++)
			if((i>>j) & 1) p1=p1*(1+Mod-p[j])%Mod;
		fp[i]=p1*Pow(Mod+1-p1,Mod-2)%Mod;
	}
	LL ss=0;
	for(int i=S-1;i>=0;i--){
		int x=(S-1) ^ i;
		for(int j=x;j;j=(j-1) & x)
			fp[i]=(fp[i]+Mod-fp[i^j])%Mod;
		if(i==0) fp[i]=0;
		ss=(ss+fp[i])%Mod;
	}
	for(int i=1,x;i<=n;i++) {
		scanf("%d",&x); a[i]=0; if(n==1) continue;
		for(int j=0;j<m;j++) a[i]+=pw[j]*(((x>>j) & 1)?1:0);
		gd[a[i]]=i; ans[i]=(ss+1)%Mod;
	}
	if(n==1) {puts("0"); return ;}
	for(int i=0;i<pw[m];i++){
		if(mi[i]<m) {
			vl[i]=vl[i-pw[mi[i]]]^(1<<mi[i]);
			int nxt=i-pw[mi[i]];
			if(gd[i]==0) gd[i]=gd[nxt];
			else if(gd[nxt]!=gd[i] && gd[nxt]!=0) gd[i]=-1;
			nxt=i-2*pw[mi[i]];
			if(gd[i]==0) gd[i]=gd[nxt];
			else if(gd[nxt]!=gd[i] && gd[nxt]!=0) gd[i]=-1;
		}
		else vl[i]=(1<<m)-1;
	}
	for(int i=0;i<pw[m];i++){
		if(gd[i]>0 && vl[i]) ans[gd[i]]=(ans[gd[i]]+Mod-fp[(S-1) ^ vl[i]])%Mod;
		gd[i]=0;
	}
	for(int i=1;i<=n;i++) printf("%lld\n",ans[i]);
}
int main(){
	pw[0]=1;
	for(int i=1;i<=15;i++) pw[i]=pw[i-1]*3;
	mi[0]=0;
	for(int i=0;i<15;i++){
		for(int j=0;j<pw[i];j++){
			mg[j*3+0]=mi[j]+1;
			mg[j*3+1]=mi[j]+1;
			mg[j*3+2]=0;
		}
		for(int j=0;j<pw[i+1];j++){
			mi[j]=mg[j];
			mg[j]=0;
		}
	}
	int T; scanf("%d",&T); while(T--) vmain();
	return 0;
}