NOIP提高组模拟赛24(Noip improvement group simulation 24)

差点又因为文件暴0。。。

A. matrix

状压,\(f[i][j][k]\)表示第\(i-1\)行状态为\(j\),第\(i\)行状态为\(k\)的最小花费。

貌似复杂度不对?但是舍弃非法状态后复杂度是可以接受的,具体怎么证明我不会

#include<cstdio>
#include<cstring>

using namespace std;
int min(int x,int y){return x<y?x:y;}
const int maxn=13;
int n,m,mp[maxn],ls[maxn];
int v[maxn][1025];
char c[maxn];
int f[11][1025][1025];
int main(){
    freopen("matrix.in","r",stdin);
    freopen("matrix.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%s",c+1);
        for(int j=1;j<=m;++j)
           if(c[j]=='1')mp[i]=mp[i]|(1<<(j-1));
    }
    int ms=(1<<m)-1;
    for(int i=1;i<=n;++i){
      for(int j=1;j<=m;++j)scanf("%d",&ls[j]);
      for(int j=1;j<=ms;++j){
          for(int k=1;k<=m;++k){
              if((1<<(k-1))&j)v[i][j]+=ls[k];
          }
      }
    }
    memset(f,0x3f,sizeof(f));
    int inf=f[0][0][0];
    f[0][ms][mp[1]]=0;mp[0]=ms;
    for(int i=1;i<=n;++i){
        for(int j=mp[i-1];j<=ms;++j){// las line
            if((j&mp[i-1])<mp[i-1])continue;
            int ch=(~j)&ms;
            for(int k=mp[i];k<=ms;++k){// now line
                if((k&mp[i])<mp[i]||f[i-1][j][k]==inf)continue;
                for(int op=ch;op<=ms;++op){
                    if((op&ch)<ch)continue;
                    int ns=((k|op|(op<<1)|(op>>1))&ms);
                    f[i][ns][mp[i+1]|op]=min(v[i][op]+f[i-1][j][k],f[i][ns][mp[i+1]|op]); 
                    // printf("%d %d %d + %d -> %d %d %d == %d\n",i-1,j,k,v[i][op],i,ns,mp[i+1]|op,f[i][ns][mp[i+1]|op]);
                }       
            }
        }
    }
    int ans=inf;
    for(int i=0;i<=ms;++i)ans=min(ans,f[n][ms][i]);
    printf("%d\n",ans);

    return 0;
}

B. block

第一问按照\(1->val 2->key\)排序,从大到小考虑每个数有多少位置可以放,统计一下即可。

可恶,第二关键字搞错了,然而…..

第二问直接拿链表暴力搞有\(90\)

正解平衡树二分或者奇妙线段树

平衡树二分我不理解,感觉那玩意两个关键字,没有二分所需要的单调性。。

线段树就是,你取一个数,所有比他小的数的\(key\)需要\(–\),然后每次贪心选择字典序最小的,但是需要保证\(key>0\),也就是说如果有\(key==1\)的需要优于字典序考虑

注意上面那个变化的\(key\)是一个类似备份的东西,它可以变,但是比较字典序需要用原数

然后,线段树有点细节啊。。。

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

using namespace std;

const int mod=1e9+7;
const int maxn=500005;
struct node{
    int key,val;
}d[maxn];
int n;
bool cmp(node x,node y){
    if(x.val!=y.val)return x.val>y.val;
    return x.key<y.key;
}
bool cmp2(node x,node y){
    if(x.val!=y.val)return x.val<y.val;
    return x.key<y.key;
}

