标签：cnt ch int tot ans CSP 模拟 mod
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);
}
}
}
标签：cnt,
ch,
int,
tot,
ans,
CSP,
模拟,
mod
From： https://www.cnblogs.com/zhengchenxi/p/18440595