马蹄集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;
}