void work(){
     sort(d+1,d+n+1,cmp);
    int ans=1,cnt=1;
    for(int i=1;i<=n;++i){
        if(d[i].val==d[i - 1].val){
            ans=1ll*ans*min(d[i].key+cnt,i)%mod;
            ++cnt;
        }else{
            ans=1ll*ans*min(d[i].key,i)%mod;
            cnt=1;
        } 
    }
    printf("%d\n",ans);
}
struct tree{
    struct note{
        int val,tag,pos,tu,vpos;
    }t[maxn<<2|1];
    void push_down(int x){
        int ls=x<<1,rs=x<<1|1;
        t[ls].val+=t[x].tag;
        t[rs].val+=t[x].tag;
        t[ls].tag+=t[x].tag;
        t[rs].tag+=t[x].tag;
        t[x].tag=0;
    }
    void push_up(int x){
        int ls=x<<1,rs=x<<1|1;
        if(t[ls].pos){
            t[x].pos=t[ls].pos;
            t[x].val=t[ls].val;
            t[x].vpos=t[ls].vpos;
            t[x].tu=t[ls].tu;
        }
        if(t[rs].pos){
            if(t[rs].val<t[x].val){
                t[x].val=t[rs].val;
                t[x].vpos=t[rs].vpos;
            }
            if(t[rs].tu<t[x].tu){
                t[x].pos=t[rs].pos;
                t[x].tu=t[rs].tu;
            }
        }
        
    }
    void modify(int x,int l,int r,int L,int R,int v){
        if(L>R)return;
        if(L<=l&&r<=R){
            t[x].val+=v;
            t[x].tag+=v;
            return;
        }
        int mid=(l+r)>>1;
        if(t[x].tag)push_down(x);
        if(L<=mid)modify(x<<1,l,mid,L,R,v);
        if(R>mid)modify(x<<1|1,mid+1,r,L,R,v);
        push_up(x);
    }
    void modify(int x,int l,int r,int pos,int v){
        if(l==r){
            t[x].pos=t[x].vpos=l;
            t[x].val=t[x].tu=v;
            return;
        }
        int mid=(l+r)>>1;
        if(t[x].tag)push_down(x);
        if(pos<=mid)modify(x<<1,l,mid,pos,v);
        else modify(x<<1|1,mid+1,r,pos,v);
        push_up(x);
    }

}T;

int main(){
    freopen("block.in","r",stdin);
    freopen("block.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d%d",&d[i].key,&d[i].val);
    work();
    sort(d+1,d+n+1,cmp2);
    for(int i=1;i<=n;++i)T.modify(1,1,n,i,d[i].key);
    for(int i=1;i<=n;++i){
        int pos=T.t[1].val==1?T.t[1].vpos:T.t[1].pos;
        printf("%d %d\n",d[pos].key,d[pos].val);
        T.modify(1,1,n,1,pos-1,-1);
        T.modify(1,1,n,pos,498244353);
    }
    return 0;
}

C. graph

\(emmm..\)

一个教训

是假的才对,为啥?类型转化。。。。。。

ceil(x/y)
ceil((float)x/y)

二维最短路,\(dis[i][j]\)表示\(1->i\)走了\(j\)条\(-1\)路径的最短路

枚举走几条\(-1\)为最短路,解不等式组

\(dis [n] [j] + val * j >= dis [n] [i] + val * i\)

解出来的范围随便取个数跑\(1-i\),\(n-i\)的最短路,枚举点看是否可以为最短路上的点,(\(d[0][j]+d[1][j]==val*i+dis[n][i]\))

不过\(lyin\)说这个解法假了,正解应该是维护凸包.

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>

using namespace std;

const int maxn=1005;
const int maxm=2005;
typedef long long ll;
int n,m,head[maxn],tot,cnt;
ll inf=0x3f3f3f3f3f3f3f3f;
bool ans[maxn];
struct edge{
    int to,net,val;
}e[maxm<<1|1];
void add(int u,int v,int w){
    e[++tot].net=head[u];
    head[u]=tot;
    e[tot].to=v;
    e[tot].val=w;
}

struct node{
    int x,cnt;
    ll val;
    node(){}
    node(int _x,int _cnt,ll _val){
        x=_x;cnt=_cnt;val=_val;
    }
    bool operator <(node x)const {
        return val>x.val;
    }
};
priority_queue<node>q;
bool vis2[maxn][maxm];
ll dis[maxn][maxm];
void dijj(){
    memset(vis2,0,sizeof(vis2));
    memset(dis,0x3f,sizeof(dis));
    dis[1][0]=0;q.push(node(1,0,0));
    while(!q.empty()){
        node x=q.top();q.pop();
        if(vis2[x.x][x.cnt])continue;
        vis2[x.x][x.cnt]=1;
        for(int i=head[x.x];i;i=e[i].net){
            int v=e[i].to;
            if(e[i].val==-1){
                if(dis[v][x.cnt+1]>dis[x.x][x.cnt]&&x.cnt<=cnt){
                    dis[v][x.cnt+1]=dis[x.x][x.cnt];
                    q.push(node(v,x.cnt+1,dis[v][x.cnt+1]));
                }
            }else{
                if(dis[v][x.cnt]>dis[x.x][x.cnt]+e[i].val){
                    dis[v][x.cnt]=dis[x.x][x.cnt]+e[i].val;
                    q.push(node(v,x.cnt,dis[v][x.cnt]));
                }
            }
        }
    }
}

