首页 > 其他分享 >模拟赛

模拟赛

时间：2023-10-11 21:11:07浏览次数：31  
标签：ch int while 模拟 include dp dis

10.11 (CSP模拟52联测14)

T1 长春花

第一反应打表,打了半天啥也没发现.最后手摸发现 \((a^{2}+b^{2})\mod {p}\)有循环节.(打表方向完全错了…………)浪费了蛮多时间的.

Code 

#include<iostream>
#include<cstdio>
#include<cmath>

#define ll long long

using namespace std;
const int N=1e5+5;

inline int read(){
    int x=0,f=1;
    char ch=getchar();

    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

int n;

namespace bl2{
    int res[N],vis[N];
    int cnt=0;

    void work(){
        for(int i=0;i<=n;i++) res[i]=1e9;
        for(int i=0;i*i<=n-1;i++) res[i*i]=0,cnt++;
        
        for(int a=0;;a++){
            for(int i=0;i<=n-1;i++) vis[i]=0;
            for(int b=0;;b++){
                ll c=1ll*a*a+1ll*b*b;
               
                if(vis[c%n]) break;
                vis[c%n]=1;

                if(res[c%n]==1e9) cnt++;
                res[c%n]=min(res[c%n],a);
            }
            if(cnt==n) break;
        }

        int ans=0;
        for(int i=0;i<=n-1;i++) ans=max(ans,res[i]);
        printf("%d",ans);
    }
}
int main(){
    freopen("A.in","r",stdin);
    freopen("A.out","w",stdout);
    n=read();

    bl2::work();

    return 0;
}

T2 紫罗兰

看到题脑子里啥也没有,确实不会应付这种题.
bfs找到最小环,并在bfs时统计答案.

我们从每个点出发bfs.\(dis_{i}\) 是出发点到\(i\)的最短距离.当\(u\)第二次到\(v\)时会产生\(dis_{u}+dis_{v}+1\) 的环但会有冗余部分但只要一直对环取\(min\) 就会消除冗余部分剩下真正的最小环.

对于答案,应为会从环的任意一个点都计算一遍,所以要除以环长,对于奇环,会从两个点各遍历一遍还要除2.

Code 
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>

#define ll long long
using namespace std;
const int N=10005;
const int M=10005;

inline int read(){
    int x=0,f=1;
    char ch=getchar();

    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

struct Node{
    int to,next;
}e[M<<1];
int lk[N],ntot;

void add(int x,int y){
    e[++ntot]={y,lk[x]};
    lk[x]=ntot;
}

int n,m;
int vis[N];

queue <int> q;
int dis[N],cnt[N];
int huan=1e9;
ll ans=0;

void check(int x,int y){
    if((dis[x]==dis[y]&&dis[x]!=2139062143)
        ||(dis[x]+1==dis[y]&&dis[x]!=2139062143&&dis[y]!=2139062143)){
        int len=dis[x]+dis[y]+1;
        if(len<huan) { huan=len; ans=1ll*cnt[x]*cnt[y]; }
        else if(len==huan) { ans+=1ll*cnt[x]*cnt[y]; }
        if(dis[y]==dis[x]+1) { cnt[y]+=cnt[x]; }
        return ;
    }
    if(dis[y]>dis[x]+1){
        dis[y]=dis[x]+1;
        cnt[y]=cnt[x];
        q.push(y);
        return ;
    }

    return;
}

void bfs(int x){
    while(!q.empty()) q.pop();
    memset(dis,0x7f,sizeof(dis));
    memset(cnt,0,sizeof(cnt));
    
    q.push(x);cnt[x]=1;dis[x]=0;

    while(!q.empty()){
        int x=q.front();
        q.pop();

        for(int i=lk[x];i;i=e[i].next){
            int y=e[i].to;
            check(x,y);
        }
    }
}

int main(){
    freopen("B.in","r",stdin);
    freopen("B.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=m;i++){
        int x=read(),y=read();
        add(x,y),add(y,x);
        vis[x]=vis[y]=1;
    }   

    for(int i=1;i<=n;i++){
        if(!vis[i]) continue;
        bfs(i);
    }

    cerr<<huan<<endl;
    ans/=huan;
    printf("%lld",(huan&1)?(ans/2):ans);

    return 0;
}

T3 天竺葵

考试时跟个傻逼似的,暴力还差点打挂.
一个有限制的最长上升子序列.\(dp_{j}\) 是长度为\(j\) 的最后一位的最小值,发现\(dp\)数组是单增的,所以直接二分转移点.(跟二分优化普通LCS差不多)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>

#define ll long long

using namespace std;
const int N=1e6+5;

inline ll read(){
    ll x=0,f=1;
    char ch=getchar();

    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

int n,flag=1;
ll a[N],b[N];

namespace bl1{
    ll c[N];
    
    void work(){
        int ans=1;
        c[ans]=a[1];
        for(int i=2;i<=n;i++){
            if(a[i]>c[ans]){
                c[++ans]=a[i];
            }else{
                int pos=lower_bound(c+1,c+1+ans,a[i])-c;
                c[pos]=a[i];
            }
        }        
        printf("%d",ans);
    }
}
namespace bl2{
    ll f[N],c[N];
    int ans;
    void work(){
        int now=0;
        memset(c,0x7f,sizeof(c));

        for(int i=1;i<=n;i++){
            int pos=lower_bound(c+1,c+1+ans,a[i])-c;
            f[i]=pos;ans=max(ans,pos);
            c[pos]=min(c[pos],1ll*a[i]*b[pos]);
        }
        printf("%d",ans);
    }
}

int main(){
    freopen("C.in","r",stdin);
    freopen("C.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++){ 
        b[i]=read();
        if(b[i]!=1) flag=0;
    }

    if(flag==1) bl1::work();
    else bl2::work();

    return 0;
}

T4 风信子

没记起来超级钢琴(不知道为什么老是记不住典题………………)

和超级钢琴一样不断拆分区间,扔进堆里查询前\(k\)大.

对于\(k==1\)的情况,维护最大值最小值,答案为\(max(ans_{lc},ans_{rc},mx_{lc}-mn_{rc})\)

(pushup一个地方写挂,调了2h………………)


Code 
#include<cstdio>
#include<queue>

#define lc (k<<1)
#define rc (k<<1|1)
#define ll long long
using namespace std;
const int N=1e5+5;
const ll inf=1e15;

inline int read(){
    int x=0,f=1;
    char ch=getchar();

    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

ll max(ll x,ll y){
    return x>y?x:y;
}
ll min(ll x,ll y){
    return x<y?x:y;
}

int n,m,flag=1;
int a[N];

struct Node{
    int opt,l,r,k;
}q[N];

namespace bl2{
    struct Tree{
        ll mx,mn,ans;
        int mxpos,mnpos;
        int np,xp;
    }t[N<<2];
    ll lazy[N<<2];

    inline Tree push_up(Tree c,Tree d){
        Tree e;
        e.mn=min(c.mn,d.mn);
        e.mx=max(c.mx,d.mx);
        e.ans=max(max(c.ans,d.ans),c.mx-d.mn);
        e.np=(e.mn==c.mn)?(c.np):(d.np);
        e.xp=(e.mx==c.mx)?(c.xp):(d.xp);
        if(e.ans==c.ans) e.mnpos=c.mnpos,e.mxpos=c.mxpos;
        else if(e.ans==d.ans) e.mnpos=d.mnpos,e.mxpos=d.mxpos;
        else if(e.ans==(c.mx-d.mn)) e.mxpos=c.xp,e.mnpos=d.np;
        return e;
    }

    inline void push_down(int k){
        if(lazy[k]==inf) return ;
        t[lc].mx+=lazy[k],t[rc].mx+=lazy[k];
        t[lc].mn+=lazy[k],t[rc].mn+=lazy[k];
        lazy[lc]=(lazy[lc]==inf)?(lazy[k]):(lazy[lc]+lazy[k]);
        lazy[rc]=(lazy[rc]==inf)?(lazy[k]):(lazy[rc]+lazy[k]);
        lazy[k]=inf;
    }

    void build(int k,int l,int r){
        lazy[k]=inf;
        if(l==r) { t[k]={a[l],a[l],0,l,l,l,l}; return ; }
        
        int mid=(l+r)>>1;
        build(lc,l,mid);
        build(rc,mid+1,r);
        t[k]=push_up(t[lc],t[rc]);
    }
    void update(int k,int l,int r,int L,int R,int val){
        if(L<=l&&r<=R){
            t[k].mx+=val,t[k].mn+=val;
            lazy[k]=(lazy[k]==inf)?(val):(lazy[k]+val);
            return;
        }

        int mid=(l+r)>>1;
        push_down(k);
        if(L<=mid) update(lc,l,mid,L,R,val);
        if(R>mid) update(rc,mid+1,r,L,R,val);
        t[k]=push_up(t[lc],t[rc]);
    }
    int query(int k,int l,int r,int pos){
        if(l==r) return t[k].mx;
        
        int mid=(l+r)>>1;
        push_down(k);
        if(pos<=mid) return query(lc,l,mid,pos);
        else return query(rc,mid+1,r,pos);
    }
    Tree query(int k,int l,int r,int L,int R){
        if(L<=l&&r<=R) return t[k];

        int mid=(l+r)>>1;
        push_down(k);

        Tree c={-inf,inf,-inf,0,0,0,0},d={-inf,inf,-inf,0,0,0,0};
        if(L<=mid) c=query(lc,l,mid,L,R);
        if(R>mid) d=query(rc,mid+1,r,L,R);
        return push_up(c,d);
    }

    struct Node{
        int lx,ly,rx,ry,x,y;
        ll val;
        bool operator < (const Node &x) const{
            return val<x.val;
        }
    };

    priority_queue <Node> q;

    inline int check(Node x){
        return (x.lx==x.rx&&x.ly==x.ry);
    }
    
    inline void work(int l0,int r0,int l1,int r1){
        if(!check({l0,r0,l1,r1})){
            // cout<<l0<<" "<<r0<<" "<<l1<<" "<<r1<<endl;
            Tree ansl=query(1,1,n,l0,r0);
            Tree ansr=query(1,1,n,l1,r1);
            q.push({l0,r0,l1,r1,ansl.xp,ansr.np,ansl.mx-ansr.mn});
        }else{
            Tree ans=query(1,1,n,l0,r0);
            q.push({l0,r0,l1,r1,ans.mxpos,ans.mnpos,ans.ans});
        }
    }
    inline void solve1(Node now){
        int l=now.lx,r=now.ly,x=now.x,y=now.y;
        // cout<<l<<" "<<r<<" "<<x<<" "<<y<<endl;
        if(x>l) { work(l,x-1,l,x-1);work(l,x-1,x,r); }
        if(x!=y) { work(x,x,x,x); }
        if(x<y-1) { work(x,x,x+1,y-1); }
        if(y<r) { work(x,x,y+1,r); }
        if(x<r) { work(x+1,r,x+1,r); }
    }
    inline void solve2(Node now){
        int l0=now.lx,r0=now.ly,l1=now.rx,r1=now.ry,x=now.x,y=now.y;
        if(x>l0) { work(l0,x-1,l1,r1); }
        if(l1<y) { work(x,x,l1,y-1); }
        if(y<r1) { work(x,x,y+1,r1); }
        if(x<r0) { work(x+1,r0,l1,r1); }
    }

    void work(){
        build(1,1,n);
        // cout<<query(1,1,n,4,7).mxpos<<" "<<query(1,1,n,4,7).mnpos<<endl;
        for(int i=1;i<=m;i++){
            int opt=read(),l=read(),r=read(),k=read();

            if(opt==1) { update(1,1,n,l,r,k); continue; }

            while(!q.empty()) q.pop();
            work(l,r,l,r);

            ll ans=0;

            while(!q.empty()&&k){
                Node now=q.top();
                q.pop();
                int posx=now.x,posy=now.y;
                ans+=now.val;

                (check(now))?(solve1(now)):(solve2(now));
                // cout<<"x:"<<posx<<" "<<"y:"<<posy<<" "<<now.val<<endl;
                k--;
            }
            printf("%lld\n",ans);
        }
    }
}

int main(){
    freopen("D.in","r",stdin);
    freopen("D.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    bl2::work();

    return 0;
}

10.9 (accoder 2023NOIP A层联测8)

T2 出租

转化成二分图匹配,直接连边不行,考虑Hall定理.

若任意 $ [l,r] $ 的人数大于 $ (r-l+1+d) * k $ 时无解,即 $ \sum_{l}^{r} (val_{i}-k) > k*d $ 时无解求最大子段和比较.

Code 
#include<iostream>
#include<cstdio>
#include<algorithm>

#define lc (k<<1)
#define rc (k<<1|1)
#define ll long long

using namespace std;
const int N=5e5+5;

inline int read(){
    int x=0,f=1;
    char ch=getchar();

    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

int n,m,v,d;
int mx[N];
ll val[N];

struct Node{
    ll sum,lmax,rmax,dat;
}t[N<<2];
int lazy[N<<2];

void push_up(int k){
    t[k].sum=(t[lc].sum+t[rc].sum);
    t[k].lmax=max(t[lc].lmax,t[lc].sum+t[rc].lmax);
    t[k].rmax=max(t[lc].rmax+t[rc].sum,t[rc].rmax);
    t[k].dat=max({t[lc].dat,t[rc].dat,t[lc].rmax+t[rc].lmax});
}

void update(int k,int l,int r,int pos,int val){
    if(l==r){ 
        t[k].lmax+=val;t[k].rmax+=val;
        t[k].sum+=val,t[k].dat+=val; 
        return ; 
    }
    
    int mid=(l+r)>>1;
    if(pos<=mid) update(lc,l,mid,pos,val);
    else update(rc,mid+1,r,pos,val);
    push_up(k);
}

int main(){
    freopen("lantern.in","r",stdin);
    freopen("lantern.out","w",stdout);
    n=read(),m=read(),v=read(),d=read();
    
    for(int i=1;i<=n;i++) update(1,1,n,i,-v);
    while(m--){
        int x=read(),y=read();
        update(1,1,n,x,y);
        cout<<t[1].dat<<endl;
        (t[1].dat>1ll*v*d)?(printf("NO\n")):(printf("YES\n"));
    }

    return 0;
}

T3 连通块

设 $ dp_{i,j} $ 表示以\(i\) 为根最大\(dfn\)为\(j\)的最大值,因为只有冲突的点会影响转移所以可以对其重编号,不影响转移的点可以编成一个号,每次用最大值转移.

Code 
#include<iostream>
#include<cstdio>
#include<vector>

#define ll long long

using namespace std;
const int N=1e5+5;
const ll inf=-1e18;

inline int read(){
    int x=0,f=1;
    char ch=getchar();

    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}


int n,m;
int a[N];
int dfn[N],dfntime;
pair <int,int> no[N];
vector<int> e[N];
int No[N];
int vis[55][55];
ll dp[N][55],ans=inf;

void dfs(int x,int fa){
    for(int i=1;i<=dfntime;i++) dp[x][i]=inf;
    dp[x][dfn[x]]=a[x];

    for(int y:e[x]){
        if(y==fa) continue;
        dfs(y,x);

        ll mx=inf;
        for(int i=1;i<=dfntime;i++) if(!vis[i][dfn[y]]) mx=max(mx,dp[x][i]);
        for(int i=1;i<=dfntime;i++) dp[x][i]=max(dp[x][i],dp[y][i]+mx); 
    }

    for(int i=1;i<=dfntime;i++) ans=max(ans,dp[x][i]);
    // cout<<ans<<endl;
}

int main(){
    freopen("connection.in","r",stdin);
    freopen("connection.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++){
        int tot=read();
        for(int j=1;j<=tot;j++){
            int x=read();
            e[i].push_back(x),e[x].push_back(i);
        }
    }

    for(int i=1;i<=m;i++){ 
        no[i].first=read(),no[i].second=read();
        No[no[i].first]=1,No[no[i].second]=1;
    }

    ++dfntime;
    for(int i=1;i<=n;i++) { if(!No[i]) dfn[i]=dfntime; }
    for(int i=1;i<=n;i++) { if(No[i]) dfn[i]=++dfntime; }
    for(int i=1;i<=m;i++){ 
        vis[dfn[no[i].first]][dfn[no[i].second]]=1; 
        vis[dfn[no[i].second]][dfn[no[i].first]]=1;
    }

    dfs(1,0);

    printf("%lld",ans);

    return 0;
}

T4 跳棋

考虑没有\(?\) 的情况 CF1545B

把两个\(1\)看做一个整体可以向周围空格移动;单独的\(1\)可以在两个\(1\)移动到它是与其中一个\(1\)配对.设有$ a \(个成对的\) 1 \(,\) b $ 个单独的$ 1 $ ,$ ans={{n-a-b}\choose{a}} $

当有$ ? $ 时 考虑$ dp_{i,j,k,0/1/2} $ 表示考虑到$ i \(,有\) j \(个成对,\) k $个单独,这一位选0/成单/成对.
最后乘上系数就行.

Code 
#include<iostream>
#include<cstdio>
#include<cstring>

#define ll long long

using namespace std;
const int N=505;
const int mod=1e9+7;

inline int read(){
    int x=0,f=1;
    char ch=getchar();

    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

ll ksm(ll a,ll b){
    ll ans=1;
    
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

int n;
char ch[N];
int dp[2][N][N][3];
ll fac[N],inv[N];

ll C(int n,int m){
    if(n==m) return 1;
    if(n<m) return 0;
    return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
}

int main(){
    freopen("checkers.in","r",stdin);
    freopen("checkers.out","w",stdout);
    scanf("%d",&n);
    scanf("%s",ch+1);

    fac[0]=1,inv[0]=1;
    for(int i=1;i<=n;i++){
        fac[i]=1ll*fac[i-1]*i%mod;
        inv[i]=ksm(fac[i],mod-2);
    }

    int now=0;
    dp[now][0][0][0]=1;

    for(int i=1;i<=n;i++){
        for(int j=0;j<=n;j++)
            for(int k=0;k<=n;k++)
                dp[now^1][j][k][0]=dp[now^1][j][k][1]=dp[now^1][j][k][2]=0;

        for(int j=0;j<=n;j++){
            for(int k=0;k<=n;k++){
                if(ch[i]=='0'||ch[i]=='?')
                    dp[now^1][j][k][0]=((dp[now][j][k][0]+dp[now][j][k][1])%mod+dp[now][j][k][2])%mod;
                if(ch[i]=='1'||ch[i]=='?'){
                    if(k>=1) dp[now^1][j][k][1]=(dp[now][j][k-1][0]+dp[now][j][k-1][2])%mod;
                    if(j>=1) dp[now^1][j][k][2]=(dp[now][j-1][k+1][1]);
                }
            }
        }
        now^=1;
    }

    ll ans=0;

    for(int i=0;i<=n/2;i++){
        for(int j=0;j<=min(n-2*i,(n+1)/2);j++){
            int x=(n-i-j);
            ll res=((dp[now][i][j][0]+dp[now][i][j][1])%mod+dp[now][i][j][2])%mod;
            ans=(ans+C(x,i)*res%mod)%mod;
        }
    }
    
    printf("%lld",ans);

    return 0;
}

10.7 (CSP模拟50)

[Ynoi2077] stdmxeypz

分治+根号分治

x $ \ge $ lim 修改不超过 \(\sqrt n\) 次 维护差分单点修改,区间查询,因为空间原因,不能全部存下来,所以每根号次重构.(……好像没被卡空间)

x \(<\) lim 对dfs序 分块 散块暴力,整块维护 \(sum[i][j][k]\) 表示 \(i\) 块 mod \(j\) 为 \(k\) 所需要加的值

Code 
#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#include<cstring>

using namespace std;
const int N=3e5+5;
const int Std1=550;
const int Std2=250;

inline int read(){
    int x=0,f=1;
    char ch=getchar();

    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

struct Node{
    int to,next;
}e[N<<1];
int lk[N],ntot;

void add(int x,int y){
    e[++ntot]={y,lk[x]};
    lk[x]=ntot;
}

int n,Q;

int dfn[N],dfnx[N],siz[N],dep[N],dfntime;
int mxdep;

void dfs(int x,int fa){
    dep[x]=dep[fa]+1;siz[x]=1;
    dfn[x]=++dfntime;dfnx[dfntime]=x;
    mxdep=max(dep[x],mxdep);

    for(int i=lk[x];i;i=e[i].next){
        int y=e[i].to;
        if(y==fa)
            continue;
        dfs(y,x);
        siz[x]+=siz[y];
    }
}

int L[N],R[N];
int len,tot;

void init(){
    len=min(Std1,(int)sqrt(n));
    tot=(n-1)/len+1;
    for(int i=1;i<=tot;i++)
        L[i]=R[i-1]+1,R[i]=i*len;
    // for(int i=1;i<=tot;i++)
    //     cout<<L[i]<<" "<<R[i]<<endl;
    // cout<<endl;
    dfs(1,0);

    // for(int i=1;i<=n;i++)
    //     cout<<"siz:"<<siz[i]<<endl;
    // cout<<endl;
}

int val[N];
int sum[Std1+5][Std2+5][Std2+5];

void work1(int v,int x,int y,int z){
    int l=dfn[v],r=dfn[v]+siz[v]-1;
    int lbe=(l-1)/len+1,rbe=(r-1)/len+1;
    // cout<<l<<" "<<r<<endl;
    // cout<<lbe<<" "<<rbe<<endl;

    if(lbe==rbe){
        for(int i=l;i<=r;i++){
            if((dep[dfnx[i]]-dep[v])%x==y)
                val[dfnx[i]]+=z;
        }
        return ;
    }
    
    for(int i=l;i<=R[lbe];i++){
        if((dep[dfnx[i]]-dep[v])%x==y)
            val[dfnx[i]]+=z;
    }
    for(int i=L[rbe];i<=r;i++){
        if((dep[dfnx[i]]-dep[v])%x==y)
            val[dfnx[i]]+=z;
    }
    for(int i=lbe+1;i<=rbe-1;i++){
        sum[i][x][(dep[v]+y)%x]+=z;
    }
}

struct Ques{
    int v,x,y,z,l,r;
}q[Std1+5];
int cnt;

vector <Ques> qcfl[N],qcfr[N];
int cf[N];

void work2(){
    for(int i=1;i<=n;i++)
        qcfl[i].clear(),qcfr[i].clear(),cf[i]=0;
    for(int i=1;i<=cnt;i++){
        qcfl[q[i].l].push_back(q[i]);
        qcfr[q[i].r+1].push_back(q[i]); 
    }

    for(int v=1;v<=n;v++){
        for(auto i:qcfl[v]){
            int x=i.x,y=i.y,z=i.z;
            int dp=dep[i.v]+y;

            while(dp<=mxdep){
                cf[dp]+=z;dp+=x;
            }
        }
        for(auto i:qcfr[v]){
            int x=i.x,y=i.y,z=i.z;
            int dp=dep[i.v]+y;

            while(dp<=mxdep){
                cf[dp]-=z;dp+=x;
            }
        }
        val[dfnx[v]]+=cf[dep[dfnx[v]]];
    }
}

int query(int v){
    int ans=val[v];
    int ql=dfn[v],qr=dfn[v]+siz[v]-1;
    int bl=(ql-1)/len+1;

    for(int i=1;i<=Std2;i++)
        ans+=sum[bl][i][dep[v]%i];
    for(int i=1;i<=cnt;i++){
        if(q[i].l<=ql&&ql<=q[i].r){
            ans+=(((dep[v]-dep[q[i].v])%q[i].x)==q[i].y)?(q[i].z):(0);
        }
    }
    return ans;
}

void solve(){
    for(int i=1;i<=Q;i++){
        int opt=read(),v=read();
        
        if(opt==1){
            int x=read(),y=read(),z=read();
            if(x<=Std2){
                work1(v,x,y,z);
            }else{
                q[++cnt]={v,x,y,z,dfn[v],dfn[v]+siz[v]-1};
                if(cnt==Std1){
                    work2();
                    cnt=0;
                }
            }
        }else{
            int ans=query(v);
            printf("%d\n",ans);
        }
    }
}

int main(){
    // freopen("in","r",stdin);
    // freopen("out","w",stdout);

    n=read(),Q=read();
    
    for(int i=2;i<=n;i++){
        int x=read();
        add(x,i),add(i,x);
    }
    init();
    solve();

    return 0;
}

[Ynoi2011] 初始化

根号分治

x \(\ge\) lim 修改不超过 \(\sqrt n\) 次 分块暴力修改

x \(<\) lim 维护 \(sum[i][j]\) 为 从 \(j\) 开始跳,跳\(i\)步的和.
查询时 暴力枚举\(x\),设 k 为跳的步数 \(l=x*k_{1}+b_{1}\) , \(r=x*k_{2}-b_{2}\) 两者 \(k\) 相同 利用前缀和直接查询,否则可以查询 \(k_{1}到k_{2}-1\) 两个块在减去在 \(l\) 处多加的,加上在 \(r\) 处 少加的.

要初始化分块的 \(add\) 数组.

好像不取模能过

Code 
#include<iostream>
#include<cstdio>
#include<cmath>

using namespace std;
const int N=2e5+5;
const int mod=1e9+7;
const int Std1=550;
const int Std2=150;

inline int read(){
    int x=0;
    char ch=getchar();

    while(ch<'0'||ch>'9')
        ch=getchar();
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x;
}

inline int add(int x,int y){
    return (x+y>mod)?(x+y-mod):(x+y);
}
inline int del(int x,int y){
    return (x-y<0)?(x-y+mod):(x-y);
}

int n,m,len;
int a[N];
int ad[N],sum[Std1+5][Std2+5];
int L[N],R[N],bl[N];

inline void work1(int x,int y,int z){
    for(int i=y;i<=n;i+=x)
        a[i]=add(a[i],z),ad[bl[i]]=add(ad[bl[i]],z);
}
inline void work2(int x,int y,int z){
    for(int i=y%x;i<x;i++)
        sum[x][i]=add(sum[x][i],z);        
}
inline int query1(int l,int r){
    int bll=bl[l],blr=bl[r];
    int ans=0;

    if(bll==blr){
        for(int i=l;i<=r;i++)
            ans=add(ans,a[i]);
        return ans;
    }
    for(int i=l;i<=R[bll];i++)
        ans=add(ans,a[i]);
    for(int i=L[blr];i<=r;i++)
        ans=add(ans,a[i]);
    for(int i=bll+1;i<=blr-1;i++)
        ans=add(ans,ad[i]);
    return ans;
}
int query2(int l,int r){
    int ans=0;

    for(int i=1;i<=Std2;i++){
        int bl=l/i,br=r/i;
        if(bl==br)
            ans=add(ans,del(sum[i][r%i],sum[i][l%i-1]));
        else
            ans=add(ans,add(1ll*(br-bl)*sum[i][i-1]%mod,del(sum[i][r%i],sum[i][l%i-1])));
    }

    return ans;		
}

void solve(){
    while(m--){
        int opt=read();
        if(opt==1){
            int x=read(),y=read(),z=read();
            // work1(x,y,z);
            (x>Std2)?work1(x,y,z):work2(x,y,z);
        }else{
            int l=read(),r=read();
            // printf("%d\n",query1(l,r));
            printf("%d\n",add(query1(l,r),query2(l,r)));
        }
    }
}

int main(){
    // freopen("in","r",stdin);
    // freopen("out","w",stdout);
    n=read(),m=read();
    len=sqrt(n);
    
    for(int i=1;i<=(n-1)/len+1;i++)
        L[i]=R[i-1]+1,R[i]=i*len;
    for(int i=1;i<=n;i++)
        bl[i]=(i-1)/len+1;

    for(int i=1;i<=n;i++)
        a[i]=read(),ad[bl[i]]=add(ad[bl[i]],a[i]);

    solve();

    return 0;
}

Crash 的文明世界

\[\sum_{i=1}^{n} \sum_{j=1}^{n} dis(i,j)^{k} \]

\[n^{k} = \sum_{i=1}^{n} i! {{n}\choose{i}} { {k}\brace{i} } \]

\[ans_{u}=\sum_{v=1}^{n} \sum_{i=1}^{k} i! {{dis(u,v)}\choose{i}} { k \brace {i} } \]

\[dp_{u,i} = \sum_{v \in son_{u}} {{dis(u,v)}\choose{i}} \]

\[dp_{u,i} = \sum_{v \in son_{u}} \sum_{y \in son_{v}} {{dis(v,y)+1} \choose {i}} \]

\[\because {{n}\choose{m}} = {{n-1}\choose{m}} + {{n-1}\choose{m-1}} \]

\[dp_{u,i} = \sum_{v \in son_{u}} dp_{v,i} + dp_{v,i-1} \]

\[f_{u,i} = \sum_{v=1}^{n} {{dis(u,v)}\choose{i}} = \sum_{v \in {son_u}} {{dis(u,v)}\choose{i}} + \sum_{v \notin {son_u} } {{dis(u,v)}\choose{i}} \]

\[\because \sum_{v \in {son_u}} {{dis(u,v)}\choose{i}} = \sum_{v \in {son_u}} {{dis(fa,v)-1}\choose{i}} \]

\[\because \sum_{v \notin {son_u}} {{dis(u,v)}\choose{i}} = \sum_{v \notin{son_u}} {{dis(fa,v)+1}\choose{i}} \]

\[\therefore f_{u,i} = f_{fa,i}+ f_{fa,i-1} - 2*dp_{u,i-1} -dp_{u,i-2} \]

Code 
#include<iostream>
#include<cstdio>

#define ll long long

using namespace std;
const int N=1e6+5;
const int mod=10007;

inline int read(){
    int x=0,f=1;
    char ch=getchar();

    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

ll ksm(int a,int b){
    ll ans=1;

    while(b){
        if(b&1)
            ans=1ll*ans*a%mod;
        a=1ll*a*a%mod;
        b>>=1;
    }
    return ans;
}
struct Node{
    int to,next;
}e[N<<1];
int lk[N],ntot;

void add(int x,int y){
    e[++ntot]={y,lk[x]};
    lk[x]=ntot;
}

int n,k;
ll st[155][155];
ll fac[N];
int dp[N][155];

void dfs(int x,int fa){
    dp[x][0]=1;

    for(int i=lk[x];i;i=e[i].next){
        int y=e[i].to;
        if(y==fa)
            continue;
        dfs(y,x);
        for(int j=0;j<=k;j++)
            dp[x][j]=((dp[x][j]+dp[y][j])%mod+dp[y][j-1])%mod;
    }
}

int f[N][155];
void dfs1(int x,int fa){
    if(x==1){
        for(int i=0;i<=k;i++)
            f[x][i]=dp[x][i]%mod;
    }else{
        for(int i=1;i<=k;i++){
            if(i-2>=0){
                f[x][i]=(((f[fa][i]+f[fa][i-1])%mod-2ll*dp[x][i-1]%mod+mod*2ll)%mod-dp[x][i-2]%mod+mod*2ll)%mod;
            }else{
                f[x][i]=((f[fa][i]+f[fa][i-1])%mod-2ll*dp[x][i-1]%mod+mod)%mod;
            }
        }
        f[x][0]=f[fa][0]%mod;
    }

    for(int i=lk[x];i;i=e[i].next){
        int y=e[i].to;
        if(y==fa)
            continue;
        dfs1(y,x);
    }
}

signed main(){
    // freopen("in","r",stdin);
    // freopen("out","w",stdout);
    n=read(),k=read();
    for(int i=1;i<=n-1;i++){
        int x=read(),y=read();
        add(x,y),add(y,x);
    }

    st[0][0]=1,fac[0]=1;
    for(int i=1;i<=k+1;i++){
        for(int j=1;j<=i;j++){
            st[i][j]=(1ll*st[i-1][j-1]+1ll*j*1ll*st[i-1][j]%mod)%mod;
        }
    }
    for(ll i=1;i<=k;i++)
        fac[i]=1ll*fac[i-1]*i%mod;
    dfs(1,0),dfs1(1,0);


    ll inv2=ksm(2,mod-2)%mod;

    for(int i=1;i<=n;i++){
        long long ans=0;
        for(int j=1;j<=k;j++){
            ans=(ans+1ll*fac[j]%mod*1ll*st[k][j]%mod*1ll*f[i][j]%mod)%mod;
        }
        printf("%lld\n",ans);
    }


    return 0;
}

<\details>

标签：ch,int,while,模拟,include,dp,dis
From： https://www.cnblogs.com/yszy/p/17753261.html

相关文章

  • CSP模拟52 & A 层联测 9
    2023NOIPA层联测9长春花观察大样例可以发现，函数\(f(x)\)的值很小，那么可以考虑暴力枚举。用一个桶存一下平方数对\(p\)取模的值是否存在，那么可以选择从小到大枚举\(a\)，找到第一个存在的\(b\)。紫罗兰考虑什么情况下会出现环，当两个点已经连通时，再在这两个点之间加一......
  • NOIP A层联测9 & CSP模拟52
    我的评价是三道傻逼题和一道牛逼题。T4上厕所时想了个奇怪东西打了一个半个小时170行结果剩10分钟发现假了，最后\(k=1\)都没来得及写就直接交了暴力。没想到HZOJ过了50pts，喜了。但是Accoders上只过了35pts，恼了。T1长春花\(b^2\bmodp=(b\bmodp)^2\bmodp\)，所以......
  • CSP模拟50联测12 T2 赌神
    CSP模拟50联测12T2赌神题面与数据规模Ps:超链接为衡水中学OJ。思路\(subtask2\)：由于\(x_i\)较小，考虑dp。假设一开始球的颜色为红和蓝，设\(dp[i][j]\)为剩\(i\)个红球，\(j\)个蓝球时可获得的最大筹码数。如果不同球掉落所获得的筹码不同，那么肯定会掉落最少筹码的那一......
  • 牛客提高模拟赛第四场 T3
    给你一个数\(n\)，让你从\(n\)中取出若干数合并成\(x\)，剩下数合并成\(y\)，求对于所有取法\(x+y\)的和例如\(12345\)可以拿出\(24\)，剩下\(135\)，此时会对答案产生\(24+135\)的贡献。而\(42,153\)或\(23,15\)是不合法的\(n\leq10^{10^5}\)显然\(\sumx......
  • 1、python脚本模拟登陆启信宝
    ##coding:utf-8#importrequests#fromlxmlimportetree#classlogin(object):#def__init__(self):#self.headers={#'Referer':'http://www.qixin.com/auth/login?return_url=%2F',#'User-......
  • 模拟赛补题
    农场道路修建与没有上司的舞会类似，关键在于添加道路。添加的道路一定是两点中一有一无或两无，则判断哪些点必须有，用总方案数减去不合法方案数即可。P7828[CCO2021]SwapSwapSort基本思路不难，没有想到根号分治（准确来说是不会，呃呃），以及在\(x\)确定的情况下不会\(O(n)\)处理......
  • 模拟赛补题
    感觉模拟赛质量比之前打的高一些。Day1A赛时过B需要保存每个点的状态，为了使状态数尽量少，让每个点代表右下方是否已经达到终止状态，故如果一个点状态为\(1\)，右下方所有点的状态都为1，那么状态能用轮廓线来描述，数量为\(\binom{n+m}{n}\)，直接高斯消元。C将每条路径对应到一条......
  • CSP模拟51联测13 B.狗
    CSP模拟51联测13B.狗目录CSP模拟51联测13B.狗题目大意题目描述输入格式输出格式样例样例1inputoutput思路题目大意题目描述小G养了很多狗。小G一共有\(n\timesn\)条狗，在一个矩阵上。小G想让狗狗交朋友，一条狗狗最多只能交一个朋友，不必所有狗狗都有朋友。但是狗狗交朋友......
  • 虚拟桌宠模拟器：VPet-Simulator，一个开源的桌宠软件, 可以内置到任何WPF应用程序
    虚拟桌宠模拟器：VPet-Simulator，一个开源的桌宠软件,可以内置到任何WPF应用程序虚拟桌宠模拟器一个开源的桌宠软件,可以内置到任何WPF应用程序获取虚拟桌宠模拟器OnSteam(免费)或通过Nuget内置到你的WPF应用程序1.虚拟桌宠模拟器详细介绍虚拟桌宠模拟器是一款桌宠软件,......
  • LY1376 [ 20231008 NOIP 模拟赛 T0 ] 递增路径
    题意\(A\),\(B\)两人轮流在一张图上移动一个点。要求这次移动的边权必须大于上次的。\(A\)希望游戏进行的轮数多，\(B\)希望游戏进行的轮数少。对于每个\(s=1,2,...,n\)作为起点，若双方都采用最优策略，游戏会进行多少轮。Sol考虑将所有边按照从大到小的顺序排序。每......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99