noip模拟52(联赛后知识待补)

A. 异或

签到题.

A_code
#include<bits/stdc++.h>
using namespace std;
namespace BSS
{
	#define ll long long int
	#define lf double
	#define lbt(x) (x&(-x))
	#define re register ll
	#define ull unsigned ll
	#define mp make_pair
	#define lb lower_bound 
	#define ub upper_bound 
	#define Fill(x,y) memset(x,y,sizeof x)
	#define Copy(x,y) memcpy(x,y,sizeof x)
	#define File(x,y) freopen(#x,"r",stdin),freopen(#y,"w",stdout)
	inline ll read()
	{
		ll ss=0; bool cit=1; char ch;
		while(!isdigit(ch=getchar())) if(ch==‘-‘) cit=0;
		while(isdigit(ch)) ss=(ss<<3)+(ss<<1)+(ch^48),ch=getchar();
		return cit?ss:-ss;
	}
} using namespace BSS;

const ll N=775;

ll n,m,ans,lg2;
ll pre[N]; // pre 记作 2^i -1 的前缀和
unordered_map<ll,ll> mp1;
signed main(){
	n=read(),lg2=log2(n)+1,pre[0]=1,mp1[1]=0;
	for(ll i=1;i<=lg2;i++){
		pre[i]=(pre[i-1]<<1ll)+1ll;
		mp1[1ll<<i]=i;
	}
	while(n){
		ans+=pre[mp1[lbt(n)]],n-=lbt(n);
	}
	printf("%lld\n",ans);
	exit(0);
}

B. 赌神

思路来自 \(Yubai\) .

我们可以发现一个通常且很实用的结论:
如果我们选择了最优策略,
那么无论黑手如何操作,我们的结果都会最优.
亦为恒优策略.
注:结论发掘于 \(Yubai\)

所以我们的策略是固定的.
考虑这个策略是什么.
我们发现样例解释是按比例分配的.
于是我们提出猜想:是不是按比例做题就可以.
大量事实举例发现确实,于是本题做完了.

B_code
#include<bits/stdc++.h>
using namespace std;
namespace BSS
{
	#define ll long long int
	#define ull unsigned ll 
	#define re register ll 
	#define lf double
	#define lb lower_bound 
	#define ub upper_bound 
	#define mp make_pair
	#define File(x,y) freopen(#x,"r",stdin),freopen(#y,"w",stdout)
	#define Fill(x,y) memset(x,y,sizeof x);
	#define Copy(x,y) memcpy(x,y,sizeof x);
	inline ll read()
	{
		ll ss=0; bool cit=1; char ch;
		while(!isdigit(ch=getchar())) if(ch==‘-‘) cit=0;
		while(isdigit(ch)) ss=(ss<<3)+(ss<<1)+(ch^48),ch=getchar();
		return cit?ss:-ss;
	}
} using namespace BSS;

const ll N=1e6+21,mod=998244353;

ll m,n,ans=1;
ll c[N],pre[N];
inline ll ksm(ll a,ll b,ll c){
	a%=c; ll res=1;
	while(b){
		if(b&1) res=(res*a)%c;
		a=(a*a)%c,b>>=1;
	}
	return res%c;
}
signed main(){
	n=read(); for(re i=1;i<=n;i++) c[i]=read(),pre[i]=pre[i-1]+c[i];
	for(re i=1;i<n;i++){
		while(c[i]) ans=(ans*n%mod*c[i]%mod*ksm(c[i]+pre[n]-pre[i],mod-2,mod)%mod),c[i]--;
	}
	ans=ans*ksm(n,c[n],mod)%mod; printf("%lld\n",ans);
	exit(0);
}

C. 路径

斯特林数,鸽了,好像 \(ftt\) 也可做.

D. 树

发现直接做很难..看到了取模,于是可以考虑一下剩余系.
好像确实有一点这样的思想,但是思想主体仍然为分块.
考虑将询问与答案与模数和模剩下的对应起来就行了.
很难叙述,但是比较好想.

D_code
#include<bits/stdc++.h>
using namespace std;
namespace BSS
{
	#define ll long long int
	#define ull unsigned ll 
	#define re register ll 
	#define lf double
	#define lb lower_bound 
	#define ub upper_bound 
	#define mp make_pair
	#define File(x,y) freopen(#x,"r",stdin),freopen(#y,"w",stdout)
	#define Fill(x,y) memset(x,y,sizeof x)
	#define Copy(x,y) memcpy(x,y,sizeof x)
	inline ll read()
	{
		ll ss=0; bool cit=1; char ch;
		while(!isdigit(ch=getchar())) if(ch==‘-‘) cit=0;
		while(isdigit(ch)) ss=(ss<<3)+(ss<<1)+(ch^48),ch=getchar();
		return cit?ss:-ss;
	}
} using namespace BSS;

const ll N=6e5+21,M=651;

