NHOI初中组题解

Prodige · 2024-01-19 10:02:47 · 题解

序言

这次NHOI本以为没什么成绩，结果误打误撞还拿了个一等奖(总分：15+0+36+4+27+0=82)

偷偷推一下我的小小荣誉

题解

T1：

题意：

一个 n 位的二进制数，n个询问，第i个询问代表当前这个二进制数能否被 2^i 整除，不能就输出需要两两交换几次才能被整除，如果改不出这个二进制数，就输出-1。

思路：

易证：一个二进制数要被 2^i 整除，则后面必须要有 i 个 0，所以判断-1的情况只需看0的个数即可.
二进制数位上两个数字交换位置，两两交换的代价必为两个下标的差，所以单次次交换的贡献为： ans=n-i-p[cnt0-i-1]
每次交换的答案可以继承。第一次交换后的答案，第二次的答案就可以变为ans[2]=ans[1]+n-i-p[cnt0-i-1]

最后就可以解决了，下面是代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define Max(a,b) (a>b?a:b)
const int N=1e5+5;
int n,m;
int cnt0,p[N],ans[N];
string s;
signed main()
{
    scanf("%lld",&n);
    cin>>s;
    for(int i=0;i<n;i++)
        if(s[i]=='0') p[++cnt0]=i;
    for(int cnt=0;cnt<n;cnt++)
    {
        if(cnt+1>cnt0)
        {
            printf("-1 ");
            continue;
        }
        int sum=n-cnt-1-p[cnt0-cnt];
        ans[cnt]=ans[cnt-1]+sum;
        printf("%lld ",ans[cnt]);
    }
    return 0;
}

T2:

题意：

有两种完美棋盘：

WBWBW BWBWB

BWBWB 和 WBWBW

WBWBW BWBWB

每次可以把一个 w 变为 b ，或者把一个 b 变为 w ，把一个棋盘变为完美棋盘的最小改变次数，称为这个棋盘的代价。

题目要求给你一个 r*c 的棋盘，和一个代价d，要求求出有多少个大小为r*c且代价为d的棋盘。

真实题意：

求C_{rc}^{d} mod p，p=10^9+7

这是一道数学！这是一道数学！这是一道数学！

考场上没往数学那方面想，用打表+二维全排列做的，写假了，成功爆零。

讲些小优化：

注意代价的定义，“最小改变次数”，所以当d大于棋盘面积的一半时，更优策略为更改棋盘的另一半。综上所述，当d>r*c/2时，直接输出0即可。
注意设问，“大小为r*c且代价为d的棋盘”，所以问题没有要求这个棋盘一定是非完美棋盘，所以当代价 (即d) =0时，直接输出2。

剩下的就是求解组合数了：

学长讲的是用逆元+阶乘，时间复杂度O(rc)，我一开始调的时候直接除，结果写假了，也没mod，提交到 OJ 上仅拿30分，学了一下逆元，不怎么懂，遂用杨辉三角，O((rc)^2)过了。

代码：

我的杨辉三角太过丑陋，就先不放了(其实是找不到代码了，又不想再写一遍)

学长的逆元神法：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1000000007;

