马蹄集oj赛（双周赛第十九次）

目录

跳蚤

序列操作

疯狂算钱

二维坐标点移动

挑兵挑将

一秒成零

三合一

小码哥的计划表

找1

?编辑连续的串

数据流的中位数

水位线

工厂

线段覆盖

---

跳蚤

难度:黄金时间限制:1秒巴: 占用内存:128 M
菜地上挖了 n 行 m 列个坑，有一只跳蚤可以从任意一个坑作为起点无限次跳跃，同一个坑也可以重复跳到，但跳蚤只能垂直或者水平方向跳坑，而且不能跳到菜地外(这时候它会改变方向保证自己不掉出去或者停止)。每一跳距离固定为8个坑，当s为1表示跳到垂直或者水平方向紧相邻的隔壁坑里。求跳蚤可以从多少个不同的坑起跳，可以满足能在菜地里到达的坑数量为最大。
格式
输入格式:三个整数 n,m,s
输出格式:一个整数，起点的数量

//
// Created by abner on 2024/1/20.
//
#include <bits/stdc++.h>
using namespace std;
int n,m,s,a,b,c,d;
int main(){
    cin >>n >>m >>s;
    a=n%s,b=m%s;
    c=n / s,d=m / s;
    a==0 ? a=s:c++;
    b==0 ? b=s:d++;
    cout << 1ll * a * b * c * d;
    return 0;
}

序列操作

少 难度:黄金时间限制:1秒巴:占用内存:128 M
一个共有几个数的单调非递减数列(每个数都是正整数)，还有一个整数target，?每轮操作可以让数列中满足以下两个要求的数+1:
1.该数比 target 小;
2.该数不等于它后面的那个数:
特别地，最后一个数默认满足要求2。
你的任务是求出最小的操作数m，使得第m轮操作后，该数列中的所有数都等于target(n,target<100，并且保证数列中任何一个数小于target)

//
// Created by abner on 2024/1/20.
//
#include <bits/stdc++.h>
using namespace std;
int n,k,a[110],ans;
int main(){
scanf("%d %d",&n,&k);
for (int i=0;i<n;i++)
scanf("%d",&a[i]);

while (a[0] != k){
    for (int i=0;i<n;i++)
        if (a[i]<k && a[i] != a[i + 1])
            a[i]++;
    ans++;
}
printf("%d\n",ans);
return 0;
}

疯狂算钱

难度:黄金时间限制:1秒巴 占用内存:128 M
他在车在小码哥赢得一场编程现场赛之后，他乘坐公交车返回学校。公共汽车的车费是220元。
上遇到了专门给别人替考的郭枪手。小码哥决定教训一下郭枪手，所以决定玩下面这个游戏。
起初，有一堆钱，里面包含了x张100元和y张10元。 他们轮流从中取钱。小码哥先手拿。 在每个回合里，他们每次必须从堆中拿出刚好220元。 在轮到小码哥时，如果他有多种方式可以从中取出228元，他会选择包含最大数量的180元纸币的方式。轮到郭枪手时，如果有多种方式可以取出220元，他会选择包含最多10元纸币的方式。如果轮到了小码哥或郭枪手不能从堆中拿出220元，那么他就会失败。
请你确定这场游戏的胜利者

//
// Created by abner on 2024/1/20.
//
#include <bits/stdc++.h>
using namespace std;
int c2,c1;//100元纸币的数量和10元纸币的数量
int main(){
    cin >>c2 >>c1;
    while(1){//一直循环直到游戏结束
        if(c2*100+c1*10<220){
            puts("gqs");
            return 0;
        }//xmg拿不出220元，直接结束，gqs获胜
        if(c2>=2&&c1>=2){
            c2-=2;
            c1-=2;
        }//xmg的方案1
        else if(c2>=1 && c1>=12){
            c2--;
            c1-=12;
        }//xmg的方案2
        else if (c1 >=22){
            c1-=22;
    }//xmg的方案3
    else if((c2>=2 && c1<2) || (c2=1 && c1<12)||
            (c2 == 0 && c1<22)){
        puts("gqs");
        return 0;
    }//xmg不能刚好凑出220，结束，gqs获胜
        if(c2*100+c1*10<220){
            puts("xmg");
            return 0;
        }//gqs拿不220元，直接结束，xmg获胜
        if(c1>=22){
            c1-=22;
        }//gqs的方案1
        else if(c1>=12 && c2>=1){
            c1-=12;
            c2-=1;
        }//gqs的方案2
        else if(c1>=2 && c2>=2){
            c1 -= 2;
            c2 -= 2;
        }//gqs的方案3
        else if((c2 == 0 && c1<22)||(c2=1 && c1<12)||
                    (c2>=2 && c1<2)){
            puts("xmg");
            return 0;
        }//gqs不能刚好凑出220，结束，xmg获胜
        }
    }

