A.复读
思路:
- 主要用到了string中的find()函数,查找一个字符串在另一个字符串中首次出现的位置,查找成功则返回该字符串首次出现的位置,查找失败返回string::npos即为-1。
string::npos是静态成员常量,通常作为find系列函数未找到的返回值。
- 定义一个字符串变量ans,每输入一个字符串s,在ans中查找是否有s,如果有则证明s已经出现过。否则证明s未出现过,并将s拼接到ans中。
代码:
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
string s;
string ans = "";
while(1){
cin >> s;
if(s == "0") break;
if(ans.find(s) == string::npos) //将string::npos换为-1也可以,表明在ans未找到s
ans += s;
}
cout << ans << endl;
return 0;
}
B.时钟
思路:
因为一天当中的“好时刻”是固定个数的,所以可以先把一天当中所有的“好时刻”都找出来。
- 每天的时间范围是 0:00 - 24:00 即 0分钟 - 1440分钟 ,但是 24:00 算作 0:00 ,假设输入的分钟数 x 恰好为 1440 的倍数,即恰好是整数天数,那么 0:00 这个“好时刻”看到的次数会比其他“好时刻”看到的次数多一次。
- 举个栗子:当 x = 1339 时,即为 0:00 - 23:59 ,从 0:00 开始 的所有“好时刻”正好都被看到过一次。当 x = 1440 时,即为 0:00 - 24:00 ,24:00 也看作 0:00,所以 0:00 就会被多看到一次。
- 如果 x % 1440 == 0,则证明 x 是整数天数。
- 答案为:一天中所有“好时刻”个数 × 天数 + 1。
- 如果 x % 1440 != 0,则证明 x 不是整数天数,tt = x % 1440,tt 为观看未满一整天的那一天中看了多少分钟数。
- 定义 ans 变量用于存储遇见的“好时刻”个数,从分钟数 0 到 tt 依次遍历,判断遍历到的每一个分钟数是否是“好时刻”,如果是则 ans++。最后将 ans + (x分钟中的所有整数天数 × 一天中所有“好时刻”个数) ,即为答案。
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool b[2000];
void init(){ //找出一天当中的所有“好时刻”
int t1[4]{};
for(int i = 0;i <= 9;++i){
t1[1] = i;
for(int j = 0;j <= 59;++j){
t1[2] = j / 10;
t1[3] = j % 10;
if(t1[1] - t1[2] == t1[2] - t1[3] || t1[3] - t1[2] == t1[2] - t1[1]){
// cout << t1[1] << ':' << t1[2] << t1[3] << endl;
int time = i * 60 + j;
b[time] = true;
}
}
}
for(int i = 10;i <= 24;++i){
t1[0] = i / 10;
t1[1] = i % 10;
for(int j = 0;j <= 59;++j){
t1[2] = j / 10;
t1[3] = j % 10;
if((t1[0] - t1[1] == t1[1] - t1[2] && t1[1] - t1[2] == t1[2] - t1[3])
|| (t1[3] - t1[2] == t1[2] - t1[1] && t1[2] - t1[1] == t1[1] - t1[0])){
// cout << t1[0] << t1[1] << ':' << t1[2] << t1[3] << endl;
int time = i * 60 + j;
b[time] = true;
}
}
}
}
void solve(){
ll x;
cin >> x;
ll ans = 0, cnt = 0;
if(x % 1440 == 0){
cnt = x / 1440;
ans = cnt * 39 + 1;
}else{
cnt = x / 1440;
ll tt = x % 1440;
for(ll i = 0;i <= tt;++i) if(b[i]) ans++;
ans += cnt * 39;
}
cout << ans << endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
init();
solve();
return 0;
}
C.平等的交易
思路:
一开始以为是个动态规划题,后来看官方直播才知道是个贪心题,这题的题意太迷惑了。
- 大概题意:你有 w 元钱,只能用钱购买一件道具,但是你可以拿你手中的道具换取其他的道具,只是这些道具的价值之和,不能超过你打算交换出去的道具。
- 所以直接购买第一个价格小于等于 w 的道具,然后找该道具能换多少件道具即可。
- 先sort排序,从后往前遍历,找到第一个价格小于等于 w 的道具,用一个变量 price 记录该道具的价格。
- 然后再从前往后遍历数组,看价格为 price 的道具最多能换多少个道具。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+10;
ll a[maxn];
void solve(){
int n;
cin >> n;
for(int i = 1;i <= n;++i) cin >> a[i];
ll w;
cin >> w;
sort(a + 1, a + n + 1);
ll price;
for(int i = n;i > 0;--i){ //找到第一个价格小于等于w的道具
if(a[i] <= w){
price = a[i];
break;
}
}
ll sum = 0, ans = 0;
for(int i = 1;i <= n;++i){ //看price最多能换多少个道具
//如果已经置换完的所有道具的价格之和再加上当前的道具价格小于等于price,则证明该道具也可以被置换
if(sum + a[i] <= price) ans++, sum += a[i];
else break;
}
cout << ans << endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
solve();
return 0;
}
D.清洁工
思路:
- 本题需要考虑两种情况
- 第一种情况:第 i 块地板只被踩到过 1 次
- 第二种情况:第 i 块地板被踩到过 2 次及以上
第一种情况:
- 该地板块在第4秒时被踩上过一次,总灰尘数为:(1+2+3)+(1+2+3+4)
- 很显然,第4秒将总时长的8秒分成了两个部分,分别是 1秒 - 3秒 ,5秒 - 8秒
- 其中每一部分的灰尘数都要从 1 开始累加
- 所以我们不妨假设,在总时长为 t 的案例中,有一块地板在第 i 秒时被踩上
- 则总灰尘数
sum = (1 + 2 + … + (i-1)) + (1 + 2 + … + (t - (i+1)+1))
= (1 + 2 + … + (i-1)) + (1 + 2 + … + (t - i))- (1 + 2 + … + (i-1))的意思是:从第 1 秒开始落灰,一直落到第 i-1 秒
- (1 + 2 + … + (t-(i+1)+1))的意思是:第i秒被踩上了,不能落灰,从第 i+1 秒时开始重新落灰,总共落了 t-(i+1)+1 秒的灰
- 根据等差数列求和公式 (首项 + 末项) × 项数 ÷ 2,将 sum 变为
sum = (1 + (i - 1)) * (i - 1) / 2 + (1 + (t - i)) * (t - i) / 2
- 则总灰尘数
第二种情况:
- 该地板在第3秒和第7秒时被踩上,总灰尘数为:(1+2)+(1+2+3)+(1+2+3)
为方便计算,定义一个函数 cal() 来表示等差数列求和公式 (首项 + 末项) × 项数 ÷ 2
int cal(int num){
return (1 + num) * num / 2;
}
在还没有踩到地板第二次之前,计算总灰尘数的方法和第一种情况一样
- sum = cal(i + 1) + cal(t - i)
- i 表示第 i 秒踩到地板, t 表示总时长
当第二次踩到地板之后,要将上一次踩到地板后计算的踩到地板后的下一秒到总时长结束的那段灰尘数减去,然后再加上当前踩到地板时计算的左右两部分灰尘数
- 将这部分减去
- 即 sum = cal(i + 1) + cal(t - i) - cal(t - i) = cal(i + 1)
- 然后再加上第二次踩到地板时,以第一次踩到地板时的下一秒的时间为开始,直至总时长结束的所有灰尘数
- 假设第一次踩到地板的时间为 i1 ,第二次踩到地板的时间为 i2 ,总时长为 t
- 则 sum = cal(i + 1) + cal(i2 - 1 - (i1 + 1) + 1) + cal(t - (i2 + 1) + 1)
= cal(i + 1) + cal(i2 - 1 - i1) + cal(t - i2)- cal(i2 - 1 - (i1 + 1) + 1)的意思是:计算从 i1 + 1 秒时 到 i2 - 1 秒时,掉落的所有灰尘数
- cal(t - (i2 + 1) + 1)的意思是:计算从 i2 + 1 秒时 到 t 秒时,掉落的所有灰尘数
一块地板的被踩数大于2次以上时,思路也是一样的,只需要考虑上一次被踩的秒数以及当前被踩的秒数即可
- 因为题中所给的初始位置是坐标,所以要先把坐标转化为二维数组对应的位置
- 第 1 秒时必定踩在初始位置格子上,所以要从第二秒开始进行上下左右移动的操作
- 考虑到为了记录每个格子被踩到时的秒数,我这里用的方法是将二维数组的格子转化为一维数组
即数组 a[n][n] 转化为 a[n * n],共有n * n 块格子
代码:
#include <bits/stdc++.h>
using namespace std;
int a[60][60];
int vis[3000]; //记录每个格子被踩到时的秒数
int n, m, x, y;
int cal(int num){ //等差数列求和公式
return (1 + num) * num / 2;
}
void print(){ //打印所有格子
for(int i = 1;i <= n;++i){
for(int j = 1;j <= n;++j){
cout << a[i][j] << ' ';
}
cout << endl;
}
}
int cal_point(int i, int j){ //将二维数组中的格子转为一维
return (i - 1) * n + j;
}
void solve(){
cin >> n >> m >> x >> y;
string s;
cin >> s;
for(int i = 1;i <= n;++i)
for(int j = 1;j <= n;++j)
a[i][j] = cal(m); //先将所有格子进行赋值,因为大多数格子都是没有被踩到的
// print();
int sx = n - y + 1, sy = x; //将初始点的坐标值转换为二维数组中的下标
int ex = sx, ey = sy;
int cnt = 0; //用于遍历操作字符串中的每个移动操作
for(int i = 1;i <= m;++i){
if(i > 1){ //第一秒会踩在初始格子上,无需进行移动操作
if(s[cnt] == 'N') ex -= 1;
if(s[cnt] == 'S') ex += 1;
if(s[cnt] == 'W') ey -= 1;
if(s[cnt] == 'E') ey += 1;
cnt++;
}
int point = cal_point(ex, ey); //将当前格子处于二维数组中的两个下标转为一个一维数组的下标
if(!vis[point]){ //如果是第一种情况,格子被踩到一次
a[ex][ey] = cal(i - 1) + cal(m - i); //计算灰尘数
vis[point] = i; //更新当前格子最近被踩到的秒数
}else{ //第二种情况,格子被踩到过两次及以上
a[ex][ey] = a[ex][ey] - cal(m - vis[point]) + cal(i - 1 - vis[point]) + cal(m - i); //计算灰尘数
vis[point] = i; //更新当前格子最近被踩到的秒数
}
}
print(); //打印所有格子
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
solve();
return 0;
}
最后附上本题的官方题解代码
(说实话我没太看明白,不过大概思路应该和我的差不多)