实验日志
题目描述
小爱正在完成一个物理实验，为期n天，其中第i天，小爱会记录
a
i
a_i
ai条实验数据在实验日志中。已知小爱的实验日志每一页最多纪录m条数据，每天做完实验后他都会将日志合上，第二天，他便从第一页开始依次翻页，直到找到第一个有空白位置的页码为止，开始新一天的数据记录。
请问在整个实验过程中，小爱每天为了找到第一个空白位置，需要翻多少页？
输入格式
输入共两行
第一行，两个正整数n,m。
第二行，n个正整数，表示每天的数据条数。
输出格式
输出共一行，n个正整数，分别表示每一天开始实验前，需要翻的页数。
数据范围
对于
30
%
30\%
30% 的数据，
1
≤
n
≤
100
1\leq n\leq 100
1≤n≤100
对于
60
%
60\%
60% 的数据，
1
≤
n
≤
1
0
4
1\leq n\leq 10^4
1≤n≤104
对于 100%100% 的数据，
1
≤
n
≤
1
0
5
1\leq n\leq 10^5
1≤n≤105
1
≤
m
,
a
i
≤
1
0
4
1\leq m,a_i\leq 10^4
1≤m,ai≤104
样例数据
输入:
4 10
7 8 5 12
输出:
0 0 1 2
说明:
第一天不用翻页
第二天开始前，由于只记了7条，仍是从第一页开始，不用翻页
第三天开始前，共记录了15条，则是从第二页开始，需翻1页
第四天开始前，共记录了20条，由于第二页已写满，则是从第三页开始，需翻2页
解题思路
不断加入当前页数除以每一页的页数同时输出
代码展示
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
int n,m,a[100100],cnt=0;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cout<<cnt/m<<" ";
cin>>a[i];
cnt+=a[i];
}
return 0;
}
凯撒加密
题目描述
恺撒密码是一种广为人知的加密技术。恺撒把需要加密的字母按字母表向后移动 3 位，替换成密文字母。例如，所有的 A 将被变成 D，B 变成 E 等等。若要加密最后三个字母，则需要折回到前三个字母，比如 x 变 a，y变 b，z 变 c。例如以下明TheQuickBrownFoxJumpsOverTheLazyDog将被加密成WkhTxlfnEurzqIraMxpsvRyhuWkhOdcbGrj给定一段只由拉丁字母组成的字符序列，请将它用凯撒加密成密文。
输入格式
一个字符序列：表示需要加密的明文
输出格式
一个字符序列：表示加密后的密文
数据范围
设输入的字符数量为 n，则保证 1 ≤ n ≤ 100 , 000 1\leq n\leq 100,000 1≤n≤100,000
样例数据
输入:
TheQuickBrownFoxJumpsOverTheLazyDog
输出:
WkhTxlfnEurzqIraMxpsvRyhuWkhOdcbGrj
解题思路
不断挪动每个字母的ASCII值即可，除了后三个要特判一下
注：网站数据可能有问题，会出现不是字母的字符，如果提交想得满分就得全部特判
代码展示
#include <bits/stdc++.h>
using namespace std;
char w;
int main(){
while(cin>>w){
if(w=='x') cout<<"a";
if(w=='y') cout<<"b";
if(w=='z') cout<<"c";
if(w=='X') cout<<"A";
if(w=='Y') cout<<"B";
if(w=='Z') cout<<"C";
if(w>='a'&&w<='w'||w>='A'&&w<='W') cout<<char(w+3);
}
return 0;
}
找零
题目描述
有一台自动售票机，每张票卖 5 元。售票机可以接受 5 元、10 元、2020元的纸币。接受大面额纸币时，若没有足够的零钱，售票机将拒绝售票并将纸币退还给客户，若有零钱足够，售票机必须出票并且找零。一开始，售票机里没有任何零钱。每位客户只买一张票也只会塞一张纸币。按照购票顺序，给定售票机收到的 n 张纸币的面额。请统计售货机最多能够卖出多少张票。
输入格式
第一行：单个整数 n
第二行：n 个整数表示 n 名客户分别塞入的纸币面额，保证只能是 5、10、20 中的一个。
输出格式
单个整数：表示售票机卖出的最多票数。
数据范围
1 ≤ n ≤ 50 , 000 1\leq n\leq 50,000 1≤n≤50,000
样例数据
输入:
8
10 5 5 5 10 10 20 20
输出:
6
说明:
由于没有零钱，无法把票卖给第一个人和最后一个人
解题思路
这题在赛场上不知道咋回事总是只拿到五十分，重构代码后就得了满分
主要思路就是将5元10元的纸币个数记下来，主要由以下几种可能
- 五块钱就把票卖出
- 十块就减去五块
- 二十就减去一个五块加一个十块或者三个五块，由于五块灵活性更高，所以偏向于减去一个五块加一个十块
代码展示
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=5e4+10;
int n,a[MAXN],ten=0,five=0,tic=0;
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]==5){
five++;
tic++;
}
if(a[i]==10){
if(five>=1){
ten++;
five--;
tic++;
}
}
if(a[i]==20){
if(ten>=1){
if(five>=1){
tic++;
ten--;
five--;
continue;
}
}
else{
if(five>=3){
tic++;
five-=3;
}
}
}
}
cout<<tic<<endl;
return 0;
}
新年灯会
题目描述
新春佳节之际，路上挂起了一排喜气洋洋的大红灯笼，从左至右编号分别为
1
,
2
,
.
.
.
,
n
1,2,...,n
1,2,...,n。但小爱发现，目前有p个灯笼不亮了，很是影响美观。
请你帮助小爱计算，最少修复多少个灯笼，便可使道路上有连续m个亮着的大红灯笼？
输入格式
输入共两行：
第一行，三个正整数分别表示n,m,p
第二行，p个正整数，表示已经不亮的灯笼编号
输出格式
输出共一行，一个正整数表示答案
数据范围
对于
30
%
30\%
30% 的数据，
1
≤
m
,
p
≤
n
≤
100
1 \leq m,p \leq n \leq 100
1≤m,p≤n≤100
对于
60
%
60\%
60% 的数据，
1
≤
m
,
p
≤
n
≤
1
0
4
1\leq m,p \leq n \leq 10^4
1≤m,p≤n≤104
对于
100
%
100\%
100% 的数据，
1
≤
m
,
p
≤
n
≤
1
0
5
1 \leq m,p \leq n \leq 10^5
1≤m,p≤n≤105
样例数据
输入:
8 5 3
5 1 8
输出:
1
说明:
只需把5号灯笼修好即可
解题思路
把坏掉的灯笼位置记录下来，然后枚举区间为m的串，然后通过前缀和找出每个长度为m中坏掉的路灯最少的即可
代码展示
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
int n,m,p,a,vh[MAXN],ans=MAXN;
int main(){
cin>>n>>m>>p;
for(int i=1;i<=p;i++){
cin>>a;
vh[a]++;
}
for(int i=1;i<=n;i++)
vh[i]+=vh[i-1];
// for(int i=0;i<=n;i++)
// cout<<vh[i]<<" ";
for(int i=1;i<=n-m+1;i++){
if(vh[i+m-1]-vh[i-1]<ans){
ans=vh[i+m-1]-vh[i-1];
}
}
cout<<ans<<endl;
return 0;
}
积木染色（二）
输入格式
三个整数分别表示 n,m,p
输出格式
输出满足条件的方案数模10^9+7的结果
数据范围
对于
30
%
30\%
30% 的数据，
1
≤
n
,
m
≤
10
1 \leq n,m \leq 10
1≤n,m≤10
对于
60
%
60\%
60%的数据，
1
≤
n
,
m
≤
500
1 \leq n,m \leq 500
1≤n,m≤500
对于
100
%
100\%
100% 的数据，
1
≤
n
,
m
≤
5000
1 \leq n,m\leq 5000
1≤n,m≤5000
输入:
4 2 2
输出:
6
说明:
设两种颜色分别为1,2
则有：1121,1211,1221,2122,2112,2212共计6种
解题思路
f ( n ， p ) = { f ( n − 1 , p ) + ( m − 1 ) × f （ n − 1 , p − 1 ) ( p > 0 ) f ( n − 1 , p ) ( p = 0 ) m ( p = 0 ) 0 ( p > 0 ) } n = 1 f(n，p)=\left\{\begin{matrix} f(n-1,p)+(m-1) \times f（n-1,p-1)&(p>0)\\ f(n-1,p)&(p=0)\\ \left. \begin{matrix} &m &(p=0)\\ &0 &(p>0)\\ \end{matrix} \right\}&n=1 \end{matrix}\right. f(n，p)=⎩ ⎨ ⎧f(n−1,p)+(m−1)×f（n−1,p−1)f(n−1,p)m0(p=0)(p>0)}(p>0)(p=0)n=1文章来源：https://www.toymoban.com/news/detail-603968.html
注：记得加记忆化，开long long,MOD文章来源地址https://www.toymoban.com/news/detail-603968.html
代码展示
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD=1e9+7;
int n,m,p,a[5010][5010];
int f(int n,int p){
if(a[n][p]!=-1)
return a[n][p]%MOD;
if(n==1){
if(p==0) return a[n][p]=m;
if(p>0) return a[n][p]=0;
}
if(p>0)
return a[n][p]=(f(n-1,p)+(m-1)*f(n-1,p-1))%MOD;
if(p==0)
return a[n][p]=f(n-1,p)%MOD;
}
signed main(){
memset(a,-1,sizeof(a));
cin>>n>>m>>p;
cout<<f(n,p)<<endl;
}
到了这里，关于上海市计算机学会竞赛平台（iai.sh.cn）2023一月月赛（丙组）解题报告的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
