上海市计算机学会月赛 2022年6月月赛丙组
上海市计算机学会月赛 2022年6月月赛丙组
-
- 邮票问题
- 密码解锁
- 模糊匹配
- 连续的零
- 平整序列
邮票问题
内存限制不得超过256兆字节（Mb），程序运行时所允许的最大执行时间不得超过1秒。
本系统支持四种不同面额的邮资支付方案：具体包括20元、10元、5元以及1元四种邮票。
当需要在包裹上粘贴总金额精确为n元的邮资时，请计算所需使用的最少邮票数量？
输入格式
单个整数表示 n。
输出格式
单个整数表示邮票的最少张数。
数据范围
对于 50% 的数据，1≤n≤1,000；
对于 100% 的数据，1≤n≤1,000,000。
样例数据
输入:
16
输出:
3
说明:
16=10+5+1
分析：
大的越多，用的越少
#include <iostream>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
long long n, ans = 0;
cin >> n;
while (n >= 20)
{
n -= 20;
++ans;
}
while (n >= 10)
{
n -= 10;
++ans;
}
while (n >= 5)
{
n -= 5;
++ans;
}
while (n)
{
n -= 1;
++ans;
}
cout << ans;
return 0;
}密码解锁
内存占用限制：256兆字节
程序运行截止时间：1秒
题目描述：
当前的安全机制通过设置短暂的时间间隔来防止未经授权的连续尝试攻击。
当用户输入错误密码时会引入短暂的时间间隔
目前有一种密码系统，在正确的密码被输入时，则该系统将被正常启动，并无需继续输入额外的密码。
系统给予前三次尝试密码的机会均为免时延。即前三次尝试密码前均可无需任何延迟。当第三次输错密码后，则需等到第四次试输前才会被强制要求等1分钟的时间间隔。当第四次输错后，则需等到第五次试输前才会被要求等两分钟的间隔期。依此类推下去的话，则每次试输之前的静默期将会是上一阶段的双倍时长
该系统将支持最多十次密码登录次数，并在第十次失败时将被锁定以确保账户安全
假设系统已经给出正确的正确登录密码，请计算用户在每次尝试时的总等待时间
当程序运行时，请先指定正确的密码字符串作为第一行输入。随后读取的每一行将被视为用户的解锁尝试。（此时如果正确或已尝试十次则程序会终止运行）请确保在正确情况下结束或在第十次失败后停止接收后续输入。
当用户连续输入错误达十次时，系统将返回一个锁定提示信息。
数据范围内的数据保证指出：正确的密码以及所有尝试过的密码仅由大写字母构成；同时包含小写字母以及数字字符
模拟测试结果如下
模拟测试结果分析
#include <string>
#include <iostream>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int cnt = 1, Time = 0, t[11] = { 0, 0, 0, 1 };
for (int i = 4; i <= 10; ++i)
t[i] = t[i - 1] * 2;
string paswad, input;
cin >> paswad;
while (cin >> input)
{
if (input == paswad)
break;
Time += t[cnt];
if (cnt == 10)
{
cout << "Locked" << endl;
return 0;
}
++cnt;
}
cout << Time << endl;
return 0;
}模糊匹配
内存限制为256 Mb 时间限制为1000 ms
输入由多个部分构成。
第一部分为指定字符串S。
第二部分则是一个正整数n。
第三部分将详细列出T_1,T_2,...,T_n等数值信息。
输出结果
输出共一行，并给出一个正整数作为数值类型变量result。result将记录文本库内与字符串S进行模糊匹配的共有多少个字符串。
数据范围
对于 30%的数据，1≤n≤10
对于 60%的数据，1 \leq n \leq 10^3
对于 100%的数据，1 \leq n \leq 10^4，且每个字符串的长度均不超过10^3
数据保证，输入的字符串，只包含大写字母与小写字母。
样例数据
输入:
I?I
4
iai
IAI
IaI
abc
输出:
2
说明:
文本库内，IAI与IaI 均可与 I?I 模糊匹配。
分析：
由于?可以代替任何字符，只需要判断剩下的是否一致就是模糊匹配了。
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
int n, ans = 0;
string s, t;
cin >> s;
int len = s.length();
cin >> n;
for (int i = 0; i < n; ++i)
{
bool flag = true;
cin >> t;
int len2 = t.length();
if (len2 == len)
for (int j = 0; j < len; ++j)
{
if (s[j] != '?')
if (t[j] != s[j])
flag = false;
}
else
flag = false;
if (flag)
++ans;
}
cout << ans;
return 0;
}连续的零
内存空间被限定为256MB；程序运行时长限定为1秒；题目要求：给定一个由0和1组成的序列b_1b_2\dots b_n（其中n表示序列长度），请计算并确定最少需要将多少个1转换为0才能使序列中出现k个连续的0。
给定两个整数n和k，并由n个字符组成的字符串b_1b_2\dots b_n仅包含数字0和1
输出格式
单个整数：最少要改多少个 1，才会出现 k 个连续的 0。
数据范围
对于 30% 的数据，1\leq k\leq n\leq 20；
对于 60% 的数据，1\leq k\leq n\leq 2000；
对于 100% 的数据，1\leq k\leq n\leq 500,000
样例数据
输入:
6 3
101010
输出:
1
说明:
改最后一个1
输入:
3 2
011
输出:
1
说明:
改左边那个1。
分析：
前缀和记录b_i之前有多少个1，这样在一段区间内1的个数就很明确了，找那个最小的区间就可以了。
#include <iostream>
#include <stdio.h>
using namespace std;
int main()
{
long long i, j, n, k, ans = 500001, sum[500001] = {0}, cnt;
char a[500001];
cin >> n >> k;
scanf("%s", a + 1);
for (i = 1; i <= n; ++i)
sum[i] = sum[i - 1] + (a[i] - '0');
for (i = 0; i <= n - k; ++i)
ans = min(ans, sum[i + k] - sum[i]);
printf("%lld", ans);
return 0;
}平整序列
内存与时间限制分别为256 MB和1秒。题目描述：假设有一个整数序列 a_1, a_2, \dots, a_n ，小爱必须执行一系列调整操作以使所有数值归零。在每次操作中她可以选择一段连续区间（也可以仅选择一个元素）并将其全部数值增加或减少一单位。
请问小爱最少需要几步操作才能将所有数字改成 0？
输入格式
第一行：单个整数表示 n；
第二行：n 个整数表示 a_1,\dots,a_n。
输出格式
单个整数：表示最少调整次数
数据分布方面：
在34%的数据样本中（即占总数据量的34%），变量n的数量在区间[1,2]内取值；
在67%的数据样本中（即占总数据量的67%），变量n的数量在区间[1,2×1e3]范围内；
而在全部样本中（即占总数据量的比例为全部），变量n的数量则扩展至[1,5×1e5]；
同时对每个样本中的变量a_i而言：
其取值范围主要集中在[-2e1,2e1]区间内；
而对于67%的大样本集，则呈现 wider分布特征；
而全部样本中的变量a_i则被限制在[-(−)¹⁰⁹,(−)¹⁰⁹]范围内。
样例数据
输入:
4
1 1 1 2
输出:
2
说明:
第一步将所有数字减一，第二步将最后一个数字减一
输入:
3
-1 1 -1
输出:
3
分析：
利用差分思想，如果比上一个要填的多就顺带填掉。
#include <cstdio>
#include <iostream>
using namespace std;
long long n, i, a[500005], ans = 0, t;
int main()
{
ios::sync_with_stdio(false);
cin >> n;
a[0] = a[n + 1] = 0;
for (i = 1; i <= n; ++i)
cin >> a[i];
for (i = 1; i <= n + 1; ++i)
if (a[i] > a[i - 1])
ans += a[i] - a[i - 1];
cout << ans;
return 0;
}