考试周欢乐赛 题解

2023/6/13 C++ 算法竞赛 题解 考试周欢乐赛

存一下训练赛的代码

A. 二分1

题源-洛谷P2249

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
int a[N];
int main() {
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    while(m--)
    {
        int q;
        cin>>q;
        int pos=lower_bound(a+1,a+1+n,q)-a;
        if(a[pos]==q)
            cout<<pos<<' ';
        else
            cout<<-1<<' ';
    }
    return 0;
}

B. 前缀和差分1

题源-洛谷-P8218

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int a[N];
ll sum[N];
int main() {
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        sum[i]=a[i]+sum[i-1];
    }
    int m;
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        int l,r;
        cin>>l>>r;
        cout<<sum[r]-sum[l-1]<<'\n';
    }
    return 0;
}

C. 素数1

题源-洛谷-P1835

直接筛肯定会超，所以缩小范围，筛 内的素数，然后用这些素数筛掉所给区间的合数

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
vector<ll>p;
bool vis[N];
int main() {
    ios::sync_with_stdio(false);
    ll L,R;
    cin>>L>>R;
    for(int i=2;i<N;i++)
    {
        if(!vis[i])
        {
            p.push_back(i);
            for(int j=2;j*i<N;j++)
                vis[j*i]=true;
        }
    }
    if(L==1)
        L+=1;
    if(L>R)
        cout<<0<<'\n';
    else
    {
        memset(vis,false,sizeof(vis));
        for(auto p:p)
        {
            for(int j=max(2ll,L/p);j*p<=R;j++)
            {
                if(j*p>=L)
                    vis[j*p-L]=true;
            }
        }
        ll cnt=0;
        for(int i=0;i<=R-L;i++)
            if(!vis[i])
                cnt++;
        cout<<cnt<<'\n';
    }
    return 0;
}

D. dfs1

题源-洛谷-P1025

可以dp， 是将整数n分为k份的方法数，考虑状态转移方程.

如果 ，那么

如果 ， 的划分中有1，那么可以把1拿出来，剩下 个数分 份；

如果 的划分中没有1，此时的每个划分块都大于1，那么可以将每个划分块都减去1，即 分 份.

将上面两种情况加起来就是结果，即

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=205;
int dp[N][10];
int main() {
    ios::sync_with_stdio(false);
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        dp[i][1]=dp[i][0]=1;
    for(int j=2;j<=k;j++)
    {
        for(int i=2;i<=n;i++)
        {
            if(i>j)
                dp[i][j]=dp[i-1][j-1]+dp[i-j][j];
            else
                dp[i][j]=dp[i-1][j-1];
        }
    }
    cout<<dp[n][k]<<'\n';
    return 0;
}

E. 杂题1

题源-CodeForces - 1771A

题目统计的是差的绝对值最大的数对，可以统计最大值和最小值的个数，然后乘起来再乘二就是结果

需要注意的是最大值和最小值可能相同，这个时候整个序列每个数都相同，这时候数对中的元素无法交换，不能乘2

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int a[N];
int main() {
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--)
    {
        ll n;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        int m=min_element(a+1,a+1+n)-a;
        int M=max_element(a+1,a+1+n)-a;
        ll x=0,y=0;
        for(int i=1;i<=n;i++)
        {
            if(a[i]==a[m])
                x++;
            if(a[i]==a[M])
                y++;
        }
        if(a[m]==a[M])
            cout<<x*y-n<<'\n';
        else
            cout<<x*y*2<<'\n';
    }
    return 0;
}

F. 二分2

题源-洛谷 - P2440

经典模板题

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
ll L[N];
ll n,k;
bool judge(ll x)
{
    ll cnt=0;
    for(int i=1;i<=n;i++)
        cnt+=L[i]/x;
    return cnt>=k;
}
int main() {
    ios::sync_with_stdio(false);
    cin>>n>>k;
    ll M=0;
    for(int i=1;i<=n;i++)
    {
        cin>>L[i];
        M=max(M,L[i]);
    }
    ll left=2,right=M;
    if(!judge(1))
        cout<<0<<'\n';
    else
    {
        ll ans=1;
        while(left<right)
        {
            ll mid=(left+right)>>1;
            if(judge(mid))
            {
                left=mid+1;
                ans=mid;
            }
            else
                right=mid;
        }
        cout<<ans<<'\n';
    }
    return 0;
}

