程序员经验分享-hwhale

CSP-M2 ：神奇的序列

2023-05-16

文章目录

  • HRZ的序列
    • 题目
    • 输入输出
    • 解题
    • 代码
  • HRZ学英语-滑动窗口
    • 题目
    • 输入输出
    • 解题
    • 代码
  • 咕咕东的奇妙序列
    • 题目
    • 输入输出
    • 解题
    • 代码

HRZ的序列

题目

相较于咕咕东，瑞神是个起早贪黑的好孩子，今天早上瑞神起得很早，刷B站时看到了一个序列aa，他对这个序列产生了浓厚的兴趣。
他好奇是否存在一个数KK，使得一些数加上KK，一些数减去KK，一些数不变，使得整个序列中所有的数相等。
其中对于序列中的每个位置上的数字，至多只能执行一次加运算或减运算或是对该位置不进行任何操作。
由于瑞神只会刷B站，所以他把这个问题交给了你！

输入输出

输入格式
输入第一行是一个正整数tt表示数据组数。
接下来对于每组数据，输入的第一个正整数nn表示序列aa的长度，随后一行有nn个整数，表示序列aa。
输出格式
输出共包含tt行，每组数据输出一行。对于每组数据，如果存在这样的K，输出"YES"，否则输出“NO”。（输出不包含引号）
样例输入

2
5
1 2 3 4 5
5
1 2 3 4 5

样例输出

NO
NO

解题

  • 观察
    一般这种题根本用不着算法（至少我没有看出来），善于观察找规律就完事了，而且这道题也很简单一眼就能看出规律。

  • 规律
    首先，如果序列中只有一种数（全都一样），直接yes
    如果有两种，只要其中一种数加或减编程另一个数就能形成目标序列，yes
    如果有三种，只要最大数和最小数与中间数的差值一样就能形成目标序列，yes，否则，no
    如果大于三种，直接no

  • 设计
    记录数的种类，当为三种时，判断最大数+最小数=中间数，是否成立（不能用最大数+最小数/2=中间数判断）。

代码

#include<iostream>
#include<algorithm>
 
using namespace std;


 
const int N=1e5+10;
long long a[N];
int n;

bool fun(){
	long long s[3];
	s[0]=1e16,s[1]=1e16,s[2]=1e16; 
	bool b=false;
	for(int t=0;t<n;t++){
		b=false;
		for(int tt=0;tt<3;tt++){
			if(s[tt]==1e16||a[t]==s[tt]){
				s[tt]=a[t];
				b=true;
				break;
			}
		}
		if(!b){
			return false;
		}
	}		
	if(s[2]==1e16){
		return true;
	}
	sort(s,s+3);
	if(s[0]+s[2]==s[1]*2){
		return true;
	}
	return false;
}
int main(){
	int t;
	bool b;
	cin>>t;
	while(t--){
		cin>>n;
		for(int i=0;i<n;i++){
			cin>>a[i];
		}
		b=fun();
		if(b){
			cout<<"YES"<<endl;
		}
		else{
			cout<<"NO"<<endl;
		}
	}
}

HRZ学英语-滑动窗口

题目

瑞神今年大三了，他在寒假学会了英文的26个字母，所以他很兴奋！
于是他让他的朋友TT考考他，TT想到了一个考瑞神的好问题：给定一个字符串，从里面寻找 连续的26个大写字母 并输出！
但是转念一想，这样太便宜瑞神了，所以他加大了难度：现在给定一个字符串，字符串中包括26个大写字母和特殊字符’?’，特殊字符’？'可以代表任何一个大写字母。
现在TT问你是否存在一个 位置连续的且由26个大写字母组成的子串 ，在这个子串中每个字母出现且仅出现一次，如果存在，请输出从左侧算起的第一个出现的符合要求的子串，并且要求，如果有多组解同时符合位置最靠左，则输出字典序最小的那个解！如果不存在，输出-1！
这下HRZ蒙圈了，他刚学会26个字母，这对他来说太难了，所以他来求助你，请你帮他解决这个问题，报酬是可以帮你打守望先锋。
说明：字典序 先按照第一个字母，以 A、B、C……Z 的顺序排列；如果第一个字母一样，那么比较第二个、第三个乃至后面的字母。如果比到最后两个单词不一样长（比如，SIGH 和 SIGHT），那么把短者排在前。例如