ll n,m,ts,cnt,bos,ops;
ll head[N],dfn[N],siz[N],rk[N],fa[N],dep[N],bl[N],val[N],ans[N];
struct I { ll u,v,nxt; } e[N<<1];
struct II { ll opt,u,x,y,z; } q[N];
inline void add(ll u,ll v){
	e[++ts].u=u,e[ts].v=v,e[ts].nxt=head[u],
	head[u]=ts;
}
void dfs(ll u,ll dad,ll depth){
	fa[u]=dad,dep[u]=depth,siz[u]=1,
	dfn[u]=++cnt,rk[cnt]=u;
	for(re i=head[u];i;i=e[i].nxt){
		if(e[i].v==dad) continue;
		dfs(e[i].v,u,depth+1);
		siz[u]+=siz[e[i].v];
	}
	return ;
}
struct Work_1 {
	ll lzy[M]; vector<ll> vec[M][M];
	inline void update(ll l,ll r,ll w){
		ll lmt=min(bl[l]*bos,r);
		for(re i=l;i<=lmt;i++) val[i]+=w;
		for(re i=bl[l]+1;i<=bl[r]-1;i++) lzy[i]+=w;
		if(bl[l]!=bl[r])
			for(re i=(bl[r]-1)*bos+1;i<=r;i++) val[i]+=w;
	}
	inline ll query(ll x){ return val[x]+lzy[bl[x]]; }
	inline void Work(){
		for(re i=1;i<=bos;i++)
			for(re j=0;j<=i-1;j++){
				for(auto k : vec[i][j]){
					if(q[k].opt&1)
						update(dfn[q[k].u],dfn[q[k].u]+siz[q[k].u]-1,q[k].z);
					else
						ans[k]+=query(dfn[q[k].u]);
				}
				for(auto k : vec[i][j]){
					if(q[k].opt&1)
						update(dfn[q[k].u],dfn[q[k].u]+siz[q[k].u]-1,-q[k].z);
				}
			}
		Fill(val,0);
	}
} A;
struct Work_2 { 
	ll cf[N]; vector<ll> vec[M];
	inline void update(ll l,ll r,ll w){
		val[l]+=w,val[r+1]-=w;
		cf[bl[l]]+=w,cf[bl[r+1]]-=w;
	}
	inline ll query(ll l,ll r){
		ll res=0,lmt=min(bl[l]*bos,r);
		for(re i=l;i<=lmt;i++) res+=val[i];
		for(re i=bl[l]+1;i<=bl[r]-1;i++) res+=cf[i];
		if(bl[l]!=bl[r]) 
			for(re i=(bl[r]-1)*bos+1;i<=r;i++) res+=val[i];
		return res;
	}
	inline void Work(){
		ll l,r;
		for(re i=1;i<=bl[n];i++){
			l=(i-1)*bos+1,r=min(i*bos,n);
			for(int j=1;j<=ops;j++){
				if(q[j].opt&1){
					if(q[j].x<=bos) continue;
					if(l%q[j].x<=r%q[j].x){
						if(l%q[j].x<=q[j].y and q[j].y<=r%q[j].x)
							vec[q[j].y-l%q[j].x+1].push_back(j);
					}
					else{
						if(q[j].y<=r%q[j].x)   
							vec[q[j].y+q[j].x-l%q[j].x+1].push_back(j);
						else{
							if(q[j].y<=r%q[j].x)
								vec[q[j].y+q[j].x-l%q[j].x+1].push_back(j);
							else
								if(q[j].y<=r%q[j].x)
									vec[q[j].y+q[j].x-l%q[j].x+1].push_back(j);
								else if(q[j].y>=l%q[j].x)
									vec[q[j].y-l%q[j].x+1].push_back(j);
						}
					}
				}
				else{
					if(l<=dep[q[j].u] and dep[q[j].u]<=r){
						if(vec[dep[q[j].u]-l+1].size())
							vec[dep[q[j].u]-l+1].push_back(j);
					}
				}
			}
			for(re j=l;j<=r;j++){
				for(auto k : vec[j-l+1]){
					if(q[k].opt&1) update(dfn[q[k].u],dfn[q[k].u]+siz[q[k].u]-1,q[k].z);
					else ans[k]+=query(1,dfn[q[k].u]);
				}
				for(auto k : vec[j-l+1])
					if(q[k].opt&1) update(dfn[q[k].u],dfn[q[k].u]+siz[q[k].u]-1,-q[k].z);
				vec[j-l+1].clear();
			}
		}
	}
} B;		
signed main(){
	n=read(),ops=read(),bos=sqrt(n); ll u,v;
	for(re i=2;i<=n;i++) u=read(),v=read(),add(u,v),add(v,u);
	for(re i=1;i<=n+1;i++) bl[i]=(i-1)/bos+1;
	dfs(1,0,1);
	for(int i=1;i<=ops;i++){
		q[i].opt=read();
		if(q[i].opt&1){
			q[i].u=read(),q[i].x=read(),q[i].y=(read()+dep[q[i].u])%q[i].x,q[i].z=read();
			if(q[i].x<=bos) A.vec[q[i].x][q[i].y].push_back(i);
		}
		else{
			q[i].u=read();
			for(re j=1;j<=bos;j++){
				if(A.vec[j][dep[q[i].u]%j].size()) 
					A.vec[j][dep[q[i].u]%j].push_back(i);
			}
		}
	}
	A.Work(),B.Work();
	for(re i=1;i<=ops;i++){
		if(q[i].opt&2) printf("%lld\n",ans[i]);
	}
	exit(0);
}

noip模拟52(联赛后知识待补)

上一篇:基于ECS搭建FTP服务


下一篇:Linux学习记录--ACL权限控制