CSP模拟5

T1光

我们来考虑一个格加 \(4\) 或者减 \(4\) ,这样有一个比较好的性质，它能提供 \(4,2,2,1\) 的贡献还不会溢出，这样我们就有一个比较好的思路，我们枚举 \(4,2,2,1\) 所无法造成的贡献，很明显只有 \(16\) 种，然后我们就可以再枚举 \(4,2,2,1\) 来算贡献.

点击查看代码

#include<bits/stdc++.h>
using namespace std;const int N=2000;
int s[5];int read()
{int f=1,s=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+(ch^48);ch=getchar();}return f*s;
}int solve(int a,int b,int c,int d)
{int maxx=max({a,b,c,d}),cnt=0;while(maxx>0){cnt++;maxx=max({a,b,c,d});if(maxx==a) a-=4,b-=2,c-=2,d-=1;else if(maxx==b) b-=4,a-=2,d-=2,c-=1;else if(maxx==c) c-=4,a-=2,d-=2,b-=1;else if(maxx==d) d-=4,c-=2,b-=2,a-=1;}return cnt*4;
}int main()
{freopen("light.in","r",stdin);freopen("light.out","w",stdout);for(int i=1;i<=4;i++) s[i]=read();int ans=1e9;for(int i=0;i<=3;i++){for(int j=0;j<=3;j++){for(int k=0;k<=3;k++){for(int l=0;l<=3;l++){ans=min(ans,i+j+k+l+solve(s[1]-(i+j/2+k/2+l/4),s[2]-(j+i/2+l/2+k/4),s[3]-(k+i/2+l/2+j/4),s[4]-(l+k/2+j/2+i/4)));}}}}printf("%d",ans-4);}

T2爬

又是喜闻乐见（丧心病狂）的分讨，那不墨迹了，直接开始。

我们很明显可以得到一个结论：把所有数拆成二进制，我们把我们目前枚举到的节点及其子节点看成一个整体，目前我们枚举到了二进制的第 \(m\) 位，则可以感性理解一下异或操作，当这一位上出现奇数个 \(1\) 的时候，这一位才会造成贡献。

那很好，我们开始分讨。

情况一：当前遍历到的节点不是根节点，那我们设它这个集合有 \(cnt\) 个元素，第 \(m\) 位上有 \(tot\) 个 \(1\) ，则为 \(0\) 的个数为 \(cnt-tot\) 个，除去这些数还有 \(n-cnt\) 个数，则它造成的贡献为 \((1<<m)*(2^{tot-1}*2^{cnt-tot}*2^{n-cnt-1}-tot*2^{n-cnt-1})\)

解释一下：首先考虑选奇数个 \(1\) 的方案应该为 \(C^{1}_{tot}+C_{tot}^{3}+...+C_{tot}^{2n-1}\) ，感性理解一下这个东西应该等于 \(2^{tot-1}\) ，那再考虑这个集合里 \(m\) 位为 \(0\) 的方案数，很显然为 \(2^{cnt-tot}\) ，在考虑这个集合外其他数的方案 \(2^{n-cnt-1}\) ，由于根节点不能动，所以减去 \(1\) ,至于为什么要减去后面那一坨，因为题目中规定了当节点上只有一个数的时候，它不造成贡献，那该节点上只有一个数的方案数应该为 \(tot*2^{n-cnt-1}\).

情况二：当遍历的节点为根节点的时候且根节点第 \(m\) 上为 \(1\),这不再解释了 \((1<<m)*(2^{tot-2}*2^{cnt-tot}*2^{n-cnt}-1*2^{n-cnt})\) .

情况三：当遍历的节点为根节点的时候且根节点第 \(m\) 上为 \(0\) ，贡献是\((1<<m)*2^{tot-1}*2^{cnt-tot-1}*2^{n-cnt}\) .

点击查看代码

