StarryCoding 算法小白周赛2 题解与代码(含视频题解)

ops/2025/2/19 12:08:16/

比赛链接(含视频题解):https://www.starrycoding.com/contest/4

A题题解:

题目大意

给你一个由 n n n 个正整数组成的数组 a a a,询问这个数组是否是严格单调递增的。

思路

因为他会按照“拜访时间安排表”的顺序拜访每一位好友,而无法成功拜访某一好友时,必定是出现靠后拜访的时间早于靠前拜访的,或者两次拜访的时间相同,所以问题的本质就是判断数组是否严格单调递增,也就是 a 1 < a 2 < ⋯ < a n a_1 < a_2 < \dots < a_n a1<a2<<an

我们只需要遍历一下整个数组,判断相邻两个数是否都满足后者大于前者即可。

核心代码

void solve()
{int n;cin >> n;vector<int> a(n + 1, 0);for (int i = 1; i <= n; i++){cin >> a[i];}for (int i = 2; i <= n; i++){if (a[i] <= a[i - 1]){cout << "NO\n";return;}}cout << "YES\n";return;
}

B:1的数量

由于数的范围很小,假如这个数合法,我们直接从此数 + 1 +1 +1开始枚举,直到合法为止

最坏情况下时间复杂度为 O ( T n / 2 ) O(Tn/2) O(Tn/2)

#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f3f3f3f
const int N = 2e5 + 10;
const int M = 15;
const int mod = 998244353;
using namespace std;
typedef pair<int, int>p;
typedef long long ll;int a(int x)
{int res = 0;while (x){if (x & 1)res++;x >>= 1;}return res;
}signed main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int T = 1;cin >> T;while (T--){int n;cin >> n;if (a(n)<=2){n++;while (a(n) >= 3)n++;cout << n << endl;}else{cout << a(n) << endl;}}
}

C:1的数量

假如我们还是一个个枚举对于 2 63 2^{63} 263 + + + 2 62 2^{62} 262这样的数,需要枚举约 2 62 2^{62} 262次,我们是无法接受的

我们考虑在哪一位上加1是可行的

首先对于只有 0 0 0 1 1 1或者 1 1 1 1 1 1的情况,我们只需要无脑在第一位上加 1 1 1即可,因为这保证了 1 1 1的数量不会超过要求

对于 2 2 2 1 1 1的情况:

1 1 1 : 假如我在最后一位 1 1 1的后面任意位增加 1 1 1,一定会使 1 1 1的数量变成 3 3 3,不符合要求

2 2 2 : 假如我在最后一位 1 1 1上加 1 1 1,能保证加的数量是最少的,并且 1 1 1的数量一定不会增加,符合要求

所以对于 2 2 2位1的情况我们加上lowbit(x)就行了

时间复杂度接近 O ( T ) O(T) OT

#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f3f3f3f
const int N = 2e5 + 10;
const int M = 15;
const int mod = 998244353;
using namespace std;
typedef pair<int, int>p;
typedef long long ll;int lowbit(int x)
{return x & -x;
}int a(int x)
{int res = 0;while (x){if (x & 1)res++;x >>= 1;}return res;
}signed main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int T = 1;cin >> T;while (T--){int n;cin >> n;if (a(n) < 3){if (a(n) <= 1)cout << n + 1 << endl;else {n += lowbit(n);cout << n << endl;}}else{cout << a(n) << endl;}}
}

D题题解:

题目大意

给你一个由 n n n 个正整数组成的数组 a a a,询问这个数组能否通过以下两个操作各至多一次变为严格单调递增

  • 将任意数量的 a i a_i ai 变为 a i + 1 a_i + 1 ai+1
  • 删除其中一个数。

思路

由于我们已经知道了合法的时间安排满足数组 a a a 严格单调递增,所以我们只需要判断是否能够将 a a a 变为严格单调递增即可。

这个问题可以用简单的贪心法来解决。逐个处理元素。如果某个数比前一个数小,那么肯定不行,我们需要考虑删去这个元素或者它前面的那个数。如果相等,则考虑将其增加 1 1 1。如果大于,则最好不要更改,给后面的元素更多的空间。

最后我们只需要判断是否能通过最多一次删除操作使数组合法即可。

当然,还有一个小细节,当某个数比前一个数小时( a i > a i + 1 a_i > a_{i+1} ai>ai+1),应该删除这个数还是前一个数,因为我们想要的是让后面的数的合法值域更大,所以我们需要最小化留下的那个数,也就是说,如果靠后的数 a i + 1 a_{i+1} ai+1 可以留下来,我们应该尽可能让其留下,也就是说

  • a i > a i + 1 a_i > a_{i+1} ai>ai+1 a i − 1 < a i + 1 a_{i-1} < a_{i+1} ai1<ai+1,时,我们应该删除 a i a_{i} ai 不改变 a i + 1 a_{i+1} ai+1
  • a i > a i + 1 a_i > a_{i+1} ai>ai+1 a i − 1 = a i + 1 a_{i-1} = a_{i+1} ai1=ai+1,时,我们应该删除 a i a_{i} ai a i + 1 a_{i+1} ai+1 变为 a i + 1 + 1 a_{i+1} + 1 ai+1+1
  • a i > a i + 1 a_i > a_{i+1} ai>ai+1 a i − 1 > a i + 1 a_{i-1} > a_{i+1} ai1>ai+1,时,由于我们将 a i a_{i} ai 删去后 a i + 1 a_{i+1} ai+1 仍然不合法,所以我们应该删除 a i + 1 a_{i+1} ai+1

核心代码