ll d[2][maxn];
bool vis [maxn];

void dij(int op,ll va){
    memset(vis,0,sizeof(vis));
    int s=op==0?1:n;
    d[op][s]=0;
    q.push(node(s,0,0));
    while(!q.empty()){
        node x=q.top();q.pop();
        if(vis[x.x])continue;
        vis[x.x]=1;
        for(int i=head[x.x];i;i=e[i].net){
            int v=e[i].to;
            ll w=e[i].val==-1?va:e[i].val;
            if(d[op][v]>d[op][x.x]+w){
                d[op][v]=d[op][x.x]+w;
                q.push(node(v,0,d[op][v]));
            }
        }
    }
}


int main(){
    freopen("graph.in","r",stdin);
    freopen("graph.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        int u,v,w;scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);add(v,u,w);if(w==-1)++cnt;
    }
    dijj();
    for(int i=0;i<=cnt;++i){
        if(dis[n][i]==inf)continue;
        ll l=0,r=inf;bool flag=0;
        for(int j=0;j<=cnt;++j){
            if(i==j)continue;
            ll x=dis[n][j]-dis[n][i];
            ll y=i-j;
            // dis [n] [j] + val * j >= dis [n] [i] + val * i
            // dis [n] [j] - dis [n] [i] >= (i-j) * val
            // x >= y * val
            if(x<=0&&y>0){flag=1;break;}
            if(x>0&&y<0)continue;
            if(y<0)l=max(l,ll(ceil((float)x/y)));
            else r=min(r,ll(x/y));
        }
        if(flag||l>r)continue;
        memset(d,0x3f,sizeof(d));
        dij(1,l);dij(0,l);
        ll mxl=l*i+dis[n][i];
        for(int j=2;j<n;++j)if(d[0][j]+d[1][j]==mxl)ans[j]=1;
    }
    ans[1]=ans[n]=1;
    for(int i=1;i<=n;++i)if(ans[i])printf("1");else printf("0");
    return 0;
}
————————

Almost because of file explosion 0…

A. matrix

State pressure, \ (f [i] [J] [k] \) indicates the minimum cost of line \ (i-1 \) with the status of \ (J \) and line \ (I \) with the status of \ (K \).

Looks like the complexity is wrong? But the complexity is acceptable after abandoning the illegal state. How can I prove that I won’t

#include<cstdio>
#include<cstring>

using namespace std;
int min(int x,int y){return x<y?x:y;}
const int maxn=13;
int n,m,mp[maxn],ls[maxn];
int v[maxn][1025];
char c[maxn];
int f[11][1025][1025];
int main(){
    freopen("matrix.in","r",stdin);
    freopen("matrix.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%s",c+1);
        for(int j=1;j<=m;++j)
           if(c[j]=='1')mp[i]=mp[i]|(1<<(j-1));
    }
    int ms=(1<<m)-1;
    for(int i=1;i<=n;++i){
      for(int j=1;j<=m;++j)scanf("%d",&ls[j]);
      for(int j=1;j<=ms;++j){
          for(int k=1;k<=m;++k){
              if((1<<(k-1))&j)v[i][j]+=ls[k];
          }
      }
    }
    memset(f,0x3f,sizeof(f));
    int inf=f[0][0][0];
    f[0][ms][mp[1]]=0;mp[0]=ms;
    for(int i=1;i<=n;++i){
        for(int j=mp[i-1];j<=ms;++j){// las line
            if((j&mp[i-1])<mp[i-1])continue;
            int ch=(~j)&ms;
            for(int k=mp[i];k<=ms;++k){// now line
                if((k&mp[i])<mp[i]||f[i-1][j][k]==inf)continue;
                for(int op=ch;op<=ms;++op){
                    if((op&ch)<ch)continue;
                    int ns=((k|op|(op<<1)|(op>>1))&ms);
                    f[i][ns][mp[i+1]|op]=min(v[i][op]+f[i-1][j][k],f[i][ns][mp[i+1]|op]); 
                    // printf("%d %d %d + %d -> %d %d %d == %d\n",i-1,j,k,v[i][op],i,ns,mp[i+1]|op,f[i][ns][mp[i+1]|op]);
                }       
            }
        }
    }
    int ans=inf;
    for(int i=0;i<=ms;++i)ans=min(ans,f[n][ms][i]);
    printf("%d\n",ans);

    return 0;
}

