模拟赛09题解

WTing · 2023-10-18 19:43:22 · 个人记录

T1 序列分组

贪心。直接升序排序后从小到大挨个分组即可


#include<cstdio>

#include<algorithm>

using namespace std;

int n,a[10039],ans,tot,pus,f[100039];

int main(){

    register int i,j,k;

    scanf("%d",&n);

    for(i=1;i<=n;i++){

        scanf("%d",&a[i]);

    }

    sort(a+1,a+n+1);

    for(i=1;i<=n;i++){

        if(!f[i]){

            for(j=1;j<=n;j++) if(a[j]%a[i]==0&&!f[j]) f[j]=1;

            ans++;

        }

    }

    printf("%d",ans);

}

T2 密码检查

分类讨论：

长度小于6，可以发现
- 只有当刚好5个字符，且全部是一样的时候，需要两步。
- 其他情况全都是直接增加即可
长度介于6和20，也好办
- 统计连续，不难发现，若某段连续个数为c个，则最少需c//3次替换
- 考虑还有必须要出现小写、大写、数字三种字符
- 综合考虑，只要先计算出替换次数，然后判断是否可以顺便在替换时将三种字符也一并获得。例. 若只有1次替换，但是颜色只有1种，则需要加多一次替换，其他情况也容易整理
最恶心的来了，长度大于20
- 考虑删除到20个以内，然后参照20个以内的做法
- 若有多个连续段：长度分别是3、6、8、4、则应先删除3的倍数的，不然你删了后还需要替换才能解决所有冲突。例. 先删4，则4变成3，你还需要将3进行一次替换。但是，先删3，则直接合法。还有，若都不是3的倍数，则应根据%3后的大小排序，小的在前，同理，%3越小，越有可能接近到3的倍数。
- 所以直接根据这个条件排序，一个一个删，每次删的时候还有维护有序序列。
- 删到20个以内，然后直接参照20个以内的做法。
核心代码：


class Solution {

public:

    static bool check(int x, int y) {

        if (x < 3 && y >= 3) {

            return true;

        } else if (x >= 3 && y >= 3) {

            return x % 3 > y % 3;

        } else if (x >= 3 && y < 3) {

            return false;

        } else {

            return x < y;

        }

    }

    int strongPasswordChecker(string s) {

        int n = s.length();

        int c = 1;

        int num_update = 0;

        int suma = 0, sumA = 0, sumX = 0;

        for (int i = 0; i < n; ++i) {

            if (s[i] >= 'a' && s[i] < 'z') {

                suma = 1;

            }

            if (s[i] >= 'A' && s[i] < 'Z') {

                sumA = 1;

            }

            if (s[i] >= '0' && s[i] < '9') {

                sumX = 1;

            }

        }

        int sumx = suma + sumA + sumX;

        for (int i = 1; i < n; ++i) {

            if (s[i] == s[i - 1]) {

                c += 1;

            } else {

                num_update += c / 3;

                c = 1;

            }

        }

        num_update += c / 3;

        if (n < 6) {

            if (n == 5) {

                string f(5, s[0]);

                if (s.substr(0, 5) == f) {

                    return 2;

                }

            }

            return max(6 - n, num_update);

        } else if (n > 20) {

            vector<int> a;

            c = 1;

            int rest = n - 20;

            num_update = 0;

            int num_delete = 0;

            int m = n;

            for (int i = 1; i < n; ++i) {

                if (s[i] == s[i - 1]) {

                    c += 1;

                } else {

                    a.push_back(c);

                    c = 1;

                }

            }

            a.push_back(c);

            int na = a.size();

            for (int j = na - 1; j > 0; --j) {

                for (int i = 1; i <= j; ++i) {

                    if (check(a[i - 1], a[i])) {

                        swap(a[i], a[i - 1]);

                    }

                }

            }

            a.push_back(1);

            while (rest > 0) {

                while (!check(a[0], a[1]) && rest > 0) {

                    a[0] -= 1;

                    rest -= 1;

                    int i = 0;

                    while (i < na && check(a[i], a[i + 1])) {

                        swap(a[i], a[i + 1]);

                        i += 1;

                    }

                }

            }

            num_update = 0;

            for (int i : a) {

                num_update += i / 3;

            }

            if (num_update <= 3 - sumx) {

                num_update = 3 - sumx;

            }

            return num_update + n - 20;

        } else {

            if (num_update <= 3 - sumx) {

                num_update = 3 - sumx;

            }

            return num_update;

        }

    }

};

