10.6 模拟赛总结

T1 光

大意：给定四个方块的需要的亮度值，有光的散射，每个方块对于另外三个有影响，问四个亮度值之和最小为多少。$ n\le 1500$
思路：一眼看出是二分答案的判定性问题，判断中枚举其中两个值出来四个不等式小范围内枚举第三个即可
错因：为什么范围要手残除二啊！！！

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,l,r,mid,ans;
bool ck(){
    int aa,bb,cc,dd,o,md,k;
    for(int i=0;i<=a+4&&i<=mid;i++) for(int j=0;j<=b+4&&i+j<=mid;j++){
        aa=a-i-j/2,bb=b-i/2-j;
        cc=c-i/2-j/4,dd=d-i/4-j/2;
        md=mid-i-j;
        for(k=max(0,max(4*aa-md,2*cc-md));k<=min(md,min(2*md-4*bb,2*md-2*dd));k++){
            o=md-k;
            if(o/4+k/2>=aa&&o/2+k/4>=bb&&k+o/2>=cc&&k/2+o>=dd) return 1;
        }
    }
    return 0;
}

int main(){
}

T2 爬

大意：一颗树，每个节点的蚂蚁都有一个权值，可以选择不动和去到父亲节点，只有一个蚂蚁的节点贡献为0，否则贡献为所有蚂蚁的权值的亦或和\(n \le10^5\)

思路：考虑把每个节点的每一位贡献单独算，只跟父亲的亲生儿子们有关。每一次把一个节点的所有儿子弄在一团，团内又分当前这一位为\(1\)或\(0\)，为0的比较自由，为1的必须取另外偶数个抵消才有贡献，发现其值为$${s \choose 0}+{s \choose 2}+{s \choose 4}+\cdots+{s \choose s}$$
放到杨辉三角上可以变成$${s-1 \choose 1}+{s-1 \choose 2}+{s-1 \choose 3}+\cdots+{s-1 \choose s-1}$$
之前不会结果打个表就发现等于 \(2^{s-1}\) （哇好神奇
再跟团内自由的方案和团外方案乘一下，剪掉只有自己爬上去但是父亲爬走的一种情况就差不多

但是，如果根为1必须特判！！！非常麻烦，考试就在这里挂了

不能让其他节点把1的贡献算重了，1作为父亲也不会跑路
（真的非常考细节！！！）

#include<bits/stdc++.h>
#define ll long long
const ll mod=1e9+7;
using namespace std;
ll a[200005],ans,n,c[203],k,m,t,jt[200005],d[205];
queue<ll>q;
struct node{
    ll f,x;
}s[200005];
bool cmp(node aa,node bb){
    return aa.f<bb.f;
}
ll gc(ll x){
	if(x<0) return 0;
	return jt[x];
}
ll gcc(ll x){
	if(x==-1) return 1;
	if(x<-1) return 0;
	return jt[x];
}
int main(){
     freopen("climb.in","r",stdin);
     freopen("climb.out","w",stdout);
    scanf("%lld",&n);
    jt[0]=1;
    for(int i=1;i<=n;i++) jt[i]=jt[i-1]*2ll%mod;
    for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(int i=2;i<=n;i++) scanf("%lld",&s[i-1].f),s[i-1].x=i;
    sort(s+1,s+n,cmp);
    for(int i=1;i<n;i++){
        q.push(s[i].x),++m;
        for(int j=0;j<=35;j++) if((a[s[i].x]>>j)&1) ++d[j];
        if(s[i+1].f!=s[i].f){
            t=0,++m;
            for(int j=0;j<=35;j++) if((a[s[i].f]>>j)&1) ++d[j];
            q.push(s[i].f);
            while(!q.empty()){
                k=q.front(),q.pop();
                for(int j=0;j<=35;j++) if((a[k]>>j)&1){
                	if(s[i].f!=1||k==1) t=(t+(gcc(c[j]-1)*gc(m-d[j])%mod-1)*(1<<j)%mod+mod)%mod;
					else{
						ll o=((a[1]>>j)&1);
						if(!o) t=(t+(gcc(c[j]-1)*(gc(m-d[j]-1))%mod)*(1<<j)%mod+mod)%mod;
					}
					++c[j];
                }
            }
            ans=(ans+t*gc(n-m-(s[i].f!=1))%mod)%mod;
            for(int j=0;j<=35;j++) c[j]=0;
            for(int j=0;j<=35;j++) d[j]=0;
            m=0;
        }
    }
    printf("%lld",ans);
}