int ksm(int a,int n)
{
    int ans = 1;
    while(n)
    {
        if(n&1)
            ans=ans*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return ans%mod;
}
signed main()
{
    int r=0,c=0,d=0;
    scanf("%lld%lld%lld",&r,&c,&d);
    if(2*d>r*c)
    {
        printf("0");
        return 0;
    }
    if(d==0)
    {
        printf("2");
        return 0;
    }
    int sum1=1,sum2=1,sum3=1,n=r*c;
    for(int i=2;i<=n;i++)
    {
        sum1=sum1*i%mod;
    }
    for(int i=2;i<=d;i++)
    {
        sum2=sum2*i%mod;
    }
    for(int i=2;i<=n-d;i++)
    {
        sum3=sum3*i%mod;
    }
    int ans=sum1*ksm(sum2,mod-2)%mod*ksm(sum3,mod-2)%mod;
    if(2*d==r*c) printf("%lld",ans); 
    //此处注意一下，文中没有提到，当d等于整个棋盘的一半时，其实是存在一个棋盘变两个完美棋盘都成立，所以此处不用乘二
    else printf("%lld",2*ans);
    return 0;
}

T3:

题意不说了，裸的宽搜题，主要讲一下剪枝：

因为这个东西可以走1~k，但不能穿过障碍物和越界，所以当遇到障碍物或越界时，可以直接break
当从一个格子走到另一个格子时，第二个格子可能已经被走过，所以如果走过之后的步数小于当前这个格子，说明走下面的格子肯定更优，则直接break
当前要走格子没走过，直接开始入队即可

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m,k,r1,c1,r2,c2;
vector<char > a[1000005];
bool flag=0;
struct node
{
    int x,y;
    node(int ax,int ay)
    {
        x=ax,y=ay;
    }
};
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
vector<int > f[1000005];
void bfs()
{
    queue<node> q;
    q.push(node(r1,c1));
    f[r1][c1]=0;
    while(!q.empty())
    {
        node t=q.front();q.pop();
        if(t.x==r2&&t.y==c2)
        {
            printf("%lld",f[r2][c2]);
            flag=1;
            return ;
        }
        for(int i=0;i<4;i++)
        {
            for(int j=1;j<=k;j++)
            {
                int xx=t.x+dx[i]*j;
                int yy=t.y+dy[i]*j;
                if(xx>n||yy>m||xx<1||yy<1||a[xx][yy]=='@') break;
                if(f[xx][yy]<=f[t.x][t.y] && f[xx][yy]!=-1) break;
                if(f[xx][yy]==-1) q.push(node(xx,yy)),f[xx][yy]=f[t.x][t.y]+1;
            }
        }
    }
    return ;
}
signed main()
{
    scanf("%lld%lld%lld",&n,&m,&k);
    scanf("%lld%lld%lld%lld",&r1,&c1,&r2,&c2);
    for(int i=1;i<=n;i++)
    {
        f[i].resize(m+1);
        a[i].resize(m+1);
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            f[i][j]=-1;
    bfs();
    if(!flag) printf("-1");
    return 0;
}

T4:

题面：

有n袋干草，第i袋干草的重量是w[i]。奶牛bessie当前的快乐值是0，bessie希望它的快乐值至少要达到s。如果奶牛吃掉第i袋干草，奶牛的快乐值会增加w[i]。对于一袋干草来说，bessie要么整袋吃掉，要么不吃，不能吃这袋干草的一部分。如果bessie当前的快乐值小于s，那么bessie必须要继续挑选干草吃。 bessie最近的感知功能不是很好，有一个延迟参数t。如果t等于0，那么奶牛当前快乐值只要不小于s，那么它就不再吃干草了。如果t是正整数，那么奶牛快乐值达到s以后，仍然要额外多吃t袋干草。求奶牛bessie能吃到的干草的总重量的最大值是多少。注意：有可能bessie吃完所有的干草后，快乐值仍然没达到s。

输入

第一行，三个整数: n, s, t。1<=n<=100, 1<=s<=10000, 0<=t<=100。

第二行，n个正整数，第i个整数是w[i]。所有w[i]的总和不超过1000000000。

输出

一个整数。

题意：

这道题题意挺好理解的，主要是思路，这里就不分析题意了。

思路：

最大值，考虑贪心和DP，这里两个都需要用到。
顺序问题，我们考虑先吃t袋快乐值多的，再使用DP的滚表对剩下干草寻找最优解，凑足s。

贪心证明(交换法)：当t=2,n=5,s=5,a=[2,4,5,7,9] 时，我们按2的策略，先排序，然后找t袋大的，再用[2,4,5]，凑出5，题目中说“不小于s”，考虑到2+4>5，所以最大价值就为ans=7+9+2+4=22，此时5在符合条件的基础上，和任何一个元素换都非最优解，由此，贪心得证。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,s,t,sum=0,res=0;
int w[105];
bool f[105][10005];
signed main()
{
scanf("%d%d%d",&n,&s,&t);
for(int i=1;i<=n;i++)
{
    scanf("%d",&w[i]);
}
sort(w+1,w+1+n);
for(int i=n;i>=max(n-t+1,1);i--)
{
    sum+=w[i];
}
if(t>=n)
{
    printf("%d",sum);
    return 0;
}
n-=t;
memset(f,false,sizeof f);
f[0][0]=true;
for(int i=0;i<n;i++)
{
    for(int j=0;j<s;j++)
    {
        if(!f[i][j]) continue;
        f[i+1][j]=true;
        if(j+w[i+1]<s) f[i+1][j+w[i+1]]=true;
        res=max(res,j+w[i+1]);
    }
}
printf("%d",sum+res);
return 0;
}

T5:

题意：

给我们一个n行m列的二维空间，要求我们按顺序把每个r行s列的区间最大值输出。

思路：

区间最大值求法：

1.线段树

2.单调队列

3.RMQ

4.ST表

这题是二维空间，用线段树会较好实现，但是码量大，显然不符合一个初中牲的想法，ST表我也说不出是哪里不好，~~主要是因为我没学~~，反正我用的是单调队列，行和列分开处理。

先枚举行，把每行s个数的最大值存到区间最靠前的位置，覆盖原数。

再枚举列，把每列r个数的最大值存到区间最上的位置，覆盖原数。

最后输出即可。

代码(非最优解)：

#include <bits/stdc++.h>
using namespace std;
int n,m,r,s;
int a[4005][4005];
signed main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
    scanf("%d%d",&r,&s);
    for(int cnt=1;cnt<=n;cnt++)
    {
        int q[4005],h=0,t=-1;
        for(int i=1;i<s;i++)
        {
            while(h<=t&&a[cnt][q[t]]<=a[cnt][i]) t--;
            q[++t]=i;
        }
        for(int i=s;i<=m;i++)
        {
            while(h<=t&&a[cnt][q[t]]<=a[cnt][i]) t--;
            q[++t]=i;
            while(h<=t&&q[h]<=i-s) h++;
            a[cnt][i-s+1]=a[cnt][q[h]];
        }
    }
    for(int cnt=1;cnt<=m;cnt++)
    {
        int q[4005],h=0,t=-1;
        for(int i=1;i<r;i++)
        {
            while(h<=t&&a[q[t]][cnt]<=a[i][cnt]) t--;
            q[++t]=i;
        }
        for(int i=r;i<=n;i++)
        {
            while(h<=t&&a[q[t]][cnt]<=a[i][cnt]) t--;
            q[++t]=i;
            while(h<=t&&q[h]<=i-r) h++;
            a[i-r+1][cnt]=a[q[h]][cnt];
        }
    }
    for(int i=1;i<=n-r+1;i++)
    {
        for(int j=1;j<=m-s+1;j++)
        {
            printf("%d ",a[i][j]);
        }
        puts("");
    }
    return 0;
}

最优解代码：

#include<bits/stdc++.h>
using namespace std;
//两者改动主要在单调队列的实现，上面那种会好理解一点，大家也可以尝试自行优化
#define Max(a,b) a>b?a:b
int n,m;
int a[10005][10005],r,s;
inline int read()
{
    int date=0,w=1;
    char c;
    c=getchar();
    while(c<'0' || c>'9')
    {
        if(c=='-')w=-1;
        c=getchar();
    }
    while(c>='0' && c<='9')
    {
        date=date*10+(c-'0');
        c=getchar();
    }
    return date*w;
}
int w[10005];
int h,t;
signed main()
{
    n=read(),m=read();
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            a[i][j]=read();
        }
    }
    r=read(),s=read();
    for(int i=1;i<=n;++i)
    {
        h=1,t=0;
        for(int j=1;j<=m;++j)
        {
            while(h<=t && a[i][w[t]]<=a[i][j])t--;
            w[++t]=j;
            while(h<=t && j-w[h]>=s)h++;
            if(h<=t && j>=s)
                a[i][j-s+1]=a[i][w[h]];
        }
    }
    for(int j=1;j<=m;++j)
    {
        h=1,t=0;
        for(int i=1;i<=n;++i)
        {
            while(h<=t && a[w[t]][j]<=a[i][j])t--;
            w[++t]=i;
            while(h<=t && i-w[h]+1>r)h++;
            if(h<=t && i>=r)a[i-r+1][j]=Max(a[w[h]][j],a[i-r+1][j]);
        }
    }
    for(int i=1;i<=n-r+1;++i)
    {
        for(int j=1;j<=m-s+1;++j)
        {
            printf("%d ",a[i][j]);
        }
        puts("");
    }

    return 0;
}

T6:

T6(小甲)：

别问我为什么放在这，放在初中组你也不会

题意：

思路：

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1000000007;
int G;
signed main()
{
    scanf("%d",&G);
    while(G--)
    {
        ll s;
        cin>>s;
        s<<=1;
        s++;
        bool f=1;
        for(int i=2;i<=300000;i++)
        {
            s<<=1;
            s++;
            s%=mod;
            if(s==0)
            {
                int ans=0;
                if(i%3==0) ans+=i/3;
                else if(i%3==1) ans+=(i-4)/3+2;
                else ans+=(i-2)/3+1;
                printf("%d\n",ans);
                f=0;
                break;
            }
        }
        if(f) puts("-1");
    }
    return 0;
}