AB??EFGHIJKLMNOPQRSTUVWXYZ
ABCDEFGHIJKLMNOPQRSTUVWXYZ
ABDCEFGHIJKLMNOPQRSTUVWXYZ

上面两种填法，都可以构成26个字母，但是我们要求字典序最小，只能取前者。
注意，题目要求的是 第一个出现的， 字典序最小的

输入输出

输入格式
输入只有一行，一个符合题目描述的字符串。
输出格式
输出只有一行，如果存在这样的子串，请输出，否则输出-1
样例输入1

ABC??FGHIJK???OPQR?TUVWXY?

样例输出1

ABCDEFGHIJKLMNOPQRSTUVWXYZ

样例输入2

AABCDEFGHIJKLMNOPQRSTUVW??M

样例输出2

-1

解题

  • 滑动窗口
    这道题很明显用滑动窗口（单调队列），维护一个局部的数组或序列。
  • 设计
    窗口大小26，且字母不同（任何一个‘ ？ ’都看作不相同）。
    用一个数组来记录当前滑动窗口中每个字母的个数，如果有一个大于1（不包括‘ ？’），则继续滑动。每次判断整个数组很麻烦，用一个cnt记录当前窗口中有几个字母个数为1+有几个‘ ？’。
  • 最小字典
    找到符合条件窗口之后，从第一个位置开始，如果遇到‘ ？’使用窗口中未使用的最小字母填充。

代码

#include<iostream>
#include<string>
#include<cstring>
using namespace std;

const int N=1e6;
int n,q[26],ans,ans_;
string s;
char ss[26];
bool fun() {
	n=s.length();
	memset(q,0,sizeof(q));
	ans=0;
	
	int t=0,tt;
	while(t<26) {
		if(s[t]=='?') {
			ans++;
			t++;
			continue;
		}
		tt=s[t]-'A';
		q[tt]++;
		if(q[tt]==1) {
			ans++;
		}
		t++;
		
	}
	int l=0,r=25;
	while(r<n) {
		if(l) {
			if(s[r]=='?') {
				ans++;
			} 
			else {
				tt=s[r]-'A';
				q[tt]++;
				if(q[tt]==1) {
					ans++;
				}
			}
			if(s[l-1]=='?'){
				ans--;
			}
			else{
				tt=s[l-1]-'A';
				q[tt]--;
				if(q[tt]==0){
					ans--;
				}
			}
		}
		if(ans==26) {
			tt=-1;
			int k=-1;
			while(l<=r){
				if(s[l]=='?'){
					while(tt<26){
						if(!q[++tt]){
							break;
						}
					}
					ss[++k]=char(tt+'A');
				}
				else{
					ss[++k]=s[l];
				} 
				l++;
			}
			return true;
		}
		l++;
		r++;
	}
	return false;
}

int main() {
	getline(cin,s);
	bool b=fun();
	if(b) {
		for(int i=0;i<26;i++){
			cout<<ss[i];
		}
		cout<<endl;
	} 
	else {
		cout<<-1<<endl;
	}
	return 0;
}

咕咕东的奇妙序列

题目

咕咕东 正在上可怕的复变函数，但对于稳拿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 项数字是多少！但是她睡醒之后发现老师讲的东西已经听不懂了，因此她把这个任务交给了你。

输入输出

输入格式
输入由多行组成。
第一行一个整数q表示有q组询问(1<=q<=500)(1<=q<=500)
接下来第i+1行表示第i个输入k_i，表示询问第k_i
项数字。(1<=k_i<=10^{18})(1<=k i​<=10 ^18 )
输出格式
输出包含q行
第i行输出对询问k_ik i的输出结果。
样例输入