B. block

The first question is to sort according to \ (1 – & gt; Val 2 – & gt; key \). From large to small, consider how many positions each number can put, and make statistics.

Damn, the second keyword is wrong, but

The second question is to take the linked list directly and engage in violence \ (90 \)

Positive solution equilibrium tree dichotomy or wonderful segment tree

I don’t understand the dichotomy of the balance tree. I feel that the two keywords of that thing don’t have the monotonicity required by dichotomy..

The segment tree is that you take a number, and all numbers smaller than it \ (key \) need \ (- \), and then greedily choose the one with the smallest dictionary order every time, but it needs to ensure that \ (Key & gt; 0 \), that is, if there is a need for \ (key = = 1 \), it is better than the dictionary order

Note that the changed \ (key \) above is something similar to backup. It can be changed, but the original number needs to be used to compare the dictionary order

Then, the line segment tree has some details…

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

using namespace std;

const int mod=1e9+7;
const int maxn=500005;
struct node{
    int key,val;
}d[maxn];
int n;
bool cmp(node x,node y){
    if(x.val!=y.val)return x.val>y.val;
    return x.key<y.key;
}
bool cmp2(node x,node y){
    if(x.val!=y.val)return x.val<y.val;
    return x.key<y.key;
}

void work(){
     sort(d+1,d+n+1,cmp);
    int ans=1,cnt=1;
    for(int i=1;i<=n;++i){
        if(d[i].val==d[i - 1].val){
            ans=1ll*ans*min(d[i].key+cnt,i)%mod;
            ++cnt;
        }else{
            ans=1ll*ans*min(d[i].key,i)%mod;
            cnt=1;
        } 
    }
    printf("%d\n",ans);
}
struct tree{
    struct note{
        int val,tag,pos,tu,vpos;
    }t[maxn<<2|1];
    void push_down(int x){
        int ls=x<<1,rs=x<<1|1;
        t[ls].val+=t[x].tag;
        t[rs].val+=t[x].tag;
        t[ls].tag+=t[x].tag;
        t[rs].tag+=t[x].tag;
        t[x].tag=0;
    }
    void push_up(int x){
        int ls=x<<1,rs=x<<1|1;
        if(t[ls].pos){
            t[x].pos=t[ls].pos;
            t[x].val=t[ls].val;
            t[x].vpos=t[ls].vpos;
            t[x].tu=t[ls].tu;
        }
        if(t[rs].pos){
            if(t[rs].val<t[x].val){
                t[x].val=t[rs].val;
                t[x].vpos=t[rs].vpos;
            }
            if(t[rs].tu<t[x].tu){
                t[x].pos=t[rs].pos;
                t[x].tu=t[rs].tu;
            }
        }
        
    }
    void modify(int x,int l,int r,int L,int R,int v){
        if(L>R)return;
        if(L<=l&&r<=R){
            t[x].val+=v;
            t[x].tag+=v;
            return;
        }
        int mid=(l+r)>>1;
        if(t[x].tag)push_down(x);
        if(L<=mid)modify(x<<1,l,mid,L,R,v);
        if(R>mid)modify(x<<1|1,mid+1,r,L,R,v);
        push_up(x);
    }
    void modify(int x,int l,int r,int pos,int v){
        if(l==r){
            t[x].pos=t[x].vpos=l;
            t[x].val=t[x].tu=v;
            return;
        }
        int mid=(l+r)>>1;
        if(t[x].tag)push_down(x);
        if(pos<=mid)modify(x<<1,l,mid,pos,v);
        else modify(x<<1|1,mid+1,r,pos,v);
        push_up(x);
    }

}T;

int main(){
    freopen("block.in","r",stdin);
    freopen("block.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d%d",&d[i].key,&d[i].val);
    work();
    sort(d+1,d+n+1,cmp2);
    for(int i=1;i<=n;++i)T.modify(1,1,n,i,d[i].key);
    for(int i=1;i<=n;++i){
        int pos=T.t[1].val==1?T.t[1].vpos:T.t[1].pos;
        printf("%d %d\n",d[pos].key,d[pos].val);
        T.modify(1,1,n,1,pos-1,-1);
        T.modify(1,1,n,pos,498244353);
    }
    return 0;
}

C. graph

\(emmm..\)

A lesson

It’s fake. Why? Type conversion……

ceil(x/y)
ceil((float)x/y)