二维坐标点移动

时间限制:1秒四占用内存:128 M难度:黄金
给定一个N*M的二维坐标矩阵A，并且给定一个整数K，K表示移动步数，矩阵A中的所有点Ai的移动操作如下:
1.A[{][j]移动到 A{][j+1](j≤m-2);
2.A[{][m-1] 移动到 A[+ 1][0](i≤n-2);
3.A[n-1][m - 1]移动到 A[0][0]
最后输出移动了 取 次后新的二维坐标矩阵A。

//
// Created by abner on 2024/1/20.
//
#include <bits/stdc++.h>
using namespace std;
int N,M,K,temp;
vector<int>A;
int main(){
    cin >>N >>M;
    for (int i=1;i<=N * M;i++){
        cin >>temp;
        A.push_back(temp);
    }
    cin >>K;
    while(K--) {
        A.insert(A.begin(), A[N * M - 1]);
        A.pop_back();
    }
    for (int i=0;i<N;i++,puts(""))
        for (int j=0;j<M;j++)
            cout <<A[i * M+j]<<" ";
    return 0;
}

挑兵挑将

黄金难度:青时间限制:1秒巴:占用内存:256 M
马上要进行阅兵仪式了，将军要在手下几个人中挑人参加，他用以下方法选人:
几个人站成一圈，逆时针编号为1-n，现在、B两人选人。A逆时针数k个停下来，B顺时针数 m 个停下来，被选中的1或2个人输出，直至所有人输出。
首次从A从1开始，B从N开始，之后AB分别从上次各自的位置的各自方向的下一位接着数。结合样例 1可知:
10 4 3
2round 1:
[1,2,3,4,5,6,7,8,9,10]3.
4A:1->2->3->4
白:B:10->9->8

//
// Created by abner on 2024/1/20.
//
#include <bits/stdc++.h>
using namespace std;
int n,k,m;
bool a[25];
//direction为1时逆时针，-1顺时针
//position,direction,count
int pick(int p,int d,int c){
    while (c--) {
        do {
            p = (p + d + n - 1) % n + 1;
        } while (a[p] == 0);
    }
        return p;
    }

    int main(){
        while(cin>>n>>k>>m,!(n == 0&& k==0 && m==0 )){
            for (int i=1;i <= n;i++)
                a[i] = true;
            int remain = n;
            int pa=n,pb=1;//注意这里pa不是1，而是往前走了一位；同理pb
            while (remain) {
                pa = pick(pa, 1, k);
                pb = pick(pb, -1, m);
                if (pa == pb) {
                    printf("%3d", pa);
                    remain--;
                } else {
                    printf("%3d%3d", pa, pb);
                    remain = remain - 2;
                }
                a[pa] = a[pb] = 0;
                if (remain)
                    printf(",");
            }
                printf("\n");
            }
            return 0;
        }

一秒成零

难度:白银
时间限制:1秒巴 占用内存:128 M
给定一个正整数n，请写一个函数Steps，将n通过以下操作变成0，并且返回操作次数。
n为偶数，则n=n/2;
n为奇数，则n=n-1。
格式
输入格式:第一行输入正整数 n
输出格式:输出操作次数

//
// Created by abner on 2024/1/20.
//
#include <bits/stdc++.h>
using namespace std;
int n,ans;
int main() {
    cin >> n;
    while (n) {
        if (n % 2)
            n--;
        else
            n /= 2;
        ans++;
    }
    cout << ans;
    return 0;
}

三合一

时间限制:1秒四占用内存:128 M乡 难度:黄金
有一个数组，每一个位置有一个1-9的数，现对其进行三合一操作
三合一操作有若干轮:每一轮，从前往后扫，如果三个相邻的数的和小于等于“轮次*3”，则这三个数合并为一个数。如果能合，本轮的下一次扫描就从三个数后面的第一个数开始扫:如果不能合，就从这三个数的第二个数开始扫。他们相加的和经过有限轮后，该数组肯定会变为一个数或两个数。
现在需要你求出一共进行了多少轮(没有进行任何操作的轮次也算)

//
// Created by abner on 2024/1/20.
//
#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
int n,a[N],ans;
int main(){
    cin >>n;
    for (int i=1;i<=n;i++)
        cin >>a[i];
    while(n>=3) {
        ans++;
        int cnt = 0;
        for (int i = 1; i + 2 <= n; i++) {
            int sum = a[i] + a[i + 1] + a[i + 2];
            if (sum <= ans * 3) {
                a[i] = sum;
                for (int j = i + 1; j <= n; j++)
                    a[j] = a[j + 2];
                n -= 2;
            }
        }
    }
        cout <<ans <<endl;
        return 0;
    }

小码哥的计划表

乡 难度:黄金
时间限制:1秒巴 占用内存:128 M
小码哥的寒假有 N天，他做了一个计划表，计划每天做若干数学题目，但是为了平衡每天的任务量，小码哥决定调整一下计划表。他首先设定了每天做题数目的上限R和下限，然后他准备做-些调整,使得每天的题目数量 A; 满足<<R。每次调整小码哥可以把某一天的某些题目换到另一天，每次操作只能移动一道题目。
小码哥请你帮忙算一算需要的最小操作数。
格式
输入格式:第一行一个正整数 N ，表示计划表的总天数;第二行 N 个整数，表示计划表初始每天的题目数;

//
// Created by abner on 2024/1/20.
//
#include <bits/stdc++.h>
using namespace std;
int n,L,R,Sum,ls,rs;
int a[100005];
int main(){
    cin >>n;
    for (int i=1;i<=n;++i){
        cin >>a[i];
        Sum += a[i];
    }
    cin >>L >>R;
    for (int i=1;i<=n;++i) {
        if (a[i] < L)
            ls += L - a[i];
        if (a[i] > R)
            rs += a[i] - R;
    }
    if (R * n < Sum || Sum < n * L)
    cout <<-1;
    else{
    if (ls > rs)
        cout << ls;
    else
        cout << rs;
}
return 0;
}

找1

乡难度:黄金时间限制:1秒巴 占用内存:128 M
最近小码哥爱上二进制，他特别喜欢全是1的二进制串，但通常会有0于是他给你一个二进制字符串，问你字符都为1的子串的个数(结果对109+7取模)
格式
输入格式:一个二进制字符串
输出格式:所有字符都为1 的子串个数

//
// Created by abner on 2024/1/20.
//
#include <bits/stdc++.h>
using namespace std;
string s;
int ans,l,mod = 1e9+7;
int main(){
    cin >>s;
    int len = s.length();
    for (int i=0;i<len;i++){
        if(s[i]=='1')
        l++;
        if(s[i]=='0'|| i==len-1) {
            ans += (l + 1) * l / 2;
            ans %= mod;
            l = 0;
        }
    }
            cout <<ans % mod;
            return 0;
        }

连续的串

少 难度:钻石
时间限制:1秒巴: 占用内存:128 M
给你一个字符串，找出现次数最多的长度为2的子串
格式
输入格式:第一行为一个正整数n，表示给出字符串的长度，第二行为字符串
输出格式:输出所求的串，若有多个结果，输出字典序最小的

//
// Created by abner on 2024/1/20.
//
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,ans = 0;
    char s[110];
    int cnt[30][30]={0};
    cin >>n >>s;
    for (int i=0;i<n-1;i++) {
        int x = s[i] - 'A';
        int y = s[i + 1] - 'A';
        cnt[x][y]++;
        ans = max(ans, cnt[x][y]);
    }
    for (int i=0;i<26;i++)
            for (int j=0;j < 26;j++)
        if (cnt[i][j]==ans){
            cout <<char('A' + i)<<char('A' + j);
            return 0;
        }
    }

数据流的中位数

难度:黄金
巴:占用内存:128 M时间限制:1秒
对于数据流问题，小码哥需要设计一个在线系统，这个系统不断的接受一些数据，并维护这些数据的一些信息。
中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值
请帮小码哥设计一个支持以下两种操作的系统:+num-从数据流中添加一个整数k到系统中(0<k<232)n返回目前所有元素的中位数。

//
// Created by abner on 2024/1/20.
//
#include <bits/stdc++.h>
using namespace std;
const int N=100000;
priority_queue<int,vector<int>,less<int>>q1;//大顶堆，存储小-半的数
priority_queue<int,vector<int>,greater<int>> q2;//小顶堆，存储大-半的数

void insert(int num){
    if(q1.size()>q2.size()) {//放入前多-个，那放入后两个堆数量相等
        q1.push(num);
        q2.push(q1.top());
        q1.pop();
    }else{
        q1.push(num);
        if(q2.size() != 0 && q1.top()>q2.top()) {//需要比较两个队头，看是
            q2.push(q1.top()), q1.pop();
            q1.push(q2.top()), q2.pop();
        }}}
            int main(){
                int n,num;
                cin >>n;
                while (n--){
                    char ch;
                    cin >>ch;
                    if(ch=='+') {
                        cin >> num;
                        insert(num);
                    }else{
                        if(q1.size()>q2.size())
                        cout <<q1.top()<<endl;
                        else
                        cout <<(float)(q1.top()+q2.top())/2 <<endl;
                    }
                }
                return 0;
            }

水位线

少 难度:黄金 时间限制:1秒巴 占用内存:128 M
饮水机中本来有k升水,小码哥希望在t天内饮水机的水量保持在l,之间,小码哥知道每天会用掉 ?升水,而小码哥可以在一天的开始选择加 y 升(一天只能加一次)或不加。给出 k,l,r,t,,y,求能否在 t天内把水量控制在l,r，能输出，否则输出NoYes0
格式
输入格式:仅一行为 k,l,r,t,?,y
输出格式:输出 Yes 或者 No

//
// Created by abner on 2024/1/20.
//
#include <bits/stdc++.h>
using namespace std;
int k,l,r,t,x,y;
int main(){
    cin >>k >>l>>r>>t >>x >>y;
    while (t--){
        if (k+y <= r)
            k +=y;
        if (k-x<l){
            cout <<"No";
            return 0;
        }
        k-=x;
    }
    cout <<"Yes";
    return 0;
}

工厂

难度:黄金时间限制:1秒巴 占用内存:128 M
有一家工厂，在一天的开始时，共有 瓶罐头，在这一天结束时，会生产x mod m 瓶罐头。现在已知第一天所拥有的罐头数a，以及m的值。请问，是否存在一个时刻，整个工厂会停止生立(x mod m=0)?
格式
输入格式:两个数 a,m 。
输出格式:当生产会停止时，输出es，否则输出 No

//
// Created by abner on 2024/1/20.
//
#include <bits/stdc++.h>
using namespace std;
int a,m;
int main() {
    cin >> a >> m;
    if (a % m == 0) {
        cout << "Yes";
        return 0;
    }
    for (int i = 1; i <= 1000; i++) {
        a += a % m;
        if (a % m == 0) {
            cout << "Yes";
            return 0;
        }
    }
    cout << "No";
    return 0;
}

线段覆盖

乡难度:黄金● 时间限制:1秒巴: 占用内存:128 M
现给定一根坐标轴，坐标轴上有n条线段，每条线段从1开始编号，若线段编号为k，则该线段覆盖的区间是:[(k-1)xm,(k-1)xm+〗]。
有一个质点从原点开始向x轴正半轴移动，每次移动d距离。问第一个不被线段覆盖的点的位置在哪里?
格式
输入格式:一行四个正整数n,d,m,!，意义见题面。保证1≤n,d,m,l≤ 1e6 ，并且l<
m 。

//
// Created by abner on 2024/1/20.
//
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,m,d,l;
    cin >>n>>d>>m>>l;
    long long a =0,b=0;
    for (int i=1;i<=n;i++){
        a=(i-1)*m+l,b=i*m-1;
    if (a /d !=b/d)
        break;
}
cout << (a / d +1) * d <<endl;
return 0;
}