20240221寒假单元测验题解

· · 个人记录

T316849 人数

考察最值、排序等。可以用最值，也可以用sort、桶排序等。

T311007 优秀的码字

本题考察枚举及其优化。

枚举：枚举第i,j个字符串(i<j)再判断其不同子串的个数。时间复杂度O(n^2m)

如何优化？

  1. 当出现小于k的距离，立即退出。

  2. 数学优化。在 60%数据基础上另有 40% 的数据 N>2^m 根据鸽笼原理，那么必然有两个相同的字符。一定不符合要求。

参考代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int maxn=222;
string ss[maxn];

int main()
{
    int N,M,K;scanf("%d%d%d",&N,&M,&K);
    if(N>(1LL<<M))return puts("No"),0;
    for(int i=1;i<=N;++i) cin>>ss[i];
    sort(ss+1,ss+1+N);//排序可以找出更近的符号。
    for(int i=1;i<=N;++i)
    {
        int dis=0,j=i+1;
        for(int k=0;k<M;++k)if(ss[i][k]!=ss[j][k]) ++dis;
        if(dis<K) return puts("No"),0;
    }

    for(int i=1;i<=N;++i)
        for(int j=i+2;j<=N;++j)
    {
        int dis=0;
        for(int k=0;k<M;++k)if(ss[i][k]!=ss[j][k]) ++dis;
        if(dis<K) return puts("No"),0;
    }
    return puts("Yes"),0;
}

T3 挑战赛

考察内容：排序+贪心。 什么情况下一个人能拍到榜首呢？

自己先拿到最高分，让后其余的选手得分尽量低。

其他选手怎样得分尽量低呢？

因为题目中讨论的是机会，可以从最有力一个选手的角度出发安排战局。 参考代码： ```cpp #include<bits/stdc++.h> using namespace std; const int N=3e5+114; int a[N]; bool cmp(int x,int y){ return x>y; } int main(){ int n,maxx=0,sum=0; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } sort(a+1,a+1+n,cmp); for(int i=1;i<=n;i++){//高分的人本次得到小分。 maxx=max(maxx,a[i]+i); } for(int i=1;i<=n;i++){ if(a[i]+n>=maxx) sum++; } cout<<sum; return 0; } ``` #### 方法二 zrul 二分如果一个排名x能拿第一，排名比x高的一定能na第一 ```cpp #include<bits/stdc++.h> #define int long long #define inl inline #define reg register #define N 300005 #define INF 2147483647 using namespace std; int n,a[N],b[N]; inl int read(){ reg int f=1,x=0; reg 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 f*x; } inl void write(int x){ if(x<0) x=-x; if(x>=10) write(x/10); putchar(x%10^48); } bool check(int x){ int tot=n-1; for(int i=1;i<=n;i++,tot--) if(b[i]!=a[x]&&(b[i]+tot>a[x]+n||b[i]+tot==a[x]+n&&i<x)) return false; return true; } int lower(){ int l=1,r=n,mid=0,ans=0; while(l<=r){ mid=l+r>>1; if(check(mid)){ ans=mid; l=mid+1; }else r=mid-1; } return ans; } signed main(){ n=read(); for(int i=1;i<=n;++i) a[i]=read(); memcpy(b,a,sizeof(a)); sort(a+1,a+n+1,greater<int>()); sort(b+1,b+n+1); write(lower()); return 0; } ``` ### T316918 爬楼梯 本题考察了递推和高精度加法。 设$f[i]$为达到第$i$层楼梯的方案数。 则$f[i]=f[i-1]+f[i-2]+f[i-3],i>3

初始条件为f[1]=1,f[2]=2,f[3]=4,数据范围较大，需要用高精度加法。

参考代码：

#include<iostream>
#include<cstdio>
using namespace std;
int n,f[5010][5010],len;
void add(int k) { //高精加法
    for(int i=1; i<=len; i++)//两数相加
        f[k][i]=f[k-1][i]+f[k-2][i]+f[k-3][i];
    for(int i=1; i<=len; i++) { //进位
        f[k][i+1]+=f[k][i]/10;
        f[k][i]%=10;
    }
    if(f[k][len+1]>0)len++;
}
int main() {

    cin>>n;
    len=1;
    f[1][1]=1;//预处理
    f[2][1]=2;//预处理
    f[3][1]=4;
    for(int i=4; i<=n; i++)//开始计算
        add(i);

    for(int j=len; j>=1; j--)//输出
        cout<<f[n][j];
    cout<<endl;
    return 0;
}

T316902 分糖果

本题的要求最大值最小，二分答案的标志性名次。那么分析本题具有单调性吗？

根据题意，小朋友们得到的糖果数越平均越好。蛀牙值越大，每个小朋友分的糖果数越多，分的份数就越少。否则越多。

我们二分蛀牙值，如果分完后糖果有剩余，就还要增大；如果不够分的，就要缩小。

参考代码：

#include <iostream>  
using namespace std;
long long n,m,l=1,r,ans;
long long a[300010];
bool check(long long x){ //x 是当前的蛀牙值
    long long sum=0;
    for(int i=1;i<=m;i++) sum+=(a[i]+x-1)/x;
    return sum<=n;
} 
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){cin>>a[i];r+=a[i];} //mid 的极限是总共的球数 
    while(l<r){ //二分模板 
        long long mid=(l+r)/2+1;
        if(check(mid)){r=mid-1;ans=mid;}
        else l=mid;
    }
    cout<<ans;
    return 0; 
}

T310718 花园

本题考察了结构体和集合的容斥。

要处理重合的部分

我们给定了矩形的对角线的两个端点，但没有说明大小，要统一为左上角和右下角，然后，找到交集部分。

如何找到交集部分？共有四个横坐标，四个纵坐标，找到中间的两个。

参考代码：

#include <iostream>
#include <iomanip>
#include<stdio.h> 
using namespace std;
typedef long long ll;
struct node{//左上角 和右下角 
    ll xa,ya,xb,yb;
}jx1,jx2,jx3;
int n;

node le_ri(){
    node t;
    cin>>t.xa>>t.ya>>t.xb>>t.yb;
    if(t.xa>t.xb)swap(t.xa,t.xb);
    if(t.ya>t.yb)swap(t.ya,t.yb);
    return t;
}
ll s(node t){
    return (t.xb-t.xa)*(t.yb-t.ya);
}
int main()
{

    cin>>n;
    jx1=le_ri();
    if(n==1){
        cout<<s(jx1)<<endl;
        return 0;
    }
    jx2=le_ri();
    if(jx1.xa>=jx2.xb||jx1.xb<=jx2.xa||jx1.ya>=jx2.yb||jx1.yb<=jx2.ya) {//2在1的左侧，右侧，下侧，上侧 
        cout<<s(jx1)+s(jx2)<<endl;
        return 0;
    }
    //相交的情况
     jx3.xa=max(jx1.xa,jx2.xa);
     jx3.xb=min(jx1.xb,jx2.xb);
     jx3.ya=max(jx1.ya,jx2.ya);
     jx3.yb=min(jx1.yb,jx2.yb);
     cout<<s(jx1)+s(jx2)-s(jx3)<<endl;

}