Two dimensional shortest path, \ (DIS [i] [J] \) indicates that \ (1 – & gt; I \) has taken the shortest path of \ (J \) \ (- 1 \)

Enumerate several \ (- 1 \) as the shortest path to solve the inequality system

\(dis [n] [j] + val * j >= dis [n] [i] + val * i\)

Take any number of the solved range and run the shortest path of \ (1-I \), \ (n-i \). Enumerate the points to see if they can be the points on the shortest path, (\ (d [0] [J] + D [1] [J] = = Val * I + dis [n] [i] \))

But \ (lyin \) said that this solution is false, and the positive solution should be to maintain the convex hull

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>

using namespace std;

const int maxn=1005;
const int maxm=2005;
typedef long long ll;
int n,m,head[maxn],tot,cnt;
ll inf=0x3f3f3f3f3f3f3f3f;
bool ans[maxn];
struct edge{
    int to,net,val;
}e[maxm<<1|1];
void add(int u,int v,int w){
    e[++tot].net=head[u];
    head[u]=tot;
    e[tot].to=v;
    e[tot].val=w;
}

struct node{
    int x,cnt;
    ll val;
    node(){}
    node(int _x,int _cnt,ll _val){
        x=_x;cnt=_cnt;val=_val;
    }
    bool operator <(node x)const {
        return val>x.val;
    }
};
priority_queue<node>q;
bool vis2[maxn][maxm];
ll dis[maxn][maxm];
void dijj(){
    memset(vis2,0,sizeof(vis2));
    memset(dis,0x3f,sizeof(dis));
    dis[1][0]=0;q.push(node(1,0,0));
    while(!q.empty()){
        node x=q.top();q.pop();
        if(vis2[x.x][x.cnt])continue;
        vis2[x.x][x.cnt]=1;
        for(int i=head[x.x];i;i=e[i].net){
            int v=e[i].to;
            if(e[i].val==-1){
                if(dis[v][x.cnt+1]>dis[x.x][x.cnt]&&x.cnt<=cnt){
                    dis[v][x.cnt+1]=dis[x.x][x.cnt];
                    q.push(node(v,x.cnt+1,dis[v][x.cnt+1]));
                }
            }else{
                if(dis[v][x.cnt]>dis[x.x][x.cnt]+e[i].val){
                    dis[v][x.cnt]=dis[x.x][x.cnt]+e[i].val;
                    q.push(node(v,x.cnt,dis[v][x.cnt]));
                }
            }
        }
    }
}

ll d[2][maxn];
bool vis [maxn];

void dij(int op,ll va){
    memset(vis,0,sizeof(vis));
    int s=op==0?1:n;
    d[op][s]=0;
    q.push(node(s,0,0));
    while(!q.empty()){
        node x=q.top();q.pop();
        if(vis[x.x])continue;
        vis[x.x]=1;
        for(int i=head[x.x];i;i=e[i].net){
            int v=e[i].to;
            ll w=e[i].val==-1?va:e[i].val;
            if(d[op][v]>d[op][x.x]+w){
                d[op][v]=d[op][x.x]+w;
                q.push(node(v,0,d[op][v]));
            }
        }
    }
}


int main(){
    freopen("graph.in","r",stdin);
    freopen("graph.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        int u,v,w;scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);add(v,u,w);if(w==-1)++cnt;
    }
    dijj();
    for(int i=0;i<=cnt;++i){
        if(dis[n][i]==inf)continue;
        ll l=0,r=inf;bool flag=0;
        for(int j=0;j<=cnt;++j){
            if(i==j)continue;
            ll x=dis[n][j]-dis[n][i];
            ll y=i-j;
            // dis [n] [j] + val * j >= dis [n] [i] + val * i
            // dis [n] [j] - dis [n] [i] >= (i-j) * val
            // x >= y * val
            if(x<=0&&y>0){flag=1;break;}
            if(x>0&&y<0)continue;
            if(y<0)l=max(l,ll(ceil((float)x/y)));
            else r=min(r,ll(x/y));
        }
        if(flag||l>r)continue;
        memset(d,0x3f,sizeof(d));
        dij(1,l);dij(0,l);
        ll mxl=l*i+dis[n][i];
        for(int j=2;j<n;++j)if(d[0][j]+d[1][j]==mxl)ans[j]=1;
    }
    ans[1]=ans[n]=1;
    for(int i=1;i<=n;++i)if(ans[i])printf("1");else printf("0");
    return 0;
}