5
1
3
20
38
56

样例输出

1
2
5
2
0

解题

  • 观察
    这道题贼恶心！！！
    首先要知道不要试图暴力破解！
    分段找规律
1
12
123
1234
...
123456789//第一块

12345678910
...
12345678910111213.......99//第二块
...

每一块按照数的最大位数区分。
第一行1个数，第二行2个数。。。等差数列。
如果去掉前面一位数的部分

10
1011
101112
...
101112131415...99

也是一个等差数列
同理第三块去掉一位数和两位数的数，剩下的也是等差数列

  • 准备
    按照上面的分块方法，对每一块进行相应的计算。
    一共分为9块（经过测试9块够用，如果不放心，可以使用容器设计成动态的。用到的时候再计算）。
    另外，我们称每一行叫做轮，例如：第13轮
12345678910111213

第 i 轮从1到 i 。

每一项都是序列数
对于我们要找的序列数x，称为最终序列数。
数列数所在的数，叫做最终数。
例如：上面的第13轮的例子中，假设我们要找第11项数，即最终序列数0，它所在的最终数是10，其中最终数的1也是序列数

  • 定位到块
    首先要定位到块，必须知道在每一块中的数的范围。
    定义两个数组，sum1是每一块最后一行序列的总数（有多少项数字，如第10轮有11个），sum2是到达某一块一共有多少序列数。
    例如：第一块最后一轮有9个序列数，到这一块一共有910/21个序列数。
    其中9代表n，10代表n+1，1是每一个数有几个序列数（等差数列和公式）
    sum2的计算
    从第二块开始，先计算每一轮共有的数（例如：123456789），可以用上一块的最后一轮总序列数（sum1）*本块的轮数。后面的10和1011等等通过等差数列和计算。
    第k项的序列数。
    找出第一个大于k的sum2，并且记录sum2的索引 i 。这表示到达第i块的所有序列数刚好大于k，k项序列数一定在第 i 块中。
    另外执行 k -= sum2
  • 定位到轮
    找出块之后，找出k所在的轮。
    计算 tmp= jsum1+j（j+1）*si，j 表示第i块的前 j 轮，sum1是上一块的sum1（即上一块最后一轮的序列数），加号后面的等差数列和（后面乘si是每个数有si个序列数）。tmp就是前 j 轮的总序列数。
    找到第一个满足tmp>=k（注意这个k已经减去前i-1块的序列数）的 j 。
    找到轮后，执行 k -= tmp

  • 定位到段
    段的意思是最终数所在的与它位数相同的一段序列。
    例如：123456789 10111213141516171819，,123456789是一段，10111213141516171819是一段。
    在之前定义了sum1是每一块的最后一轮，第一个sum1是123456789总序列数，第二个sum1是123456789 10111213141516171819...99总序列数。
    找出第一个大于等于k的sum1，执行k -= sum1，并且记录sum1的索引ti，即是这一段每个数的位数。
  • 定位到最终数
    现在我们知道了第k项所在的段，以及这一段数的位数。那么k/ti就是k项数在段中的偏移量（初始位置是这一段的以一个数，指的是10，100,100，这些第一个过渡到更高位数的数）
  • 定位到答案
    找到坐在那个数之后，用k%ti的余数判断k项数在最终数的位置。
    可以用stringstream流快速找到。
  • stringstream
    如下，kk是整数，str是字符串，通过流能完成快速类型转换。
	stringstream ss;
	string str;
	ss << kk;
	ss >> str;
	cout << str[k % ti]<<endl;

代码

