程序设计思维与实践 CSP-M2 (3/4/数据班)
HRZ的序列
题意:
相较于咕咕东,瑞神是个起早贪黑的好孩子,今天早上瑞神起得很早,刷B站时看到了一个序列a,他对这个序列产生了浓厚的兴趣。
他好奇是否存在一个数K,使得一些数加上K,一些数减去K,一些数不变,使得整个序列中所有的数相等。
其中对于序列中的每个位置上的数字,至多只能执行一次加运算或减运算或是对该位置不进行任何操作。
由于瑞神只会刷B站,所以他把这个问题交给了你!
思路:
使用三个数记录当前的序列就可,如果超过三个数或者三个数之间不符合要求,就输出NO。
总结:
这个题其实比较简单,提交的时候没有初始化,爆0了。
代码:
#include <iostream>
using namespace std;
const int N = 100000 + 1;
int t, n;
long long a[N];
long long p1, p2, p3;
bool b1 = false, b2 = false, b3 = false;
int main()
{
cin >> t;
while (t--)
{
cin >> n;
bool flag = true;
b1 = false, b2 = false, b3 = false;
for (int i = 1; i <= n; i++)
{
long long temp;
cin >> temp;
if (!b1)
{
p1 = temp;
b1 = true;
}
else if (b1 && p1 == temp)
continue;
else if (!b2)
{
p2 = temp;
b2 = true;
}
else if (b2 && p2 == temp)
continue;
else if (!b3)
{
p3 = temp;
b3 = true;
}
else if (b3 && p3 == temp)
continue;
else
flag = false;
}
if (!flag)
cout << "NO" << endl;
else if (!b2 || !b3 || p1 + p2 == 2 * p3 || p1 + p3 == 2 * p2 || p2 + p3 == 2 * p1)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
}
B - HRZ 学英语
题意:
瑞神今年大三了,他在寒假学会了英文的26个字母,所以他很兴奋!
于是他让他的朋友TT考考他,TT想到了一个考瑞神的好问题:给定一个字符串,从里面寻找 连续的26个大写字母 并输出!
但是转念一想,这样太便宜瑞神了,所以他加大了难度:现在给定一个字符串,字符串中包括26个大写字母和特殊字符’?’,特殊字符’?'可以代表任何一个大写字母。
现在TT问你是否存在一个 位置连续的且由26个大写字母组成的子串 ,在这个子串中每个字母出现且仅出现一次,如果存在,请输出从左侧算起的第一个出现的符合要求的子串,并且要求,如果有多组解同时符合位置最靠左,则输出字典序最小的那个解!如果不存在,输出-1!
这下HRZ蒙圈了,他刚学会26个字母,这对他来说太难了,所以他来求助你,请你帮他解决这个问题,报酬是可以帮你打守望先锋。
说明:字典序 先按照第一个字母,以 A、B、C……Z 的顺序排列;如果第一个字母一样,那么比较第二个、第三个乃至后面的字母。如果比到最后两个单词不一样长(比如,SIGH 和 SIGHT),那么把短者排在前。例如
AB??EFGHIJKLMNOPQRSTUVWXYZ
ABCDEFGHIJKLMNOPQRSTUVWXYZ
ABDCEFGHIJKLMNOPQRSTUVWXYZ
上面两种填法,都可以构成26个字母,但是我们要求字典序最小,只能取前者。
注意,题目要求的是 第一个出现的, 字典序最小的 !
思路:
尺取法,真的不难。
总结:
没有认真读题,第一个出现的符合要求的子串!!!!
代码:
#include <iostream>
#include <stdlib.h>
using namespace std;
string s;
string ch;
int sum[27], l = 0, r = 0;
void Minus(int x)
{
int len = s[x] - 'A';
int len2 = '?' - 'A';
(len == len2) ? sum[26]-- : sum[len]--;
}
void Plus(int x)
{
int len = s[x] - 'A';
int len2 = '?' - 'A';
(len == len2) ? sum[26]++ : sum[len]++;
}
bool check()
{
int num = sum[26];
for (int i = 0; i < 26; i++)
{
if (sum[i] == 0 && num == 0)
return false;
else if (sum[i] == 0)
num--;
}
ch = s.substr(l, 26);
return true;
}
void print()
{
int j = 0;
char ch2[26];
int num = sum[26];
int a = 0;
for (int i = 0; i < 26; i++)
{
if (sum[i] == 0)
ch2[a++] = char(i + 'A');
}
a = 0;
for (int i = 0; i < 26; i++)
{
if (ch[i] != '?')
cout << ch[i];
else
cout << ch2[a++];
}
}
int main()
{
int flag = 0;
cin >> s;
while (r < s.size())
{
if (check())
{
print();
//system("pause");
return 0;
}
else if ((r - l) < 26)
Plus(r++);
else
{
Plus(r++);
Minus(l++);
}
}
if (check())
{
print();
//system("pause");
return 0;
}
cout << -1;
//system("pause");
}
C - 咕咕东的奇妙序列
题意:
咕咕东 正在上可怕的复变函数,但对于稳拿A Plus的 咕咕东 来说,她早已不再听课。
此时她在睡梦中突然想到了一个奇怪的无限序列:112123123412345…
这个序列由连续正整数组成的若*分构成,其中第一部分包含1至1之间的所有数字,第二部分包含1至2之间的所有数字,第三部分包含1至3之间的所有数字,第i部分总是包含1至i之间的所有数字。
所以,这个序列的前56项会是11212312341234512345612345671234567812345678912345678910,其中第1项是1,第3项是2,第20项是5,第38项是2,第56项是0。
咕咕东 现在想知道第 k 项数字是多少!但是她睡醒之后发现老师讲的东西已经听不懂了,因此她把这个任务交给了你。
思路:
这个题具体实现方法五花八门,但实际上都是通过分组,然后搜索,最终找到k。
分组总共有三步:
- 首先,如下图所示,将整个数列分成0-9行,10-99行等等。
- 找到对应的块后,我们需要搜索k在第几行。二分法
- 找到行后,我们需要搜索k的具体位置。使用log
代码:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <climits>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
int q, len;
long long k, sum[20], up[20], down[20], num[20], height = 9;
//sum数组存储当前块为止字符数,up,down分别是当前块的上底和下底,num是最长层内分组
int main()
{
for (int i = 1;; i++)
{ //计算到此块为止字符数
len = i;
num[i] = i * height + num[i - 1];
up[i] = down[i - 1] + i; //上底
down[i] = up[i] + i * (height - 1); //下底
sum[i] = sum[i - 1] + ((up[i] + down[i]) * height) / 2; //梯形面积
if (sum[i] >= 1e18)
break;
height *= 10; //高
}
scanf("%d", &q);
while (q--)
{
scanf("%lld", &k);
for (int i = 1; i <= len; i++)
{ //搜块
if (k <= sum[i])
{ //在第i块
k -= sum[i - 1]; //更新k的数值
height = ((down[i] - up[i]) / i) + 1;
long long left = 1, right = height, level = 0;
while (left + 1 < right)
{ //二分层数,搜层
long long mid = (left + right) / 2;
long long temp = ((up[i] + (up[i] + i * (mid - 1))) * mid) / 2;
if (temp > k)
right = mid; //在上面
else
left = mid; //在下面
}
//由于当前数字不能确定是left层还是right层,在这里比较一下
if (((up[i] + (up[i] + i * (left - 1))) * left) / 2 < k)
level = right;
else
level = left;
k = k - ((up[i] + (up[i] + i * (level - 2))) * (level - 1)) / 2; //当前层内第k个数
//搜索到是level层,开始层内搜组
for (int j = 1; j <= i; j++)
{
if (k <= num[j])
{ //找到了,在第j组内
k -= num[j - 1];
int remainder = (k % j == 0 ? j : k % j);
k = ceil(k * 1.0 / j * 1.0); //第j组内的第k个数
int theNumber = k + pow(10, j - 1) - 1;
//要的数字是theNumber中的第reminder个数
int temp = (int)log10(theNumber) + 1 - remainder;
while (temp--)
theNumber /= 10;
printf("%d\n", theNumber % 10);
break;
}
}
break;
}
}
}
return 0;
}
总结:
这三道题,其实前两道自己都会做,但是因为不细心,爆0了
第三道题可以打表得60分,但是经验太少了,没意识到。这个题细心一点应该也能做出来。
上一篇: SQLITE3 使用总结