T3 雨中人

其实从左往右去遍历，只要考虑上升段就可以了，因为每上升一段，那么肯定在某些水位下会出现一个新的陆地，如果当前高度是x，下一高度是y，且y \gt x那么水位高度从x+1到y这一段都会有新的陆地诞生，这里相当于一个区间修改，统一加1，所以可以用数据结构如树状数组结合差分去实现。至于下降，其实是无所谓的。所以我们只需离散化后用树状数组即可。但是还有修改，注意到每次修改只会影响到和前后的升降关系，所以将这个关系进行维护，考虑先将原先的高度和前后形成的关系删除（同样要利用差分），然后更新高度，在和前后重新进行差分维护。


#include<bits/stdc++.h>

#define lowbit(x) x&-x

using namespace std;

int n,m,tot,h[500000],f[500000],high[500000],sum[500000],t[500000];

struct data{

    int high,id;

}a[500000];;

bool cmp(data a,data b){

    return a.high<b.high;

}

inline void read(int &x){

    int f=1;x=0;char ch;

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();x*f;}

}

inline void add(int x,int num){

    while(x<=tot)sum[x]+=num,x+=lowbit(x);

}

inline int getsum(int x){

    int Sum=0;while(x>0)Sum+=sum[x],x-=lowbit(x);

    return Sum;

}

inline void operation(int i,int x){

    if(h[i]>h[i-1])add(h[i-1]+1,-x),add(h[i]+1,x);

    if(h[i]<h[i+1]&&i<n)add(h[i]+1,-x),add(h[i+1]+1,x);

}

int main(){

    read(n);read(m);

    for(int i=1;i<=n;i++)read(a[i].high),a[i].id=i;

    for(int i=1;i<=m;i++){

        read(t[i]);

        if(t[i]==2)read(high[i]);

        read(a[n+i].high);a[n+i].id=n+i;

    }

    sort(a+1,a+n+m+1,cmp);

    f[a[1].id]=1;tot=1;

    for(int i=2;i<=n+m;i++){

        if(a[i].high!=a[i-1].high)

            f[a[i].id]=++tot;

        else

            f[a[i].id]=tot;

    }

    for(int i=1;i<=n;i++){

        h[i]=f[i];

        if(h[i]>h[i-1])add(h[i-1]+1,1),add(h[i]+1,-1);

    }

    for(int i=1;i<=m;i++){

        if(t[i]==1)cout<<getsum(f[n+i])<<endl;

        else{

            operation(high[i],1);

            h[high[i]]=f[n+i];

            operation(high[i],-1);

        }

    }

    return 0;

}

T4 Miku们的要求

由于miku的数量只有16个，容易想到状态压缩DP。