void solve() {int n, k = 0;cin >> n;vector<int> a(n + 1, 0);for (int i = 1; i <= n; i++) {cin >> a[i];}int b = a[1];for (int i = 2; i <= n; i++){if (a[i] > b) {b = a[i];continue;}if (a[i] == b) {a[i]++;b = a[i];}else {k++;if (k == 2) {cout << "NO\n";return;}if (a[i] < a[i - 2]) {b = a[i - 1];}else if (a[i] == a[i - 2]) {a[i]++;b = a[i];}else {b = a[i];}}}cout << "YES\n";return;
}

E题题解:

观察到 k k k并不大,并且是一个比较经典的网格dp

网格dp一般设:dp[i][j]表示从(1,1)点走到(i,j)点的最大价值/收益等,因题目而异。

dp中,一般遇到模数问题,我们可以将模数作为状态保存在数组中。于是我们可以得到

dp[i][j][x]:表示从(1,1)走到(i,j)点切mod k = x的方案数

我们一开始就在(1,1)点,即dp[1][1][a[1][1] % k] = 1

状态转移如下

dp[i + 1][j][x * a[i + 1][j] % k] += dp[i][j] // 向下走
dp[i][j + 1][x * a[i][j + 1] % k] += dp[i][j] // 向右走

显然,最后的答案是:dp[n][n][0]

AC Code

const int MOD = 998244353, N = 510; int a[N][N];
long long dp[N][N][30];void solve(){int n, k;std::cin >> n >> k;for(int i = 1; i <= n; i ++ ){for(int j = 1; j <= n; j ++ ){std::cin >> a[i][j];}}for(int i = 1; i <= n; i ++ ){for(int j = 1; j <= n; j ++ ){if(i == 1 && j == 1){dp[1][1][a[1][1] % k] = 1;}for(int x = 0; x < 20; x ++ ){dp[i + 1][j][a[i + 1][j] * x % k] += dp[i][j][x];dp[i + 1][j][a[i + 1][j] * x % k] %= MOD;dp[i][j + 1][a[i][j + 1] * x % k] += dp[i][j][x];dp[i][j + 1][a[i][j + 1] * x % k] %= MOD;}}}std::cout << dp[n][n][0];
}

StarryCoding是面向计算机专业学生的综合学习与刷题平台,欢迎同学们的加入!
www.starrycoding.com

在这里插入图片描述


http://www.ppmy.cn/ops/32428.html

相关文章

android_systemServer进程启动流程

一&#xff0c;systemServer进程是被Zygote进程fork出来的&#xff0c;具体代码&#xff0c; 在startBootstrapServices、startCoreServices、startOtherServices、startApexServices中&#xff0c;对各类服务进行了启动&#xff0c;比如我们常见的ActivityManagerService、Pa…

区块链 | IPFS:IPNS(实操版)

&#x1f98a;原文&#xff1a;Publishing IPNS names Publishing IPNS names with Kubo Step1&#xff1a; 启动你的 IPFS 守护进程&#xff08;如果尚未运行&#xff09;&#xff1a; $ ipfs daemon说明&#xff1a;以 $ 开头的是命令&#xff0c;以 > 开头的是执行结果…

(一)深度神经网络的安全性和可信度的调查----验证、测试、对抗性攻击和防御,以及可解释性

在过去的几年中&#xff0c;深度神经网络&#xff08;DNNs&#xff09;在几个长期任务上实现人类水平的表现方面取得了重大进展。随着dnn在各种应用上的广泛应用&#xff0c;人们对其安全性和可信度的担忧被公开提出&#xff0c;特别是在广泛报道涉及自动驾驶汽车的致命事件之后…

3.SpringSecurity基本原理

SpringSecurity本质是一个过滤器链。十多个过滤器构成一个过滤器链。 这些过滤器在项目启动就会进行加载。每个过滤器执行放行操作才会执行下一个过滤器。 常见过滤器 FilterSecurityInterceptor 是一个方法级的权限过滤器&#xff0c;基本位于过滤器链的最底部。 Excepti…

软考网络工程师 第六章 第二部分 第三节 IP分类与特殊IP地址

IPV4地址分类 A类&#xff1a;1.0.0.0 - 127.255.255.255 B类&#xff1a;128.0.0.0 - 191.255.255.255 ABC类单播地址&#xff0c;应用最广 C类&#xff1a;192.0.0.0 - 223.255.255.255 D类&#xff1a;224.0.0.0 - 239.255.255.255 D类组播地址 E类&#x…

微信小程序 uniapp家庭食谱菜谱食材网上商城系统小程序ko137

随着生活节奏的不断加快&#xff0c;越来越多的人因为工作忙而没有时间自己出去订购喜欢的菜品。随着Internet的飞速发展&#xff0c;网络已经成为我们日常生活中必不可少的部分&#xff0c;越来越多的人也接受了电子商务这种快捷、方便的交易方式。网上订餐其独有的便捷性和直…

MongoDB的分片集群

MongoDB分片技术 介绍 ​ 分片&#xff08;sharding&#xff09;是MongoDB用来将大型集合分割到不同服务器上采用的方法。分片这种说法起源于关系型数据库。但是实际上非关系型数据库在分片方面相比于传统的关系型数据库更有优势。 ​ 与MySQL分库方案对比&#xff0c;MongoDB…

Python词频统计

在Python中进行词频统计是一项基础的文本分析任务&#xff0c;通常涉及以下步骤&#xff1a; 文本预处理&#xff1a;包括去除标点符号、转换为小写、去除停用词等。分词&#xff1a;将文本分割成单词或词汇。统计词频&#xff1a;对分词后的结果进行计数。 以下是一个简单的…