#include<iostream>
#include<algorithm>
#include<cmath>
#include<sstream>
#include<string>
using namespace std;
typedef long long LL;
LL sum1[10], sum2[10];
void init() {
	LL len = 9;
	sum1[0] = 0; sum2[0] = 0;
	for (int i = 1; i < 10; i++) {
		sum1[i] = sum1[i-1] + len * i;
		sum2[i] = sum2[i - 1] + sum1[i - 1] * len + (len + 1) * len / 2 * i;
		len *= 10;
	}
}
void fun(LL k) {
	/**
	 *定位到块，九大块，最大位数一样的归为一块
	*/
	int si;
	for (si = 1; si < 10; si++) {
		if (k <= sum2[si]) {
			break;
		}
	}
	k -= sum2[si - 1];
	/**
	 *定位到轮，1到i是第i轮
	*/
	LL len = 9 * pow(10, si - 1);
	LL l = 1, r = len, mid;
	while (l <= r) {
		mid = (l + r) >> 1;
		if (k <= mid * sum1[si - 1] + mid * (mid + 1) / 2 * si) {
			r = mid - 1;
		}
		else {
			l = mid + 1;
		}
	}
	k -= (l - 1) * sum1[si - 1] + (l - 1) * l / 2 * si;
	/**
	 *定位到与最终数位数相等的区域，前面位数小于最终数的排除
	*/
	int ti = 1;
	while (k > sum1[ti]) {
		ti++;
	}
	k -= sum1[ti - 1];
	/**
	 *定位到最终数
	*/
	LL kk = pow(10, ti - 1) + (--k) / ti;
	/**
	 *定位到答案
	*/
	stringstream ss;
	string str;
	ss << kk;
	ss >> str;
	cout << str[k % ti]<<endl;
}
int main() {
	LL a, q;
	cin >> q;
	init();
	while (q--) {
		cin >> a;
		fun(a);
	}
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

CSP-M2 ：神奇的序列 的相关文章

  • 逻辑思维能力选择题30道

    逻辑思维能力选择题30道 这些题目都是作者选取于网络 xff0c 靠自己动脑做出来的是最棒的 1 有一个有钱人想让你和他玩一个游戏 xff0c 你在纸上写下一句话 xff0c 并作出选择 选择1 xff1a 如果你写的是实话 xff0c 那

  • 单位换算表大全

    长度 1千米 km 61 0 621英里 mile 1米 m 61 3 281英尺 ft 61 1 094码 yd 1丝米 dmm 61 1忽米 cmm 61 1丝 61 0 01毫米 61 0 001厘米 1厘米 cm 61 0 394英

  • Debian配置CA_配置Apache2使用ssl_配置http连接自动跳转到https

    需要使用到两台Debian服务器 xff0c 一台作为ca端 xff0c 一台作为Apache端 ca端IP xff1a 192 168 200 129 Apache端IP xff1a 192 168 200 131 以下是CA端配置 xf

  • 重量（计量单位）英文缩写和转换表

    重量的缩写是W 一 质量单位换算 xff1a 1长吨 xff08 long ton xff09 61 1 016吨 xff08 t xff09 1千克 xff08 kg xff09 61 2 205磅 xff08 lb xff09 1磅 x

  • 逻辑学三大定律是什么?

    逻辑思维三大定律 同一律 xff0c 矛盾律 xff0c 排中律 同一律 xff1a A 是 A 前后思维中 xff0c 概念要同一 白马非马论违反同一律 商家的买一赠一 xff0c 前后两个一不是同一个概念 违反同一律 矛盾律 xff1a

  • 逻辑学三大定律

    1 同一律就是前后提及概念 论题要是同一个 xff0c 不是同一个就是不合逻辑的 看这句话 xff0c 人有几百万年的历史 xff0c 你没有几百万年的历史 xff0c 所以你不是人 xff0c 典型的三段论 xff0c 大前提 xff0c

  • LeetCode:移除元素

    给你一个数组 nums 和一个值 val xff0c 你需要 原地 移除所有数值等于 val 的元素 xff0c 并返回移除后数组的新长度 不要使用额外的数组空间 xff0c 你必须仅使用 O 1 额外空间并 原地 修改输入数组 元素的顺序

  • C#高级特性（反射）

    今天来讲解反射的应用 xff1a 一 反射是什么 xff1f 简诉一下 xff0c 反射就是 Net Framework 的一个帮助类库 xff0c 可以获取并使用metadata xff08 元数据清单 xff09 xff1b 说的通俗易

  • Linux 操作命令 c

    1 打开终端的快捷键 ctr 43 alt 43 t 2 终端字体放大 ctr 43 shift 43 43 3 终端字体缩小 ctr 43 4 ls 查看当前目录的下文件信息 5 pwd 当前当前目录的路径 6 touch 创建一个文件

  • java实现平面4点最小距离

    已知平面上若干个点的坐标 需要求出在所有的组合中 xff0c 4个点间平均距离的最小值 xff08 四舍五入 xff0c 保留2位小数 xff09 比如有4个点 xff1a a b c d 则平均距离是指 xff1a ab ac ad bc

  • 【HTTPS】TLS/SSL握手失败的场景分析

    0 背景知识 TLS SSL握手的过程参考 SSL握手过程图解 1 常见报错 1 1 SSLHandshakeException handshake failure 1 1 1 TLS SSL协议版本不匹配 自从TLS 1 2版本在2008

  • 使用RKE部署Rancher v2.5.8 HA高可用集群

    文章目录 一 了解 Rancher1 关于Helm2 关于RKE3 关于K3S4 Rancher 名词解释4 1 仪表盘4 2 项目4 3 多集群应用4 4 应用商店4 5 Rancher Server URL4 6 RKE 模板4 7 G

  • SQL练习题

    网上有一篇关于SQL的经典文章 xff0c 超经典SQL练习题 xff0c 做完这些你的SQL就过关了 xff0c 引用和分析它的人很多 xff0c 于是今天复习SQL的时候找来练了练手 原作者用的是SQL Server 2008 xff0

  • VS2015编译报MS8020错误

    新装的VS2015 xff0c 调试旧的代码报错 xff0c 信息如下 xff1a MSB8020 The build tools for v120 Platform Toolset 61 39 v120 39 cannot be foun

  • 1001. Poker (思维 / 模拟)(2020年百度之星*程序设计大赛-初赛二)

    传送门 思路 xff1a 嗐 xff0c 又是这种模拟题 xff0c 每次都不长记性看数据范围 xff0c 非得傻傻的去循环模拟T一次才知道思考 呜呜呜太菜了 既然每次至少拿出m xff0c 且求的是最多次数 xff0c 那我们每次就拿m出

  • ffmpeg/libavformat/tcp.c中getaddrinfo在IOS下的问题

    IOS的播放器用了ffmpeg 3 1 发现不支持ipv6 跟踪到ffmpeg libavformat tcp c下的getaddrinfo函数 xff0c 发现执行完之后 xff0c 如果是由ipv4合成ipv6的时候 会把端口设成0 所

  • iOS UIImagePickerController 自定义导航条背景、标题和按钮的颜色

    UIImagePickerController span class token operator span imagePickerController span class token operator 61 span span clas

  • centos7.9安装mysql8.0-参考官网简易安装文档，简洁且必成功

    目录 文章目录 目录一 前面的话二 环境三 选择什么下载安装方式四 安装过程1 到官网选择合适的yum repositoty版本2 把这个rpm包下载下来3 使用yum工具添加这个mysql的yum repo4 安装mysql5 启动服务器

  • Mysql8.0设置允许远程连接

    Mysql8 0设置允许远程连接 1 登录mysql 2 选择mysql数据库 3 修改user表使其root用户可以通过远程连接 4 刷新权限 1 登录mysql mysql uroot p 1 2 选择mysql数据库 user mys

  • C/C++经典例题：百钱百鸡

    c 43 43 程序 百钱买百鸡 的解法 题型介绍 xff1a 百鸡问题是一个数学问题 xff0c 出自中国古代约5 6世纪成书的 张邱建算经 xff0c 是原书卷下第38题 xff0c 也是全书的最后一题 xff0c 该问题导致三元不定方

随机推荐

热门标签