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

幸运的3

打靶

照亮街道

九次九日九重色

寻找串

竹鼠的白色季节

捉迷藏

好的三连

三角数

买马

可怜的小码哥

花园浇水

高次方程

幸运的3

难度:黄金时间限制: 1秒四占用内存:128M
你有 n 个数，可以将它们两两匹配(即将两数首尾相连)，每个数只能使用一次，问匹配后最多有多少个 3的倍数(没有进行匹配的数不算) ?
格式
输入格式:第一行一个n，接下来n个正整数
输出格式:输出最多有多少个3的倍数

//
// Created by abner on 2024/1/4.
//
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, a[3] = {0};
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int temp;
        cin >> temp;
        a[temp % 3]++;
    }
    cout << a[0] / 2 + min(a[1], a[2]);
    return 0;
}

打靶

难度:黄金时间限制: 3秒占用内存:256M
小码哥在练习射箭，他要射穿个靶子，且每个靶子有高度。箭会因为受到靶子的摩擦力而下坠，当射穿一个靶子后箭的高度会下降 1。小码哥可以射任意高度的箭。求出小码哥最少需射几箭。 ( 1< n,h 106 )
格式
输入格式:第一行一个整数n。
第二行n个整数hi。
输出格式:输出一个整数，表示小码哥最少需要射几箭

//
// Created by abner on 2024/1/4.
//
#include <bits/stdc++.h>
using namespace std;
int h,n,ans,a[1000010];
int main(){
    scanf("%d",&n);
    while (n--){
        scanf("%d",&h);
        a[h] ? a[h]--:ans++;
        a[h-1]++;
    }
    printf("%d",ans);
    return 0;
}

照亮街道

难度: 黄金时间限制: 秒四占用内存:128 M
有一条可以视为线段的街道，长度为工，其中有 n 个路灯，每个路灯能照亮的半径都是相同的求最小的照亮半径r使得整条街道上的每一个点都能被照亮
格式
输入格式:第一行两个正整数n，工第二行为初始n个实数，表示个路灯的坐标数据保证在0到工之间。
输出格式:输出一行一个实数表示答案，答案保留两位小数。

//
// Created by abner on 2024/1/4.
//
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
double d[N];

int main(){
    int n,L;
    double ans =0;
    cin >>n >>L;
    for (int i=0;i<n;i++)
        cin >>d[i];
    sort(d,d + n);
    for(int i=0;i<n-1;i++)
        ans = max(ans,d[i+1]-d[i]);
    ans =max(ans / 2,max(L-d[n -1],d[0]));
    
    printf("%.2lf",ans);
    return 0;
}

九次九日九重色

难度: 黄金时间限制: 1秒四占用内存:128M
小码哥是一个喜欢字符串的男孩子。
如果一个字符串 s 可以由一个字符串集合P中的元素拼接得到，我们就称 s 可以分解为P
现在有一个字符串集合 P和一个字符串，他想知道最长的可以分解为 P 的前缀有多长。请你帮帮他!
格式
输入格式:输入的开头有若千个字符串，以空格或换行隔开，它们是集合 P 中的元素集合的结束标志是 .，之后若干行，每行有一个字符串，为将这些字符串拼接得到的串。

//
// Created by abner on 2024/1/4.
//
#include <bits/stdc++.h>
using namespace std;

string s[210];
string str;
bool f[200005]={1};//f[1]表示字符串s的前1个字母是否可以分解成P
int main(){
    int k = 1;
    string ss;
    while (true){
        cin >>ss;
        if(ss==".")
            break;
        s[k++]=ss;
    }
    while (cin >> ss)
        str+=ss;//字符串s可能有多行，连接到一起
    int ans = 0;
    int len = str.size();
    for (int i = 1;i<=len;i++)
    for (int j=1;j<k;j++){
        int l=s[j].size();
        if (i>=1 && f[i-l] && s[j]== str.substr(i-l,l)){
            f[i] = true;
        ans = i;
        break;
        }
    }
    cout <<ans <<endl;
    return 0;
}

寻找串

难度: 黄金时间限制:1秒四占用内存:128M
在所给字符串中找出最少出现两次的最长子串的长度，没有则输出.
格式
输入格式:这一定是非空的字符串S，并由小写字母组成
输出格式:输出一个数。这个数是子串中最少出现两次的最长子串的长度
样例 1
输入: ababa

//
// Created by abner on 2024/1/4.
//
#include <bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin>>s;//输入字符串
    int l = s.size();
    for(int i=l-1;i>=1;i--)//从大到小枚举长度
    for(int j=0;j<l-i;j++) {//枚举子串的起点
        string tmp = s.substr(j, i);//用s.substrl取出子串
        if (s.find(tmp, j + 1) != s.npos) {
            cout << i;
            return 0;
        }
    }
    cout <<0;
    return 0;
}

竹鼠的白色季节