T3 字符串

大意：给n个A，m个B，AB间切换贡献+1，连续a个A贡献+1，连续b个B贡献+1，B至少连续c个才能换A，A无限制。

比赛时50分DP都能挂。。。

正解：贪心，枚举切换次数，再把剩下的A，B贪心塞进去看，很简单

#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,c,sum,aa,bb,ans;
int main(){
    // freopen("string.in","r",stdin);
    // freopen("string.out","w",stdout);
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d%d%d",&n,&m,&a,&b,&c);
        ans=0;
        for(int i=1;i<=min(m/c,n)+1;i++){
            sum=i+1;
            aa=n-i,bb=m-i*c;
            sum+=(c-1)/b*i;
            if(aa) --aa,++sum;
            sum+=aa/a;
            if(bb) --bb,++sum;
            if((c-1)%b!=0) sum+=bb/((c-1)%b),bb%=((c-1)%b);
            sum+=bb/b;
            ans=max(ans,sum);
        }
        printf("%d\n",ans);
    }
}

T4 奇怪的函数

大意:一堆\(min,max\)和\(+\)弄在一起，可修改，询问Q次给定输入\(x\)，求最后得出什么

看出是分段函数，可以把\(+\)套在之前的\(min,max\)之间\(O(1)\)查询
分块解决简单易懂

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=2e5+10,inf=1e18,M=500;
ll n,a[N],qr,l[M],r[M],q[N],h[N],mi[M],mx[M],s[M],k,Q,x,y,z,mii,mxx,ss;
void pp(int i){
    k=0,mx[i]=mxx=inf,mi[i]=mii=-inf;
    for(int j=l[i];j<=r[i];j++) if(h[j]==1) k+=a[j];
    s[i]=k;
    for(int j=l[i];j<=r[i];j++){
        if(h[j]==1) k-=a[j];
        if(h[j]==2){
            mx[i]=min(mx[i],a[j]+k);
            if(mi[i]>mx[i]) mi[i]=mx[i];
        }
        if(h[j]==3){
            mi[i]=max(mi[i],a[j]+k);
            if(mi[i]>mx[i]) mx[i]=mi[i];
        }
    }
}
void qq(){
    k=ss=0;
    for(int i=1;i<=q[n];i++) k+=s[i],ss+=s[i];
    for(int i=1;i<=q[n];i++){
        k-=s[i];
        mii=max(mii,mi[i]+k);
        if(mii>mxx) mxx=mii;
        mxx=min(mxx,mx[i]+k);
        if(mii>mxx) mii=mxx;
    }
}
int main(){
    freopen("function.in","r",stdin);
    freopen("function.out","w",stdout);
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld%lld",&h[i],&a[i]);
    qr=sqrt(n);
    for(int i=1;i<=n;i++) q[i]=(i-1)/qr+1;
    for(int i=1;i<=q[n];i++){
        l[i]=(i-1)*qr+1,r[i]=min(n,i*qr);
        pp(i);
    }
    qq(),scanf("%lld",&Q);
    int bz=0;
    while(Q--){
        scanf("%lld%lld",&x,&y);
        if(x==4){
            if(bz) bz=0,qq();
            printf("%lld\n",min(max(mii,y+ss),mxx));
            continue;
        }
        scanf("%lld",&z);
        h[y]=x,a[y]=z,bz=1;
        pp(q[y]),bz=1;
    }
}

炸得很惨，引以为戒，对拍！！！