当前位置: 首页 > news >正文

牛客周赛 Round 110 E,F题解

E、小苯的数字变换

题意:

小苯在研究一种特殊的数字变换。对于一个正整数 \(x\),定义一个数字的“根”为不断将其各位数字相加直到得到个位数。例如:

\[\text{根}(38) = 3 + 8 = 11 \rightarrow 1 + 1 = 2 \]

\[\text{根}(999) = 9 + 9 + 9 = 27 \rightarrow 2 + 7 = 9 \]

现在给定一个数字串 \(x\),请你求出:所有 \(x\) 的连续子区间代表的十进制数字(去掉前导 0 后)的 “根” 之和。

思路:

考虑\(dp\)
\(dp[i][j]\)表示以第\(i\)个数字结尾,“根”的和为\(j\)的子序列个数
具体细节见代码

代码

#include<bits/stdc++.h>
#define ll long long
#define ce cerr
#define ull unsigned long long
#define lll __int128
#define PII pair<int, int>
#define PLL pair<long ,long>using namespace std;const int inf = 0x3f3f3f3f;
const ll iinf = 1e18;//cin.ignore(std::numeric_limits< streamsize >::max(), '\n');
int t;void solve() {string s;cin >> s;int n = s.size ();s=  ' ' + s;vector<ll> a (n + 1);vector<vector<ll> > dp (n + 1, vector<ll> (10, 0));for (int i = 1; i <= n; ++i) {a[i] = (int) s[i] - '0';}// dp[i][j] : 第i个数字结尾,“根”之和为j的连续子区间的个数for (int i = 1; i <= n; ++i) {for (int j = 0; j <= 9; ++j) {int num = s[i] - '0';int temp = num + j;if (temp >= 10) temp -= 9;dp[i][temp] += dp[i - 1][j];}dp[i][a[i]] ++;}ll res = 0;for (int i = 1; i <= n; ++i) {for (int j = 0; j <= 9; ++j) {res += dp[i][j] * j;}}cout << res << "\n";
}
int main() {ios::sync_with_stdio (false);cin.tie(NULL);cout.tie(NULL);t = 1;cin >> t;while (t --) {solve();}return 0;
}

F、小苯的序列合并

题意:

给定长度为 \(n\) 的序列 \(a\),你可以对 \(a\) 做如下操作任意次:

  • 选择一个下标 \(i \ (1 \leq i < |a|)\),将 \(a_i\)\(a_{i+1}\) 合并起来,结果为 \(a_i \oplus a_{i+1}\)。(其中 \(\oplus\) 表示按位异或运算符,\(|a|\) 表示 \(a\) 当前的长度。)

所有操作结束后,小苯希望你最大化最终 \(a\) 中所有数字的按位与,即 AND(&)值,请你算一下这个最大值是多少吧。

思路:

关键点:最优解最多只会划分成两段(进行&的段数\(\leq 2\)
对于三个数字一定有:\(x_1 \oplus x_2 \oplus x_3 >= x_1 \& x_2 \& x_3\)(这里异或顺序不定)
所以,对于大于等于三段的分段方法,一定能够通过相邻三个数字之间不断异或,得到最终一个或者两个数字进行与运算

代码

#include<bits/stdc++.h>
#define ll long long
#define ce cerr
#define ull unsigned long long
#define lll __int128
#define PII pair<int, int>
#define PLL pair<long ,long>using namespace std;const int inf = 0x3f3f3f3f;
const ll iinf = 1e18;//cin.ignore(std::numeric_limits< streamsize >::max(), '\n');
int t;void solve() {int n;cin >> n;vector<ll> a (n + 1);vector<ll> b (n + 1);for (int i = 1; i <= n; ++i) {cin >> a[i];b[i] = b[i - 1] ^ a[i];}ll res = b[n];for (int i = 0; i <= n; ++i) {//ce << b[i] <<" " << (b[n] ^ b[i]) << "\n";res = max (res, b[i] & (b[n] ^ b[i]));}cout << res << "\n";
}
int main() {ios::sync_with_stdio (false);cin.tie(NULL);cout.tie(NULL);t = 1;cin >> t;while (t --) {solve();}return 0;
}
http://www.hskmm.com/?act=detail&tid=15182

相关文章:

  • 第5章:路由(Routing)与直连交换机(Direct Exchange)
  • 搜索百科(4):OpenSearch — 开源搜索的新选择
  • JAVA的计算方式
  • 安装 elasticsearch-9.1.4 - 集群 和 kibana-9.1.4
  • 反码 原码 补码
  • 线性结构常见应用之栈[基于郝斌课程]
  • 实测对比:权威榜单之公众号排版Top 5(含效果对比与适用建议)
  • go的泛型
  • 原码补码反码
  • lc1034-边界着色
  • 【汽车电子】汽车功能安全标准 ISO 26262
  • ISO 26262的不同安全等级:ASIL-D ASIL-C ASIL-B ASIL-A
  • C#学习1
  • 02020405 EF Core基础05-EF Core反向工程、EF Core和ADO.NET Core的联系、EF Core无法做到的事情
  • 02020406 EF Core基础06-EF Core生成的SQL
  • Gemini-2.5-Flash-Image-Preview 与 GPT-4o 图像生成能力技术差异解析​ - 教程
  • 新学期每日总结(第2天)
  • 在CodeBolcks下wxSmith的C++编程教程——使用菜单和组件
  • 单调队列
  • 软工第一次编程
  • 第二次软工作业
  • 9.23总结
  • 日志|力扣|不同路径|最小路径和|动态规划|Javase|IO|File|Javaweb
  • 如何建立 5 μm 精度的视觉检测?不仅仅是相机的事
  • 函数 cmd_info_change_cur_model_group
  • 线程--相关概念、两种创建线程的方式
  • 恢复某个数据文件不适当,导致DataGuard无法open数据库
  • Nginx 部署及配置
  • vite静态资源处理
  • 洛谷B4040 [GESP202409 四级] 黑白方块 题解