难度:黄金时间限制: 1秒占用内存: 250 M
小码哥的竹鼠养殖场中的竹鼠都在一条直线的隔间里，一共有n只竹鼠，它们的坐标分别为Pi,p2,p3,p4,...,pn(0<pi< 10)，1<n<100000又到了冬季，竹鼠们也要谈恋爱，因为竹鼠们都太胖了，它们的活动范围有限，这里统一规定它们的活动范围为 d(0d<104 )。
由于竹鼠之间也需要双向奔赴，所以如果两只竹鼠之间的距离小于等于d，则称它们是有缘的一对竹鼠，问小码哥的养殖场里一共有多少对有缘的竹鼠?
注:一只竹鼠可能存在于多个有缘的竹鼠对之中，多只竹鼠可能在同一个坐标上。
格式
输入格式:第一行，两个用空格隔开的数字n和d。

//
// Created by abner on 2024/1/4.
//
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int p[N];
int main(){
    int n,d,ans = 0;
    cin >>n >>d;
    for (int i=0;i<n;i++)
        cin >>p[i];
    sort(p,p + n);
    for (int i=0;i<n;i++){
        int j=i+1;
    while (j <n && p[j] - p[i]<=d){
        j++;
        ans++;
    }
}
cout<<ans;
return 0;
}

捉迷藏

难度: 钻石时间限制: 1秒四占用内存:128M
给 n 个单元格，这n个单元格在同一行，将一个代币放在单元格内，让另一个人猜代币放在哪了(视为一次询问)。可以选择在某一次询问之前或之后，将代币移动到所在单元格旁边两个单元格之一(移动操作在全部询问过程中至多进行一次，至少零次) 。问在依次进行 m 次询问后依旧找不到代币的情况(代币位置的改变) 有几种?
格式
输入格式:第一行n，m
第二行 m个数x，表示询问
输出格式:输出仅一行，为所求答案

//
// Created by abner on 2024/1/4.
//
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int N = 100010;

int a[N],first [N],last [N],
        ans;//fist,last表示某一个位置查询第一次和最后一次出现的位置
int main() {
    int n, m;
    cin >> n >> m;
    memset(last, -1, sizeof(last));
    memset(first, INF, sizeof(first));
    for (int i = 1; i <= m; i++) {
        cin >> a[i];
        first[a[i]] = min(first[a[i]], i);
        last[a[i]] = max(last[a[i]], i);
    }
    for (int i = 1; i <= n; i++) {
        if (i > 1 && first[i] > last[i - 1])
            ans++;
        if (i < n && first[i] > last[i + 1])
            ans++;
        if (first[i] > last[i])
            ans++;
    }
    cout << ans;
    return 0;
}

好的三连

难度:黄金时间限制: 1秒世占用内存:128M
给出01串 S，求[l,区间个数，使得至少能找到一对 ,k ，满足1<,kS 且x<x+k<x+2k<r 且Sa =Sa+k=Sx+2k
格式
输入格式:输入一个01字符串
输出格式:输出一个数，即答案

//
// Created by abner on 2024/1/4.
//
#include <bits/stdc++.h>
using namespace std;
const int N=300010;
char s[N];
int main(){
    long long ans = 0;
    scanf("%s",s +1);
    int n = strlen(s + 1);
    for (int l = 1;l<n;l++)
    for (int r=l;r<=n;r++){
        bool flag = false;
        for (int k = 1;l+2 * k <=r;k++)
        if(s[r]== s[r-k] && s[r-k]== s[r-2*k]){
            flag = true;
            break;
        }
        if (flag){
            ans +=n -r+1;
        break;
    }
}
cout<<ans;
return 0;
}

三角数

难度:黄金时间限制: 1秒占用内存:128M
k(k+1)我们规定，三角数是可表示为，k 为正整数，如果一个数 2 可以由两个三角数相加得到那么它就被成为双倍三角数。
现在给你一个数 n，让你判断 n 是不是双倍三角数。是则输出YES，否则输出 NO
格式
输入格式:第一行: n(1<n<1e9)
输出格式:如果是，输出YES，否则输出 NO

//
// Created by abner on 2024/1/4.
//
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >>n;
for (int k1 = 1;k1 <= n;k1++){
long long temp = n - 1LL * k1 * (k1 + 1)/2;
int k2 = sqrt(temp * 2 + 0.25)-0.5;
if(k2 * (k2+1)/2 == temp && k2>0){
cout <<"YES"<< endl;
return 0;
    }
}
cout <<"NO";
return 0;
}

买马