#include<bits/stdc++.h>
using namespace std;#define int long long
const int N=3e5+107;
const int mod=1e9+7;
int n,a[N];int read()
{int f=1,s=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+(ch^48);ch=getchar();}return f*s;
}int h[N],to[N],nxt[N],tot;
void add(int x,int y)
{to[++tot]=y;nxt[tot]=h[x];h[x]=tot;
}int q(int a,int b)
{int ans=1;while(b){if(b&1) ans=ans*a%mod;b=b>>1;a=a*a%mod;}return ans;
}int ans;
int s[N],cnt,num[60];
bitset<60> b[N];
void dfs(int u,int fa)
{for(int i=h[u];i;i=nxt[i]){int v=to[i];if(v==fa) continue;dfs(v,u);}cnt=0;for(int i=h[u];i;i=nxt[i]){int v=to[i];if(v==fa) continue;s[++cnt]=v;}s[++cnt]=u;memset(num,0,sizeof num);for(int i=1;i<=cnt;i++){for(int j=0;j<=40;j++){if(b[s[i]][j]) num[j]++;}}
//	cout<<u<<" "<<cnt<<endl;
//	for(int i=0;i<=5;i++)
//	{
//		cout<<num[i]<<" ";
//	}cout<<endl;if(u!=1){for(int i=0;i<=40;i++){int tot=num[i];if(tot>=1) ans=(ans+q(2,i)*(q(2,tot-1)*q(2,cnt-tot)%mod*q(2,n-cnt-1)%mod-q(2,n-cnt-1)*tot%mod+mod)%mod)%mod;}}else{for(int i=0;i<=40;i++){int tot=num[i];if(b[s[cnt]][i]==1){if(tot>=2) ans=(ans+q(2,i)*(q(2,tot-2)*q(2,cnt-tot)%mod*q(2,n-cnt)%mod-1*q(2,n-cnt)+mod)%mod)%mod;if(tot==1) ans=(ans+q(2,i)*(q(2,cnt-tot)%mod*q(2,n-cnt)%mod-1*q(2,n-cnt)+mod)%mod)%mod;}else {if(tot>=1) ans=(ans+q(2,i)*q(2,tot-1)%mod*q(2,cnt-tot-1)%mod*q(2,n-cnt)%mod)%mod;}
//			cout<<ans<<endl;}}
//	cout<<ans<<endl;
}signed main()
{freopen("climb.in","r",stdin);freopen("climb.out","w",stdout);n=read();for(int i=1;i<=n;i++) a[i]=read(),b[i]=a[i];for(int i=2;i<=n;i++) {int fa=read();add(i,fa);add(fa,i);}dfs(1,0);printf("%lld\n",ans);
}

T3字符串

直接按照题解模拟就行了。

点击查看代码

#include<bits/stdc++.h>
using namespace std;#define int long long
const int N=4e5+107;
int n,m,a,b,c;int read()
{int f=1,s=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+(ch^48);ch=getchar();}return f*s;
}signed main()
{freopen("string.in","r",stdin);freopen("string.out","w",stdout);int T=read();while(T--){n=read(),m=read(),a=read(),b=read(),c=read();int res=0;for(int i=0;i<=min(n,m/c);i++){int ans=i*2;ans+=(c-1)/b*i;int x=n-i,y=m-i*c;if(x<0||y<0) break;if(x>=1) x--,ans++,ans+=x/a;if(y>=1) y--,ans++;int z=(((c-1)/b+1)*b-(c-1));if(y>=z*i){y-=i*z;ans+=i;ans+=y/b;}else if(y<z*i){while(y>=z) y-=z,ans++;}res=max(res,ans);}printf("%lld\n",res);}}

T4奇怪的函数

知道这个函数是一个分段函数之后，这题就没啥了，直接分块维护边界即可。

这个函数大概长成这样

点击查看代码

#include<bits/stdc++.h>
using namespace std;#define int long long
const int N=4e5+107;
const int inf=1e18;
int n,q;int read()
{int f=1,s=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+(ch^48);ch=getchar();}return f*s;
}struct Func
{int l,r;int t;
}func[N];struct lmy
{int op,val;
}s[N];void get_func(int id,int op,int val)
{if(op==1) func[id].t+=val,func[id].l+=val,func[id].r+=val;if(op==2) func[id].l=min(func[id].l,val),func[id].r=min(func[id].r,val);if(op==3) func[id].l=max(func[id].l,val),func[id].r=max(func[id].r,val);return ;
}int li[N],ri[N],bel[N];
void fk()
{int sq=sqrt(n);for(int i=1;i<=sq;i++){li[i]=ri[i-1]+1;ri[i]=sq*i;if(i==sq) ri[i]=n;func[i]={-inf,inf,0};for(int j=li[i];j<=ri[i];j++){bel[j]=i;get_func(i,s[j].op,s[j].val);}
//		cout<<func[i].l<<" "<<func[i].r<<" "<<func[i].t<<endl;}
}void update(int pos,int op,int val)
{s[pos]={op,val},func[bel[pos]]={-inf,inf,0};for(int i=li[bel[pos]];i<=ri[bel[pos]];i++){get_func(bel[pos],s[i].op,s[i].val);}
}int query(int x)
{int sq=sqrt(n);for(int i=1;i<=sq;i++){if(x+func[i].t>=func[i].r) x=func[i].r;else if(x+func[i].t<=func[i].l) x=func[i].l;else x=x+func[i].t;}return x;
}signed main()
{freopen("function.in","r",stdin);freopen("function.out","w",stdout);n=read();for(int i=1;i<=n;i++) s[i]={read(),read()};fk();q=read();for(int i=1;i<=q;i++){int op=read();if(op==4) printf("%lld\n",query(read()));else{int pos=read(),x=read();update(pos,op,x);}}
}