于是$f[S][i] = min(f[S'][j] + dist[i][j]) (S == S' + {i}, j \in S')

其中 j 为下一个miku，dist[i][j] 为两个miku之间的最短距离，可以通过以所有葱为起点的BFS预处理出来。


#include<cstdio>

#include<queue>

#include<iostream>

#include<cstring>

#define min(a,b) ((a)<(b)?(a):(b))

using namespace std;

int n,m,k,head,ans,tot,pus,num,now;

int xp[5]= {0,1,0,-1,0};

int yp[5]= {0,0,1,0,-1};

char _s;

int mx[39],my[39],mhead;

int xs[10039],ys[10039];

int sx,sy,tx,ty;

int f[139][139],a[139][139],fs[100039][39],qs[39][10039],ss[39][39];

struct yyy {

    int x,y;

} tmp;

queue<yyy> q;

int main() {

    register int i,j,k,h;

    scanf("%d%d",&n,&m);

    for(i=1; i<=n; i++) {

        for(j=1; j<=m; j++) {

            cin>>_s;

            if(_s=='.') a[i][j]=1;

            if(_s=='S') a[i][j]=1,sx=i,sy=j;

            if(_s=='T') a[i][j]=1,tx=i,ty=j;

            if(_s=='O') ans++,a[i][j]=2,xs[ans]=i,ys[ans]=j;

            if(_s=='M') a[i][j]=3,mx[++mhead]=i,my[mhead]=j;

        }

    }

    for(i=1; i<=n; i++) {

        for(j=1; j<=m; j++) {

            if(a[i][j]==3) {

                q.push((yyy) {i,j});

                while(!q.empty()) {

                    tmp=q.front();

                    q.pop();

                    for(k=1; k<=4; k++) {

                        if(!f[tmp.x+xp[k]][tmp.y+yp[k]]&&a[tmp.x+xp[k]][tmp.y+yp[k]]) f[tmp.x+xp[k]][tmp.y+yp[k]]=f[tmp.x][tmp.y]+1,q.push((yyy) {tmp.x+xp[k],tmp.y+yp[k]});

                    }

                }

                ++head;

                for(k=1; k<=ans;k++) {

                    qs[head][k]=f[xs[k]][ys[k]];

                    if(f[xs[k]][ys[k]]==0) qs[head][k]=1e9;

                }

                memset(f,0,sizeof(f));

            }

        }

    }

    q.push((yyy) {sx,sy});

    while(!q.empty()) {

        tmp=q.front();

        q.pop();

        for(i=1; i<=4; i++) {

            if(!f[tmp.x+xp[i]][tmp.y+yp[i]]&&a[tmp.x+xp[i]][tmp.y+yp[i]]) f[tmp.x+xp[i]][tmp.y+yp[i]]=f[tmp.x][tmp.y]+1,q.push((yyy) {tmp.x+xp[i],tmp.y+yp[i]});

        }

    }

    for(i=1; i<=ans; i++) {

        qs[0][i]=f[xs[i]][ys[i]];

        if(f[xs[i]][ys[i]]==0) qs[0][i]=1e9;

    }

    memset(f,0,sizeof(f));

    q.push((yyy) {tx,ty});

    while(!q.empty()) {

        tmp=q.front();

        q.pop();

        for(i=1; i<=4; i++) {

            if(!f[tmp.x+xp[i]][tmp.y+yp[i]]&&a[tmp.x+xp[i]][tmp.y+yp[i]]) f[tmp.x+xp[i]][tmp.y+yp[i]]=f[tmp.x][tmp.y]+1,q.push((yyy) {tmp.x+xp[i],tmp.y+yp[i]});

        }

    }

    for(i=1; i<=mhead; i++) {

        qs[head+1][i]=f[mx[i]][my[i]];/*printf("%d\n",qs[head+1][i]);*/

        if(f[mx[i]][my[i]]==0) qs[head+1][i]=1e9;

    }

    memset(fs,0x3f,sizeof(fs));

    for(i=1; i<=head; i++) {

        for(j=1; j<=ans; j++) {

            fs[1<<i-1][i]=min(fs[1<<i-1][i],qs[0][j]+qs[i][j]);

        }

    }

    for(i=1;i<=head;i++){

        for(j=1;j<=head;j++){

            if(i!=j){

                ss[i][j]=1e9;

                for(k=1;k<=ans;k++){

                    ss[i][j]=min(ss[i][j],qs[i][k]+qs[j][k]);

                }

            }

        }

    }

    for(i=1; i<=(1<<head)-1; i++) {

        for(j=1; j<=head; j++) {

            if(i&(1<<j-1)) {

                for(k=1; k<=head; k++) {

                    if((!(i&(1<<k-1)))&&j!=k) {

                        fs[i+(1<<k-1)][k]=min(fs[i+(1<<k-1)][k],fs[i][j]+ss[j][k]);

                    }

                }

            }

        }

    }

    ans=1e9;

    for(i=1; i<=head; i++) ans=min(ans,fs[(1<<head)-1][i]+qs[head+1][i]);

    if(ans==1e9) printf("-1");

    else printf("%d\n",ans);

}