难度:黄金时间限制:1秒占用内存: 128 M
在市场当中，每一个编号为的马都住在相应编号为的马中，现在小码哥想要在市场里购买定数量的马匹，由于市场很大，小码哥可以买回编号非常大的马匹回来，但是小码哥的牧场并没有这么大，使得马匹住在相应编号的马厩中。但聪明的小码哥想到可以使用某种哈希映射来解决该问题。他想出的方法是对它们进行取模操作(即编号为 ;的马住在小码哥家编号为 s;odk 的马既里》。现在已经知道了买回来马匹的编号，你是否可以找到一个最小的 k 来完成此映射，使得每一匹马单独住在一个马厩中。(注意小码哥家有编号为 0的马厩)
格式
输入格式:第一行一个整数 n 表示小码哥买回来马的总数(马的数量不超过 100)接下来n行，每一行一个数字 s;表示第匹马的编号(马的编号为不超过1000的正整数)。

//
// Created by abner on 2024/1/4.
//
#include <bits/stdc++.h>
using namespace std;
const int N = 100,K = 1000;
int main() {
    int n, aa[N] = {0};
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> aa[i];
    for (int i = n; i <= K; i++) {
        bool f[K] = {0};
        bool flag = true;
        for (int j = 0; j < n; j++) {
            int remain = aa[j] % i;
            if (!f[remain])
                f[remain] = true;
            else {
                flag = false;
                break;
            }
        }
        if (flag) {
            cout << i;
            return 0;
        }
    }
    return 0;
}

可怜的小码哥

时间限制: 1秒四占用内存:128M
难度:黄金
提瓦特大陆上有一个贫穷的占星术士小码哥，出于占星术的要求，他时常要解决一些困难的数学问题。这天，他有遇到一个难题:对于一给定的素数集合 S = p,p2,...,pk ，考虑一个正整数集合，该集合中任一元素的质因数全部属于 S 。这个正整数集合包括， p1、p1 p2、P1XP1、P1 X 2x p3·(还有其它)。该集合被称为 S集合的“丑数集合”。小码哥现在的工作是对于给定的集合 S，去寻找“丑数集合”中的第 n 个“丑数”说明:丑数集合中每个数从小到大排列，每个丑数都是素数集合中的数的乘积，第 n 个“丑数”就是在能由素数集合中的数相乘得来的(包括它本身)第 n小的数
格式
输入格式:输入的第一行是两个的整数Sn，分别代表集合S的大小S和给定的参

//
// Created by abner on 2024/1/4.
//
#include <bits/stdc++.h>
using namespace std;
int n,m;
//n个素数，寻找第m个丑数
int a[100],b[100];//a是素数集合，b记忆了对应质数在s里的遍历点
int s[100001];
//丑数集合
int main(){
    scanf("%d %d",&n,&m);
    for (int i=0;i<n;i++)
        scanf("%d",&a[i]);
    s[0]=1;
    for(int i=1;i<=m;i++) {//每次找-个丑数
        int temp = pow(2, 31) - 1;
        for (int j = 0; j < n; j++) {//遍历n个质数，让循环次数更少
            while (a[j] * s[b[j]] <= s[i - 1])
                b[j]++;
            temp = min(a[j] * s[b[j]], temp);
        }
        s[i] = temp;
    }
        printf("%d",s[m]);
        return 0;
    }

花园浇水

难度: 黄金时间限制:1秒四占用内存:128M
小码哥需要给花园浇水。花园是 1 x n 的长方形。每块地有一个高度。他会选择一块地方浇水，如果与这块地相邻的区域的高度小于等于这块地的高度，水就可以流过去，直到不能流为止。求他次最多可以浇灌多少块地。
格式
输入格式:第一行为一个正整数n第二行为初始高度
输出格式:输出一行一个整数表示答案

//
// Created by abner on 2024/1/4.
//
#include <bits/stdc++.h>
using namespace std;
const int N=1000;
int main(){
    int n,a[N],ans =0;
    cin >>n;
    for (int i=0;i<n;i++)
        cin >>a[i];
    for (int i=0;i<n;i++){
        int l=i,ltemp = a[i],r=i,rtemp = a[i];
        while (l>0 && ltemp >= a[l -1])
            ltemp = a[--l];
        while (r<n-1 && rtemp >= a[r + 1])
        rtemp = a[++r];
        ans = max(ans,r-l+1);
    }
    cout <<ans;
    return 0;
}

高次方程

难度:黄金时间限制: 1秒四占用内存:128M
给定三个整数 A、B、，试求满足 A+X”= B的Y值(X必须为整数，若无解则输出“NOsolution”，有多个解则输出最小的解)。
A,B 的绝对值不超过 1000，且均不等于 0。
格式
输入格式:三个数: A,B,n(1<n<10)
输出格式:按题目要求输出一行一个整数X或者 No solution。

//
// Created by abner on 2024/1/4.
//
#include <bits/stdc++.h>
using namespace std;
int main(){
    double a,b,c,n;
    cin >>a >>b >>n;
    c=b-a;
    for (double i=-abs(c);i <= abs(c);i++)
        if (pow(i,n)==c){
            cout <<i;
            return 0;
        }
    cout <<"No solution";
    return 0;
}

//
// Created by abner on 2024/1/4.
//
#include <bits/stdc++.h>
using namespace std;
int main(){
char n[200],s[200];
scanf("%s",n);
int len = strlen(n),index =0;
while (n[index]=='0')
index++;
len -= index;
strncpy(s,n + index,len);
s[len]='\0';
for (index = 0;index < len /2;index++){
if (s[index] <= s[len -1 - index])
s[len - 1 - index] = s[index];
else{
int index2 = len -2 - index;
while (s[index2]=='0'){
s[index2] = '9';
index2--;
}
s [index2]--;
s[len -1 - index] = s[index];
if (index2 ==0 && s[index2]=='0') {
    s[index2] = '9';
    s[len - 1] = '\0';
    break;
        }   
    }
}
    printf("%s",s);
    return 0;
}