G. 前缀和差分2

题源-洛谷 - P2367

只用最后一次查询最小值，可以用差分优化修改

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e6+5;
int a[N];
int d[N];
int main() {
    ios::sync_with_stdio(false);
    int n,p;
    cin>>n>>p;
    a[0]=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        d[i]=a[i]-a[i-1];
    }
    while(p--)
    {
        int x,y,z;
        cin>>x>>y>>z;
        d[x]+=z;
        d[y+1]-=z;
    }
    for(int i=1;i<=n;i++)
        a[i]=a[i-1]+d[i];
    int pos=min_element(a+1,a+1+n)-a;
    cout<<a[pos]<<'\n';
    return 0;
}

H. 二分3

题源-洛谷 - P2678

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e4+5;
int d[N];
int L,n,m;
bool judge(int x)
{
    int cur=0,cnt=0;
    for(int i=1;i<=n+1;i++)
    {
        if(d[i]-d[cur]<x)
            cnt++;
        else
            cur=i;
    }
    if(cnt>m)
        return false;
    return true;
}
int main() {
    ios::sync_with_stdio(false);
    cin>>L>>n>>m;
    d[0]=0;
    for(int i=1;i<=n;i++)
        cin>>d[i];
    d[n+1]=L;
    if(n==0)
        cout<<L<<'\n';
    else
    {
        int left=0,right=L;
        int ans=0;
        while(left<right)
        {
            int mid=(left+right)>>1;
            if(judge(mid))
            {
                left=mid+1;
                ans=mid;
            }
            else
                right=mid;
        }
        cout<<ans<<'\n';
    }
    return 0;
}

dfs2

题源-洛谷 - P1434

直接dfs复杂度会炸，于是用记忆化搜索优化

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=105;
int h[N][N],s[N][N];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int length;
int ans;
int R,C;
void dfs(int x,int y)
{
    if(x<1||x>R||y<1||y>C)
        return;
    if(s[x][y]!=0)
    {
        length+=s[x][y];
        ans=max(ans,length);
        length-=s[x][y];
        return;
    }
    length++;
    ans=max(ans,length);
    for(int i=0;i<4;i++)
    {
        int x_now=x+dx[i],y_now=y+dy[i];
        if(h[x_now][y_now]<h[x][y])
            dfs(x_now,y_now);
    }
    length--;
}
int main() {
    ios::sync_with_stdio(false);

    cin>>R>>C;
    for(int i=1;i<=R;i++)
    {
        for(int j=1;j<=C;j++)
            cin>>h[i][j];
    }
    for(int i=1;i<=R;i++)
    {
        for(int j=1;j<=C;j++)
        {
            length=0;
            ans=0;
            dfs(i,j);
            s[i][j]=ans;
        }
    }
    int M=0;
    for(int i=1;i<=R;i++)
    {
        for(int j=1;j<=C;j++)
            M=max(M,s[i][j]);
    }
    cout<<M<<'\n';
    return 0;
}

K. 前缀和差分3

题源-洛谷 - P2368

的时候肯定是0， 的时候暴搜跑一下能抛出这8个数

111111111
119357639
380642361
388888889
611111111
619357639
880642361
888888889

显然如果更高位数的平方后9位是987654321，那么这个更高位数的后9位也得是这些里面的一个、

于是答案就显然了

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ios::sync_with_stdio(false);
    // for(ll i=100000000;i<=999999999;i++)
    // {
    //     if(i*i%1000000000==987654321)
    //         cout<<i<<'\n';
    // }
    int n;
    cin>>n;
    if(n<9)
        cout<<0<<'\n';
    else if(n==9)
        cout<<8<<'\n';
    else if(n==10)
        cout<<72<<'\n';
    else
    {
        cout<<72;
        for(int i=1;i<=n-10;i++)
            cout<<0;
        cout<<'\n';
    }
    return 0;
}
img_show